This task is a variation of the short story by Arthur C. Clarke.

(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
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


{\displaystyle n}

   corresponds to integer   



n


{\displaystyle n}

,   and each column   



C


{\displaystyle C}

   in row   



m


{\displaystyle m}

   from left to right corresponds to the number of names beginning with   



C


{\displaystyle C}

.

A function   



G
(
n
)


{\displaystyle G(n)}

   should return the sum of the   



n


{\displaystyle n}

-th   row.

Demonstrate this function by displaying:   



G
(
23
)


{\displaystyle G(23)}

,   



G
(
123
)


{\displaystyle G(123)}

,   



G
(
1234
)


{\displaystyle G(1234)}

,   and   



G
(
12345
)


{\displaystyle G(12345)}

.

Optionally note that the sum of the   



n


{\displaystyle n}

-th   row   



P
(
n
)


{\displaystyle P(n)}

   is the     integer partition function.

Demonstrate this is equivalent to   



G
(
n
)


{\displaystyle G(n)}

   by displaying:   



P
(
23
)


{\displaystyle P(23)}

,   



P
(
123
)


{\displaystyle P(123)}

,   



P
(
1234
)


{\displaystyle P(1234)}

,   and   



P
(
12345
)


{\displaystyle P(12345)}

.



Extra credit
If your environment is able, plot   



P
(
n
)


{\displaystyle P(n)}

   against   



n


{\displaystyle n}

   for   



n
=
1
…
999


{\displaystyle n=1\ldots 999}

.

Related tasks
 Partition function P


 
let get, sum_unto =
  let cache = ref [||]
  let rec get i j =
    if Array.length !cache < i then
      cache :=
        Array.init i begin fun i ->
          try !cache.(i) with Invalid_argument _ ->
          Array.make (i+1) (Num.num_of_int 0)
        end;
    if Num.(!cache.(i-1).(j-1) =/ num_of_int 0)
    then !cache.(i-1).(j-1) <- sum_unto (i-j) j;
    !cache.(i-1).(j-1)
  and sum_unto i j =
    let rec sum_unto sum i j =
      match (i,j) with
      |(0,0) -> (Num.num_of_int 1)
      |(_,0) -> sum
      |(i,j) when j > i -> sum_unto sum i i
      |(i,j) -> sum_unto Num.(sum +/ (get i j)) i (j-1)
    in
    sum_unto (Num.num_of_int 0) i j
  in
  get, sum_unto
 
let sum_of_row n = sum_unto n n
 
let euler_recurrence =
  let cache = ref [||] in
  let rec recurrence = function
    |n when n < 0 -> Num.num_of_int 0
    |0 -> Num.num_of_int 1
    |n ->
        if n >= Array.length !cache then
          cache :=
            Array.init (n+1) (fun i ->
              try !cache.(i) with Invalid_argument _ -> Num.num_of_int 0);
        if Num.(!cache.(n) =/ num_of_int 0)
        then begin
          let rec summing sum = function
            |0 -> sum
            |k ->
                let op = if k mod 2 = 0 then Num.sub_num else Num.add_num in
                let sum = op sum (recurrence (n - k * (3*k - 1) / 2)) in
                let sum = op sum (recurrence (n - k * (3*k + 1) / 2)) in
                summing sum (k-1)
          in
          !cache.(n) <- summing (Num.num_of_int 0) n
        end;
        !cache.(n)
  in
  recurrence
 
let print i_max =
  for i=1 to i_max do
    print_int (i+1); print_string ": ";
    for j=1 to i do
      print_string (Num.string_of_num (get i j));
      print_char ' ';
    done;
    print_newline ();
  done
 
let () =
  print 30;
  print_newline ();
  List.iter begin fun i ->
      Printf.printf "%i: %s ?= %s\n" i
        (Num.string_of_num (sum_of_row i))
        (Num.string_of_num (euler_recurrence i));
      flush stdout;
    end
  [23;123;1234;];
  List.iter begin fun i ->
      Printf.printf "%i: %s\n" i
        (Num.string_of_num (euler_recurrence i));
      flush stdout;
    end
  [23;123;1234;12345;123456]
 