[QUOTE=ewmayer;247536]I have a credit card with a 16-digit number, having the following properties:

1. The full 16-digit CC number is prime;
2. The rightmost 8-digit portion of the CC number is prime;
3. The rightmost 4-digit portion of the CC number is prime;
4. The CC number satisfies the standard checksum.

How many possible 16-digit numbers fit the criteria?

(Note: My actual credit card number fits this description, so there is a possible financial-fraud incentive in play here.)[/QUOTE]Just for fun:

We have a credit card with a 16-digit number, having the following properties:

Let the card number be visualized with "×" being a digit and with "_" being a truncated digit. (?)

[CODE]×××××××××××××××× is not prime
×××××××××××××××_ is not prime
××××××××××××××__ is not prime
×××××××××××××___ is not prime
××××××××××××____ is not prime
×××××××××××_____ is not prime
××××××××××______ is not prime
×××××××××_______ is not prime
××××××××________ is not prime
×××××××_________ is not prime
××××××__________ is not prime
×××××___________ is not prime
××××____________ is not prime
×××_____________ is not prime
××______________ is not prime
×_______________ is not prime[/CODE][CODE]×××××××××××××××× is not prime
_××××××××××××××× is not prime
__×××××××××××××× is not prime
___××××××××××××× is not prime
____×××××××××××× is not prime
_____××××××××××× is not prime
______×××××××××× is not prime
_______××××××××× is not prime
________×××××××× is not prime
_________××××××× is not prime
__________×××××× is not prime
___________××××× is not prime
____________×××× is not prime
_____________××× is not prime
______________×× is not prime
_______________× is not prime[/CODE](Is there an easier way to say all of that without listing each example?)

The card number satisfies the standard checksum. ([URL]http://rosettacode.org/wiki/Luhn_test_of_credit_card_numbers[/URL])

How many possible 16-digit numbers fit the criteria?

(Note: Our actual credit card number fits this description, so there is a possible financial-fraud incentive in play here.)

If "not prime" includes 0 and 1 (which are neither prime nor composite), my estimate is that there are 7.9*10^13, or 79,000,000,000,000, such card numbers. If it does not include those, my estimate is 4.7*10^13.

I figured this by calculating the numbers out to length 8 (that's where the quickly-increasing memory and time requirements for my naive approach strongly suggest I should stop) and [STRIKE]guessing[/STRIKE] extrapolating from there.

[QUOTE=Mini-Geek;387750]If "not prime" includes 0 and 1 (which are neither prime nor composite), my estimate is that there are 7.9*10^13, or 79,000,000,000,000, such card numbers.[/QUOTE]There are no situations where a 0 or a 1 are alone in any of those listings.

There are three places in the following listing (from above) where there is a leading zero, which we mentally truncated when factoring the number.

[CODE]×××××××××××××××× is not prime
_××××××××××××××× is not prime
__×××××××××××××× is not prime
___××××××××××××× is not prime
____×××××××××××× is not prime
_____××××××××××× is not prime
______×××××××××× is not prime
_______××××××××× is not prime
________×××××××× is not prime
_________××××××× is not prime
__________×××××× is not prime
___________××××× is not prime
____________×××× is not prime
_____________××× is not prime
______________×× is not prime
_______________× is not prime[/CODE]To make it more interesting, here is another pattern:

Let "E" represent an even digit and "O" represent an odd digit:

[CODE]EEEEEOOOEOEEOOOE[/CODE]

[QUOTE=Xyzzy;387751]There are no situations where a 0 or a 1 are alone in any of those listings.

There are three places in the following listing (from above) where there is a leading zero, which we mentally truncated when factoring the number.

[CODE]×××××××××××××××× is not prime
_××××××××××××××× is not prime
__×××××××××××××× is not prime
___××××××××××××× is not prime
____×××××××××××× is not prime
_____××××××××××× is not prime
______×××××××××× is not prime
_______××××××××× is not prime
________×××××××× is not prime
_________××××××× is not prime
__________×××××× is not prime
___________××××× is not prime
____________×××× is not prime
_____________××× is not prime
______________×× is not prime
_______________× is not prime[/CODE]To make it more interesting, here is another pattern:

Let "E" represent an even digit and "O" represent an odd digit:

[CODE]EEEEEOOOEOEEOOOE[/CODE][/QUOTE]

With the new hints, I've calculated it out to size 12 and estimate that 3,360,000 numbers that still match the pattern.

10^16 is a big number. :smile:

Well, the information about it not being prime when the first digits are truncated isn't particularly useful now since it's given that the final number is even. The only thing that information really tells us is that the last digit isn't 2.

Since truncating the last digits sometimes allows the number to end in an odd number, that is where I searched. However, for the first 10 digits I found 5,697,267 candidates (which remains as 5,697,267 candidates up to 12 digits, since the next two numbers are even, and therefore not prime). So it seems we differ on this result Mini-Geek. I did get this with 2 separate pieces of code (an original and a much more optimised version).

I then ran code to find candidates for the first 13 digits, and found 662,414,546 of them (a disappointingly high number, but I suppose primes are much rarer at that size).

Assuming that with the last 3 digits, 95% of candidates would remain after filtering the primes out, I estimate that there are around 63 billion of them.

Then with the Luhn check, 90% of the candidates would drop out leaving 6.3 billion total.

If I'm correct in my working, then guessing your card number from such a list of filtered candidates, would be roughly as likely as picking you out of a line-up of the entire human race despite never having seen you.

Edit: To search for candidates up to 10 digits (effectively 12 digits) takes only 8 seconds. Searching for 13 digits takes 20 minutes. By extension searching for all candidates would take over 8 hours, plus some extra time for the luhn checks.

I'm running a full 16 digit search now. I've made a few optimisations which should mean the run time will be under 4 hours, but we shall see.

Once you have all the candidates for the first 14 digits, there are only 2 possibilities for the last 2 digits due to the Luhn check, so a full up 16 digit run should only take about twice as long as a 14 digit run.

I would expect 14 digits to take ~1h 40m, meaning 16 digits should be in the region of 3h 20m. But then again the primality checks are on larger numbers so it probably won't scale quite so nicely.

Anyway, hopefully there are no bugs in my code (squashed several already), but it'd be nice to have an independant check if someone else runs their code on the full number.

Another hint:

The sum of all the digits is 43.

[QUOTE=lavalamp;387807]Well, the information about it not being prime when the first digits are truncated isn't particularly useful now since it's given that the final number is even. The only thing that information really tells us is that the last digit isn't 2.

Since truncating the last digits sometimes allows the number to end in an odd number, that is where I searched. However, for the first 10 digits I found 5,697,267 candidates (which remains as 5,697,267 candidates up to 12 digits, since the next two numbers are even, and therefore not prime). So it seems we differ on this result Mini-Geek. I did get this with 2 separate pieces of code (an original and a much more optimised version).

I then ran code to find candidates for the first 13 digits, and found 662,414,546 of them (a disappointingly high number, but I suppose primes are much rarer at that size).

Assuming that with the last 3 digits, 95% of candidates would remain after filtering the primes out, I estimate that there are around 63 billion of them.

Then with the Luhn check, 90% of the candidates would drop out leaving 6.3 billion total.[/QUOTE]

I improved my code so that I could extend the calculation to 14 digits in a reasonable time (writing the intermediate results to a file instead of trying to store it in memory). The numbers are far higher than I expected (didn't fit the pattern that was there previously), so I'm no longer sure of how to extrapolate to 16 digits: my guess is from 200 million to 2 billion. That's an order of magnitude, and yours is another half above the upper part there. It seems unlikely, but I wouldn't be too surprised if my figure did come out to something like your 6.3 billion.

I'm also pretty sure that your quoted intermediate numbers are not as filtered as mine, so it's not strange that they're higher.

And with the new hint, all of the above is pretty much pointless. :cat:
[QUOTE=Xyzzy;387836]Another hint:

The sum of all the digits is 43.[/QUOTE]
Now I'm well on my way to calculating it for the full 16 digits (estimating a half hour run time, with trivial memory requirements and under 1GB of intermediate files at any one time). My current guess is that there are only 1 million numbers. Put another way, this means that your rules have eliminated all but 1 in every 10 billion potential card numbers (10^10).
Edit: My final result is 695,029 numbers, which took 15 minutes to calculate. [URL="https://drive.google.com/file/d/0B72y7-pdB73bUElmYVRVSFhqdVE/view?usp=sharing"]Download it here (797 KB compressed).[/URL] If you create a list yourself, we should compare it and see if we got it right. Xyzzy: let us know if your number is really on that list! And the index. :whistle:

[QUOTE=Mini-Geek;387844]... 695,029 numbers ...[/QUOTE]I think it can be narrowed down further by taking into account the posters location. You could eliminate prefix numbers that are clearly issued from banks well outside the potential candidates of the posters location. e.g It is unlikely that the poster has a card issued from an Algerian bank so you can eliminate all the Algerian bank prefixes.

I would post my output but I don't have access to my desktop from university currently (my own fault, kicking myself there).

I don't know how you're filtering the results Mini-geek, but I had just over 17 million results when taking into account that the sum of the digits is 43. Without that knowledge, I had 5.9 billion, not too far off my earlier estimate (what's 400 million between friends?).

For my code I only used the information given about odd/even, lack of primality and the Luhn check. Perhaps there are other rules of credit/debit card rules that you're using that I'm not aware of? I notice that your first candidate starts with a 4, whereas mine starts 0000.

Also, you have a very large amount of intermediate files. Like yours, my code has a trivial memory footprint, but unlike yours, no intermediate files. I assume you output something like all possible first 8/12 digits and then run through that output in a separate loop for the last 8/4 digits? I just kept everything smashed together with 8 nested loops.

[QUOTE=lavalamp;387871]For my code I only used the information given about odd/even, lack of primality and the Luhn check. Perhaps there are other rules of credit/debit card rules that you're using that I'm not aware of? I notice that your first candidate starts with a 4, whereas mine starts 0000.[/QUOTE]
I'm not using any rules from outside this thread (unless you count the Luhn check).
Here are some rules (as in, filtering rules by Xyzzy, not general rules about what a credit card number can be) that contradict anything starting with "0000":
[QUOTE=Xyzzy;387751]There are no situations where a 0 or a 1 are alone in any of those listings.

There are three places in the following listing (from above) where there is a leading zero, which we mentally truncated when factoring the number.[/QUOTE]
Yours has a "0" alone when you ask the question "is x_______________ prime?", and would have at least four instances where there is a leading zero.

My code is now at [url]https://github.com/Mini-Geek/SubComposite[/url].
A note if you want to execute it, not just read the code: It goes through different end size targets; these are independent runs, so if you want to see how it works with some simple examples, keep the initial value of "size" low; if you just want it to run for 16 digits, set the initial size to 16 (and expect that it might take 15 minutes or so, maybe longer if you're on an HDD).

[QUOTE=lavalamp;387871]Also, you have a very large amount of intermediate files. Like yours, my code has a trivial memory footprint, but unlike yours, no intermediate files. I assume you output something like all possible first 8/12 digits and then run through that output in a separate loop for the last 8/4 digits? I just kept everything smashed together with 8 nested loops.[/QUOTE]

You've got the general idea, but I do it by every digit, not every 4/8. Maybe doing it your way would be faster, but it's reasonably fast now. *shrug*