Products of Partitions

Computer Science Level 4

A partition of an integer is a way of representing a positive integer as a sum of other positive integers. For example, 4 can be partitioned in the following 5 ways

$4=1+1+1+1=2+1+1=2+2=3+1$

The product reduction of each partition is

$4, \ 1\times1\times1\times1, \ 2\times1\times1, \ 2\times2, \ 3\times1$

Out of these 5 products, $2$ of the products are odd ( $3\times1$ and $1\times1\times1\times1$ ).

How many odd product reductions of the partitions of 40 are there?

The answer is 1113.

1 solution

Bill Bell
Aug 23, 2015

Using Jerome Kelleher's code.

## http://jeromekelleher.net/partitions.php

def accelAsc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2*x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]

count=0
for p in accelAsc(40):
    count+=reduce(lambda x,y:x*y,p,1) % 2
print count

Products of Partitions

The answer is 1113.

1 solution

0 pending reports