Odd Fibonacci pseudoprimes

[efeuvete]

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,

[Batalov]

Originally Posted by efeuvete

I checked the test up to natural 1.066.393 (83.282 prime numbers)

This doesn't check out already. There are 83284 primes under 1066393 (83284th is 1066379, 83285th is 1066399).

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 pre-test (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.

[efeuvete]

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) = N-1 (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(N-1)

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,

[Batalov]

Originally Posted by efeuvete

I did not count numbers 1 and 2, that's all; 83284 with them, Ok.

1 is not a prime number, so your count is still one off.
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 p-1, and consequently you will have F(p-1)=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.

[efeuvete]

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.

[efeuvete]

Yes, 5 is not included, so, evrything is clear.

[Batalov]

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.

[efeuvete]

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.