Euler Solution 26

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 26

Find the d in the range 2..999 such that 1/d has the longest recuring cycle in it's digits.

Haskell by SanguineV

Runtime: 764.583 ms

{- Given a numerator and a denominator, find the length of the longest recuring cycle
 - in the digits of the fraction. -}
cyc :: Integer -> Integer -> Integer
cyc n d = fromIntegral (inner [n] ((mod n d) * 10 ))
  where
    inner :: [Integer] -> Integer -> Int
    inner ns n' | elem n' ns = length (takeWhile (\x -> not (x == n')) ns) + 1
    inner ns n' | mod n' d == 0 = 0
    inner ns n' = inner (n' : ns) ((mod n' d) * 10)

{- Print the first of the fold to find the maximum by the second of the pairs the
 - map of a denominator and the cycle length for 1 ove the denominator for
 - denominators in the range 2..999. -}
main = print (fst (foldl (\(md,mc) (cd,cc) -> if mc > cc then (md,mc) else (cd,cc)) 
                         (0,0) (map (\x -> (x,cyc 1 x)) [2..999])))

Java by tomchristmas

Text message conversation:

TB: I grok your Euler 26 now :) Now to come up with own solution...

TGW: Do it in Java so Neo Phyte can follow it.

I've tried as best as I can to adhere to JavaSchoolTM principles e.g. unnecessary use of braces, unnecessary comparison of a Boolean variable, and no "hard" stuff like recursion.

Runtime: 2.085s

class Euler26
{
 
  // Basically, we build a chain of moduli, which we terminate
  // when we either obtain a zero result, meaning that the 
  // fraction is not recursive, or we obtain a modulus that we
  // have previously obtained, meaning that the chain will repeat
  // itself from this point onwards.

  private static int cycle(int d)
  {
    int cycleLength = 0;
    int count = 0;
    int prevMod = 1;

    // I conjecture that, given a fraction 1/d, the length of its cycle 
    // (if it has one) is always less than d, hence the allocation of d+1
    // cells.
    // Is there a proof of this anywhere?

    int[] dd = new int[d+1];
    dd[0] = 0;
    boolean keepLooping = true;
    boolean foundMatch = false;

    while (keepLooping == true)
    {
       prevMod = (prevMod % d) * 10;
       if (prevMod == 0) // divisible, hence not recursive, so let's stop
       {
          cycleLength = 0;
          keepLooping = false;
       }
       else
       {
          // If we have a match, then we've come full circle!
          int count2 = 0;
          while (dd[count2] != 0)
          {
             count2 = count2 + 1;
             if (dd[count2] == prevMod)
             {
                foundMatch = true;
             }
          }

          if (foundMatch == true)
          {
             cycleLength = count2 + 1;
             keepLooping = false;
          }
          else
          {
             dd[count] = prevMod;
             if (count < d)
             {
                dd[count+1] = 0;
             }
          }
       }
       count = count + 1;
    }

    return cycleLength;
  }

  public static void main(String[] args)
  {
    int c, d;
    int greatestCycle = 0;
    int greatestD = 0;

    for (d = 2; d < 1000; d++)
    {
       c = cycle(d);
       if (c > greatestCycle)
       {
          greatestCycle = c;
          greatestD = d;
       }
    }

    System.out.println(Integer.toString(greatestD));
  }

}
Personal tools