Periodic sequences of integers generated by $a_{n+1}=\operatorname{rad}(a_{n})+\operatorname{rad}(a_{n-1})$

experimental-mathematicsnumber theoryprime factorizationprime numberssequences-and-series

Let's define the radical of the positive integer $n$ as
$$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\ p\text{ prime}}}p$$
and consider the following Fibonacci-like sequence
$$a_{n+1}=\operatorname{rad}(a_{n})+\operatorname{rad}(a_{n-1})$$
If $a_1=1,\,a_2=1$ the sequence coincides with OEIS A121369
$$1, 1, 2, 3, 5, 8, 7, 9, 10, 13, 23, 36, 29, 35, 64, 37, 39, 76, 77, …$$
If $a_1=2,\,a_2=2$ the sequence becomes
$$2, 2, 4, 4, 4, …$$
If $a_1=3,\,a_2=3$ the sequence becomes
$$3, 3, 6, 9, 9, 6, 9, …$$
If $a_1=5,\,a_2=5$ the sequence becomes
$$5, 5, 10, 15, 25, 20, 15, 25, …$$
If $a_1=7,\,a_2=7$ the sequence becomes
$$7, 7, 14, 21, 35, 56, 49, 21, 28, 35, 49, 42, 49, 49, 14, 21, …$$
The above sequences, except for the first, are all periodic. Continuing with the successive prime numbers, we obtain:

for $\,p=11,\,$ a sequence with a period length of $\,9$,

for $\,p=13,\,$ a sequence with a period length of $\,81$,

but for $\,p=17\,$ and $\,p=19\,$ two apparently divergent sequences.

Other primes that generate periodic sequences are (the respective period lengths in brackets):

$$23 (9), 29 (12), 31 (207), 37 (27), 41 (36), 47 (39), 73 (198), 79 (60)$$

Some questions arise from the previous experimental observations:

  • is the period length always a multiple of $3$ (not considering the case $p=2$)?

  • also in the doubtful cases mentioned above, does the sequence become periodic at some point?

  • given the starting prime number, is it possible to predict the length of the period of the generated sequence or, at least, to identify some pattern?

I have posted a more general question of the same nature here.

Edit

For the calculation of $\,\operatorname{rad}(n)\,$ I used the sympy.primefactors() method inside Python:

from sympy import primefactors

def rad(num):
    primes = primefactors(num)
    value = 1
    for p in primes:
        value *= p
    return value

(a0, a1) = (17, 17)
for n in range(2, 10001):
    a2 = rad(a1) + rad(a0)
    print(n, a2)
    a0 = a1
    a1 = a2

Best Answer

This is basically a comment of how hard the problem is by demonstrating that the sequence starting with $a_1=a_2=p$ with $a_{n+1}=\operatorname{rad}(a_n)+\operatorname{rad}(a_{n-1})$ is equivalent to taking the sequence from OEIS A121369 but modifying it so that $b_1=b_2=1$ and computing $\operatorname{rad}(b_n)+\operatorname{rad}(b_{n-1})$ as usual, but then removing the highest power of $p$ dividing that sum to get $b_{n+1}$.

In particular, if you think determining if sequence OEIS A121369 is periodic is difficult, then adding the complexity of dividing out the largest power of $p$ at every step of the iteration seems to make this even more eratic and difficult. If you don't agree with that heuristic you can stop reading now, but if you think that's acceptable, you can continue on to the proof of the claim that the sequences are equivalent.

If $p$ divides two consecutive terms, then they divide the third term. So that means $p$ divides all the terms of our sequence. We can then write our sequence as $a_n=p^{1+k_n}b_n$ with $b_n$ not divisible by $p$ and $k_n \ge 0$. $$a_{n+1}=\operatorname{rad}(a_n)+\operatorname{rad}(a_{n-1})$$ $$p^{1+k_{n+1}}b_{n+1}=\operatorname{rad}(p^{1+k_{n+1}}b_n)+\operatorname{rad}(p^{1+k_n}b_{n-1})$$ $$p^{k_{n+1}}b_{n+1}=p\operatorname{rad}(b_n)+p\operatorname{rad}(b_{n-1})$$ $$p^{k_{n+1}}b_{n+1}=\operatorname{rad}(b_n)+\operatorname{rad}(b_{n-1})$$

We can always reconstruct the $k_n$ immediately with the $p$-adic absolute value:

$$k_{n+1}= v_p(\operatorname{rad}(b_n)+\operatorname{rad}(b_{n-1}))$$

So we can introduce the notation that $[x]_p$ means $x$ with the largest power of $p$ divided out of it, in terms of the $p$-adic valuation, $x=p^{v_p(x)}[x]_p$.

$$b_{n+1}=[\operatorname{rad}(b_n)+\operatorname{rad}(b_{n-1})]_p$$

This sequence starts the same as OEIS A121369, the only difference is we are simply dividing out all the $p$ from it at each step of the iteration.

In order for the sequence $a_n$ to be periodic, since $a_n=p^{1+k_n}b_n$, $b_n$ must be periodic. It turns out this is not only necessary, but sufficient. To prove it's sufficient, let's suppose $b_n=b_{n+T}$.

$$k_n = v_p(\operatorname{rad}(b_{n-1})+\operatorname{rad}(b_{n-2})= v_p(\operatorname{rad}(b_{n-1+T})+\operatorname{rad}(b_{n-2+T})=k_{n+T}$$

That concludes the proof.

Related Question