"Prime Rewards" Credit Card - Page 3

lavalamp · 2011-01-21, 00:17

I didn't see your post, so I don't know what you said. However, instead of finding the number of primes less than 10^4 and multiplying by 10^12, you could have found the number of primes less than 10^16:
http://en.wikipedia.org/wiki/Prime-counting_function

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

279 trillion versus 1.23 quadrillion.

R. Gerbicz · 2011-01-21, 00:41

Quote:

Originally Posted by R. Gerbicz

If we "forget" that the card is prime, but other 3 requirements are true, then it is easy to calculate this number:

Code:

s=0;forprime(p=2,10^8,s+=isprime(p%10000));return(s*10^7)
17673550000000

It wouldn't be terrible to calculate the answer for the original puzzle: For this fix p, where 0<p<10^8 prime and p%10000 is also prime. Then sieve p+10^8*i for 0<=i<10^8 so in a remainder class, this is quite good, since that's 10^8 numbers and we have to sieve by primes up to sqrt(10^16)=10^8. For each q=p+i*10^8 prime check if it is a valid card for Luhn alg.

For p there are 1767355 choices, it means that we have to sieve out only about 1.7*10^14 numbers, instead of 10^16.

science_man_88 · 2011-01-21, 00:47

Quote:

Originally Posted by lavalamp

I didn't see your post, so I don't know what you said. However, instead of finding the number of primes less than 10^4 and multiplying by 10^12, you could have found the number of primes less than 10^16:
http://en.wikipedia.org/wiki/Prime-counting_function

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

279 trillion versus 1.23 quadrillion.

Yeah. I was going off the prime <10^4 because the last 4 digits must form a prime and just knowing how many primes there are under 10^16 may have got me closer but I'd still have to eliminate based on which ones ended in a 4 digit prime (including leading 0's for smaller amounts)

lavalamp · 2011-01-21, 03:05

Quote:

Originally Posted by R. Gerbicz

For p there are 1767355 choices

Ah, I got 112 higher, but now I remember it's because the upper limit in a pari/gp for loop is inclusive and I ran an outer loop from 0 to 10000.

Code:

{

n=0;

for(a=0,9999,
  forprime(p=2,9999,
    if(isprime(a*10000+p),n++)
  )
);

print(n);

}

As for the sieve, I wouldn't call 1.7*10^14 candidates "only". Even after sieveing out composites there will still be several billion candidates remaining (admittedly lower than the 800 billion I took a stab at earlier).

Anyone have an off-the-shelf segmented sieve they feel like running these numbers through?

Uncwilly · 2011-01-21, 04:10

Quote:

Originally Posted by ixfd64

Man, I could see the headlines already...

"MersenneForum fully funded through 2197."

ewmayer · 2011-01-21, 05:11

Quote:

Originally Posted by Uncwilly

"MersenneForum fully funded through 2197."

Does that mean my impending "financially wrenching" experience would at least be tax-deductible?

Xyzzy · 2011-01-21, 05:33

Imagine all of the Hoff memorabilia we could buy!

Flatlander · 2011-01-21, 13:40

Maybe we should ask him how much credit he has left before we hit him over the head ... I mean, calculate the number.

lavalamp · 2011-01-21, 17:58

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.

science_man_88 · 2011-01-21, 18:48

1) let $Z$ be the primes.
2) let $Y$ be the numbers less than 10 000
3) we can define the set $X$ to be the subset of $Y\cap Z$
4) let $A$ be the set of 8 digit numbers with ${last 4 digits}\in X$
5)we let $B$ become the subset of A where $A\cap Z$
6) we make new sets $C$ $D$ and $E$ , where C is the set of 16 digits card numbers, D is where C conforms to ${last 8 digits}\in A$ , and E is where $D\cap Z$

if $\cap$ means intersect, then my logic points me in the direction that what we are solving for is how many elements in E pass the Luhn-algorithm checksum.

is my logic even close to accurate ?

davar55 · 2011-01-21, 19:53

Quote:

Originally Posted by ewmayer

Science_man, of you can't be bothered to even read up on the most elementary aspects of number theory, just STFU, will you?

Good grief, that was some unbelievably stupid shit there. I had to delete it simply to keep this from turning into another 100-post flamefest between you and Bob Silverman.

Deleted before I read it.

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

Could someone fill me in?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
AMD Announces Industry's First "Supercomputing" Server Graphics Card	ET_	GPU Computing	23	2013-11-18 17:49
Speeding up double checking when first test returns "prime"	Unregistered	PrimeNet	16	2006-02-28 02:00
Oh noes! The "42nd Mersenne prime" isn't prime!	ixfd64	Lounge	7	2005-04-03 19:27
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2011-01-21, 00:17	#23
lavalamp Oct 2007 Manchester, UK 5·271 Posts	I didn't see your post, so I don't know what you said. However, instead of finding the number of primes less than 10^4 and multiplying by 10^12, you could have found the number of primes less than 10^16: http://en.wikipedia.org/wiki/Prime-counting_function pi(10^16) = 279,238,341,033,925 279 trillion versus 1.23 quadrillion.

2011-01-21, 05:33	#29
Xyzzy "Mike" Aug 2002 10000000100000₂ Posts	Imagine all of the Hoff memorabilia we could buy!

2011-01-21, 13:40	#30
Flatlander I quite division it "Chris" Feb 2005 England 31×67 Posts	Maybe we should ask him how much credit he has left before we hit him over the head ... I mean, calculate the number.

2011-01-21, 17:58	#31
lavalamp Oct 2007 Manchester, UK 5×271 Posts	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.

2011-01-21, 18:48	#32
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶×131 Posts	1) let $Z$ be the primes. 2) let $Y$ be the numbers less than 10 000 3) we can define the set $X$ to be the subset of $Y\cap Z$ 4) let $A$ be the set of 8 digit numbers with ${last 4 digits}\in X$ 5)we let $B$ become the subset of A where $A\cap Z$ 6) we make new sets $C$ $D$ and $E$ , where C is the set of 16 digits card numbers, D is where C conforms to ${last 8 digits}\in A$ , and E is where $D\cap Z$ if $\cap$ means intersect, then my logic points me in the direction that what we are solving for is how many elements in E pass the Luhn-algorithm checksum. is my logic even close to accurate ?