TheAlgorithms-Python

1
"""
2
Problem 78
3
Url: https://projecteuler.net/problem=78
4
Statement:
5
Let p(n) represent the number of different ways in which n coins
6
can be separated into piles. For example, five coins can be separated
7
into piles in exactly seven different ways, so p(5)=7.
8

9
            OOOOO
10
            OOOO   O
11
            OOO   OO
12
            OOO   O   O
13
            OO   OO   O
14
            OO   O   O   O
15
            O   O   O   O   O
16
Find the least value of n for which p(n) is divisible by one million.
17
"""
18

19
import itertools
20

21

22
def solution(number: int = 1000000) -> int:
23
    """
24
    >>> solution(1)
25
    1
26

27
    >>> solution(9)
28
    14
29

30
    >>> solution()
31
    55374
32
    """
33
    partitions = [1]
34

35
    for i in itertools.count(len(partitions)):
36
        item = 0
37
        for j in itertools.count(1):
38
            sign = -1 if j % 2 == 0 else +1
39
            index = (j * j * 3 - j) // 2
40
            if index > i:
41
                break
42
            item += partitions[i - index] * sign
43
            item %= number
44
            index += j
45
            if index > i:
46
                break
47
            item += partitions[i - index] * sign
48
            item %= number
49

50
        if item == 0:
51
            return i
52
        partitions.append(item)
53

54
    return 0
55

56

57
if __name__ == "__main__":
58
    import doctest
59

60
    doctest.testmod()
61

62
    print(f"{solution() = }")
63