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 ?

$\endgroup$
3

1 Answer 1

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.

$\endgroup$
5
  • $\begingroup$ I didn't know that such test exists . As you can see my test uses lesser number of iterations . $\endgroup$
    – pedja
    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$ 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$ 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$ 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
    Apr 6, 2012 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.