1
$\begingroup$

Let's define sequence $S_i$ as :

$ S_i= S^4_{i-1}-4\cdot S^2_{i-1}+2 ~\text{with}~ S_0=8$

I have found that :

$F_2 \mid S_1 , ~F_3 \mid S_3 ,~F_4 \mid S_7 $

where $F_2 , F_3 , F_4 $ are Fermat numbers .

Conjecture :

$ F_n = 2^{2^n}+1 ,(n \geq 2) ~\text{is a prime iff}~F_n \mid S_{2^{n-1}-1}$

In this document you can find my proof of this conjecture .

Question :

Is my proof acceptable ? Are there similar criteria in the literature ?

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
5
$\begingroup$

There are already similar results in the literature giving necessary and sufficient conditions for primality of Fermat numbers. For example, using the sequence $(R_n)_{n \geq 0}$ defined by $R_0=8$ and $R_{n+1}=R_n^2-2$, Inkeri has proved that $F_n$ ($n \geq 2$) is prime if and only if $F_n$ divides $R_{2^n-2}$.

The reference is Inkeri, Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I 279 (1960), 1-19.

See also Krizek, Luca, Somer, 17 Lectures on Fermat Numbers, CMS Books, Springer, 2001.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I didn't know that such test exists . As you can see my test uses lesser number of iterations . $\endgroup$
    – pedja
    Commented Mar 23, 2012 at 11:58
  • $\begingroup$ I don't know how you count iterations. Looking at the indices suggests to me that you use more iterations than the test of Inkeri does. Gerhard "Ask Me About System Design" Paseman, 2012.03.23 $\endgroup$
    – Gerhard Paseman
    Commented Mar 23, 2012 at 17:21
  • $\begingroup$ I apologize. I switched indices in my head as I was writing the remark. I support your assertion (based only on the post, however) that your test uses fewer indices. Gerhard "Needs To Drink More Coffee" Paseman, 2012.03.23 $\endgroup$
    – Gerhard Paseman
    Commented Mar 23, 2012 at 17:24
  • 6
    $\begingroup$ The tests are the same, one step of pedja’s recurrence amounts to doing two steps of Inkeri’s recurrence. Obviously, you can cut down the number of iterations $k$ times by doing $k$ original steps in one iteration, but that’s not going to reduce the number of arithmetic operations used. $\endgroup$
    – Emil Jeřábek
    Commented Mar 23, 2012 at 18:18
  • $\begingroup$ @EmilJerabek On my computer Java implementation of this test is approximately $1.5$ time faster than Java implementation of Inkeri's test... $\endgroup$
    – pedja
    Commented Apr 6, 2012 at 4:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .