Project Euler 537 - Counting Tuples

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

Note: My code took 702 seconds to run, however I am happy with my solution

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.

I investigate the case T(3, 3) further to find the pattern.

It is clear that we can generate B using A! Our goal is achieved.

After solving the problem I learnt that this type of array multiplication is called a Convolution.

Now it is clear that we just need to generate an array [T(0, 1), T(1, 1), ..., T(n, 1)] and keep convolving (not sure if this is a word?) then to reach [T(0, k), T(1, k), ..., T(n, k)].

However, convolving this k times will take extremely long, instead we use binary exponentiation to get the answer in only 18 steps instead of 20,000.

Interactive Code

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

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