Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
If there is one, it can only end in $1$ or $7$. –  Lucian May 10 at 4:08
    
Can you please explain how you got to that conclusion? –  ASKASK May 10 at 4:11
1  
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 at 4:17
    
Sorry I'm not exactly a whiz at this, why couldn't it end in a 5? –  ASKASK May 10 at 4:18
    
Because it would be a multiple of $5$. –  Lucian May 10 at 4:20

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
    
Mathematica's PrimeQ verifies this is indeed a prime. –  Batman May 10 at 4:09
    
According to WolframAlpha, that is not a prime number –  ASKASK May 10 at 4:10
    
cl.ly/image/2p240S0L110o –  ASKASK May 10 at 4:11
    
ASKASK - that isn't the same number qwr put in his answer. –  Batman May 10 at 4:12
    
@ASKASK your input obviously got cut off, it ends in 0. –  qwr May 10 at 4:12

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

share|improve this answer
2  
what is PARI/gp and how did you get those numbers? –  ASKASK May 10 at 4:34
1  
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 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 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 at 17:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.