If it is your intention for the inner loop not to run, why not put the upper limit for the primes at 10^7? I am almost certain that this code does not do what you think it does.

Also there is no point in running the luhn check on 8 digit numbers unless you expect the first 8 digits to be 0.

To make it as obvious as I can that only nonsense is happening, here are the range of values for your loops and all that stuff in the isprime and luhn functions:

x = 2 - 7, y = 1 - 9999999, 10^crap*y+x = 10000002 - 99999990000007
x = 11 - 97, y = 1 - 999999, 10^crap*y+x = 1000011 - 999999000097
x = 101 - 997, y = 1 - 99999, 10^crap*y+x = 100101 - 9999900997
x = 1009 - 9973, y = 1 - 9999, 10^crap*y+x = 11009 - 99999973
x = 10007 - 99991, y = 1 - 999, 10^crap*y+x = 11007 - 1098991
x = 100003 - 999983, y = 1 - 99, 10^crap*y+x = 100103 - 1009883
x = 1000003 - 9999991, y = 1 - 9, 10^crap*y+x = 1000013 - 10000081
x = 10000019 - 99999989, [COLOR="Red"]y = 1 - 0[/COLOR], 10^crap*y+x = 10000019 - 99999989, but this never runs.

[QUOTE=lavalamp;248688]If it is your intention for the inner loop not to run, why not put the upper limit for the primes at 10^7? I am almost certain that this code does not do what you think it does.

Also there is no point in running the luhn check on 8 digit numbers unless you expect the first 8 digits to be 0.

To make it as obvious as I can that only nonsense is happening, here are the range of values for your loops and all that stuff in the isprime and luhn functions:

x = 2 - 7, y = 1 - 9999999, 10^crap*y+x = 10000002 - 99999990000007
x = 11 - 97, y = 1 - 999999, 10^crap*y+x = 1000011 - 999999000097
x = 101 - 997, y = 1 - 99999, 10^crap*y+x = 100101 - 9999900997
x = 1009 - 9973, y = 1 - 9999, 10^crap*y+x = 11009 - 99999973
x = 10007 - 99991, y = 1 - 999, 10^crap*y+x = 11007 - 1098991
x = 100003 - 999983, y = 1 - 99, 10^crap*y+x = 100103 - 1009883
x = 1000003 - 9999991, y = 1 - 9, 10^crap*y+x = 1000013 - 10000081
x = 10000019 - 99999989, [COLOR="Red"]y = 1 - 0[/COLOR], 10^crap*y+x = 10000019 - 99999989, but this never runs.[/QUOTE]

fine what ever lets put it this way I was trying to do that step I know the amount of elements in X

Warning, big post with lots of numbers ahead.

Aside from 2 and 5, all primes less than 10^4 and 10^8 must end in one of four numbers; 1, 3, 7, 9. Therefore a reasonable estimate for the number of primes less than 10^8, for which the 4 right-most digits also form a prime is:

π(10^4) = 1,229
π(10^8) = 5,761,455

5,761,455 * 1,229 / (4 * 10^3) = 1,770,207

The actual value being relatively easy to come by has of course already been established as 1,767,355. The estimate is quite close (0.16% difference), and so using this method a reasonably close value for the full 16 digits is possible to find:

π(10^16) = 279,238,341,033,925

279,238,341,033,925 * 1,767,355 / (4 * 10^7) = 12,337,831,955,450

The Luhn checksum then removes 9/10 of all candidates, so we are left with a value of 1.234 trillion candidates. This includes candidates with leading zeroes, since this is a credit card number, which allows for such things.

I also wrote some code to count up all composite numbers less than 10^12 where the last 4 and 8 digits are prime. The result for that is 16,010,694,859. Again, the estimation gets very close.

π(10^12) = 37,607,912,018

First find the number of numbers it's possible to intersect with:
4 * 10^11 - 4 * 10^7 = 399,960,000,000

And subtract the number of primes to leave the number of composites:
399,960,000,000 - π(10^12) + π(10^8) = 399,960,000,000 - 37,607,912,018 + 5,761,455 = 362,357,849,437

Now the estimation:
362,357,849,437 * 1,767,355 / (4 * 10^7) = 16,010,373,925, accurate to 0.0020%.

And through a similar method, estimating the number of 16 digit primes with the condition that the 12 right-most digits form a composite number:
279,200,733,121,907 * 16,010,694,859 / (4 * 10^11) = 11,175,494,356,060

Leaving 1,117,549,435,606 after the Luhn check. So requiring the 12 right-most digits to be prime drops the number of 16 digit candidates from 1.234 trillion to 1.118 trillion.

So what if the last 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14 and 15 digits (all except 4, 8 and 16) were required to be composite? Well there are 118,443 8 digit candidates, so starting from there, here are the actual and estimated values:[code]9 actual: 938,683
9 estimated: 932,484, good so far

10 actual: 8,431,359
10 estimated: 8,438,279, still pretty close

11 actual: 68,967,513
11 estimated: 76,592,568, what...

12 actual: 562,857,858
12 estimated: 631,932,326, sigh[/code]For some reason it goes way off track, so there must be some factor I'm missing.

Here is the full method for estimating 10 and 11 digit candidates with the above conditions:

π(10^9) = 50,847,534
π(10^10) = 455,052,511
π(10^11) = 4,118,054,813

10 digits:
desired intersection = 4 * 10^9 - 4 * 10^8 - π(10^10) + π(10^9) = 3,195,795,023
estimate = 3,195,795,023 * 938,683 / (4 * 10^8) = 7,499,596

Now because all 9 digit candidates are perfectly acceptable 10 digit candidates, we must add them on:
final estimate = 7,499,596 + 938,683 = 8,438,279

11 digits:
desired intersection = 4 * 10^10 - 4 * 10^9 - π(10^11) + π(10^10) = 32,336,997,698
estimate = 32,336,997,698 * 8,431,359 / (4 * 10^9) = 68,161,209

And again, add on the 10 digit candidates:
final estimate = 68,161,209 + 8,431,359 = 76,592,568

Note that before adding on the 10 digit candidates to get the final estimate, it's reasonably close. It's the same situation for estimating the 12 digit candidates. Could be purely coincidental, but I don't know. Does anyone see a flaw in the estimation method and/or how to fix it?

With such large errors it isn't possible to accurately estimate the number of 16 digit candidates with these conditions. I could let the code run all the way to 10^16, but that would take 6 months, at least without any further optimisations. I don't think that is something I'll be undertaking.

Finally, how many candidates would there be if every 1 to 16 right-most digits were required to be prime? With these conditions, code can run to 10^16 in a couple of minutes, so assuming I did it right, there are 912525 numbers that fit the bill, and assuming my Luhn check code is correct, 87945 pass (9.6% of them). The smallest being 0000 0000 0000 0059, and the largest being 9999 5600 0033 0347.

[QUOTE=lavalamp;248912]The smallest being 0000 0000 0000 0059, and the largest being 9999 5600 0033 0347.[/QUOTE]Bleh, small error, the smallest is of course 0000 0000 0000 0067, since 9 isn't a prime number!

What I don't get is why people haven tried a simplified problem? Reduce it to 8 digits in groups of 2 rather than 4. That should be easier to work out an exact number then you can start working on a non-brute force method.

I cannot think of any way to enumerate all candidates exactly other than to brute force it. Of course, there are some clever tricks that could be employed to speed up the process, but ultimately it's still going to involve a lot of CPU time.

However, you'll note that I did look at a reduced number of digits in order to determine a method for accurately estimating the number of possibilities for the full 16 digits.

Admittedly it only works sometimes. It seems that it goes haywire when estimating the number of composite candidates when previous digit levels are also required to be composite. I do not know why this is, so to reiterate, does anyone see a flaw in the estimation method and/or how to fix it?

[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 [url=http://www.merriampark.com/anatomycc.htm]Luhn-algorithm checksum[/url].

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]

I have the PARI code for the solve the problem is it's slow by the looks of it and it relies on 2 other codes care for a peek ? though I don't want someone stealing the card number if it's a rare property.

With regards to rarity, in relative terms only 0.12% of valid credit card numbers fit the bill, however in absolute terms that's still 1.2 trillion.

[QUOTE=lavalamp;253179]With regards to rarity, in relative terms only 0.12% of valid credit card numbers fit the bill, however in absolute terms that's still 1.2 trillion.[/QUOTE]

fine:

[CODE]creditcard() =b=[];c=0;d=0;until(e=1 && luhn(a) && isprime(a%10^4) && isprime(a%10^8),a=randomprime(16));return(a)[/CODE] the real problem is making random prime less random I have a way but it slows it down, though trying ten repeats of the same number may not help either.

[QUOTE=science_man_88;253180]fine:

[CODE]creditcard() =b=[];c=0;d=0;until(e=1 && luhn(a) && isprime(a%10^4) && isprime(a%10^8),a=randomprime(16));return(a)[/CODE] the real problem is making random prime less random I have a way but it slows it down, though trying ten repeats of the same number may not help either.[/QUOTE]

never mind that has the alterations lol.

[CODE]creditcard() =until(luhn(a) && isprime(a%10^4) && isprime(a%10^8),a=randomprime(16));return(a)[/CODE] is the simpler( but likely slower) version.

My approach:

Generate all 1767355 8-digit numbers that fulfil criteria 2 and 3 (right 4 and 8 digits are prime).

For each of these numbers, count all 16 digit CC numbers that also fulfil criteria 1 and 4. Expect about 3 weeks of calculation time for every second one candidate takes.


For every of these 1767355 candidates do:

Calculate the Luhn checksum of the right 8 digits. (checksum8)

Generate a sieving array of 100000000 elements.

Part 1:
(remove all candidates where the Luhn checksum fails. Don’t calculate the whole Luhn checksum every time, just add the last part in the inner loop to the intermediate checksum)

Digits 9 - 13
For(a=0, 99999, checksum13 = Checksum8 + Luhn(digits 9 -13) (no need to split up in 5 loops. The next inner 2 loops are more time critical)

Digit 14
For(b=0, 9, checksum14 = checksum13 + ((2*b)-1)%9 + 1

Digit 15
For(c=0, 9, checksum15 = checksum14 + c; calculate digit 16 (the first on the left side) and remove the other 9 from the array)

))
10000000 candidates remaining.

Part 2:
Sieve of Eratosthenes n * 100000000 + current candidate.
Sieve so far until the removal rate of composites is equal the speed of primalty checking.
Maybe use Miller Rabin to the first 9 prime bases (or is there a set of a smaller number of bases, where all exceptions <10^17 are known?)