Problem 104 of Project Euler is squeezed in between three related problems, but that should not keep us from actually solving it. The problem reads

The Fibonacci sequence is defined by the recurrence relation:

F_{n}= F_{n-1}+ F_{n-2}, where F_{1}= 1 and F_{2}= 1.

It turns out that F_{541}, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F_{2749}, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that F_{k}is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, findk.

It is pretty obvious to me that there is a brute force approach which requires almost no brainpower to implement, so I went for that one first to see if that would do the trick.

## Hitting it right on

I just keep generating Fibonacci numbers until I reach one where the last 9 digits (which can be extracted with modulo) are pandigital. If I find a candidate, I will remove anything but the first 9 digits and check those. The number of digits can be easily found using the log_{10}. Going for this method obviously requires us to use the Biginteger library as the problem description is talking numbers with 575 digits which is smaller than the solution will be. The code looks like

BigInteger fn2 = 1; BigInteger fn1 = 1; BigInteger fn; BigInteger tailcut = 1000000000; int n = 2; bool found = false; while (!found) { n++; fn = fn1 + fn2; long tail = (long)(fn % tailcut); if (IsPandigital(tail)) { int digits = 1 + (int) BigInteger.Log10(fn); if (digits > 9) { long head = (long)(fn / BigInteger.Pow(10, digits - 9)); if (IsPandigital(head)) { found = true; } } } fn2 = fn1; fn1 = fn; }

The isPandigital function is reused from Problem 32. Easy solution to derive and easy to code, but execution is not so easy

Fibonacci number 329468 is the first solution Solution took 39810,8247 ms

That is fourty seconds! Within the given time limit on the site, but I have a fairly fast computer and I am sure for a lot of computers this algorithm is not fast enough. So what to do? Well the number has 68854 digits

## Other ways to calculate the Fibonacci numbers

We can calculate as being the closest integer to , where is the golden ration or

You can get a longer explanation why this is the case on wikipedia. So if we can manipulate this formula to only get the first 10 digits we can eliminate the use of BigInteger which is most likely the performance killer in the above solution. If we take the log10 function , hereafter just denoted *log* we get

If we then remove everything before the decimal point we will get rid of the information about the number of digits. So all we have is the information about the first digits until the precision of the floating point variable we are storing it in. If we then add 8 to t and raise 10 to the power of t then the integer part of that number will be the first 9 digits of our Fibonacci number assuming that we have enough precision.

In the code I have precalculated some of the numbers such that we have the approximations

The c# code for this looks like

long fn2 = 1; long fn1 = 1; long fn; long tailcut = 1000000000; int n = 2; bool found = false; while (!found) { n++; fn = (fn1 + fn2) % tailcut; fn2 = fn1; fn1 = fn; if (IsPandigital(fn)) { double t = (n * 0.20898764024997873 - 0.3494850021680094); if (IsPandigital((long)Math.Pow(10, t - (long)t + 8))) found = true; } }

When we evaluate this we get

Fibonacci number 329468 is the first solution Solution took 33,4137 ms

“Only” a bit more than a factor 100 in performance and well within the limits of the 1 minute time limit.

## Wrapping up

This concludes the Problem 104 and we are now returning to the problems with special sub sets. I gave you two solutions to the problem one which was easy to derive and one which was actually fast enough to be worth anything.

As always you can find the source code for download here.

The blog image is of a flower displaying patterns that relate to Fibonacci numbers. It was captured by Brian Wolfe who shared it under the creative commons license.

Good solution. My code for this problem was in Java with BigInteger library. But it was too slow, this solution is much faster.

So did you solve it with something similar to the first method, or something completly different? Please share you code with us. Even though you think it is too slow, it might still be interesting and people might learn something from it.

🙁 I would like to but I solved PE 104 long long ago. And I do not have that code. But recently I am keeping my PE solutions in a file. So when I will have the code I’ll post it.

P.S. look at Uva divisors proglem (I found even faster solution.)

Ahh, nice. That is a clever, and new to me, way of using logarithms. I had to try it out for myself and think about it a bit before I saw it was true.

I think I originally did the brute force method, but if I were to do it today (and would not have seen how you did it), I would go the brute force way, but only keep track of the first digits and the last 9 digits.

I created a simple

HeadTailNumberclass, which keeps track of the specified amount of head digits, and the specified amount of tail digits. It supports addition.Then it is trivial to create the brute force program:

This code runs in 16 seconds. For whatever weird reason, the code takes 5 seconds less to finish if I uncomment that line that outputs the index of each Fibonacci number that I loop through. I’m using Mono C# on a Linux machine, but that is still pretty weird.

And also: I noticed that you did

to find the number of digits in a number. This would fail when the number is a power of 10. The correct way:

You probably already knew that, and it may have been a mistake, but correct should be correct.

Interesting approach and a great idea. There is not need to keep track of all the intermediate digits.

Regarding the number of digits in a number you are also right. That is corrected now.

Hello Dear Kristian

First thank you for your website and reveal your code and your description

really thanx.

about this problem when I solved it the result has 68855 digits but you write 68854 digits.

please check it agin

I might be mistaken, but I will check it again at some point. However, if you found a solution with the same number in the Fibonacci sequence you are probably right.

Java’s BigInteger is terribly slow. 🙁

Interesting that you got Binet’s method to work out for you. I got in to accuracy problems with that one and never solved it.

I tried brute force but found it much to slow.

The solution was brute force to fine the pandigitals at the end of the string – just carrying forward the last then digits at each iteration. (I think a good chunk of computing time was taken up with carrying forward the big integers.) When I found one I would then compute the entire Fibonacci number using the algorithm further down the Wikipedia page that you reference. Where F[2n} is calculated in terms of F[n] and F[n-1]. That allowed me to cut the time to log(n). Set up a dictionary in Python for the first dozen or so Fibonacci numbers. If F[n] was what i wanted. I calculated n/2 recursively until I got a value under 12, call it i. Starting at that value for the series I used the Wikipedia method to computed F[2i] recursively until I got close to F[n]. Do to the integer division I had to calculate the last few number with the standard method – F[n+1] = F[n] + F[n-1].

Here is my Python Fibonacci number calculator.

def fib_n(n):

“””returns the Fibonacci number for n”””

fibs = {}

fibs[0] = 0

fibs[1] = 1

for i in range(2,11):

fibs[i] = fibs[i-1] + fibs[i-2]

current = n

while current > 10:

current /= 2

while current < n/2+1:

fibs[2*current] = (2*fibs[current-1] + fibs[current]) * fibs[current]

fibs[2 * current -1] = fibs[current]**2 + fibs[current-1]**2

current = 2 * current

while current < n:

current += 1

fibs[current] = fibs[current – 1] + fibs[current – 2]

return fibs[n]

hmmmmmmmmmmmmmmmmm,It seems that SQL is not cool because no one has tried to solve this prbleom with SQL.Here Oracle SQL:select num, count_tot, (max(diff) over ()) max_difffrom(select num, (count(*) over ()) count_tot, (num-(lag(num) over (order by num))) difffrom(select level numfrom dualconnect by level = length(num) -1and length(replace(translate(num,’1 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’2 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’3 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’4 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’5 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’6 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’7 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’8 ,’X’),’X’,null)) >= length(num) -1and length(replace(translate(num,’9 ,’X’),’X’,null)) >= length(num) -1)or (length(num)=1))order by num/NUM COUNT_TOT MAX_DIFF – – -1 738 112 738 113 738 114 738 115 738 116 738 117 738 118 738 119 738 1110 738 1112 738 1113 738 11 ..967 738 11968 738 11970 738 11971 738 11972 738 11973 738 11974 738 11975 738 11976 738 11978 738 11980 738 11981 738 11982 738 11983 738 11984 738 11985 738 11986 738 11987 738 11I used the Mikito way the generate the numbers.If anyone knows how to use a regular expression as a filter to check for duplicate digits I could use this regular expressions instead of all the translate functions?

import time as time

def comDiv(m,n):

while 1:

i = m % n

if i == 0:

return 0

break

elif i == 1:

return 1

break

else:

m = n

n = i

#print comDiv(10,5)

num = 1000

n = 2

y = [1]*(num-1)

max = 0

maxindex = 0

t0 = time.time()

for i in range(2,num+1):

for j in range(1,i):

if comDiv(i,j):

y[i-2] += 1

out = n/(float)(y[i-2])

if out > max:

max = out

maxindex = n

n += 1

print maxindex,’ ‘,max

print “running time:”,(time.time() – t0),’s’