Project Euler 537 - Counting Tuples

Official link: https://projecteuler.net/problem=537

Note: My code took 702 seconds to run, ~30s with pypy

Thought Process

My first idea was to find the number of partitions of length less than or equal to k for n and then directly calculate the total number of possible outcomes.

For example to calculate T(3, 3)

• 3 = 3 + 0 + 0

  1. There is only 1 number such that pi(n) = 0, that is n = 1

  2. There are 2 numbers such that pi(n) = 3, n = 5, 6

  3. Therefore we have 3!/2! * 2 = 6 different combinations of this form:

     1. (1,1,5), (1,5,1), (5,1,1), (1,1,6), (1,6,1), (6,1,1)

• 3 = 2 + 1 + 0

  1. pi(n) = 0 mean we have n = 1

  2. pi(n) = 1 mean we have n = 2

  3. pi(n) = 2 mean we have n = 3, 4

  4. total 3!/(1! * 1! * 1!) * 2 = 12 combs of this form:

     1. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,2,4), (1,4,2), (2,1,4), (2,4,1), (4,1,2), (4,2,1)

• 3 = 1 + 1 + 1

  1. pi(n) = 1 mean we have n = 2

  2. 3!/3! * 1 = 1 comb of this form:

     1. (2, 2, 2)

However generating partitions is too intensive and this method was too slow. 

My next attempt ended up being what almost everyone did.

Interactive Code

Enter 2 integers separated by a space (n, k)

Code will output T(n, k) (mod 1004535809)