17

If you consider the (decimal) numbers 10, 101, 1010, 10101... where the 1 and 0 alternate, what is the largest prime number in the sequence?

Thanks in advance for your help, I appreciate it.

Three OneFour
  • 391
  • It has to end in 1, and it has to have a prime number of ones (because if it had $pq$ ones, it would be divisible by its substring of the first $2p+1$ digits). – Deusovi Mar 09 '17 at 06:34
  • What do you mean by the substring of the first 2p +1 digits? – Three OneFour Mar 09 '17 at 06:39
  • Whoops, should be $2p-1$. I mean the number "101010...1", with $p$ ones (and therefore $2p-1$ digits) – Deusovi Mar 09 '17 at 06:40

2 Answers2

23

Clearly the number cannot end in $0$, so we consider integers of the form $$k_n=1010101\cdots 01,$$ where $k_n$ is of length $2n-1$. Note that every such integer is of the form $$k_n = \frac{10^{2n}-1}{99} = \frac{(10^{n}-1)(10^n + 1)}{99}.$$ If $n=1$, then $k_1=1$. If $n=2$, then $k_2 = 101$, which is prime. If $n>2$ and $n$ is even, then $$k_n = k_{n/2}(10^n+1),$$ so that $k_n$ is composite. Finally, if $n>2$ is odd, then $11\mid (10^n+1)$ and $9\mid (10^n - 1)$ so that again $k_n$ is composite. It follows that in this sequence, only $k_2 = 101$ is prime.

EuYu
  • 41,421
  • I don't understand sorry. Why can the number be represented by 10^2n-1 / 99 ? – Three OneFour Mar 09 '17 at 06:53
  • 1
    Write $k_n$ as $10^{2n-2} + 10^{2n-4} + 10^{2n-6} + \cdots + 1$. This is a geometric sum in $10^2$. – EuYu Mar 09 '17 at 06:56
  • 1
    @ThreeOneFour The simpliest way is to see what happens if you multiply $k_n$ by $99$, do it using paper-and-pen algorithm and you'll see what happens (you'll get a number of only nines). – skyking Mar 09 '17 at 07:04
  • Note that this argument should work in any base. If $n>3$ the factors in the nominator will have a quotient larger than $1$ when divided by the factors of the denominator (since they are larger) and you will be left with two factors. The only difference in outcome is whether $k_2$ is prime or not. For example in the base $3$ we have $k_2 = (101)_3 = 10$ which is composite (so there is no primes in the sequence then). – skyking Mar 09 '17 at 07:13
  • 3
    Not sure what you make of $101010101$ - what do you say that is divisible by? – Mark Bennet Mar 09 '17 at 08:07
  • 1
    Well $k_5 = 101010101 = \frac{10000199999}{911} = 9091*11111$ is definitely not prime. – Urukann Mar 09 '17 at 09:38
  • To fix this answer: $k_ {2 n - 1}$ is divisible by a string of $(2n-1)$ $1's$. k_{2n} is even for @EuYu's reason. – robertkin Mar 09 '17 at 10:27
  • @Urukann So to get the structure of this proof in my head, I do $101010101\times 99=9999999999=10^{10}-1=(10^5+1)\cdot(10^5-1)$. The first of these factors is divisible by $11$ and the second by $9$, and that gives a non-trivial factorisation of my original number. – Mark Bennet Mar 09 '17 at 12:03
4

The only prime in this sequence is $101$.

As @EuYu pointed out, for even n, $k_{2n} = k_{n}(10^{2n}+1)$ is even. This equality can be easily shown by considering multiplication by $10^n$ as appending $n$ zeros to the end of the number in base 10, and noting that $k_{2n}$ has $2n$ digits.

$k_{2 n + 1}$ is divisible by a string of $(2n+1)$ $1$'s. Explicitly, $$\left(\sum_{i=0}^{2n+1} 10^i \right)*\left(1+ \sum_{i=0}^{n} 10^{2 i}*90\right ) = k_{2 n + 1}$$

Algebraically you can bash this out (or throw at Wolfram), but there's a good pen-n-paper way to see this.
Look at $909091*1111111$.
$90*1111111=99999990$.
Adding $1111111$ to this will "overflow" the number to $101111101$, which is of the form $10[1...1]01$
Now add that to $9999999000=9000*1111111$.
Look at the digit-wise sums from right to left: last 3 unchanged because $10^3 | 9000$, then 10s until the first 0 in $101111101$.
Considering the carried "1" at each step, the sum is $1010[1...1]0101$.

Proceed inductively, result = $1010101010101$.

robertkin
  • 223
  • 1
    I think you misunderstood the argument: because 9 | (10^n - 1) and 11 | (10^n + 1), k_n is composite. Can 198 be written as a product of such terms ?

    For your second argument, I'm not sure why 909 would not be divisible by 9...

     – Urukann Mar 09 '17 at 09:17
  • His argument is that as $9 | a$, and $11 | b$, $\frac {a*b} {99}$ is composite. – robertkin Mar 09 '17 at 09:24
  • BTW, I checked and $k_5$ = 101010101 = (100001/11)(99999/9) = 9091 1010 is definitely not prime.

    e/ Sorry hadn't seen your answer... If $9|a$ and $11|b$ then $c = a/9$ and $d = b/11$ are integers, thus $\frac{ab}{9*11} = cd$ is composite...

     – Urukann Mar 09 '17 at 09:25
  • You are right actually, my bad... – Urukann Mar 09 '17 at 09:29
  • 2
    What EuYu says is this: if $(10^n+1)=11a$ and $(10^n-1)=9b$ (with $a,b>0$), then $k_n=\tfrac{11a\cdot 9b}{99} = ab$ is composite. No one claimed that $k_n$ is divisible by 9 or 11. – Ben Mar 09 '17 at 09:46
  • 2
    @robertkin I think you misunderstood what I meant. Ben's understanding is entirely correct. $9\mid (10^n - 1)$, and the quotient is clearly greater than $1$ for $n>1$. Likewise, $11\mid (10^n + 1)$, and again the quotient is greater than $1$ for $n>1$. Thus $k_n$ is composite, being the product of the integers $(10^n-1)/9$ and $(10^n+1)/11$. I never claimed that $9\mid k_n$ or that $11\mid k_n$. – EuYu Mar 09 '17 at 12:31
  • Ah yes. That was stupid. Well, now there's a constructive proof for a factor, too. – robertkin Mar 09 '17 at 15:13