Euler Solution 78

From ProgSoc Wiki

Jump to: navigation, search

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.

Find the least value of n for which p(n) is divisible by one million.

Solutions for Problem 78

Python by Althalus

Runtime: 28.5 seconds.

def pentagonal_numbers():
    # Calculate pentagonal numbers for use in the partition generating function
    n = 0
    while 1:
        n += 1   
        yield int(0.5*n*(3*n-1))
        yield int(0.5*-n*(3*-n-1))

iter = pentagonal_numbers()
pents = [iter.next() for i in range(10000)]

# Dictionary containing calculated partitions.
# Start off with 0 in there, and the code below fills the rest out.
ps = {0:1,}

# Calculate partitions up to arbitrary number.
# To calculate the partitions, we use this generating function:
# http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Generating_function
# For each partition we calculate, store it in a dict for later retrieval for
# future partition calculations.
for i in xrange(1,1000000):
    res = 0
    flip,plus = 1,1
    for j in pents:
        x = i - j
        if x < 0: break
        if plus: res += ps[x]
        else: res -= ps[x]
        #Switch from positive to negative every second run.
        flip ^= 1
        if flip: plus ^=1

    ps[i] = res
    # mod 1000 is quicker than mod 1000000, and will knock out a lot of bad candidates. 
    # Really only saves us 1 second.
    if not res % 1000:
        if not res % 1000000:
                print i
                print res
                exit()

My first few approaches were similar to (ie implementations and variations of) the intermediate function method. Took me longer than it should have to realise the generator below was far more efficient (or that there even WAS a generating function on the same page...)

Personal tools