Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
    
Skimming through it, I didn't see anything obviously wrong. –  zeb Mar 23 '12 at 10:28
    
I like the conjecture, but your question is not appropriate for Math Overflow. May I suggest that you change it to "I think I've proved that ..., are there similar criteria in the literature?" Otherwise, I suspect that this question will be closed. –  Kevin O'Bryant Mar 23 '12 at 17:38
    
add comment

1 Answer

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.

share|improve this answer
    
I didn't know that such test exists . As you can see my test uses lesser number of iterations . –  pedja Mar 23 '12 at 11:58
    
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 –  Gerhard Paseman Mar 23 '12 at 17:21
    
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 –  Gerhard Paseman Mar 23 '12 at 17:24
6  
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. –  Emil Jeřábek Mar 23 '12 at 18:18
    
@EmilJerabek On my computer Java implementation of this test is approximately $1.5$ time faster than Java implementation of Inkeri's test... –  pedja Apr 6 '12 at 4:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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