When is 111…111 prime?

July 1, 2011

When you’re on facebook, you’ll see a lot of people posting a lot of silly things.  It would be interesting to see what kinds of things are posted when, but this is a subject for some kind of cybersociologists.  Nonetheless, if you are awake at around 11pm and on facebook (and, I’ll admit it, I’m one of these people), you might see a string of comments that essentially say: "omg, it’s 11:11, make a wish."

If you’re superstitious or obsessive compulsive, this might be a lucky reminder to make a wish at this time, but besides its symmetry and visually appealing form, what’s so special about 1111? 

The first thing I like to do when I see a number is check to see if it is prime or not.  But we notice that 1111 is not even prime!  It’s 101 * 11.   What about 111?  No, that’s also not prime.  It’s divisible by 3. 

Then I thought, "Well, what kinds of numbers of the form 111…111 are prime?  That is, how many 1’s do I need to make something like that prime?  Is 111111 prime?  Is 11111111111111 prime?"

So, without appealing to any number theory [which I, honestly, am quite terrible at] I decided to try to figure some stuff out about this.  It’s clear that:

  • There cannot be an even number (greater than 2) of 1’s, since otherwise the number is divisible by 11.
  • The number of 1’s cannot be a multiple of 3, since otherwise the number is divisible by 3. 
  • We note initially that 1 is not prime and 11 is prime.

But besides this, I was unable to think of any other criteria for these numbers to be prime.  I made a simple python program to test the first hundred or so of these numbers, but the program wasn’t able to test numbers that had more than 20 digits quickly.  Thus, I went to wolfram alpha, which started to get quite slow around 100 digits.  I decided to dust off my Mathematica hat and attempt to code it.  I wrote the following elementary code to test and display the numbers of this form that were prime.

 

For[i = 1, i < 5000, i++,
If[PrimeQ[Sum[10^(j), {j, 0, i}]],
  Print[Sum[10^(j), {j, 0, i} ], " ", i + 1]]]

 

Below, instead of reproducing the prime numbers in the form 111…111, I’ve decided to just list how many digits they have.  For example, 11 is prime so I’ve written "2". 

2, 19, 23, 317, 1031…

Only these five (up to 45,000 digits) are primes.  This is kind of curious.  Also, I have no way of even showing that infinitely many will be primes, but I suspect that this is true. 

Also, many of these numbers are also divisible by 41.

At first I wasn’t exactly sure why.  But then I made this little Mathematica script:

 

For[i = 1, i < 10, i++,
If[Divisible[Sum[10^(j), {j, 0, i}], 41],
  Print[Column[{Sum[10^(j), {j, 0, i}], (Sum[10^(j), {j, 0, 1}])/
      41}]]]]

 

And something quite beautiful came out of it.  I’ll only reproduce the first part of it, because you’ll get the idea.  See if you can find other pretty stuff about these numbers! 

 

The number of digits in the 111…111 number. Divide by 41 and we get…
5 271
10 27100271
15 2710027100271
20 271002710027100271
25 27100271002710027100271
30 2710027100271002710027100271
35 271002710027100271002710027100271

 

Cool.  See what else you can find!

 

 

Edit: Apparently, there’s been a bunch of work on this.  I can’t access the papers, but here’s a website about it, and here’s the OEIS page for the sequence.  I would have been calculating a long time; the next number in that sequence at the beginning of the post is 49,081!  It’s also interesting that all the numbers in this list seem to be prime…

EditEdit: As a few of you have pointed out, those 27100 numbers have a definite pattern to them.  I’m making this chart below to illustrate it:

 

This… is equal to…
271 271
27100271 271 * 100001
2710027100271 271 * 10000100001
271002710027100271 271 * 1000010000100001

 

Which brings some things into perspective.  We can do this same sort of process to show some other neat things.  For example, suppose that we have an r-digit number of the form 111…111, and we know that this is not prime.  Then for any n\in {\mathbb N}, we know that the r\cdot n-digit number will not be prime, since we may factor it almost exactly as the chart above with the 271-numbers.  For example, we know that 1111111 is not prime (7 digits) and so we note that

 

Number of digits… Factors into…
7 1111111*1
14 1111111*10000001
21 1111111*100000010000001
28 1111111*1000000100000010000001

 

Notice that the length of the string "0000001" is exactly 7 and there are n-1 of them appended to an initial 1.  Thus we predict that if we have a number in this form of length, say, 100, then we know it can’t be prime since, in particular, 100 = 4*25, so we would have that our number with 100 1’s would factor into:

1111 *

100010001000100010001000100010001000100010001000

1000100010001000100010001000100010001000100010001

which is exactly what the calculator gives us. 

 

Thus, we should expect all of the numbers that give us the number of digits in the prime numbers of the form 111…111 to be primes themselves.  Otherwise, we could decompose these as we did above.  So, that answers one question at least.

Advertisements

4 Responses to “When is 111…111 prime?”

  1. zariski said

    Henryk Iwaniec proves a sequence in the form a^2 + b^4 has infinitely many primes. As I know, this is the fastest increasing sequence which is confirmed infinitely many primes.

    111…11 increases exponentially like Mersenne sequence 2^n -1 or Fermat sequence 2^{2^n}+1 so it is very hard problem, in my opinion. :)

  2. nasim said

    hello
    I have one question

    Find a formula for the sum 1+11+111+1111+…+111..11(n times)
    =?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: