"Prime Rewards" Credit Card

[ewmayer]

Originally Posted by davar55

Deleted before I read it.

I keep missing the "fun" (disruption isn't really fun).

Could someone fill me in?

Alright, alright ... I undeleted the 2 posts in question. Like I said, it was really my fault for not respecting the "ignore user" I placed on sm88 last year. My ignorance of his repeated putting-on-display of his own ignorance was bliss, but then curiosity demised the metaphorical feline, or something.

[science_man_88]

I've got a code working to check the luhn test. now it's checking through the 16 digits primes that have the last 8 digits a prime that have the last 4 digits a prime.

[CRGreathouse]

Originally Posted by science_man_88

I've got a code working to check the luhn test. now it's checking through the 16 digits primes that have the last 8 digits a prime that have the last 4 digits a prime.

Why don't you just check 1000000000000000 through 1000001000000000 and tell us how long that takes? That way you'll have a good idea of how long the whole thing will take (about a million times longer).

[science_man_88]

Originally Posted by CRGreathouse

Why don't you just check 1000000000000000 through 1000001000000000 and tell us how long that takes? That way you'll have a good idea of how long the whole thing will take (about a million times longer).

I know I'm a crappy idea major lol.

(17:09)>a=0;forstep(x=1000000000000001,1000000000100001,2,if(isprime(x) && luhn(x),a=a+1));print(a)
82
(17:11)>a=0;forstep(x=1000000000000001,1000000000100001,2,if(isprime(x) && isprime(x%10^8) &&luhn(x),a=a+1));print(a)
84

This shouldn't happen! and it returned the 2 numbers on the test site perfectly to spec. Sorry crossed a control variable.

[science_man_88]

(17:19)>b=0;forstep(x=1000000000000001,1000000000100001,2,if(isprime(x) && isprime(x%10^8) && isprime(x%10^4) && luhn(x),b=b+1));print(b)
22
(17:20)>##
  ***   last result computed in 5,000 ms.
(17:21)>b=0;forstep(x=1000000000000001,1000000001000001,2,if(isprime(x) && isprime(x%10^8) && isprime(x%10^4) && luhn(x),b=b+1));print(b)
126
(17:22)>##
  ***   last result computed in 51,875 ms.
(17:22)>b=0;forstep(x=1000000000000001,1000000010000001,2,if(isprime(x) && isprime(x%10^8) && isprime(x%10^4) && luhn(x),b=b+1));print(b)
1019
(17:32)>##
  ***   last result computed in 8mn, 48,719 ms.

what does this tell you ?

[ewmayer]

Originally Posted by lavalamp

I don't know how much it would narrow down the search, but from the looks of it Ernst checked the primality of the rightmost numbers on his credit card in batches of 4, so that in all likelyhood, the rightmost 12-digit portion is NOT prime.

Of course he may have checked them in batches of 2^n from n = 2 to 4, but since they are grouped into 4 batches of 4, this seems less likely.

This opens up another interesting avenue for winnowing candidates: Let's assume for the sake of argument that for the mystery 16-digit number N, I checked the primality of (N mod (10^d)) for d = 1,2,3,...,16, and those d-values I reported as yielding a prime are the only ones. (That's not what I did for my card number, but ... I could be lying. ;) How much would knowledge of the prime/not-prime status of all 16 power-of-10 residues narrow the list of possibilities?

[science_man_88]

Originally Posted by ewmayer

This opens up another interesting avenue for winnowing candidates: Let's assume for the sake of argument that for the mystery 16-digit number N, I checked the primality of (N mod (10^d)) for d = 1,2,3,...,16, and those d-values I reported as yielding a prime are the only ones. (That's not what I did for my card number, but ... I could be lying. ;) How much would knowledge of the prime/not-prime status of all 16 power-of-10 residues narrow the list of possibilities?

your new idea has made me see a flaw in my code (no big surprise). That's I test the last eight digits before the last 4. If the last 4 isn't prime I'm wasting time.

[CRGreathouse]

Originally Posted by science_man_88

(17:19)>b=0;forstep(x=1000000000000001,1000000000100001,2,if(isprime(x) && isprime(x%10^8) && isprime(x%10^4) && luhn(x),b=b+1));print(b)
22
(17:20)>##
  ***   last result computed in 5,000 ms.
(17:21)>b=0;forstep(x=1000000000000001,1000000001000001,2,if(isprime(x) && isprime(x%10^8) && isprime(x%10^4) && luhn(x),b=b+1));print(b)
126
(17:22)>##
  ***   last result computed in 51,875 ms.
(17:22)>b=0;forstep(x=1000000000000001,1000000010000001,2,if(isprime(x) && isprime(x%10^8) && isprime(x%10^4) && luhn(x),b=b+1));print(b)
1019
(17:32)>##
  ***   last result computed in 8mn, 48,719 ms.

what does this tell you ?

You're going to 10^15 and it took you 8:48.719 to get to 10^7. Your expected completion time is (10^15 / 10^7) * 8:48.719 or 1675 years. Get comfy.

[ewmayer]

Ah, the return of blissful stillness:

[CRGreathouse]

Originally Posted by ewmayer

This opens up another interesting avenue for winnowing candidates: Let's assume for the sake of argument that for the mystery 16-digit number N, I checked the primality of (N mod (10^d)) for d = 1,2,3,...,16, and those d-values I reported as yielding a prime are the only ones. (That's not what I did for my card number, but ... I could be lying. ;) How much would knowledge of the prime/not-prime status of all 16 power-of-10 residues narrow the list of possibilities?

I had the same thought. Most of the advantage is gained with the small numbers; there are only 118,443 candidates mod 10^8 rather than 1,767,355.

[R.D. Silverman]

Originally Posted by CRGreathouse

I'd think more than that. If the 16-digit number is prime, then the last digit is relatively prime to 10*, so the odds improve by a factor of ~ (5/2)^2.

* 0000000000000002 and 0000000000000005 fail the Luhn test.

Neither of these are 16 digit numbers!! They are 1 digit numbers.

They are however, 16 digit digit STRINGS.

Ernst did say "number", not "string". The most significant digit of a number
is non-zero.