# 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.

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;
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));
}

}
```