Euler Project – Problem 25 solution

1000-digit Fibonacci number

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 index of the first term in the Fibonacci sequence to contain 1000 digits?

Answer:4782

Solution

public class Problem25 {

    public static void main(String[] args) {

        String a = "1";
        String b = "1";
       
        int count = 2;
        while(b.length()<1000)
        {
            System.out.println("index "+count+":"+b.length()+"digits");
            String temp = b;
            b = sum(a,b);
            a = temp;
            count++;
        }

        System.out.println(count);

    }

    public static String sum(String a, String b) {

        char[] a_digits = a.toCharArray();
        char[] b_digits = b.toCharArray();

        String sum = "";
        boolean remainder = false;
        for (int i = 0; i < a_digits.length; i++) {
            char a_digit = a_digits[a_digits.length - i - 1];
            char b_digit = b_digits[b_digits.length - i - 1];

            int a_int = Integer.parseInt(String.valueOf(a_digit));
            int b_int = Integer.parseInt(String.valueOf(b_digit));

            int s = a_int + b_int;
            if (remainder) {
                s++;
            }
            remainder = (s>=10);
           
            String s_str = String.valueOf(s);
            String last_digit = s_str.substring(s_str.length()-1);
            sum = last_digit+sum;
        }
       
        int beginning = 0;
        if(b.length()>a.length())
        {
            beginning=Integer.parseInt(b.substring(0,1));
        }
        if(remainder)
        {
            beginning++;
        }
        if(beginning>0)
        {
            sum = beginning + sum;
        }
       

        return sum;
    }

}