20130525, 21:55  #1 
"Fernando Villanueva"
May 2013
Madrid /Spain
5 Posts 
Odd Fibonacci pseudoprimes
Hi, I'm new here (From Madrid, Spain)
I've registered to look for an answer to this question (If you are so kind): Some years ago I found a Prime test (Conjecture) related to Fibonacci sequence based in three rules. I checked the test up to natural 1.066.393 (83.282 prime numbers). Results were as follows: First rule: 167 seudoprimes First and second rule: 83 seudoprimes First, second and third rules: 44 seudoprimes. These: 4181 5777 10877 13201 15251 51841 64079 64681 67861 68251 75077 90061 96049 97921 100127 113573 118441 146611 161027 162133 197209 219781 231703 254321 272611 302101 330929 430127 433621 438751 520801 530611 556421 635627 638189 722261 741751 851927 853469 925681 999941 1024651 1033997 1034881 And the question is: Honestly, I do not Know how relevant can be a prime number test with 44 seudoprimes in 83.282 primes ¿What do you think? Thanks, 
20130525, 22:23  #2  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10011101001001_{2} Posts 
Quote:
Secondly, there are many tests that have no false positives (your "pseudoprimes"*, i.e. the numbers that pass your test and are not prime) up to much higher limits. Does your method have false negatives (misses 2 true primes) or was is a typo? Third, if this triple test is very fast (you didn't give any details what it was), then it could be a useful pretest (before doing a more expensive test). There are already many fast pretests, though. For practical purposes, this problem is solved many times over. It is very hard to find anything new for it, but who knows  maybe you found something new. Describe it. _______________ *strictly speaking, this word is reserved for a well defined category. But lets talk loosely. 

20130525, 23:01  #3 
"Fernando Villanueva"
May 2013
Madrid /Spain
5_{16} Posts 
I did not count numbers 1 and 2, that's all; 83284 with them, Ok.
As far as I've checked (Up to 1.066.393), from the first rule there are not false negatives. I'm afraid my triple test is not very fast but in any case, I have no idea of what can be considered fast testing primes. I will describe the two first rules now. My short english and spanish time, (01h00) don't allow me going to the third one now. If it is worth I'll Try to do that tomorrow. Here I go: Lets define a function to be applied on numbers ending 1,3,7 or 9. I will call it SH() (From shift) SH (N) = N1 (N, Natural number N ending on 1 or 9) SH (N) = N+1 (N, Natural number N ending on 3 or 7) And Lets Call F(N) to the N term of Fibonacci sequence FIRST RULE: IF F(SH(N)) MOD N = 0 then N is prime or pseudo as to 1st rule (167 pseudos) SECOND RULE Lets call S to the set of all numbers which satisfy FIRST RULE. If N belongs to S and F(N) belongs to S too, N is prime as to 1st and 2nd rules (83 pseudos) In order to test FIRST RULE you must consider that when you divide the Fibonacci sequence for a number N, the remainders sequence satisfy the same fibonacci rule F(N+1)=F(N)+F(N1) And in order to test second rule you need a nice trick a bit complicated to write now, I'll do if it is worth while. Thanks, Last fiddled with by efeuvete on 20130525 at 23:28 Reason: Fibonacci rule 
20130525, 23:05  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2749_{16} Posts 
Quote:
You are probably skipping 2 and 5 based on your description. If so, then ok. Your method seems to play with the properties of the Pisano periods. For some primes (see details on that Wiki page), the period will divide p1, and consequently you will have F(p1)=F(0)=0 (mod p), and for others, you will have F(p+1)=F(0)=0 (mod p). So, indeed, for the first rule, there shouldn't be false negative results other than 2 and 5. Your pseudo's are probably numbers with low Pisano periods (including some Lucas numbers?), but I haven't looked in detail. Last fiddled with by Batalov on 20130525 at 23:48 

20130525, 23:20  #5 
"Fernando Villanueva"
May 2013
Madrid /Spain
5 Posts 
from number 2 included, and if I'm not wrong, there are 83283 prime numbers up to 1.066.393 (Last one 1.066.379 as you said) please, if you don't mind, check this.

20130525, 23:25  #6 
"Fernando Villanueva"
May 2013
Madrid /Spain
5 Posts 
Yes, 5 is not included, so, evrything is clear.

20130526, 00:14  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
89·113 Posts 
The pseudo's have some properties:
in the 3,7 class, the smallest ones are 323, 377, 3827, 5777... in the 1,9 class, the smallest ones are 1891, 4181, 6601, 6721, 8149... Combined they are actually OEIS http://oeis.org/A081264 (Now, having found this sequence, the bottom of the message which I typed earlier is totally redundant, instead  have a look at comments in that article.) _____________________ Take for example 323 (=17*19); the Pisano period for 17 divides 18, and for 19 divides 18, and the combined period would be pi(mn) = lcm(pi(m),pi(n)), i.e. 18 (or divides 18); so F(323+1)=F(18*k)=0 (mod 17 or mod 19, i.e. also mod 323). This makes it work for 323. I didn't aim for strictness with this example, but if you take apart a few more examples, you will see what is going on. 
20130526, 11:24  #8 
"Fernando Villanueva"
May 2013
Madrid /Spain
5 Posts 
Yes, those pseudos "Of mine" start from A081264 integer sequence (Which I did'nt know then, in 1997). But in my quest of "Taking those pseudos out" I found a different period (In "Pisano's Style"), which I use on my third rule.
I go now on how to test second rule. It is as follows: SECOND RULE: When N and F(N) satisfy first rule. So: F( SH( F(N))) MOD F(N) = 0. But, according to Fibonacci sequence rule: "If F(X) MOD F(Y) = 0, then X MOD Y = 0", we have: SH( F(N)) MOD N = 0 wich is as easy to check as first rule. And that rule took out 50% of the pseudos. So, when I found this, I thought... ¿And what would happen with pseudos if F(F(N)) satisfy first rule too? I would bet a beer this rule would take out another 50% of pseudos, but my modest math knowledge did'nt allow me here to find an easy way to check it. Anyhow, is easy to check that numbers 3 and 7 satisfy it (To test 11 you need more than 16 digits) This would be wonderful, because if it would be true (And you can find how to check it) then you can go stairs up with F(F(FN))) and so on "Killing" pseudos as a "Prime warrior" Another curious thing to mention is that, in any case, "My" pseudos decrease very fast with N, I mean: From 1 to 200.000 there are 21 pseudos, in the next 200,000 N there are only 6 more... and from 800.000 to 1.000.000 only 4 more. I would like to know how many pseudos are from 1.000.000 to 2.000.000; some day I will check that. Well, if someone in the forum wants to continue this game, I will continue too (But it would take me some time to translate my third rule) Thanks and regards, Fernando. Last fiddled with by efeuvete on 20130526 at 11:55 Reason: My short english 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pseudoprimes in special fields  devarajkandadai  Number Theory Discussion Group  7  20171206 01:46 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  sweety439  17  20170613 03:49 
On generating Strong PseudoPrimes DataBase?  TheoryQuest1  Factoring  10  20160919 16:08 
Pseudoprimes  CRGreathouse  Computer Science & Computational Number Theory  36  20131121 07:47 
Fibonacci modulo Fibonacci  robert44444uk  Math  3  20070519 07:15 