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:

var [const] BN=Import.lib("zklBigNum");
 
const N=0d100_000;
p:=List.createLong(N+1,BN.fp(0),True);  // (0,0,...) all different

fcn calc(n,p){
   p[n].set(0);  // reset array for each run
   foreach k in ([1..n]){
      d:=n - k *(3*k - 1)/2;
      do(2){
         if (d<0) break(2);
	 if (k.isOdd) p[n].add(p[d]);
	 else         p[n].sub(p[d]);
	 d-=k;
      }
   }
}

idx:=T(23, 123, 1234, 12345, 20000, 30000, 40000, 50000, N);
p[0].set(1);

foreach i in (idx){
   (1).pump(i,Void,calc.fp1(p));	// for n in [1..i] do calc(n,p)
   "%2d:\t%d".fmt(i,p[i]).println();
}