15
$\begingroup$

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.

$\endgroup$

4 Answers 4

Reset to default
34
$\begingroup$

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

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

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.

$\endgroup$
6
$\begingroup$

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.)

$\endgroup$
5
  • $\begingroup$ Can you explain the last line? $\endgroup$
    – zz20s
    Mar 23, 2016 at 13:55
  • $\begingroup$ Thank you! Your answer makes a lot of sense. Can you explain why you decided to multiply by $9$? $\endgroup$
    – zz20s
    Mar 23, 2016 at 14:11
  • $\begingroup$ @zz20s, to clear the denominators. $\endgroup$
    – lhf
    Mar 23, 2016 at 14:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gareth McCaughan
    Mar 23, 2016 at 14:22
  • $\begingroup$ Bottom line: $1001\cdots 17= 53 \cdot 18\cdots 89$. $\endgroup$
    – lhf
    Mar 23, 2016 at 22:34
2
$\begingroup$

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$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .