Social Security Number

2008-10-25, 03:49

I'm not sure if people who are not in the programme can ask questions, and I'm also not sure if I can ask questions that are not about the programme (GIMPS), but as this place seems to be full of guys who know stuff about prime numbers I will ask anyway, and if that strikes anyone as rude then I'm sorry.

A friend asked me the following question:

I have an eleven-digit prime number (he actually said it was a Social Security Number but that is largely irrelevant). The first 7-digits form a prime, the first 8-digits form a prime and the first 9-digits form a prime. What is the probability of such a number occurring?

I am not interested in the probability part of his question. What appealed to me was the challenge of writing a programme to find his number. It turns out the number is not unique and I have so far found just under 5,000 of them.

Looking at the numbers kicked out by my programme I noticed something quite odd about them. To understand what is odd about them I need to explain how I searched for them.

I looked initially for 9-digit prime numbers with their final three digits all in the set [1, 3, 7, 9], like this: 100069733, 100093199, 100102799, 100138979. Then I confirmed that the 8-digit and 7-digit truncations of them were also prime. Lastly, I added a 2-digit extension to them and checked for primality. It is this final 2-digit extension that interests me.

There are obviously 40 valid combinations in the set, [11, 13, 17, 19, 21, 23, 27, etc] and I was expecting these to be represented in some arbitrary distribution. However, every single one of the numbers I have found ends with the 2-digit combination 11, as follows: 10006973311, 10009319911, 10010279911, 10013897911, 10014113311, 10022599711, 10026239911, 10034639911, 10039633711, 10039637911.

Admittedly, having found only 5,000 of them may seem a small sample from which to be drawing conclusions, but I was wondering if there is some mathematical explanation for this curiosity?

I thought it might have to do with congruence so have looked, briefly at that. The following table shows what I found.

Congruence......7-digit......8-digit......9-digit
1....................3342.........1677.........0
5....................1518.........3183.........4860

From the fact that all of the 9-digit numbers = 5(mod 6) we can see that our list of possible 2-digit extensions has 12 values that won't work. These are [ 13, 19, 31, 37, 43, 49, 61, 67, 73, 79, 91, 97] all of which would require the 11-digit number to be = 3(mod 6) and therefore not prime. but the other 28 values all work (from this point of view).

Next, I considered a fault in my programme. The 2-digit combinations are stored in an array and it struck me as possible that the routine for cycling through the array was not functioning properly. So I checked this by getting an output file of the numbers rejected at this stage and they show examples of all the other combinations. That obviously does not exhaust the possibility for fault with my programme, but it is not going to be something trivially obvious.

So, my question is:

Is there a mathematical explanation for these numbers all ending with 11?

Jens K Andersen · 2008-10-26, 03:23

I guess your program has a bug but I cannot say where without seeing the source. Here is a primitive PARI/GP search:
? for(p=1000000,1000100,if(isprime(p),for(d=1,9,q=10*p+d;if(isprime(q),for(e=1,9,r=10*q+e;if(isprime(r),for(f=11,99,s=100*r+f;if(isprime(s),print(s)))))))))
10000813327
10000813331
10000813351
10000813369
10000819937
10000819943
10000819963
10000993337
10000993351
10000993361
10000993399

If it's modified to only test numbers ending in 11 then it gives your list of numbers:
? for(p=1000000,1004000,if(isprime(p),for(d=1,9,q=10*p+d;if(isprime(q),for(e=1,9,r=10*q+e;if(isprime(r),for(f=11,11,s=100*r+f;if(isprime(s),print(s)))))))))
10006973311
10009319911
10010279911
10013897911
10014113311
10022599711
10026239911
10034639911
10039633711
10039637911

axn · 2008-10-26, 05:37

The very first eligible 9 digit number (100008133) yields the following primes:

10000813307
10000813309
10000813327
10000813331
10000813351
10000813369

Oleg V.Cat · 2008-10-26, 10:24

Hmmm...

Loks like that are just two 10 digits prime numbers, which are under the following rules:

First digit is a prime.
First 2 digits form a prime
...
First n-1 digits form a prime.

Numbers are:
1979339333
1979339339

If we need 11 digits number, then we must use 10, 40 or 82 as first two digits (so, only 3,4,5...10 first digits form a prime), full result set with 11 and more digits is:
10399793993
40993391939
82939939933
103997939939
409933919393
829399399331
829399399333
4099339193933

Intresting, that digits "1" and "7" are rare, average probability for all 4 possible digits (1,3,7,9) must be 0.25, but we have only 0.025 for "7" and 0.05 for "1".

Jens K Andersen · 2008-10-27, 02:33

Quote:

Originally Posted by Oleg V.Cat

First digit is a prime.
...
1979339333
...
Intresting, that digits "1" and "7" are rare.

You appear to include 1 in the primes. This is rarely done today. If 1 is not considered prime then we get the right-truncatable primes in A024770. There are 83 in total and the largest is 73939133.

Your 4099339193933 is listed at http://www.primepuzzles.net/puzzles/puzz_131.htm. My submitted numbers included 133028062963 which is the smallest prime where a prime-making digit can be appended 14 times, ending with 13302806296379339933399333. Can you find a 15?

The many 3's and 9's is no coincidence. Appending 3 or 9 to a decimal number does not change the value modulo 3. But appending 1 or 7 increases the value modulo 3 by 1. If it was 2 before then it becomes 3 (or congruently 0) and thus divisible by 3. If it was 1 then it becomes 2, and will become divisible by 3 next time a 1 or 7 is appended. So at most two 1's or 7's in total can be appended.

My website has another variation at http://hjem.get2net.dk/jka/math/left-truncatable.htm where two decimal digits are appended at a time. Let p110 =
112997419307834977573171270727470309575119399999236391538737\
53018739231353934953196323876313992301272907878337
p110 gives 55 primes after 2, 4, 6, ..., 110 digits. An exhaustive search showed this is maximal for primes starting with 11. Exhaustive searches for all other starts would be feasible but take longer than I'm willing to do.

Oleg V.Cat · 2008-10-27, 03:48

Quote:

Originally Posted by Jens K Andersen

You appear to include 1 in the primes. This is rarely done today.

Yep, I re-read the definition. Prime numbers must have two different dividers, not one

.

Quote:

Originally Posted by Jens K Andersen

numbers included 133028062963 which is the smallest prime where a prime-making digit can be appended 14 times, ending with 13302806296379339933399333. Can you find a 15?

Oh, no... I am not so addicted to primes

2008-10-27, 08:44

Jens and axn1,
I think computer bugs have evolved to be the principal cause of male pattern baldness!

Nevertheless, I found it. Thanks to your work I knew I was looking for a bug that actually existed. This is much better than looking for speculative bugs, so thank you very much for your help.

Martin.

2008-10-25, 03:49	#1
Unregistered 3×2,729 Posts	Social Security Number I'm not sure if people who are not in the programme can ask questions, and I'm also not sure if I can ask questions that are not about the programme (GIMPS), but as this place seems to be full of guys who know stuff about prime numbers I will ask anyway, and if that strikes anyone as rude then I'm sorry. A friend asked me the following question: I have an eleven-digit prime number (he actually said it was a Social Security Number but that is largely irrelevant). The first 7-digits form a prime, the first 8-digits form a prime and the first 9-digits form a prime. What is the probability of such a number occurring? I am not interested in the probability part of his question. What appealed to me was the challenge of writing a programme to find his number. It turns out the number is not unique and I have so far found just under 5,000 of them. Looking at the numbers kicked out by my programme I noticed something quite odd about them. To understand what is odd about them I need to explain how I searched for them. I looked initially for 9-digit prime numbers with their final three digits all in the set [1, 3, 7, 9], like this: 100069733, 100093199, 100102799, 100138979. Then I confirmed that the 8-digit and 7-digit truncations of them were also prime. Lastly, I added a 2-digit extension to them and checked for primality. It is this final 2-digit extension that interests me. There are obviously 40 valid combinations in the set, [11, 13, 17, 19, 21, 23, 27, etc] and I was expecting these to be represented in some arbitrary distribution. However, every single one of the numbers I have found ends with the 2-digit combination 11, as follows: 10006973311, 10009319911, 10010279911, 10013897911, 10014113311, 10022599711, 10026239911, 10034639911, 10039633711, 10039637911. Admittedly, having found only 5,000 of them may seem a small sample from which to be drawing conclusions, but I was wondering if there is some mathematical explanation for this curiosity? I thought it might have to do with congruence so have looked, briefly at that. The following table shows what I found. Congruence......7-digit......8-digit......9-digit 1....................3342.........1677.........0 5....................1518.........3183.........4860 From the fact that all of the 9-digit numbers = 5(mod 6) we can see that our list of possible 2-digit extensions has 12 values that won't work. These are [ 13, 19, 31, 37, 43, 49, 61, 67, 73, 79, 91, 97] all of which would require the 11-digit number to be = 3(mod 6) and therefore not prime. but the other 28 values all work (from this point of view). Next, I considered a fault in my programme. The 2-digit combinations are stored in an array and it struck me as possible that the routine for cycling through the array was not functioning properly. So I checked this by getting an output file of the numbers rejected at this stage and they show examples of all the other combinations. That obviously does not exhaust the possibility for fault with my programme, but it is not going to be something trivially obvious. So, my question is: Is there a mathematical explanation for these numbers all ending with 11?

2008-10-26, 05:37	#3
axn Jun 2003 2×7×389 Posts	The very first eligible 9 digit number (100008133) yields the following primes: 10000813307 10000813309 10000813327 10000813331 10000813351 10000813369 Last fiddled with by axn on 2008-10-26 at 05:38

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
security of the webpage?	Unregistered	Information & Answers	4	2013-02-08 04:42
Social Network Analysis Project	garo	Lounge	26	2009-05-29 13:11
v5 security problems	ixfd64	PrimeNet	12	2008-11-10 09:31
Key fob security.	Xyzzy	Science & Technology	13	2007-03-09 02:39
A security puzzle	T.Rex	Puzzles	12	2007-02-11 11:54

2008-10-26, 03:23	#2
Jens K Andersen Feb 2006 Denmark 2·5·23 Posts	I guess your program has a bug but I cannot say where without seeing the source. Here is a primitive PARI/GP search: ? for(p=1000000,1000100,if(isprime(p),for(d=1,9,q=10p+d;if(isprime(q),for(e=1,9,r=10q+e;if(isprime(r),for(f=11,99,s=100r+f;if(isprime(s),print(s))))))))) 10000813327 10000813331 10000813351 10000813369 10000819937 10000819943 10000819963 10000993337 10000993351 10000993361 10000993399 If it's modified to only test numbers ending in 11 then it gives your list of numbers: ? for(p=1000000,1004000,if(isprime(p),for(d=1,9,q=10p+d;if(isprime(q),for(e=1,9,r=10q+e;if(isprime(r),for(f=11,11,s=100r+f;if(isprime(s),print(s))))))))) 10006973311 10009319911 10010279911 10013897911 10014113311 10022599711 10026239911 10034639911 10039633711 10039637911

2008-10-26, 10:24	#4
Oleg V.Cat Oct 2008 Riga, Latvia 11 Posts	Hmmm... Loks like that are just two 10 digits prime numbers, which are under the following rules: First digit is a prime. First 2 digits form a prime ... First n-1 digits form a prime. Numbers are: 1979339333 1979339339 If we need 11 digits number, then we must use 10, 40 or 82 as first two digits (so, only 3,4,5...10 first digits form a prime), full result set with 11 and more digits is: 10399793993 40993391939 82939939933 103997939939 409933919393 829399399331 829399399333 4099339193933 Intresting, that digits "1" and "7" are rare, average probability for all 4 possible digits (1,3,7,9) must be 0.25, but we have only 0.025 for "7" and 0.05 for "1".

2008-10-27, 08:44	#7
Unregistered 3487₁₀ Posts	Jens and axn1, I think computer bugs have evolved to be the principal cause of male pattern baldness! Nevertheless, I found it. Thanks to your work I knew I was looking for a bug that actually existed. This is much better than looking for speculative bugs, so thank you very much for your help. Martin.