nekedome / project-euler

solutions/problem41.py

"""
Project Euler Problem 41: Pandigital Prime
==========================================

.. module:: solutions.problem41
   :synopsis: My solution to problem #41.

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

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

We shall say that an :math:`n`-digit number is pandigital if it makes use of all the digits :math:`1` to :math:`n`

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

exactly once. For example, :math:`2143` is a :math:`4`-digit pandigital and is also prime.

What is the largest :math:`n`-digit pandigital prime that exists?

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

First, observe that a decimal representation is assumed, so, only integers up to nine digits in length need be

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

considered. However, the search space may be reduced even further by observing that some :math:`n`-digit pandigital

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

patterns cannot possibly be prime. In particular, by enumeration of all pandigital numbers for a given :math:`n` or by

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

the application of rules of divisibility.

**Case: 1-digit pandigital (by enumeration)**

:math:`1` is not prime
:raw-html:`<br />`
:math:`\\therefore` no :math:`1`-digit pandigital number is prime

**Case: 2-digit pandigital (by enumeration)**

:math:`12 = 2^2 \\times 3` is not prime
:raw-html:`<br />`
:math:`21 = 3 \\times 7` is not prime
:raw-html:`<br />`
:math:`\\therefore` no :math:`2`-digit pandigital number is prime

**Case: 3-digit pandigital (by rules of divisibility)**

Observe that any such number must contain the digits :math:`1,2,3`
:raw-html:`<br />`
Now, observe that :math:`1 + 2 + 3 = 6`, which is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\Rightarrow` any :math:`3`-digit pandigital is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\therefore` no :math:`3`-digit pandigital number is prime

**Case: 5-digit pandigital (by rules of divisibility)**

Observe that any such number must contain the digits :math:`1,2,3,4,5`
:raw-html:`<br />`
Now, observe that :math:`1 + 2 + 3 + 4 + 5 = 15` which is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\Rightarrow` any :math:`5`-digit pandigital is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\therefore` no :math:`5`-digit pandigital number is prime

**Case: 6-digit pandigital (by rules of divisibility)**

Observe that any such number must contain the digits :math:`1,2,3,4,5,6`
:raw-html:`<br />`
Now, observe that :math:`1 + 2 + 3 + 4 + 5 + 6 = 21` which is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\Rightarrow` any :math:`6`-digit pandigital is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\therefore` no :math:`6`-digit pandigital number is prime

**Case: 8-digit pandigital (by rules of divisibility)**

Observe that any such number must contain the digits :math:`1,2,3,4,5,6,7,8`
:raw-html:`<br />`
Now, observe that :math:`1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36` which is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\Rightarrow` any :math:`8`-digit pandigital is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\therefore` no :math:`8`-digit pandigital number is prime

**Case: 9-digit pandigital (by rules of divisibility)**

Observe that any such number must contain the digits :math:`1,2,3,4,5,6,7,8,9`
:raw-html:`<br />`
Now, observe that :math:`1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45` which is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\Rightarrow` any :math:`9`-digit pandigital is divisible by :math:`3`
:raw-html:`<br />`
:math:`\\therefore` no :math:`9`-digit pandigital number is prime

So, we only need to consider :math:`4`-digit and :math:`7`-digit numbers.

Originally, my solution enumerated primes up to (and including) :math:`7`-digits and then checked whether each prime is

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

:math:`n`-digit pandigital. While this algorithm produces the correct answer, we can do better. The runtime of this

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

algorithm is dominated by the cost of prime sieving.

My second, superior, solution enumerates :math:`n`-digit pandigital numbers and checks whether they are prime. This

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

solution is faster because there are generally less pandigital numbers than primes for the same number of digits (at

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

least for the search interval considered):

- The number of :math:`7`-digit primes is about :math:`\\frac{10^7}{\\log(10^7)} \\approx 620420`
- The number of :math:`7`-digit pandigital numbers is precisely :math:`7! = 5040`

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

.. literalinclude:: ../../solutions/problem41.py
   :language: python
   :lines: 112-
"""

from itertools import chain

from lib.numbertheory import is_probably_prime
from lib.sequence import Pandigitals


def solve():
    """ Compute the answer to Project Euler's problem #41 """
    answer = 0
    for candidate in chain(Pandigitals(n=4), Pandigitals(n=7)):
        if is_probably_prime(candidate):
            answer = max(answer, candidate)  # the n-digit pandigital is also prime
    return answer


expected_answer = 7652413

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