6

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

ASKASK
  • 9,000
  • 4
  • 28
  • 49

2 Answers2

9

Edit: code fixed, uses gmpy2 now.

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

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901

is a prime based on gmpy2's probable prime Miller-Rabin test.

Code if you want to verify:

import gmpy2

digit = 1
number = 1234567890
while True:
    number = 10*number + digit
    if gmpy2.is_prime(number):
        print(number)
        break

    digit = (digit + 1)%10
qwr
  • 10,716
1

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

  • 2
    what is PARI/gp and how did you get those numbers? – ASKASK May 10 '14 at 04:34
  • 2
    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
  • 1
    According to http://oeis.org/A120819, there is at least one more such prime. – Alexis Olson Oct 04 '16 at 14:12