Gaping Tuples!

If $A_{k}(n)$ is the number of $k$ -tuples of positive integers $(a_1,a_2,...,a_k)$ such that $a_1 + 2a_2 + \cdots + ka_k = n$ , and if $B_{k}(n)$ is the number of $k$ -tuples of nonnegative integers $(b_1,b_2,...,b_k)$ such that $b_1 + 2b_2 + \cdots + kb_k = n$ , then we see that $A_{k}(n) \; = \; \left\{ \begin{array}{lll} B_k\big(n-\tfrac12k(k+1)\big) & \hspace{1cm} & n \ge \tfrac12k(k+1) \\ 0 & & n < \tfrac12k(k+1) \end{array}\right.$ (comparing the $k$ -tuples $a_1,a_2,...,a_k$ and $b_1,b_2,...,b_k$ , where $a_j = b_j + 1$ for $1 \le j \le k$ ). The Mathematica code

B[k_, n_] := If[k == 1, 1, Sum[B[k - 1, n - j k], {j, 0, Floor[n/k]}]]

calculates $A_6(60) = B_6(39) = \boxed{3331}$ .

Below you will find my python and C++ solutions. In both cases I use recursion and caching of the solutions of the sub problems. The recursion is based on the following observation. For $n, t \in \N$ let $S_{n, t}$ be the number of positive solutions of the equation $a_1 + 2a_2 + 3a_3 + \ldots + na_n = t.$ Note that for $n, t \in \N$ , $n > 1$

• $S_{1, t} = 1$ ,
• $S_{n, t} = \sum_{k=1}^{\lfloor\frac{t}{n}\rfloor} S_{n-1, t-kn}$ .

The C++ solution is a bit tricky. The computation is done at the compile time. The solutions of the sub-problems are cached, because each template is generated only once. The C++ version requires C++17.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

"""
solution of:
    https://brilliant.org/problems/gaping-tuples/
"""

def solve(in_len, in_target_val):
    """
    returns the number of tuples (a_1, a_2, ..., a_in_len)
    such that:
        a_1+2*a_2+...+in_len*a_in_len == in_target_val
    """
    res_data = {}
    def inner(in_len, in_target_val):
        if in_len == 1 and in_target_val > 0:
            res = 1
        elif (in_len, in_target_val) in res_data:
            res = res_data[(in_len, in_target_val)]
        else:
            res = \
                sum(inner(in_len-1, in_target_val-_)
                    for _ in range(in_len, in_target_val+1, in_len))
            res_data[(in_len, in_target_val)] = res
        return res
    return inner(in_len, in_target_val)


assert solve(6, 60) == 3331

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

template <unsigned InSize, unsigned TargetValue>
constexpr unsigned solve();

template <unsigned CurVal, unsigned EndVal, unsigned StepSize>
constexpr unsigned solve_sum()
{
    if constexpr (CurVal >= EndVal)
    {
        return 0;
    }
    else
    {
        return solve<StepSize-1, EndVal-CurVal>()+solve_sum<CurVal+StepSize, EndVal, StepSize>();
    }
}

template <unsigned InSize, unsigned TargetValue>
constexpr unsigned solve()
{
    if constexpr (InSize == 1 && TargetValue > 0)
    {
        return 1;
    }
    else
    {
        return solve_sum<InSize, TargetValue, InSize>();
    }
}

int main()
{
    constexpr auto solution = solve<6, 60>();
    static_assert(solution == 3331);
    return 0;
}