Problem Statement

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

Display the first 25 rows of a number triangle which begins: 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)}

.

If your environment is able, plot

P ( n )

{\displaystyle P(n)}

against

n

{\displaystyle n}

for

n

1 … 999

{\displaystyle n=1\ldots 999}

.

Let's start with the solution:

import cp.

main =>
  foreach(N in 1..25)
     P = integer_partition(N).reverse,
     G = P.map(sort_down).map(first).counts.to_list.sort.map(second),
     println(G=G.sum)
  end,
  println("Num partitions == sum of rows:"),
  println([partition1(N) : N in 1..25]).

% Get all partitions
integer_partition(N) = find_all(X,integer_partition(N,X)).
integer_partition(N,X) =>
  member(Len,1..N),
  X = new_list(Len),
  X :: 1..N,
  increasing(X),
  sum(X) #= N,
  solve($[split],X).

% Counts the occurrences of the elements in L
counts(L) = Map =>
  Map = new_map(),
  foreach(I in L)
    Map.put(I,Map.get(I,0)+1)
  end.

% Number of partitions
go2 => 
  foreach(N in [23,123,1234,12345,123456])
    println(N=partition1(N))
  end,  
  nl.

table
partition1(0) = 1.
partition1(N) = P =>
  S = 0,
  K = 1,
  M = (K*(3*K-1)) // 2,  
  while (M <= N)
     S := S - ((-1)**K)*partition1(N-M),
     K := K + 1, 
     M := (K*(3*K-1)) // 2 
  end,
  K := 1,
  M := (K*(3*K+1)) // 2,
  while (M <= N)
     S := S - ((-1)**K)*partition1(N-M),
     K := K + 1,
     M := (K*(3*K+1)) // 2  
  end,
  P = S.

pc(N) = pc(1,N).
table
pc(_,0) = 1.
pc(1,1) = 1.
pc(K,M) = cond(M < K, 0, pc(K, M-K) + pc(K + 1,M)).