Expressing Natural Number by sum of Triangular numbers

Question

Triangular numbers are numbers which is number of things when things can be arranged in triangular shape.

For Example, 1, 3, 6, 10, 15... are triangular numbers.

o

o o

o o o

o o o o

is shape of n=4 triangular number

what I have to do is A natural number N is given and I have to print N expressed by sum of triangular numbers.

if N = 4

output should be

1 1 1 1

1 3

3 1

else if N = 6

output should be

1 1 1 1 1 1

1 1 1 3

1 1 3 1

1 3 1 1

3 1 1 1

3 3

6

I have searched few hours and couldn't find answers...

please help.

(I am not sure this might help, but I found that

If i say T(k) is Triangular number when n is k, then

T(k) = T(k-1) + T(k-3) + T(k-6) + .... + T(k-p) while (k-p) > 0

and p is triangular number )

Here's Code for k=-1(Read comments below)

#include <iostream>
#include <vector>

using namespace std;

long TriangleNumber(int index);
void PrintTriangles(int index);

vector<long> triangleNumList(450); //(450 power raised by 2 is about 200,000)
vector<long> storage(100001);

int main() {
    int n, p;

    for (int i = 0; i < 450; i++) {
        triangleNumList[i] = i * (i + 1) / 2;
    }
    cin >> n >> p;
    cout << TriangleNumber(n);
    if (p == 1) {
        //PrintTriangles();
    }

    return 0;
}

long TriangleNumber(int index) {
    int iter = 1, out = 0;
    if (index == 1 || index == 0) {
        return 1;
    }
    else {
        if (storage[index] != 0) {
            return storage[index];
        }
        else {
            while (triangleNumList[iter] <= index) {
                storage[index] = ( storage[index] + TriangleNumber(index - triangleNumList[iter]) ) % 1000000;
                iter++;
            }
        }
    }
    return storage[index];
}
void PrintTriangles(int index) {
    // What Algorithm?
}

Answer 1

Here is some recursive Python 3.6 code that prints the sums of triangular numbers that total the inputted target. I prioritized simplicity of code in this version. You may want to add error-checking on the input value, counting the sums, storing the lists rather than just printing them, and wrapping the entire routine into a function. Setting up the list of triangular numbers could also be done in fewer lines of code.

Your code saved time but worsened memory usage by "memoizing" the triangular numbers (storing and reusing them rather than always calculating them when needed). You could do the same to the sum lists, if you like. It is also possible to make this more in the dynamic programming style: find the sum lists for n=1 then for n=2 etc. I'll leave all that to you.

""" Given a positive integer n, print all the ways n can be expressed as
the sum of triangular numbers.
"""
def print_sums_of_triangular_numbers(prefix, target):
    """Print sums totalling to target, each after printing the prefix."""
    if target == 0:
        print(*prefix)
        return
    for tri in triangle_num_list:
        if tri > target:
            return
        print_sums_of_triangular_numbers(prefix + [tri], target - tri)

n = int(input('Value of n ? '))

# Set up list of triangular numbers not greater than n
triangle_num_list = []
index = 1
tri_sum = 1
while tri_sum <= n:
    triangle_num_list.append(tri_sum)
    index += 1
    tri_sum += index

# Print the sums totalling to n
print_sums_of_triangular_numbers([], n)

Here are the printouts of two runs of this code:

Value of n ? 4
1 1 1 1
1 3
3 1

Value of n ? 6
1 1 1 1 1 1
1 1 1 3
1 1 3 1
1 3 1 1
3 1 1 1
3 3
6