4
$\begingroup$

Given is the following sequence: $a_1 = 1$ and $a_n$ equals the biggest prime divisor of $1+ a_1*\dots*a_{n-1}$ . It is then claimed: $11$ does not occur in this sequence.

How can one approach this problem? I first thought about trying a proof by contradiction. Let's then be $a_m$ the first occurrence of $11$ in this sequence. Then there exist $a,b,c,d, e \in \mathbb{N_0}$ such that: $2^a * 3^b * 5^c * 7^d * 11^e = 1+ a_1*\dots*a_{m-1}$ .

From there however, it looks me like a dead end. It seems like I am missing a key observation. I would be happy, if anyone with more knowledge could offer an advice/suggestion how to begin here.

EDIT: Related: Euclid Mullin Sequence

$\endgroup$
  • $\begingroup$ I am not a number theory specialist, but this does not look “elementary” to me. There are some references in oeis.org/A000946, oeis.org/A216227, and Euclid–Mullin sequence. – Where did you encounter the problem? $\endgroup$ – Martin R Nov 25 '18 at 21:43
  • $\begingroup$ It's from a previous exam preparing for the IMO - so it should be solvable within maybe 1 hour and not require university level mathematics. I tried finding more values of the sequence with a python script, but the values become too big way for the program to handle. $\endgroup$ – Imago Nov 25 '18 at 21:46
  • 1
    $\begingroup$ Note: it's easy to see that no prime can appear twice in the sequence. As to $11$, and the other missing primes, the wiki article gives a reference for the claim $\endgroup$ – lulu Nov 25 '18 at 21:46
  • $\begingroup$ @lulu, if this is true, this says indeed a lot and probably just nails the problem. I will look into that. EDIT: Ok the wiki article spoilers quite a lot. $\endgroup$ – Imago Nov 25 '18 at 21:50
  • 2
    $\begingroup$ Cox and van der Poorten had a short paper in 1967 that solves this in a fairly elementary way. doi.org/10.1017/S1446788700006236 $\endgroup$ – B. Goddard Nov 25 '18 at 21:59
0
$\begingroup$

Note: Personally, I find my solution too short and "too easy" to be a solution to this problem. Therefore, feel free to make a note or comment, when there is an error.

I would "solve" this specific problem stated above like this:

The first elements of the sequence can be computed fairly quickly: $a_1 = 1, a_2 = 2, a_3 = 7, a_4 = 43, a_5 = 139$

Now following lulu's advice, we show that a prime number occurs at most twice in this sequence.

Given that $a_n = 1+a_1 * \dots * a_{n-1}$ it follows that $a_n \equiv 1\pmod {a_i} $ for $1 \le i \le n-1$, thus there is no $a_i$ with $a_i| a_n$ $\Rightarrow a_i \neq a_n \ \forall i$ with: $ \ 1\le i \le n-1$

Now: Let $a_n = 11$ and $b_n = 1+ a_1* \dots \ * a_{n-1}$ then by definition $11|b_n$ and if $k|b_n$ and $k \neq 11$, then $k = 1 \lor k= 5$, in particular: $2,3,7 \nmid b_n$ $\Rightarrow b_n \le 55$, but: $\frac{b_n}{55} \ge \frac{a_1 * \dots * a_5 +1}{55} \gt 1 \Rightarrow$ $b_n$ has at least one prime factor greater than $11$, thus: $11$ can't occur in this sequence.

EDIT: Proving that does not occur in the sequence can be doen quickly: If 5 occurred, then we had for some $b_n = 2^a * 3^b * 5^c = 1+2* \dots * a_{n-1} $.

$a,b$ must be equal to $0$. If they weren't, then $2^a * 3^b * 5^c \equiv 0 \pmod {2,3} $, but $b_n \equiv 1 \pmod {2,3} $

Thus $b_n$ would be of the form: $b_n = 5^c$ for some $c$ however: $5^c - 1 \equiv 0 \pmod 4 \forall \ c \in \mathbb{N}$ and $a_1* \dots \ * a_{n-1} \equiv 2 \pmod 4 $

Thus $5$ cannot occur in the sequence.

However there is still some way to go to prove $11$ does not occur and I actually don't see how one would do that. The same argument/trick, used for $5$, doesn't seem work.

EDIT2 : $5^a * 11 ^b \equiv 3 \pmod 4$ as $2 | a_1 * \dots* a_{n-1} $ $\Rightarrow 1^a * 3^b \equiv 3 \pmod 4 \Rightarrow b$ is odd.

$3 | 5^a * 11^b -1 \Rightarrow (-1)^a *(-11)^b \equiv (-1)^{a+b} -1 \equiv 0 \pmod 3 \Rightarrow a+b $ even$ \Rightarrow a$ is also odd.

Then: $7 | 5^a * 11^b -1 \Rightarrow (-2)^a * 4^b \equiv (-2)^{a+2*b} \equiv 1 \pmod 7 $

This however is only the case: if $a+2*b$ is a multiple of $6$ (Little Fermat), which can't be the case. Hence: $11$ cannot occur in the series and we are done. Quite a journey over the past few days, but I believe the proof is now complete.

$\endgroup$
  • 1
    $\begingroup$ $b_n$ might be $5^y11^z$ for integers $y,z$ $\endgroup$ – Empy2 Nov 26 '18 at 14:27
  • $\begingroup$ Valid point. I need more time to think about it. $\endgroup$ – Imago Nov 26 '18 at 14:40

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.