9 billion names of God the integer

This task is a variation of the short story by Arthur C. Clark. (Solvers should be aware of the consequences of completing this task.) In detail, to specify what is meant by a “name”:

The integer 1 has 1 name “1”.

The integer 2 has 2 names “1+1”, and 2.

The integer 3 has 3 names “1+1+1”, “2+1”, and “3”.

The integer 4 has 5 names “1+1+1+1”, “2+1+1”, “2+2”, “3+1”, “4”.

The integer 5 has 7 names “1+1+1+1+1”, “2+1+1+1”, “2+2+1”, “3+1+1”, “3+2”, “4+1”, “5”.

Task

The task is to display the first 25 rows of a number triangle which begins:

                                      1
                                    1   1
                                  1   1   1 
                                1   2   1   1
                              1   2   2   1   1
                            1   3   3   2   1   1

Where row $n$ corresponds to integer $n$ , and each column $C$ in row $m$ from left to right corresponds to the number of names begining with $C$ .

The sum of the $n$ -th row $P(n)$ is the integer partition function. Demonstrate this function by displaying: $P(23)$ , $P(123)$ , $P(1234)$ , and $P(12345)$ .

Extra credit

If your environment is able, plot $P(n)$ against $n$ for $n=1\ldots 999$ .

D

Translation of: Python

<lang d>import std.stdio, std.bigint, std.algorithm, std.range;

auto cumu(in uint n) {

   __gshared cache = 1.BigInt;
   foreach (l; cache.length .. n + 1) {
       auto r = [0.BigInt];
       foreach (x; 1 .. l + 1)
           r ~= r.back + cache[l - x][min(x, l - x)];
       cache ~= r;
   }
   return cache[n];

}

auto row(in uint n) {

   auto r = n.cumu;
   return n.iota.map!(i => r[i + 1] - r[i]);

}

void main() {

   writeln("Rows:");
   foreach (x; 1 .. 11)
       writefln("%2d: %s", x, x.row);

   writeln("\nSums:");
   foreach (x; [23, 123, 1234])
       writeln(x, " ", x.cumu.back);

}</lang>

Output:

Rows:
 1: [1]
 2: [1, 1]
 3: [1, 1, 1]
 4: [1, 2, 1, 1]
 5: [1, 2, 2, 1, 1]
 6: [1, 3, 3, 2, 1, 1]
 7: [1, 3, 4, 3, 2, 1, 1]
 8: [1, 4, 5, 5, 3, 2, 1, 1]
 9: [1, 4, 7, 6, 5, 3, 2, 1, 1]
10: [1, 5, 8, 9, 7, 5, 3, 2, 1, 1]

Sums:
23 1255
123 2552338241
1234 156978797223733228787865722354959930

Python

<lang python>cache = 1 def cumu(n):

   for l in range(len(cache), n+1):
       r = [0]
       for x in range(1, l+1):
           r.append(r[-1] + cache[l-x][min(x, l-x)])
       cache.append(r)
   return cache[n]

def row(n):

   r = cumu(n)
   return [r[i+1] - r[i] for i in range(n)]

print "rows:" for x in range(1, 11): print "%2d:"%x, row(x)

print "\nsums:" for x in [23, 123, 1234, 12345]: print x, cumu(x)[-1]</lang>

Output:

(I didn't actually wait long enough to see what the sum for 12345 is)

rows:
 1: [1]
 2: [1, 1]
 3: [1, 1, 1]
 4: [1, 2, 1, 1]
 5: [1, 2, 2, 1, 1]
 6: [1, 3, 3, 2, 1, 1]
 7: [1, 3, 4, 3, 2, 1, 1]
 8: [1, 4, 5, 5, 3, 2, 1, 1]
 9: [1, 4, 7, 6, 5, 3, 2, 1, 1]
10: [1, 5, 8, 9, 7, 5, 3, 2, 1, 1]

sums:
23 1255
123 2552338241
1234 156978797223733228787865722354959930
^C