"Prime Rewards" Credit Card

[lavalamp]

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 ?

That it will take you a LONG time to finish. Also that you should be using a forprime loop.

R. Gerbicz posted some good code, he used a forprime loop to generate all primes for the last 8 digits, and only incremented a counter if p%10^4 was also prime. This completely removes checking the primality of lots of 8 digit numbers from the code.

Modified, you could increment a counter if it passes the checksum, and the full 16 digit number is prime too. But it will still take a REALLY long time. Sieving really does seem to be the way to go.

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?

Well, applying that to just the last 8 digits takes it from 1,767,355 candidates to 118443.

[science_man_88]

Originally Posted by lavalamp

. Also that you should be using a forprime loop.

you realize 2^32 has 10 digits and that's above what my primelimit can goto so no I don't need a forprime loop unless I'm checking ones under 2^32.

[lavalamp]

Your loop increments 2 every time, this means that you must run 10^16 / 2 = 5*10^15 iterations. If instead you had a forprime loop running from 2 to 10^8, and a regular for loop nested inside running from 0 to 10^8, the total number of iterations inside both loops would be 5.76*10^14.

However, you can cut that number down more by performing the primality check on the last 4 digits before entering the inside loop. This drops the number of iterations inside both loops to 1.77*10^14. It also removes the need for nearly 10^16 primality tests.

[science_man_88]

Originally Posted by CRGreathouse

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.

I tried reversing the isprime and it ended up being about half as long for a 1 digit increase in digits between that second and last 1. how much faster is that ?

(18:51)>b=0;forstep(x=1000000000000001,1000000100000001,2,if(isprime(x%(10^4)) && isprime(x%(10^8)) && isprime(x) && luhn(x),b=b+1));print(b)
8959
(18:57)>##
  ***   last result computed in 4mn, 44,641 ms.

[science_man_88]

Originally Posted by lavalamp

Your loop increments 2 every time, this means that you must run 10^16 / 2 = 5*10^15 iterations. If instead you had a forprime loop running from 2 to 10^8, and a regular for loop nested inside running from 0 to 10^8, the total number of iterations inside both loops would be 5.76*10^14.

However, you can cut that number down more by performing the primality check on the last 4 digits before entering the inside loop. This drops the number of iterations inside both loops to 1.77*10^14. It also removes the need for nearly 10^16 primality tests.

it would increase the multiplications needed to get a result as the only way i see this working is by appending the 2 numbers on top of each other which means I'd have to multiply the last loop control variable by 10^8, to get the full 16 digit number to test. oh and to CRG my test last i checked were at minimal memory for PARI.

[science_man_88]

never mind you beat me lol, thanks for the tip I can tell you a small list lol.

(19:18)>b=0;forprime(x=1,10^8-1,if(isprime(x%(10^4)),for(y=1,10^8-1,if(isprime(10^8*y+x) && luhn(10^8*y+x),print(10^8*y+x)))))
list cleaned for safety purposes.
  *** print: user interrupt after 52,672 ms.

431 in the list I cleared by the way. highest one was 13 digits i think.

[lavalamp]

I would be interested to see your luhn function. I wrote my own luhn function, and ran your code using it. I got a result of 8464, whereas you posted 8959. I wrote some double-loop code and that also returned 8464. The difference lies in the luhn function.

There are the timings I recorded:

Your code: 6mn, 19,644 ms
My code: 5mn, 27,758 ms (16% faster)

Then I reversed the order of the isprime(<16digitnum>) and luhn functions, and got these timings:

Your code: 1mn, 49,278 ms
My code: 57,409 ms (90% faster)

For a real demonstration of how much quicker the double loop method is, I removed the isprime(<16digitnum>) and luhn checks:

Your code: 49,795 ms
My code: 5,647 ms (782% faster)

I have no idea how you recorded a time of 4mn, 44,641 ms for that run a couple of posts up, I ran the same code but without the luhn check (so it should have been faster) and it took 6mn, 15,573 ms. This was on a 4 GHz dedicated CPU core. Do you have an overclocked Sandy Bridge?

Anyway, onto actual code. Here is my luhn function and double-loop code:

{

(l(x)=
  t=2*floor(x%100000000/10000000)+(x%100000000>49999999)+floor(x%10000000/1000000)+2*floor(x%1000000/100000)+(x%1000000>499999)+floor(x%100000/10000)+2*floor(x%10000/1000)+(x%10000>4999)+floor(x%1000/100)+2*floor(x%100/10)+(x%100>49)+x%10;
  x=(x-x%100000000)/100000000;
  return((t+2*floor(x%100000000/10000000)+(x%100000000>49999999)+floor(x%10000000/1000000)+2*floor(x%1000000/100000)+(x%1000000>499999)+floor(x%100000/10000)+2*floor(x%10000/1000)+(x%10000>4999)+floor(x%1000/100)+2*floor(x%100/10)+(x%100>49)+x%10)%10==0)
);

n=0;

forprime(p=3,100000000,
  if(isprime(p%10000),
    for(a=10000000,10000000,
      if(l(a*100000000+p)&&isprime(a*100000000+p),n++)
    )
  )
);

print(n);

}

My luhn function (just l(x) in my code) looks kind of a mess, that's because I did some loop unrolling on it to make it faster. On my system it can do about 100,000 checks / second (10 µs each) for 16 digit numbers. The inner loop only runs once, that's so it runs over the same range as your code for a direct comparison.

Edit: Despite being made several hours ago, I didn't actually see your last post, but upon reading it now I see that we posted virtually identical code. I would still like to see your luhn function though.

[science_man_88]

Originally Posted by lavalamp

I would be interested to see your luhn function. I wrote my own luhn function, and ran your code using it. I got a result of 8464, whereas you posted 8959. I wrote some double-loop code and that also returned 8464. The difference lies in the luhn function.

There are the timings I recorded:

Your code: 6mn, 19,644 ms
My code: 5mn, 27,758 ms (16% faster)

Then I reversed the order of the isprime(<16digitnum>) and luhn functions, and got these timings:

Your code: 1mn, 49,278 ms
My code: 57,409 ms (90% faster)

For a real demonstration of how much quicker the double loop method is, I removed the isprime(<16digitnum>) and luhn checks:

Your code: 49,795 ms
My code: 5,647 ms (782% faster)

I have no idea how you recorded a time of 4mn, 44,641 ms for that run a couple of posts up, I ran the same code but without the luhn check (so it should have been faster) and it took 6mn, 15,573 ms. This was on a 4 GHz dedicated CPU core. Do you have an overclocked Sandy Bridge?

Anyway, onto actual code. Here is my luhn function and double-loop code:

{

(l(x)=
  t=2*floor(x%100000000/10000000)+(x%100000000>49999999)+floor(x%10000000/1000000)+2*floor(x%1000000/100000)+(x%1000000>499999)+floor(x%100000/10000)+2*floor(x%10000/1000)+(x%10000>4999)+floor(x%1000/100)+2*floor(x%100/10)+(x%100>49)+x%10;
  x=(x-x%100000000)/100000000;
  return((t+2*floor(x%100000000/10000000)+(x%100000000>49999999)+floor(x%10000000/1000000)+2*floor(x%1000000/100000)+(x%1000000>499999)+floor(x%100000/10000)+2*floor(x%10000/1000)+(x%10000>4999)+floor(x%1000/100)+2*floor(x%100/10)+(x%100>49)+x%10)%10==0)
);

n=0;

forprime(p=3,100000000,
  if(isprime(p%10000),
    for(a=10000000,10000000,
      if(l(a*100000000+p)&&isprime(a*100000000+p),n++)
    )
  )
);

print(n);

}

My luhn function (just l(x) in my code) looks kind of a mess, that's because I did some loop unrolling on it to make it faster. On my system it can do about 100,000 checks / second (10 µs each) for 16 digit numbers. The inner loop only runs once, that's so it runs over the same range as your code for a direct comparison.

Edit: Despite being made several hours ago, I didn't actually see your last post, but upon reading it now I see that we posted virtually identical code. I would still like to see your luhn function though.

my computer reset and it's not dedicated or sandy bridge as far as I know.

I'll have to recreate my luhn code I involved my sumdigits code for the 4 min and something test I believe.

(x)->w=eval(Vec(Str(x)));a=0;if(#w%2==1,for(i=1,#w,if(i%2==0,a=a+(2*w[i]),a=a+w[i])),for(i=1,#w,if(i%2==1,a=a+(2*w[i]),a=a+w[i])));if(a%10==0,return(1),return(0))

I've seen a problem with my code though and that's that in odd number of digits cases it would ad double the last digit(aka the sumdigit) I'll have to fix that. mind you I check if it's odd or even length, for using it for an even numbered case I should just use the second half and save time.

[science_man_88]

Originally Posted by science_man_88

I've seen a problem with my code though and that's that in odd number of digits cases it would ad double the last digit(aka the sumdigit) I'll have to fix that. mind you I check if it's odd or even length, for using it for an even numbered case I should just use the second half and save time.

god I'm stupid I've made sure it can't because the #w is odd in a odd length one but I'm only targeting even ones for doubling doh.

[cheesehead]

Speaking of the number of combinations of digits that follow certain rules:

Yesterday I received my copy of Knuth 4A (or "The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1" by Donald E. Knuth).

[davar55]

Originally Posted by cheesehead

Speaking of the number of combinations of digits that follow certain rules:

Yesterday I received my copy of Knuth 4A (or "The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1" by Donald E. Knuth).

I may have to look in the stores for it.