Prove there are no prime numbers in the sequence $a_n=10017,100117,1001117,10011117, \dots$

Define a sequence as $a_n=10017,100117,1001117,10011117$. (The $nth$ term has $n$ ones after the two zeroes.)

I conjecture that there are no prime numbers in the sequence. I used wolfram to find the first few factorisations:

$10017=3^3 \cdot 7 \cdot 53$

$100117=53\cdot 1889$

$1001117=13 \cdot 53\cdot1453$ and so on.

I've noticed the early terms all have a factor of $53$, so the problem can be restated as showing that all numbers of this form have a factor of $53$. However, I wouldn't know how to prove a statement like this. Nor am I sure that all of the terms do have a factor of $53$.

I began by writing the $nth$ term of the sequence as

$a_n=10^{n+3}+10^n+10^{n-1}+10^{n-2}+10^{n-3}+\cdots+10^3+10^2+10^1+7$ but cannot continue the proof.

It is as simple as $$a_{n+1}=10a_n-53$$

• Can you elaborate a little further? – zz20s Mar 23 '16 at 13:05
• $1001117+53=1001170$, so if $100117$ is a multiple of $53$, $1001117$ must be too. – Empy2 Mar 23 '16 at 13:06
• Just to clarify: $a_{n+1}=10(a_n-7+1)+7=10a_n-53$. – lhf Mar 23 '16 at 13:55

Use induction in order to complete the (excellent) hint by @Michael.

First, show that this is true for $n=1$:

$a_1=53\cdot189$

Second, assume that this is true for $n$:

$a_n=53k$

Third, prove that this is true for $n+1$:

$a_{n+1}=$

$10\cdot\color\red{a_n}-53=$

$10\cdot\color\red{53k}-53=$

$530k-53=$

$53(10k-1)$

Please note that the assumption is used only in the part marked red.

The sequence is given by $$a_n = 10^{n+3}+10\cdot \frac{10^n-1}{9}+7$$ Then $$9a_n = 9\cdot10^{n+3}+10\cdot (10^n-1)+63 = 9010\cdot 10^n+53 = 53\cdot(170 \cdot 10^n+1)$$ Therefore, $53$ divides $9a_n$. Since $53$ does not divide $9$, we have that $53$ divides $a_n$, by Euclid's lemma. (We don't even need to use that $53$ is prime, just that $9$ and $53$ are coprime.)

• Can you explain the last line? – zz20s Mar 23 '16 at 13:55
• Thank you! Your answer makes a lot of sense. Can you explain why you decided to multiply by $9$? – zz20s Mar 23 '16 at 14:11
• @zz20s, to clear the denominators. – lhf Mar 23 '16 at 14:21
• When you have a number whose base-10 representation has long strings of repeated digits, multiplying by 9 tends to make them turn into long strings of 0s (or sometimes 9s for the obvious reason). Here are two ways to see why. (1) 1111111=9999999/9 = (10000000-1)/9, etc. (2) 9 = 10-1, so multiplying by 9 means shifting one place left and subtracting the original number, which makes those long strings of digits cancel out. – Gareth McCaughan Mar 23 '16 at 14:22
• Bottom line: $1001\cdots 17= 53 \cdot 18\cdots 89$. – lhf Mar 23 '16 at 22:34

Another way to find the inductive relationship already cited, from a character manipulation point of view:

Consider any number in the sequence, $a_n$. To create the next number, you must:

1. Subtract $17$, leaving a number terminating in two zeroes;
2. Divide by $10$, dropping one of the terminal zeroes;
3. Add $1$, changing the remaining terminal zero to a $1$;
4. Multiply by $100$, sticking a terminal double zero back on;
5. Add $17$, converting the terminal double zero back to $17$

Expressing this procedure algebraically, and simplifying: $$a_{n+1}=\left (\frac{a_n-17}{10}+1 \right ) \times 100+17=10a_n-53$$