{"id":73,"date":"2014-12-23T02:01:23","date_gmt":"2014-12-23T01:01:23","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=73"},"modified":"2014-12-23T20:05:23","modified_gmt":"2014-12-23T19:05:23","slug":"fibonacci-concat-primes","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/fibonacci-concat-primes\/","title":{"rendered":"Fibonacci concat primes"},"content":{"rendered":"<p>A <em>Fibonacci concat prime<\/em> is a prime number obtained by concatenating several first elements of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_number\">Fibonacci sequence<\/a> (1, 1, 2, 3, 5, 8, 13, &#8230;). These numbers showed up in <a href=\"https:\/\/twitter.com\/evelynjlamb\/status\/546943925357785089\">Evelyn Lamb&#8217;s tweet<\/a> and got me interested, especially since I wanted to play with primality testing of big numbers in Haskell. (&#8216;Fibonacci concat prime&#8217; is a completely made up name; shout if you know the right one!)<\/p>\n<p>Known trivial examples:<\/p>\n<ul>\n<li>11 = 1 \u2022 1<\/li>\n<li>1123 = 1 \u2022 1 \u2022 2 \u2022 3<\/li>\n<\/ul>\n<p>I got curious if there were any other Fibonacci concat primes and wrote a generator in Haskell using <a href=\"https:\/\/github.com\/pernas\/Primes\">this implementation of Miller-Rabin primality test<\/a>.<\/p>\n<p><!--more--><\/p>\n<p><a href=\"https:\/\/github.com\/snowleopard\/fib-concat-primes\/blob\/master\/fibConcatPrimes.hs\">My generator<\/a> seems to work fine, but unfortunately it reported that there were no other Fibonacci concat primes less than 10<sup>35000<\/sup>! 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.<\/p>\n<p>Being a bit disappointed by my wasted efforts, I decided to try my luck by <em>reversing<\/em> the numbers. And it worked!<\/p>\n<p>The following four <em>reversed Fibonacci concat primes<\/em> were found below 10<sup>20000<\/sup>:<\/p>\n<ul>\n<li>11 = reverse (1 \u2022 1)<\/li>\n<li>211 = reverse (1 \u2022 1 \u2022 2)<\/li>\n<li>853211 = reverse (1 \u2022 1 \u2022 2 \u2022 3 \u2022 5 \u2022 8)<\/li>\n<li>8807636183460050617945574903584919919511612709750316609341373260988735867648438276143212267642043327441464197323493449875748800793972557076092264546143508797705841112756829445969403139394033551560846297811045489492107112516080353190709429309149906403096671114184206432727358212075549448825300987777256577108676171327758902016012489130747556188735937250416918703740522955780084511406202276599789276821952616925345637173341585225442683859312721757626837119261335990082159234701105630252096268521940247877767962570843705121792309113638171309431133780410773449433469241976214108556155143320168954236961880937187514225303941564722978820758754253903871296264314023892241511871381469139312152057863647568211771649015676181448527951789167733324419855431231853211 = reverse (1 \u2022 &#8230; \u2022 160500643816367088)<\/li>\n<\/ul>\n<p>So, now if you need a big (754 digits) prime number, just concatenate Fibonacci numbers from F<sub>1<\/sub> to F<sub>84<\/sub> and then reverse the result!<\/p>\n<p>P.S.: A comment on <a href=\"http:\/\/oeis.org\/A019523\" title=\"Online Encyclopedia of Integer Sequences\">this OEIS sequence<\/a> says that no other non-reversed Fibonacci concat primes are currently known.<\/p>\n<p>P.P.S: There is another related sequence at OEIS: <a href=\"http:\/\/oeis.org\/A134069\" title=\"Online Encyclopedia of Integer Sequences\">A134069<\/a>. 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 <em>semireversed Fibonacci concat primes<\/em>. I have implemented their generation as well (try the <code>-semireversed<\/code> option); the only semireversed Fibonacci concat primes below 10<sup>20000<\/sup> are 11, 211 and 853211.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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, &#8230;). These numbers showed up in Evelyn Lamb&#8217;s tweet and got me interested, especially since I wanted to play with primality testing of big numbers in Haskell. (&#8216;Fibonacci concat prime&#8217; &hellip; <a href=\"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/fibonacci-concat-primes\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Fibonacci concat primes<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1174,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[4],"class_list":["post-73","post","type-post","status-publish","format-standard","hentry","category-coding","tag-haskell"],"_links":{"self":[{"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/posts\/73","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/users\/1174"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/comments?post=73"}],"version-history":[{"count":20,"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/posts\/73\/revisions"}],"predecessor-version":[{"id":93,"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/posts\/73\/revisions\/93"}],"wp:attachment":[{"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/media?parent=73"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/categories?post=73"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/wp-json\/wp\/v2\/tags?post=73"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}