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`
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
considered. However, the search space may be reduced even further by observing that some :math:`n`-digit pandigital
patterns cannot possibly be prime. In particular, by enumeration of all pandigital numbers for a given :math:`n` or by
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
:math:`n`-digit pandigital. While this algorithm produces the correct answer, we can do better. The runtime of this
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
solution is faster because there are generally less pandigital numbers than primes for the same number of digits (at
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_]*)|(__.*__))$).