Fibonacci concat primes

A Fibonacci concat prime is a prime number obtained by concatenating several first elements of the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, …). These numbers showed up in Evelyn Lamb’s tweet and got me interested, especially since I wanted to play with primality testing of big numbers in Haskell. (‘Fibonacci concat prime’ is a completely made up name; shout if you know the right one!)

Known trivial examples:

  • 11 = 1 • 1
  • 1123 = 1 • 1 • 2 • 3

I got curious if there were any other Fibonacci concat primes and wrote a generator in Haskell using this implementation of Miller-Rabin primality test.

My generator seems to work fine, but unfortunately it reported that there were no other Fibonacci concat primes less than 1035000! It took just a couple of hours for the generator to do the work, which I thought was pretty impressive since I made no effort to optimise the code.

Being a bit disappointed by my wasted efforts, I decided to try my luck by reversing the numbers. And it worked!

The following four reversed Fibonacci concat primes were found below 1020000:

  • 11 = reverse (1 • 1)
  • 211 = reverse (1 • 1 • 2)
  • 853211 = reverse (1 • 1 • 2 • 3 • 5 • 8)
  • 8807636183460050617945574903584919919511612709750316609341373260988735867648438276143212267642043327441464197323493449875748800793972557076092264546143508797705841112756829445969403139394033551560846297811045489492107112516080353190709429309149906403096671114184206432727358212075549448825300987777256577108676171327758902016012489130747556188735937250416918703740522955780084511406202276599789276821952616925345637173341585225442683859312721757626837119261335990082159234701105630252096268521940247877767962570843705121792309113638171309431133780410773449433469241976214108556155143320168954236961880937187514225303941564722978820758754253903871296264314023892241511871381469139312152057863647568211771649015676181448527951789167733324419855431231853211 = reverse (1 • … • 160500643816367088)

So, now if you need a big (754 digits) prime number, just concatenate Fibonacci numbers from F1 to F84 and then reverse the result!

P.S.: A comment on this OEIS sequence says that no other non-reversed Fibonacci concat primes are currently known.

P.P.S: There is another related sequence at OEIS: A134069. Note that it is different from what I call reversed Fibonacci concat primes: the sequence of Fibonacci numbers is reversed, but the numbers themselves are not, e.g., it contains 13853211 instead of 31853211. To distinguish the sequences, I will refer to A134069 as semireversed Fibonacci concat primes. I have implemented their generation as well (try the -semireversed option); the only semireversed Fibonacci concat primes below 1020000 are 11, 211 and 853211.

Leave a Reply

Your email address will not be published. Required fields are marked *