# On a similar recurrence to the Lucas-Lehmer test: the variation involving the multiplicative function $\operatorname{rad}(n)$

I did a variation of the so-called Lucas–Lehmer primality test, I say this Wikipedia. I've used the radical $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\ p\text{ prime}}}p$$

of the integer $n> 1$, and taking $\operatorname{rad}(1)=1$ that is this definition from Wikipedia.

We define $$\left. \begin{array}{l} R_i=\operatorname{rad}(R_{i-1})R_{i-1}-2,\quad\text{for }i\geq 1\\ R_0=4 \end{array} \right\}\tag{1}$$

If there are no mistakes this sequence starts as $$4,6,34,1154,1331714,\ldots\tag{2}$$

Question 1. Please prove or refute some of these conjectures:

Conjecture-R1: One has that $R_k$ is a square-free integer $\forall k\geq 1$.

Conejcture-R2: $\forall k\geq 2$ one has that $$R_k=2\cdot\prod\text{distinct odd primes being the hypothenuses of primitive Pythagorean triples}$$ Many thanks.

Updated: The $\prod$ in Conjecture R-2 means a product.

As example for Conjecture R-2 is that Wolfram Alpha online calculator tell me that the corresponding odd primes of $R_5=1773462177794$ satisfy $257^2=32^2+255^2$, $1409^2=159^2+1400^2$ and $2448769$ also is the hypothenuse of a primitive Pythagorean triple since $2448769^2 = 28769^2 + 2448600^2$.

• One approach is to "self-delete" a question, edit it, and then self-un-delete it once the desired problem is framed. – hardmath Mar 12 '18 at 23:09
• I take note, the problem is that I started in a bad way by asking two things in the same post @hardmath – user243301 Mar 12 '18 at 23:11
• There seems to be something missing in your Conjecture-R2. While $R_k$ clearly depends on $k$, the way the right hand side depends on $k$ is not explicit. Perhaps you have in mind a product of odd primes each of which can be expressed as the sum of two squares. However this is not in itself a terribly unusual situation; by Fermat's Thm. on sums of two squares, the primes which can be so expressed are precisely the primes $p\equiv 1 \bmod 4$. – hardmath Mar 13 '18 at 14:02
• Many thanks @hardmath for your feedback and help about the conjecture R-2. I suspect that maybe this conjecture is easy to get. On the other hand I believe that the statement of this conjecture is right as was stated as two times the product of certain odd primes. – user243301 Mar 13 '18 at 14:19
• We can restate the recurrence using only odd numbers, taking $R_k = 2S_k$ which is defined by $S_1 = 3$ and for $k\gt 1$, $$S_k=2\operatorname{rad}(S_{k-1}) S_{k-1} - 1$$ – hardmath Mar 13 '18 at 15:10

If we drop the term $R_0 = 4$ from the sequence defined above, then it appears to agree with a modified Lucas sequence OEIS A003423 which Shallit (1975) describes as having been proposed by Lucas to test primality of Fermat numbers $2^{2^n} + 1$.

Indeed if the first conjecture holds, that $R_k$ is square-free for $k\ge 1$, then $\operatorname{rad}(R_k) = R_k$ and the agreement is necessitated:

$$\begin{cases} R_1 = 6 \\ R_k = R_{k-1}^2 - 2 \text{ when } k\gt 1\end{cases}$$

Conversely, if the modified Lucas sequence of OEIS A003423 has no terms with square prime divisors, then the sequence defined in the Question is also free of square prime divisors.

It appears to be an open problem whether all OEIS A003423 entries are square free. A closely related Question here asks whether the unmodified Lucas-Lehmer sequence has terms with square prime divisors. The only posted answer by David Speyer gives a heuristic argument for the expected number of square prime divisors to be finite (and "small").

The second conjecture (as already mentioned in Comments) amounts to a claim that the odd prime divisors of terms $R_k$ for $k\ge 2$ are always of the form $p\equiv 1 \bmod 4$ (as Fermat proved).

Assuming the first conjecture we can at least show for $k\ge 1$ that each $R_k = 2S_k$ for unique odd number $S_k$, and that for $k\ge 2$ one always has $S_k\equiv 1 \bmod 4$. This is consistent with (but does not prove that) all odd factors of $R_k$ (equiv. of $S_k$) are of the required form (because integers congruent to $1 \bmod 4$ are closed under multiplication).

Let $S_1 = 3$ and define recursively for $k\gt 1$:

$$S_k = 2\operatorname{rad}(S_{k-1}) S_k - 1$$

Then $R_k = 2S_k$ satisfies the "initial condition" $R_1 = 6$ and also for $k\gt 1$ the recurrence:

$$R_k = \operatorname{rad}(R_{k-1}) R_k - 2$$

since $S_k$ is odd and hence $\operatorname{rad}(2S_k)=2\operatorname{rad}(S_k)$. By induction $R_k$ and $2S_k$ must agree.

Now by assuming the first conjecture the recurrence simplifies to:

$$S_k = 2S_{k-1}^2 - 1$$

because $R_k$ square free implies $S_k$ square free. Then $S_2 = 17$ is congruent to $1 \bmod 4$, and hence by induction:

$$S_k \equiv 2(1^2) - 1 \equiv 1 \bmod 4$$

• Wow this is incredible, nor is my dreams more delirious I expected such a detailed answer to my question. Many thanks much tomorrow I am going to study all references and details. – user243301 Mar 13 '18 at 20:55
• I suspect more can be said, but I wanted to get a first round of observations out. – hardmath Mar 13 '18 at 21:00