# 9 billion names of God the integer

9 billion names of God the integer
You are encouraged to solve this task according to the task description, using any language you may know.

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”.

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 ${\displaystyle n}$ corresponds to integer ${\displaystyle n}$, and each column ${\displaystyle C}$ in row ${\displaystyle m}$ from left to right corresponds to the number of names begining with ${\displaystyle C}$.

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

Extra credit

If your environment is able, plot ${\displaystyle P(n)}$ against ${\displaystyle n}$ for ${\displaystyle 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
```