# On the Infinitude of Prime Divisors of a Recursively Defined Integer Sequence

Given a sequence of positive integers $$(m_k)_{k \geq 2}$$ and a sequence $$(a_k)_{k \in \mathbb{N}}$$ defined as $$a_{k+1} = a_k(1+m_{k+1}+a_km_{k+1}) \hspace{4mm} k \in \mathbb{N} \cdots (*)$$

such that the set $$\{ p: \exists k \in \mathbb{N} s.t. p|a_k \}$$ is finite, is it possible for the set of primes $$\{ p: \exists k \in \mathbb{N} s.t. p|(1+a_k) \}$$ to be finite?

Reformulation:

Does there exist a sequence $$(a_k)_{k \in \mathbb{N}}$$ such that $$a_k|a_{k+1}$$, $$(a_k+1)|(a_{k+1}+1)$$ for all $$k \in \mathbb{N}$$ and the set of primes dividing some term of the sequence $$(a_k)_{k \in \mathbb{N}}$$ or some term of the sequence $$(1+a_k)_{k \in \mathbb{N}}$$ is finite?

Description: I was thinking about sequences such that every term divides the next, and when each term is increased by one the new sequence also satisfies this property. There are of course infinitely many such possible sequences (namely, consider any prime $$p$$, and an odd positive integer $$n$$, and define the sequence $$a_k:=p^{n^k}$$, but by some order arguments I could observe that in this case, the sequence $$(a_k+1)_{k \geq \mathbb{N}}$$ has arbitrarily large prime divisors). So I tried characterizing such sequences and a straightforward divisiblity argument shows that such sequences are those precisely defined by the recursion $$(*)$$. However the computations arising in an attempt to prove the general statement above by contradiction are becoming too messy, and also I considered many other such sequences but there seems to be no counterexample either. A solution or hint would be really appreciated.

You can nuke this question with Kobayashi's theorem, which states that

If $$S$$ is an infinite set of positive integers so that only finitely many primes divide elements of $$S$$, then for any positive integer $$a$$, $$\{s+a|s\in S\}$$ is not.

As long as the sequence $$\{a_k\}$$ is not eventually constant, then the set of values of $$a_k$$ is infinite, and thus Kobayashi's theorem applies to show that either $$\{a_k\}$$ or $$\{1+a_k\}$$ has infinitely many prime divisors. As you noted, the fact that $$a_k=p^{n^k}$$ for some odd $$n$$ satisfies

$$(a_k+m)|(a_{k+1}+m)$$

for each $$m\in\{-1,0,1\}$$ means that it is possible for either one of the above sequences to have only finitely many prime divisors.

• I'm not sure why you are ascribing to a paper from '80s a trivial case of the S-unit equation proved 50+ years before then. May 19, 2019 at 3:50
• @user670344 The result is usually referred to as Kobayashi's theorem in contest math, at least, and this was the first reference I could find to it. May 19, 2019 at 5:02
• Strange, and a collective -1 to contest math. If the sequence is only divisible by primes in $S$ (assume primes dividing $m$ lie in $S$ too) then you immediately get infinitely many solutions to $u+v=1$ in $\mathbf{Z}[1/S]$. In this particular case, you can even deduce it immediately from Thue's Theorem (1909) as well. I recommend perusing kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1710-09.pdf. May 19, 2019 at 12:19
• Thanks for the answers, Carl and user670344. May 23, 2019 at 7:07