nekedome / project-euler

solutions/problem26.py

"""
Project Euler Problem 26: Reciprocal Cycles
===========================================

.. module:: solutions.problem26
   :synopsis: My solution to problem #26.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem26.py>`_.

Problem Statement
#################

A unit fraction contains :math:`1` in the numerator. The decimal representation of the unit fractions with denominators

This line is too long as per the coding-style (119/100).

:math:`2` to :math:`10` are given:

.. math::

    \\ ^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

Where :math:`0.1(6)` means :math:`0.166666\\dots`, and has a :math:`1`-digit recurring cycle. It can be seen that

This line is too long as per the coding-style (113/100).

:math:`\\ ^1 / _7` has a :math:`6`-digit recurring cycle.

Find the value of :math:`d \\lt 1000` for which :math:`\\ ^1 / _d` contains the longest recurring cycle in its decimal

This line is too long as per the coding-style (118/100).

fraction part.

Solution Discussion
###################

The decimal expansion of :math:`\\ ^1 / _d` falls into one of three possibilities:

1. Divisors :math:`d` of the form :math:`2^n \\times 5^m` produce a finite expansion, e.g. :math:`\\ ^1 / _2 = 0.5`

This line is too long as per the coding-style (115/100).

   (non-recurring)
2. Prime divisors :math:`d` that are co-prime with :math:`2` and :math:`5` produce an infinite expansion

This line is too long as per the coding-style (104/100).

3. Multiples of prime divisors :math:`d` that are divisible by :math:`2` or :math:`5` produce infinite expansion with a

This line is too long as per the coding-style (119/100).

   non-recurring prefix

.. note:: the cycle produced by numbers of the third class are actually rotations of the cycles produced by their prime

This line is too long as per the coding-style (119/100).

          divisor.

.. math::

    \\ ^1 / _7 &= 0.(142857) \\\\
    \\ ^1 / _{14} &= 0.0(714285)

Observe that the cycles are rotations of one-another and that :math:`7` is a prime divisor of :math:`14`.

This line is too long as per the coding-style (105/100).

Therefore, we must only consider prime divisors that are co-prime with :math:`2` and :math:`5`.

Interestingly, the cycle length of such a divisor :math:`p` in the decimal representation of :math:`\\ ^1 / _p` is the

This line is too long as per the coding-style (118/100).

multiplicative order of :math:`10 \\mod p`. That is, the cycle length is the minimum :math:`k` s.t.
:math:`10^k = 1 \\mod p`.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem26.py
   :language: python
   :lines: 70-
"""

from lib.grouptheory import multiplicative_order
from lib.sequence import Primes


def solve():
    """ Compute the answer to Project Euler's problem #26 """
    upper_bound = 1000
    max_cycle_length = 0
    answer = 0
    primes = filter(lambda _p: _p not in [2, 5], Primes(upper_bound=upper_bound))
    for p in primes:

The name p does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        cycle_length = multiplicative_order(10, p)
        if cycle_length > max_cycle_length:
            max_cycle_length = cycle_length
            answer = p
    return answer


expected_answer = 983

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).