Project Euler – Problem 26 Solution

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Answer: 983 (it has 982 recurring cycle length)

Solution:

import java.math.BigInteger;
import java.util.ArrayList;

public class Problem26 {

    public static void main(String[] args) {

        // This ArrayList is to collect numbers like
        // 9,90,99,900,990,999,9000,9900,9990,9999...1000 digits out of digit 9
        ArrayList<BigInteger> nums = new ArrayList<>();
        for (int i = 1; i <= 1000 ; i++) {
            for (int j = 1; j <= i; j++) {
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < j; k++) {
                    sb.append("9");
                }
                for (int k = 0; k < i-j; k++) {
                    sb.append("0");
                }
                String str = sb.toString();
                BigInteger num = new BigInteger(str);
                nums.add(num);
            }
        }

        int num_with_max_freq = 0;
        int max_freq = 0;
        // lets divide each number in arraylist to numbers from 1 till 1000
        for (int d = 1; d < 1000; d++) {
            for (int j = 0; j < nums.size(); j++) {
                BigInteger bi = BigInteger.valueOf(Integer.valueOf(d));
                BigInteger zero = BigInteger.valueOf(Integer.valueOf(0));
                // if some number can be divided by i without remainder so it is find its pattern
                // for example for 6, pattern is 90
                if(nums.get(j).mod(bi)==zero)
                {
                    String num = String.valueOf(nums.get(j));
                    // freq - length of recurring cycle
                    int freq = num.lastIndexOf("9")+1;
                    if(freq>max_freq)
                    {
                        // save max frequency
                        max_freq=freq;
                        // save max d
                        num_with_max_freq = d;
                    }
                    break;
                }
            }
        }
       
        System.out.println(num_with_max_freq+":"+max_freq);

    }

}