TheAlgorithms-Python

1
"""
2
Combinatoric selections
3

4
Problem 47
5

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

8
14 = 2 × 7
9
15 = 3 × 5
10

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

13
644 = 2² × 7 × 23
14
645 = 3 × 5 × 43
15
646 = 2 × 17 × 19.
16

17
Find the first four consecutive integers to have four distinct prime factors each.
18
What is the first of these numbers?
19
"""
20

21
from functools import lru_cache
22

23

24
def unique_prime_factors(n: int) -> set:
25
    """
26
    Find unique prime factors of an integer.
27
    Tests include sorting because only the set really matters,
28
    not the order in which it is produced.
29
    >>> sorted(set(unique_prime_factors(14)))
30
    [2, 7]
31
    >>> sorted(set(unique_prime_factors(644)))
32
    [2, 7, 23]
33
    >>> sorted(set(unique_prime_factors(646)))
34
    [2, 17, 19]
35
    """
36
    i = 2
37
    factors = set()
38
    while i * i <= n:
39
        if n % i:
40
            i += 1
41
        else:
42
            n //= i
43
            factors.add(i)
44
    if n > 1:
45
        factors.add(n)
46
    return factors
47

48

49
@lru_cache
50
def upf_len(num: int) -> int:
51
    """
52
    Memoize upf() length results for a given value.
53
    >>> upf_len(14)
54
    2
55
    """
56
    return len(unique_prime_factors(num))
57

58

59
def equality(iterable: list) -> bool:
60
    """
61
    Check equality of ALL elements in an interable.
62
    >>> equality([1, 2, 3, 4])
63
    False
64
    >>> equality([2, 2, 2, 2])
65
    True
66
    >>> equality([1, 2, 3, 2, 1])
67
    False
68
    """
69
    return len(set(iterable)) in (0, 1)
70

71

72
def run(n: int) -> list:
73
    """
74
    Runs core process to find problem solution.
75
    >>> run(3)
76
    [644, 645, 646]
77
    """
78

79
    # Incrementor variable for our group list comprehension.
80
    # This serves as the first number in each list of values
81
    # to test.
82
    base = 2
83

84
    while True:
85
        # Increment each value of a generated range
86
        group = [base + i for i in range(n)]
87

88
        # Run elements through out unique_prime_factors function
89
        # Append our target number to the end.
90
        checker = [upf_len(x) for x in group]
91
        checker.append(n)
92

93
        # If all numbers in the list are equal, return the group variable.
94
        if equality(checker):
95
            return group
96

97
        # Increment our base variable by 1
98
        base += 1
99

100

101
def solution(n: int = 4) -> int:
102
    """Return the first value of the first four consecutive integers to have four
103
    distinct prime factors each.
104
    >>> solution()
105
    134043
106
    """
107
    results = run(n)
108
    return results[0] if len(results) else None
109

110

111
if __name__ == "__main__":
112
    print(solution())
113