View Single Post
Old 2008-10-25, 03:49   #1

2·3,547 Posts
Default 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.


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?
  Reply With Quote