# Fibonacci

## Project Euler 137: Fibonacci golden nuggets

I think that Problem 137 of Project Euler is a really fantastic problem since it has so many facets of how it can be solved. I will go through a one of them, and then link to a few other. The problem reads

Consider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + …, where Fk is the kth term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, … ; that is, Fk = Fk-1 + Fk-2, F1 = 1 and F2 = 1.

For this problem we shall be interested in values of x for which AF(x) is a positive integer.

 Surprisingly AF(1/2) = (1/2).1 + (1/2)2.1 + (1/2)3.2 + (1/2)4.3 + (1/2)5.5 + … = 1/2 + 1/4 + 2/8 + 3/16 + 5/32 + … = 2

The corresponding values of x for the first five natural numbers are shown below.

 x AF(x) √2-1 1 1/2 2 (√13-2)/3 3 (√89-5)/8 4 (√34-3)/5 5

We shall call AF(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 10th golden nugget is 74049690.

Find the 15th golden nugget.

Posted by Kristian in Project Euler, 7 comments

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

Posted by Kristian in Project Euler, 14 comments

## UVa 10229: Modular Fibonacci

In problem 10229 at UVa Online Judge, Modular Fibonacci, our task is to calculate huge Fibonacci numbers, modulo some given integer. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 3 comments

## Project Euler 25: What is the first term in the Fibonacci sequence to contain 1000 digits?

Back to the big numbers again in Problem 25 of Project Euler. The problem reads

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12 is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

With the BigInteger class this is rather easy to brute force. So a brute force solution is one of the two solutions I will show you. The other solution is one you can use with a calculator, or if you are good at mental arithmetic, you can do it with pen and paper.

Posted by Kristian in Project Euler, 20 comments

## Project Euler – Problem 2

The problem description of Problem 2 of Project Euler reads

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Before heading on with a solution, I will make a small comment on the problem formulation. Usually the first two numbers in the Fibonacci sequence is defined as F1 = F2 = 1. But that is just nitpicking and wont change anything in the solution.

Posted by Kristian in Project Euler, 31 comments