Python Implementation of Problem 47

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 47

I was able to chain this with a previous problem. Probably a suboptimal solution because of it, but it felt prettier this way.

I was able to add a short-circuited fail case to the is_prime() method, though

Problem:

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7 15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

python.src.p0047.cached_is_prime(args: Tuple[int, int, bool], cache: MutableMapping[Tuple[int, int, bool], bool]) → bool
python.src.p0047.main() → int
 1"""
 2Project Euler Problem 47
 3
 4I was able to chain this with a previous problem. Probably a suboptimal
 5solution because of it, but it felt prettier this way.
 6
 7I was able to add a short-circuited fail case to the is_prime() method, though
 8
 9Problem:
10
11The first two consecutive numbers to have two distinct prime factors are:
12
1314 = 2 × 7
1415 = 3 × 5
15
16The first three consecutive numbers to have three distinct prime factors are:
17
18644 = 2² × 7 × 23
19645 = 3 × 5 × 43
20646 = 2 × 17 × 19.
21
22Find the first four consecutive integers to have four distinct prime factors
23each. What is the first of these numbers?
24"""
25from itertools import count
26from typing import MutableMapping, Tuple
27
28from .lib.iters import groupwise
29from .lib.primes import is_prime
30
31
32def cached_is_prime(
33    args: Tuple[int, int, bool],
34    cache: MutableMapping[Tuple[int, int, bool], bool]
35) -> bool:
36    if args in cache:
37        return cache[args]
38    result = is_prime(*args)
39    cache[args] = result
40    return result
41
42
43def main() -> int:
44    cache: MutableMapping[Tuple[int, int, bool], bool] = {}
45    for group in groupwise(count(2), 4):
46        if all(cached_is_prime((x, 4, True), cache) for x in group):
47            return group[0]
48    return -1  # pragma: no cover

Tags: prime-number, divisibility, python-iterator