Longest recurring cycle in its decimal fraction - a bug or a misunderstanding?

This is fairly 'math-y' but I'm posting here because it's a Project Euler problem, & I have working code that presumably has bugs in it.

The question Determing longest repeating cycle in a decimal expansion solves the problem using logarithms, but I'm interested in solving with simple brute force. More accurately, I'm interested in understanding why my algorithm and code is not returning the correct solution.

The algorithm is simple:

• replicate a 'long division',
• at each step record the divisor and the remainder
• when a divisor / remainder tuple is repeated, infer that the decimal representation will repeat.

Here are private fields, as requested

private int numerator; 
private int recurrence; 
private int result; 
private int resultRecurrence; 
private List<dynamic> digits;

and here is the code:

private void Go()
{
    foreach (var i in primes)
    {
        digits = new List<dynamic>();
        numerator = 1;
        recurrence = 0;

        while (numerator != 0)
        {
            numerator *= 10;

            // quotient
            var q = numerator / i;

            // remainder
            var r = numerator % i;
            digits.Add(new { Divisor = q, Remainder = r });

            // if we've found a repetition then break out
      开发者_开发百科      var m = digits.Where(p => p.Divisor == q && p.Remainder == r).ToList();
            if (m.Count > 1)
            {
                recurrence = digits.LastIndexOf(m[0]) - digits.IndexOf(m[0]);
                break;
            }
            numerator = r;
        }

        if (recurrence > resultRecurrence)
        {
            resultRecurrence = recurrence;
            result = i;
        }
}}

When testing integers < 10 and < 20 I get the correct result; and I correctly identify the value of i as well. However the decimal represetation that I get is incorrect - I calculate i-1 whereas the correct result is far less (something like i-250).

So presumably I either have a programming bug - which I can't find - or a logic bug.

I'm confused because it feels like a multiplicative group over p to me, in which there would be p-1 elements. I'm sure I'm missing something, can anyone provide suggestions?

edit

I'm not going to include my prime number code - it's not relevant, as I explain above I correctly identify the value of i (from memory it is 983) but I'm having problems getting the correct value for resultRecurrence.

---

I'm confused because it feels like a multiplicative group over p to me, in which there would be p-1 elements. I'm sure I'm missing something, can anyone provide suggestions?

Close.

For all primes except 2 and 5 (which divide 10), the sequence of remainders is formed by starting with 1 and transforming by

remainder = (10 * remainder) % prime

thus the k-th remainder is 10^k (mod prime) and the set of remainders forms a subgroup of the group of nonzero remainders modulo prime[1]. The length of the recurring cycle is the order of that subgroup, which is also known as the order of 10 modulo prime.

The order of the group of nonzero remainders modulo prime is prime-1, and there's a theorem by Fermat:

Let G be a finite group of order g and H be a subgroup of G. Then the order h of H divides g.

So the length of the cycle is always a divisor of prime-1, and sometimes it's prime-1, e.g. for 7 or 19.

[1] For composite numbers n coprime to 10, that would be the group of remainders modulo n that are coprime to n.

---

First off, you don’t need the divisors, you only need the remainders.

Secondly, I would split the function into multiple independent parts instead of having everything in one big method: The long division / finding of the cycle length is independent of the rest (= finding the longest cycle).

Your break on Where coupled with Count is unintuitive. Why not just use a while loop with the condition (! digits.Contains(r))? (This would require putting 0 as a remainder into the digits list before the loop start.)

This leaves us with a much cleaner code that should be straightforward to debug.

---

recurrence = digits.LastIndexOf(m[0]) - digits.IndexOf(m[0]);

Surely the value of resultRecurrence is always going to be i-1 ? Since for a fraction of the form 1/n, the decimal starts repeating exactly when the division-in-progress (the ith digit) gives the same quotient-remainder as the very first trial division (1, hence i-1).

(as a side note, may I introduce you to Math.DivRem).