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$
33
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Can you elaborate a little further? $\endgroup$ – zz20s Mar 23 '16 at 13:05
  • 4
    $\begingroup$ $1001117+53=1001170$, so if $100117$ is a multiple of $53$, $1001117$ must be too. $\endgroup$ – Empy2 Mar 23 '16 at 13:06
  • 4
    $\begingroup$ Just to clarify: $a_{n+1}=10(a_n-7+1)+7=10a_n-53$. $\endgroup$ – lhf Mar 23 '16 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$
  • $\begingroup$ Can you explain the last line? $\endgroup$ – zz20s Mar 23 '16 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 '16 at 14:11
  • $\begingroup$ @zz20s, to clear the denominators. $\endgroup$ – lhf Mar 23 '16 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 '16 at 14:22
  • $\begingroup$ Bottom line: $1001\cdots 17= 53 \cdot 18\cdots 89$. $\endgroup$ – lhf Mar 23 '16 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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