Smarandache-Fibonacci Primes

[rogue]

I started a search for Smarandache-Fibonacci primes. A Smarandache-Fibonacci number is a concatenation of Fibonacci numbers. Using the notation SmF, one can specify a specific number in that sequence. For example, SmF₆ = 11235813. So far only SmF₂ and SmF₄ are prime up to SmF₁₂₇₅. I am currently sieving (with pixsieve) up to SmF₇₅₀₀ which is over 2 million decimal digits in length. This form is sieving very nicely. I have a little over 100 terms left and am still sieving.

One little "feature by accident" with pixsieve is that you can use a pfgw DECIMAL as input even when starting a new sieve. Because of this feature I was able to create an input file that only tested terms of specific lengths which corresponded to the SmF lengths rather than all lengths between two values.

[R. Gerbicz]

You can sieve this form much faster what your general string sieve does:

SmF_{k+1}=SmF_{k}*10^e(k+1)+Fib(k+1) if Fib(k+1) has e(k+1) decimal digits.

Precompute the e sequence.
Use that e(k+1) is e(k) or e(k)+1, so for fixed p prime:
10^e(k+1) mod p is just r=10^e(k) mod p or 10*r mod p.
And obviously Fib(k+1)=Fib(k)+Fib(k-1), here you now already Fib(k) and Fib(k-1) mod p.
So you need only one mulmod and other faster operations per each term.

[science_man_88]

Originally Posted by R. Gerbicz

You can sieve this form much faster what your general string sieve does:

SmF_{k+1}=SmF_{k}*10^e(k+1)+Fib(k+1) if Fib(k+1) has e(k+1) decimal digits.

Precompute the e sequence.
Use that e(k+1) is e(k) or e(k)+1, so for fixed p prime:
10^e(k+1) mod p is just r=10^e(k) mod p or 10*r mod p.
And obviously Fib(k+1)=Fib(k)+Fib(k-1), here you now already Fib(k) and Fib(k-1) mod p.
So you need only one mulmod and other faster operations per each term.

the only reason I see to use the fibonacci sequences is within the terms that aren't even ( every third term is even for example) also for any prime r you still only have to test up to r^2-1 terms ( at most because of combinations of modular remainders that aren't 0,0 ) at last check to check if it's cyclical. technically you could use the fact that all powers of 10 are 4 mod 6 when you multiply and add for the next term to eliminate to all those that aren't 1 or 5 mod 6. anyways I'm repetitive at best at this point.

[rogue]

Originally Posted by R. Gerbicz

You can sieve this form much faster what your general string sieve does:

SmF_{k+1}=SmF_{k}*10^e(k+1)+Fib(k+1) if Fib(k+1) has e(k+1) decimal digits.

Precompute the e sequence.
Use that e(k+1) is e(k) or e(k)+1, so for fixed p prime:
10^e(k+1) mod p is just r=10^e(k) mod p or 10*r mod p.
And obviously Fib(k+1)=Fib(k)+Fib(k-1), here you now already Fib(k) and Fib(k-1) mod p.
So you need only one mulmod and other faster operations per each term.

Duh! I hadn't thought about that. It isn't worth the time to write new code to sieve in that method for my current range, but if someone wants to go beyond my search limits, that would certainly be helpful. I'll leave that for someone else to write.

[rogue]

Completed to SmF₇₅₀₀. Considering how long these tests are starting to take (over 2 days on a fast i7) and how few are left after sieving, it will take quite a bit of luck to find another one. If anyone wants to try, you should write a custom sieve as described above. You will likely have well close to 1% of the candidates left to test after sieving.

[R. Gerbicz]

Originally Posted by rogue

Completed to SmF₇₅₀₀. Considering how long these tests are starting to take (over 2 days on a fast i7) and how few are left after sieving, it will take quite a bit of luck to find another one. If anyone wants to try, you should write a custom sieve as described above. You will likely have well close to 1% of the candidates left to test after sieving.

Well, it is very probable that the sequence of the Smarandache-Fibonacci primes is finite, because SmF(n)=a(n) is roughly exp(c*n^2) for fixed c>0, so if a(n) is a random integer (or "close" to that) then with 1/(c*n^2) chance it will be prime. And here sum(n=1,inf,1/(c*n^2)) is a convergent serie.