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

106 Views Asked by At

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$.

1

There are 1 best solutions below

2
On

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 $$