Testing primality for large numbers

Computer Science Level 4

The number $121$ is composite.
The number $1211$ is composite.
The number $12111$ is composite.
The number $121111$ is composite.

Let $n$ be the smallest positive integer such that $12\underbrace{11...11}_{n \text{ times}}$ is prime.

Find $n$ .

The answer is 136.

2 solutions

Steven Perkins
Jun 7, 2017

Here is my Python program:

t=12
for i in range(1,1000):
 t=t*10+1
 if (isprime(t)):
  print i,t

Of course the isprime() function is where the fun lies. I use a Miller–Rabin primality test. You can look those up on the web.

It's important to know that for numbers this large, the test only gives likely primes. But if the test is run with enough "witness" numbers, it gives a very good probability of indicating primality. It's not a bad idea to double check the result if you have another way to do that.

It's surprising to me that it required such a large number to finally find a prime. n = 136.

Then may I accept are there no any method to solve it manually ?

Amit Kumar - 3 years, 12 months ago

NO, you can't solve it manually. Or more precisely: it's too tedious to solve it by hand.

Pi Han Goh - 3 years, 12 months ago

Well, we can cut the problem down a little. If we write $x_n \; = \; 12\underbrace{11 \ldots 1}_{\times n}$ then $11$ divides $x_n$ whenever $n$ is odd, and $3$ divides $x_n$ whenever $3$ divides $n$ , so we can restrict our search to even $n$ which are not multiples of $3$ . That has cut out two-thirds of the numbers to test.

Mark Hennings - 3 years, 11 months ago

@Mark Hennings – Add to this the fact that $7$ divides $x_n$ when $n \equiv 2 \pmod{6}$ , and we only need to search for primes in integers $x_n$ where $n \equiv 4 \pmod{6}$ . That means you only have to test $23$ numbers until you find the prime number $x_{136}$ .

At this point, short cuts run out, since some of the prime factorisations of these $x_n$ only involve seriously large prime numbers. For example: $x_{34} \; = \; 10149217781 \times 102964488541 \times 115894799982791$

Mark Hennings - 3 years, 11 months ago

@Mark Hennings – Oh that's nice! I don't know why I didn't thought of this...

Pi Han Goh - 3 years, 11 months ago

Please anyone post the solution manually notwithstanding long and tedious.

Amit Kumar - 3 years, 11 months ago

This is meant to be "Computer Science" problem, so I seriously doubt that there's a "notwithstanding long and tedious" solution.

Pi Han Goh - 3 years, 11 months ago

For Matlab, this made it much easier! https://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic Thank you John D'Errico!

James Wilson - 3 years, 4 months ago

By the way, I also found this problem to be very interesting!

James Wilson - 3 years, 4 months ago

Since the number $X_n$ is a multiple of $3$ when $n \equiv 2 \pmod{3}$ , and a multiple of $11$ if $n$ is odd, we can cut down our hunt to number of the form $6m$ and $6m+4$ straight away...

Mark Hennings - 3 years, 4 months ago

Rishabh Deep Singh
Jul 4, 2017

Here is My Java Code

import java.math.BigInteger;

public class Main {

    public static void main(String[] args) {
        BigInteger no = new BigInteger("12");
        BigInteger n = BigInteger.ZERO;
        while(true){
            if (no.isProbablePrime(1)){
                break;
            }else {
                no = no.multiply(BigInteger.TEN);
                no = no.add(BigInteger.ONE);
                n=n.add(BigInteger.ONE);
            }
        }
        System.out.println(n);
        System.out.println(no);
    }
}

I used BigInteger to calculate the value of n.

Testing primality for large numbers

The answer is 136.

2 solutions

0 pending reports