# Does there exist a prime that is only consecutive digits starting from 1?

This is a problem I came up with the other day, and have absolutely no clue how to solve. The problem is: does there exist a number in the set $K$ that is prime, where $K$ is defined to be the set of all numbers that follow this pattern: $$1$$ $$123$$ $$12345$$ $$123456789$$ $$12345678901$$ $$1234567890123$$ $$...$$

I have left out numbers that end in even digits such as $1234$ because they are obviously not prime, although they are still members of the set.

In WolframAlpha I have checked up to $1234567890123456789012345678901234567890123456789$ but still found $0$ primes.

My intuition is telling me to believe that there is no such prime, but I am reluctant to believe that given that I have no formal proof.

For those of you who want specifics, the set $K$ is defined such that:

$$K_n = \sum_{i=1}^{n}{10^{n-i}D(n)}$$ given that $D(x)$ is the last decimal digit of $x$, or equivalently the remainder of $x/10$, and if you are still craving a mathematical formula, take this: $D(x)=x-10\lfloor{\frac{x}{10}}\rfloor$

UPDATE: SOLVED (by exhaustion):

Shortest one I could find:

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901

-
If there is one, it can only end in $1$ or $7$. – Lucian May 10 '14 at 4:08
Can you please explain how you got to that conclusion? – ASKASK May 10 '14 at 4:11
It can't end in $5$ or in an even digit. Nor in $3$ or $9$, since then the sum of its digits, and thus the entire number, would be a multiple of $3$. – Lucian May 10 '14 at 4:17
Sorry I'm not exactly a whiz at this, why couldn't it end in a 5? – ASKASK May 10 '14 at 4:18
Because it would be a multiple of $5$. – Lucian May 10 '14 at 4:20

## 2 Answers

The power of brute force: I wrote a quick python program, and

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567

is a prime based on the Miller-Rabin test and elliptic curve factorization.

Code if you want to verify:

import miller_rabin

digit = 1
number = 1234567890
while True:
number = int(str(number)+str(digit))
if str(number)[-1] not in (0, 2, 4, 5, 6, 8):
if miller_rabin.is_probable_prime(number):
print(number)
break

digit = (digit + 1)%10


ASKASK has shown a shorter solution that for some reason my miller-rabin test did not catch:

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901

-
Mathematica's PrimeQ verifies this is indeed a prime. – Batman May 10 '14 at 4:09
According to WolframAlpha, that is not a prime number – ASKASK May 10 '14 at 4:10
cl.ly/image/2p240S0L110o – ASKASK May 10 '14 at 4:11
ASKASK - that isn't the same number qwr put in his answer. – Batman May 10 '14 at 4:12
@Batman: Of course Mathematica's PrimeQ doesn't prove primality, it does a probable-prime test. you need ProvablePrimeQ to prove primality. – Charles May 10 '14 at 16:35

If PARI/gp is to be believed then K_n is prime for n=171,277,367,561 and 567.

-
what is PARI/gp and how did you get those numbers? – ASKASK May 10 '14 at 4:34
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free. The built-in function isprime(x) uses a combination of algorithms to prove x is prime (or not). – O. S. Dawg May 10 '14 at 15:49
My GP script for this problem (probably similar to yours): N=0;for(n=1,1e4,if(ispseudoprime(N=10*N+n%10),print1(n", "))) – Charles May 10 '14 at 16:38
Yes, I used a similar script. Each of the five numbers above is provably prime. If I were a betting man (which I am), I would wager these are the only n for which K_n is prime. – O. S. Dawg May 10 '14 at 17:23