Euler Problem 26

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 ¹/₇ has a 6-digit recurring cycle.

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

Generating very long decimal remainders is easy, if you use the BigDecimal class. Again, Java has tons of wonderful prebuilt stuff like this. Then just iterate over <1000 and test for string duplications. I had to adjust the number of signifcant figures generated (digits) a couple of times in order to ensure that digits was more than double the longest repeating string. This ensured I had the longest.

import java.math.*;

public class Euler26
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 26:\n”);
        Euler26 e = new Euler26();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        String [] D = new String [1001];
        int answer = 0;
        int longest = 3;
        int digits = 2000;
        for (int i = 7; i < 1000; i++)
        {
            BigDecimal num = new BigDecimal (“1”);
            BigDecimal denom = new BigDecimal (Integer.toString(i));
            D[i]= num.divide(denom,new MathContext(digits)).toString().substring(2);
            System.out.print(“i: “+i+” Longest:”+longest+” Generated by:”+answer+”\n”);
            if (D[i].length() >= longest)
            {
                for (int j = 2; j <= digits/2-1; j++)
                {
                    String first = D[i].substring(0, j+1);
                    String second = D[i].substring(j+1, 2*j+2);
                    if (first.equals(second) && j % longest != 0)
                    {
                        if (j+1 > longest)
                        {
                            longest = j+1;
                            System.out.print(“NEW longest = “+longest+”\n”);
                            answer = i;
                        }
                        break;
                    }
                }
            }
        }
        return String.valueOf(answer);
    }
}

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 ¹/₇ has a 6-digit recurring cycle.

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