problem 78 url https projecteuler netproblem78 statement let pn represent the number of different ways in which n coins can be separated into piles for example five coins can be separated into piles in exactly seven different ways so p57 ooooo oooo o ooo oo ooo o o oo oo o oo o o o o o o o o find the least value of n for which pn is divisible by one million solution1 1 solution9 14 solution 55374 solution 1 1 solution 9 14 solution 55374
import itertools


def solution(number: int = 1000000) -> int:
    
    partitions = [1]

    for i in itertools.count(len(partitions)):
        item = 0
        for j in itertools.count(1):
            sign = -1 if j % 2 == 0 else +1
            index = (j * j * 3 - j) // 2
            if index > i:
                break
            item += partitions[i - index] * sign
            item %= number
            index += j
            if index > i:
                break
            item += partitions[i - index] * sign
            item %= number

        if item == 0:
            return i
        partitions.append(item)

    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()

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