# Euler Solution 26

### From ProgSoc Wiki

# 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 JavaSchool^{TM} 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)); } }