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 ^(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.

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 ^(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.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s