mersenneforum.org Smarandache-Fibonacci Primes
 Register FAQ Search Today's Posts Mark Forums Read

 2016-06-19, 15:25 #1 rogue     "Mark" Apr 2003 Between here and the 11100001011012 Posts Smarandache-Fibonacci Primes 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, SmF6 = 11235813. So far only SmF2 and SmF4 are prime up to SmF1275. I am currently sieving (with pixsieve) up to SmF7500 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.
 2016-06-19, 17:20 #2 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2·19·43 Posts You can sieve this form much faster what your general string sieve does: Code: 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.
2016-06-19, 18:23   #3
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

845010 Posts

Quote:
 Originally Posted by R. Gerbicz You can sieve this form much faster what your general string sieve does: Code: 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.

2016-06-20, 16:02   #4
rogue

"Mark"
Apr 2003
Between here and the

7,213 Posts

Quote:
 Originally Posted by R. Gerbicz You can sieve this form much faster what your general string sieve does: Code: 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.

 2016-07-18, 12:49 #5 rogue     "Mark" Apr 2003 Between here and the 7,213 Posts Completed to SmF7500. 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.
2016-07-18, 14:33   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

110011000102 Posts

Quote:
 Originally Posted by rogue Completed to SmF7500. 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 151 2022-05-03 01:05 Batalov And now for something completely different 9 2017-06-28 16:56 sweety439 sweety439 17 2017-06-13 03:49 rogue And now for something completely different 25 2016-01-01 17:07 robert44444uk Math 3 2007-05-19 07:15

All times are UTC. The time now is 06:25.

Thu Jun 1 06:25:59 UTC 2023 up 287 days, 3:54, 0 users, load averages: 0.77, 0.93, 1.06