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

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

Written by on 7 July 2012

Topics: Project Euler

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

9 Comments For This Post I'd Love to Hear Yours!

  1. Eman says:

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

  2. Kristian says:

    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.

  3. Eman says:

    :( 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.)

  4. Bjarki Ágúst says:

    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 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 _head;
    	private BigInteger _tail;
    	private int _head_exponent;
    	private int _head_len;
    	private int _tail_len;
    
    	public BigInteger Head { get { return _head; } }
    	public BigInteger Tail { get { return _tail; } }
    
    	public HeadTailNumber(BigInteger n, int head_len, int tail_len) : this(n, 0, n, head_len, tail_len) { }
    
    	public HeadTailNumber(BigInteger head, int head_exponent, BigInteger tail, int head_len, int tail_len)
    	{
    		this._head = head;
    		this._tail = tail;
    		this._head_exponent = head_exponent;
    		this._head_len = head_len;
    		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);
    		if (len > this._head_len)
    		{
    			this._head /= BigInteger.Pow(10, len - this._head_len);
    			this._head_exponent += len - this._head_len;
    		}
    	}
    
    	public static HeadTailNumber operator +(HeadTailNumber left, HeadTailNumber right)
    	{
    		BigInteger left_head = left._head,
    				   right_head = right._head;
    
    		left_head *= BigInteger.Pow(10, left._head_exponent - Math.Min(left._head_exponent, right._head_exponent));
    		right_head *= BigInteger.Pow(10, right._head_exponent - Math.Min(left._head_exponent, right._head_exponent));
    
    		return new HeadTailNumber(left_head + right_head, Math.Min(left._head_exponent, right._head_exponent), left._tail + right._tail, Math.Max(left._head_len, right._head_len), Math.Max(left._tail_len, right._tail_len));
    	}
    
    	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()
    {
       	HeadTailNumber f_1 = new HeadTailNumber(1, 15, 9),
       				   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))
    		{
    			BigInteger head = f_n.Head;
    			head /= BigInteger.Pow(10, Math.Max((int)BigInteger.Log10(head) + 1 - 9, 0));
    			if (IsPandigital((long)head))
    			{
    				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.

  5. Kristian says:

    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.

  6. Babak says:

    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

  7. Kristian says:

    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.

  8. francis says:

    Java’s BigInteger is terribly slow. :(

  9. Larry C says:

    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]

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.