Generate token for Credit card numbers

Can anyone please help me in generating tokens for Card numbers?

I have done a lot of research on this topic, gone through several articles on tokenization and PCI DSS compliance guide.

All this study has told me that: I should NOT try to store credit card data as there are several PCI DSS compliance rules and it is quite easy to break them

But I am thinking from the point of view of companies like master card, visa etc. They are generating tokens and providing them to E-commerce developers.

My research says that there are two formats in which credit card companies provide tokens to merchants (E-commerce):

1) 36-40 character Alphanumeric token: I think we can implement it using UUID class of Java

2) 16 digit number: This point is my question. How do they generate these 16 digit tokens which are always unique for each credit card (I know that it is called Format Preserving Encryption. I am not interested in the Encryption part in this question)? How can I generate such number using Java ? How do I make sure that I am not generating the same token again(I should not have to go to Db to check whether the generated token is already there as this will make the process slower)?

Do I just start with 10^15 and keep on increment it by 1 for each new credit card?

Please suggest a better solution.