# How to approach this sequence? (elementary number theory)

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

• 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? – Martin R Nov 25 '18 at 21:43
• 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. – Imago Nov 25 '18 at 21:46
• 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 – lulu Nov 25 '18 at 21:46
• @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. – Imago Nov 25 '18 at 21:50
• Cox and van der Poorten had a short paper in 1967 that solves this in a fairly elementary way. doi.org/10.1017/S1446788700006236 – B. Goddard Nov 25 '18 at 21:59

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.

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