Reciprocal Cycles

A unit fraction contains \(1\) in the numerator. The decimal representation of the unit fractions with denominators \(2\) to \(10\) are given:

\begin{align} 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 \end{align}

Where \(0.1(6)\) means \(0.166666\cdots\), 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 \lt 1000\) for which \(1/d\) contains the longest recurring cycle in its decimal fraction part.

Naive solution (dead end)

The problem is a bit tricky because it’s hard to imagine a naive solution that performs poorly and can then be improved upon. In this case, that’s not really possible.

Calculating the decimal representation of a fraction using standard division alone won’t work because of precision limitations.

Using a BigDecimal might seem like an improvement, but then we run into the problem of detecting the recurring cycle. And that’s only the beginning. Consider the following code:

val mathContext = new MathContext(100, RoundingMode.HALF_EVEN)
BigDecimal(1, mathContext) / BigDecimal(7)

This returns a very long number:

\(0.1428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571429\)

In theory, we could find the cycle by performing many lookups on this representation, but that wouldn’t be very efficient.

What’s worse, the choice of 100 decimal places was arbitrary. In this case, it overshoots the required precision considerably. More importantly, we have no way of knowing in advance how many digits will be needed for a different fraction.

That’s a very hacky, dirty solution. There must be a better way!

Solution

My other idea was inspired by a pen and paper division. If we wanted to divide 1 by 7 by hand, it would be an iterative process, where each step requires one division, remembering the remainder and writing down the next decimal number.

So, for 1 / 7, we would have the following steps:

• 10 / 7 -> writing down 1, remainder is (10 - 7) = 3
• 30 / 7 -> writing down 4, remainder is (30 - 28) = 2
• 20 / 7 -> writing down 2, remainder is (20 - 14) = 6
• 60 / 7 -> writing down 8, remainder is (60 - 56) = 4
• 40 / 7 -> writing down 5, remainder is (40 - 35) = 5
• 50 / 7 -> writing down 7, remainder is (50 - 49) = 1
• 10 / 7 -> ugh, this looks familiar. Right! That’s a cycle.

It means that our solutions needs to keep track of how deep the cycle is (its length) and the previous remainders. If we already processed the remainder before, then it’s a cycle.

There are also cases like 1 / 6, where the cycle starts at the second number, so instead of storing just the remainder, let’s also store the index to see where the cycle starts. Here’s one way of doing that:

import scala.annotation.tailrec

object Euler026 extends EulerApp {
  override def execute(): Any = (1 until 1000).maxBy(findCycleLength)

  private type Index = Int
  private type Remainder = Int

  private def findCycleLength(divisor: Int): Int = {

    @tailrec
    def findCycleLength(remainder: Int, pastResults: Map[Remainder, Index]): Int = {
      pastResults.get(remainder) match {
        // If it's in the map, then we've found the cycle
        case Some(index) => pastResults.size - index
        case None        =>
          remainder match {
            case 0                        => 0
            case r if remainder < divisor =>
              val newRemainder = remainder * 10
              findCycleLength(newRemainder, pastResults + (remainder -> pastResults.size))
            case r =>
              val newRemainder = (remainder % divisor) * 10
              findCycleLength(
                newRemainder,
                pastResults + (remainder -> pastResults.size)
              )
          }
      }
    }

    findCycleLength(remainder = 1 % divisor, pastResults = Map.empty)
  }
}

The implementation itself is pretty straightforward. There’s nothing worth discussing that wasn’t covered before, as it’s a standard tail recursive solution, that could’ve been a simple loop in other languages. d