 # Project Euler 104: Finding Fibonacci numbers for which the first and last nine digits are pandigital.

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:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.

It turns out that F541, 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 F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

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 log10. 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));
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.

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. ### Posted by Kristian Eman

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

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. Eman

🙁 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.) Bjarki Ágúst

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 [latex]x \ge 9[/latex] digits and the last 9 digits.

I created a simple HeadTailNumber class, which keeps track of the specified amount of head digits, and the specified amount of tail digits. It supports addition.

```public class HeadTailNumber
{
private BigInteger _tail;
private int _tail_len;

public BigInteger Tail { get { return _tail; } }

{
this._tail = tail;
this._tail_len = tail_len;
this.Fix();
}

private void Fix()
{
this._tail %= BigInteger.Pow(10, this._tail_len + 1);
int len = 1 + (int)BigInteger.Log10(this._head);
{
}
}

{

}

public override string ToString()
{
return this._head.ToString() + " * 10^" + this._head_exponent + " + " + this._tail.ToString();
}
}```

Then it is trivial to create the brute force program:

```public static void Main()
{
f_2 = new HeadTailNumber(1, 15, 9),
f_n;

for (int i = 3; ; i++)
{
f_n = f_1 + f_2;

// Code is 5 seconds faster if I uncomment this line:
// Console.WriteLine(i);

if (i >= 2749 && IsPandigital((long)f_n.Tail))
{
{
Console.WriteLine(i);
break;
}
}

f_1 = f_2;
f_2 = f_n;
}
}```

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

`int digits = (int)Math.Ceiling(BigInteger.Log10(fn));`

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

`int digits = 1 + (int)BigInteger.Log10(fn);`

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

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. Babak

Hello Dear Kristian
really thanx.
about this problem when I solved it the result has 68855 digits but you write 68854 digits. Kristian

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. francis

Java’s BigInteger is terribly slow. 🙁 Larry C

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
fibs = 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] Sheryl

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? paprika

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 = *(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’ Jean-Marie Hachey

Quote:
“fibonacci number such that the first and last 9 digits are pandigital
for n = 329,468, fib(329,468) has 68,855 digits, the top 9 digits are (2 4 5 6 8 1 7 3 9), the last 9 digits are (3 5 2 7 8 6 9 4 1)” Jean-Marie Hachey

Fibonacci number 100: F(100) has 21 digits.

Fibonacci rank (number of digits)
100 (21)
200 (42)
300 (63)
400 (84)
500 (105)
600 (126)
700 (146)
800 (167)
900 (188)
1000 (209)

In this list, we can see that the number of digits is increasing by 21 for all the Fibonacci numbers except F(700) which is increasing only by 20 units. It can be observed that this situation is repeated in the following Fibonacci numbers:
List of Fibonacci numbers for which the increase in the number of digits is only 20:
700
1700
2700
3700
4600
5600
6600
7600
8600
9600
10600

Etc…
These exceptions were only verified for Fibonacci numbers reaching up to11000.

Source:
Calculations done with:
Big Integer Calculator: 100 digits! A million digits?!
http://www.javascripter.net/math/calculators/fibonaccinumberscalculator.htm Jean-Marie Hachey

t = n*log(Φ) – log (sqrt 5)
(Testing)

F(n) Number of digits (t)
[Estimated] {Observed}

40000 [8359.869] {8360}
40400 [8443.465] {8443}
329468 [68855.208] {68855}