9 billion names of God the integer

From Rosetta Code
Task
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. 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     corresponds to integer   ,   and each column     in row     from left to right corresponds to the number of names beginning with   .

A function     should return the sum of the   -th   row.

Demonstrate this function by displaying:   ,   ,   ,   and   .

Optionally note that the sum of the   -th   row     is the     integer partition function.

Demonstrate this is equivalent to     by displaying:   ,   ,   ,   and   .


Extra credit

If your environment is able, plot     against     for   .

Related tasks



11l

Translation of: Python
V cache = [[BigInt(1)]]
F cumu(n)
   L(l) :cache.len .. n
      V r = [BigInt(0)]
      L(x) 1 .. l
         r.append(r.last + :cache[l - x][min(x, l - x)])
      :cache.append(r)
   R :cache[n]

F row(n)
   V r = cumu(n)
   R (0 .< n).map(i -> @r[i + 1] - @r[i])

print(‘rows:’)
L(x) 1..10
   print(‘#2:’.format(x)‘ ’row(x))

print("\nsums:")

V pp = [BigInt(1)]

F partitions(n)
   :pp.append(BigInt(0))

   L(k) 1 .. n
      V d = n - k * (3 * k - 1) I/ 2
      I d < 0
         L.break

      I k [&] 1 != 0
         :pp[n] += :pp[d]
      E
         :pp[n] -= :pp[d]

      d -= k
      I d < 0
         L.break

      I k [&] 1 != 0
         :pp[n] += :pp[d]
      E
         :pp[n] -= :pp[d]

   R :pp.last

V ns = Set([23, 123, 1234, 12345])
V max_ns = max(ns)

L(i) 1 .. max_ns
   I i > max_ns
      L.break
   V p = partitions(i)
   I i C ns
      print(‘#6: #.’.format(i, p))
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
 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program integerName64.s   */ 

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

.equ MAXI,   524

/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .asciz "Total  : @  pour @ \n"
szMessError:        .asciz "Number too large !!.\n"
szCarriageReturn:   .asciz "\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
tbNames:          .skip 8 * MAXI
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                 // entry of program 
    
    mov x0,#5
    bl functionG
    
    mov x0,#23
    bl functionG

    mov x0,#123
    bl functionG
    
    mov x0,#524
    bl functionG
    
    mov x0,#1234
    bl functionG
100:                                  // standard end of the program 
    mov x0, #0                        // return code
    mov x8, #EXIT                     // request to exit program
    svc #0                            // perform the system call
 
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrtbNames:              .quad tbNames
qAdrsZoneConv:            .quad sZoneConv
/******************************************************************/
/*            compute function G                                 */ 
/******************************************************************/
/* x0 contains N */
functionG:
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    cmp x0,#MAXI + 1
    bge 2f
    mov x3,x0
    mov x2,#1
1:                               // loop compute every item
    mov x0,x2
    bl computeNumber
    add x2,x2,#1
    cmp x2,x3
    ble 1b
 
    ldr x1,qAdrsZoneConv         // result display
    bl conversion10              // call decimal conversion
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConv         // insert conversion in message
    bl strInsertAtCharInc
    mov x4,x0
    mov x0,x3
    ldr x1,qAdrsZoneConv         // result display
    bl conversion10              // call decimal conversion
    mov x0,x4
    ldr x1,qAdrsZoneConv         // insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    mov x0,#0
    b 100f
2:
    ldr x0,qAdrszMessError
    bl affichageMess
    mov x0,#-1
100:
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
qAdrszMessError:         .quad szMessError
/******************************************************************/
/*            random door test strategy                           */ 
/******************************************************************/
/* x0 contains N */
computeNumber:
    stp x1,lr,[sp,-16]!          // save  registres
    stp x2,x3,[sp,-16]!          // save  registres
    stp x4,x5,[sp,-16]!          // save  registres
    stp x6,x7,[sp,-16]!          // save  registres
    ldr x6,qAdrtbNames           // table address
    mov x1,#1
    str x1,[x6]                  // init item 0
    mov x1,#0
    str x1,[x6,x0,lsl #3]        // init item N
    mov x2,#1                    // indice
1:
    add x3,x2,x2, lsl #1
    sub x4,x3,#1
    mul x4,x2,x4
    lsr x4,x4,#1
    subs x3,x0,x4                // compute new indice
    blt 90f
    tst x2,#1                    // indice owen ?
    beq 2f
    ldr x4,[x6,x3,lsl #3]
    ldr x5,[x6,x0,lsl #3]
    add x5,x5,x4                 // addition
    str x5,[x6,x0,lsl #3]
    b 3f
2:                               // else substrac
    ldr x4,[x6,x3,lsl #3]
    ldr x5,[x6,x0,lsl #3]
    sub x5,x5,x4
    str x5,[x6,x0,lsl #3]
3:
    subs x3,x3,x2                // compute new indice
    blt 90f
    
    tst x2,#1                    // owen ?
    beq 4f
    ldr x4,[x6,x3,lsl #3]
    ldr x5,[x6,x0,lsl #3]
    add x5,x5,x4
    str x5,[x6,x0,lsl #3]
    b 5f
4:
    ldr x4,[x6,x3,lsl #3]
    ldr x5,[x6,x0,lsl #3]
    sub x5,x5,x4
    str x5,[x6,x0,lsl #3]
5:
    add x2,x2,#1
    cmp x2,x0
    ble 1b
90:
   ldr x0,[x6,x0,lsl #3]         // return last item of table
100:
    ldp x6,x7,[sp],16           // restaur des  2 registres
    ldp x4,x5,[sp],16           // restaur des  2 registres
    ldp x2,x3,[sp],16           // restaur des  2 registres
    ldp x1,lr,[sp],16           // restaur des  2 registres
    ret
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Output:
Total  : 7  pour 5
Total  : 1255  pour 23
Total  : 2552338241  pour 123
Total  : 18324532310194337942  pour 524
Number too large !!.

Ada

Translation of: C#
Translation of: VBA
with Ada.Text_IO;
with Ada.Numerics.Big_Numbers.Big_Integers;

procedure Names_Of_God is

   NN         : constant := 100_000;
   Row_Count  : constant := 25;
   Max_Column : constant := 79;

   package Triangle is
      procedure Print;
   end Triangle;

   package Row_Summer is
      procedure Calc (N : Integer);
      procedure Put_Sums;
   end Row_Summer;

   package body Row_Summer is
      use Ada.Text_IO;
      use Ada.Numerics.Big_Numbers.Big_Integers;

      P : array (0 .. NN + 1) of Big_Integer := (1, others => 0);

      procedure Calc (N : Integer) is
      begin
         P (N) := 0;

         for K in 1 .. N + 1 loop
            declare
               Add : constant Boolean := K mod 2 /= 0;
               D_1 : constant Integer := N - K * (3 * K - 1) / 2;
               D_2 : constant Integer := D_1 - K;
            begin
               exit when D_1 < 0;

               if Add
               then P (N) := P (N) + P (D_1);
               else P (N) := P (N) - P (D_1);
               end if;

               exit when D_2 < 0;

               if Add
               then P (N) := P (N) + P (D_2);
               else P (N) := P (N) - P (D_2);
               end if;
            end;
         end loop;
      end Calc;

      procedure Put_Wrapped (Item : Big_Integer) is
         Image : constant String := To_String (Item);
      begin
         Set_Col (11);
         for I in Image'Range loop
            if Ada.Text_IO.Col >= Max_Column then
               Set_Col (12);
            end if;
            Put (Image (I));
         end loop;
      end Put_Wrapped;

      procedure Put_Sums
      is
         package Integer_IO is new Ada.Text_IO.Integer_IO (Integer);

         Printout : constant array (Natural range <>) of Integer :=
           (23, 123, 1234, 12_345, 20_000, 30_000, 40_000, 50_000, NN);

         Next : Natural := Printout'First;
      begin
         for A in 1 .. Printout (Printout'Last) loop
            Calc (A);
            if A = Printout (Next) then
               Put ("G (");
               Integer_IO.Put (A, Width => 0);
               Put (")");
               Put_Wrapped (P (A));
               New_Line;
               Next := Next + 1;
            end if;
         end loop;
      end Put_Sums;

   end Row_Summer;

   package body Triangle is

      Triangle : array (0 .. Row_Count,
                        0 .. Row_Count) of Integer := (others => (others => 0));

      procedure Calculate is
      begin
         Triangle (1,1) := 1;
         Triangle (2,1) := 1;
         Triangle (2,2) := 1;
         Triangle (3,1) := 1;
         Triangle (3,2) := 1;
         Triangle (3,3) := 1;
         for Row in 4 .. Row_Count loop
            for Col in 1 .. Row loop
               if Col * 2 > Row then
                  Triangle (Row, Col) := Triangle (Row - 1, Col - 1);
               else
                  Triangle (Row, Col) :=
                    Triangle (Row - 1, Col - 1) +
                    Triangle (Row - Col, Col);
               end if;
            end loop;
         end loop;
      end Calculate;

      procedure Print
      is
         use Ada.Text_IO;
         Width : array (1 .. Row_Count) of Natural := (others => 0);
      begin
         for Row in 1 .. Row_count loop
            for Col in 1 .. Row loop
               Width (Row) := Width (Row) + Triangle (Row, Col)'Image'Length;
            end loop;
         end loop;

         for Row in 1 .. Row_Count loop
            Set_Col (1 + Positive_Count (1 + Width (Width'Last)
                                           - Width (Row)) / 2);
            for Col in 1 .. Row loop
               Put (Triangle (Row, Col)'Image);
            end loop;
            New_Line;
         end loop;
      end Print;

   begin
      Calculate;
   end Triangle;

begin
   Triangle.Print;
   Row_Summer.Put_Sums;
end Names_Of_God;
Output:

The program run takes 23 seconds on 2016 MacBook Air.

                                       1
                                      1 1
                                     1 1 1
                                    1 2 1 1
                                   1 2 2 1 1
                                  1 3 3 2 1 1
                                 1 3 4 3 2 1 1
                                1 4 5 5 3 2 1 1
                               1 4 7 6 5 3 2 1 1
                              1 5 8 9 7 5 3 2 1 1
                           1 5 10 11 10 7 5 3 2 1 1
                          1 6 12 15 13 11 7 5 3 2 1 1
                        1 6 14 18 18 14 11 7 5 3 2 1 1
                       1 7 16 23 23 20 15 11 7 5 3 2 1 1
                     1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
                    1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
                  1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
                 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
               1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
             1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
          1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
        1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
      1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
    1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
G (23)     1255
G (123)    2552338241
G (1234)   156978797223733228787865722354959930
G (12345)  6942035795392611681956297720520938446066767309467146362027032170080
           6074195845953959951425306140971942519870679768681736
G (20000)  2521148138125296979166195332304704522813289496018115934368503141080
           3428442380156495662397073168982436919232478935199490301641182623057
           8166735959242113097
G (30000)  4296358424632538517488315748300592091269024864540113906601448061276
           4163986215458185192990173314832179564211367228855321718015074490598
           095469727784182254987592569621576375743614022636192786
G (40000)  2280772827447072828934057124081695970464622037835161185943949940867
           2657828590548093703330014605000554127042566412316061732771683740688
           0512642374788938691635864264873546003424774916205066033895952328900
           82673857997469797
G (50000)  3626186097141667844592140891595633728165383082527785049015872755414
           1099042567120827181227473166105658246308817729102175442616592394326
           7067153241385837825618898733387712189158660795738975053844747471259
           2979263719012461858719791627302489739548263
G (100000) 2749351056977569651267751632098635268817342931598005475820312598430
           2147328114964173055050741660736621590157844774296248940493063070200
           4617927644930335101160793424571901557189435097253124661084520063695
           5893446424871682878983218234500926285383140459702130713067451062441
           9227311238999702284408609370935531629697851569569892196108480158600
           569421098519

ARM Assembly

Works with: as version Raspberry Pi
/* ARM assembly Raspberry PI  */
/*  program integerName.s   */ 

/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"

.equ MAXI,   127

/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .asciz "Total  : @  \n"
szMessError:        .asciz "Number too large !!.\n"
szCarriageReturn:   .asciz "\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
tbNames:          .skip 4 * MAXI
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                 @ entry of program 
    
    mov r0,#5
    bl functionG
    
    mov r0,#23
    bl functionG

    mov r0,#123
    bl functionG
    
    mov r0,#1234
    bl functionG
    
100:                                  @ standard end of the program 
    mov r0, #0                        @ return code
    mov r7, #EXIT                     @ request to exit program
    svc #0                            @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrtbNames:               .int tbNames
iAdrsZoneConv:            .int sZoneConv
/******************************************************************/
/*            compute function G                                 */ 
/******************************************************************/
/* r0 contains N */
functionG:
    push {r1-r3,lr}              @ save registers
    cmp r0,#MAXI + 1
    bge 2f
    mov r3,r0
    mov r2,#1
1:                               @ loop compute every item
    mov r0,r2
    bl computeNumber
    add r2,r2,#1
    cmp r2,r3
    ble 1b
 
    ldr r1,iAdrsZoneConv         @ result display
    bl conversion10              @ call decimal conversion
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv         @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    mov r0,#0
    b 100f
2:
    ldr r0,iAdrszMessError
    bl affichageMess
    mov r0,#-1
100:
    pop {r1-r3,lr}
    bx lr                         @ return 
iAdrszMessError:         .int szMessError
/******************************************************************/
/*            random door test strategy                           */ 
/******************************************************************/
/* r0 contains N */
computeNumber:
    push {r1-r7,lr}              @ save registers
    ldr r6,iAdrtbNames           @ table address
    mov r1,#1
    str r1,[r6]                  @ init item 0
    mov r1,#0
    str r1,[r6,r0,lsl #2]        @ init item N
    mov r2,#1                    @ indice
1:
    add r3,r2,r2, lsl #1
    sub r4,r3,#1
    mul r4,r2,r4
    lsr r4,r4,#1
    subs r3,r0,r4                @ compute new indice
    blt 90f
    tst r2,#1                    @ indice owen ?
    beq 2f
    ldr r4,[r6,r3,lsl #2]
    ldr r5,[r6,r0,lsl #2]
    add r5,r5,r4                 @ addition
    str r5,[r6,r0,lsl #2]
    b 3f
2:                               @ else substrac
    ldr r4,[r6,r3,lsl #2]
    ldr r5,[r6,r0,lsl #2]
    sub r5,r5,r4
    str r5,[r6,r0,lsl #2]
3:
    subs r3,r3,r2                @ compute new indice
    blt 90f
    
    tst r2,#1                    @ owen ?
    beq 4f
    ldr r4,[r6,r3,lsl #2]
    ldr r5,[r6,r0,lsl #2]
    add r5,r5,r4
    str r5,[r6,r0,lsl #2]
    b 5f
4:
    ldr r4,[r6,r3,lsl #2]
    ldr r5,[r6,r0,lsl #2]
    sub r5,r5,r4
    str r5,[r6,r0,lsl #2]
5:
    add r2,r2,#1
    cmp r2,r0
    ble 1b
90:
   ldr r0,[r6,r0,lsl #2]         @ return last item of table
100:
    pop {r1-r7,lr}
    bx lr                        @ return 

/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
Output:
Total  : 7
Total  : 1255
Total  : 2552338241
Number too large !!.

AutoHotkey

SetBatchLines -1

InputBox, Enter_value, Enter the no. of lines sought
array := []
Loop, % 2*Enter_value - 1
	Loop, % x := A_Index
		y := A_Index, Array[x, y] := 1

x := 3

Loop
{
	base_r := x - 1
	, x++
	, y := 2
	, index := x
	, new := 1
	
	Loop, % base_r - 1
	{
		array[x, new+1] := array[x-1, new] + array[base_r, y]
		, x++
		, new ++
		, y++
	}
	x := index
	If ( mod(x,2) = 0 )
	{
		to_run := floor(x - x/2)
		, y2 := to_run + 1
	}
	Else
	{
		to_run := x - floor(x/2)
		, y2 := to_run
	}
	Loop, % to_run
	{
		array[x, y2] := array[x-1, y2-1]
		, y2++
		If ( y2 = Enter_value + 1 ) && ( x = Enter_value ) 
		{
			Loop, % Enter_value
			{
				Loop, % x11 := A_Index
				{
					y11 := A_Index
					, string2 .= " " array[x11, y11]
				}
				string2 .= "`n"
			}
			MsgBox % string2
			ExitApp
		}
	}
}

~Esc::ExitApp
Output:

If user inputs 25, the result shall be:

1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 
1 3 4 3 2 1 1 
1 4 5 5 3 2 1 1 
1 4 7 6 5 3 2 1 1 
1 5 8 9 7 5 3 2 1 1 
1 5 10 11 10 7 5 3 2 1 1 
1 6 12 15 13 11 7 5 3 2 1 1 
1 6 14 18 18 14 11 7 5 3 2 1 1 
1 7 16 23 23 20 15 11 7 5 3 2 1 1 
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 

C

Library: GMP

If we forgo the rows and only want to calculate , using the recurrence relation is a better way. This requires storage for caching instead the -ish for storing all the rows.

#include <stdio.h>
#include <gmp.h>

#define N 100000
mpz_t p[N + 1];

void calc(int n)
{
	mpz_init_set_ui(p[n], 0);

	for (int k = 1; k <= n; k++) {
		int d = n - k * (3 * k - 1) / 2;
		if (d < 0) break;

		if (k&1)mpz_add(p[n], p[n], p[d]);
		else	mpz_sub(p[n], p[n], p[d]);

		d -= k;
		if (d < 0) break;

		if (k&1)mpz_add(p[n], p[n], p[d]);
		else	mpz_sub(p[n], p[n], p[d]);
	}
}

int main(void)
{
	int idx[] = { 23, 123, 1234, 12345, 20000, 30000, 40000, 50000, N, 0 };
	int at = 0;

	mpz_init_set_ui(p[0], 1);

	for (int i = 1; idx[at]; i++) {
		calc(i);
		if (i != idx[at]) continue;

		gmp_printf("%2d:\t%Zd\n", i, p[i]);
		at++;
	}
}
Output:
23:     1255
123:    2552338241
1234:   156978797223733228787865722354959930
12345:  69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
...

C#

Translation of: Python
Translation of: C

(this requires a System.Numerics registry reference)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace NamesOfGod
{
    public class RowSummer
    {
        const int N = 100000;
        public BigInteger[] p;

        private void calc(int n)
            /* Translated from C */
        {
            p[n] = 0;

            for (int k = 1; k <= n; k++)
            {
                int d = n - k * (3 * k - 1) / 2;
                if (d < 0) break;

                if ((k & 1) != 0) p[n] += p[d];
                else p[n] -= p[d];

                d -= k;
                if (d < 0) break;

                if ((k & 1) != 0) p[n] += p[d];
                else p[n] -= p[d];
            }

        }
        public void PrintSums()
            /* translated from C */
        {
            p = new BigInteger[N + 1];
            var idx = new int[] { 23, 123, 1234, 12345, 20000, 30000, 40000, 50000, N, 0 };
            int at = 0;

            p[0] = 1;

            for (int i = 1; idx[at] > 0; i++)
            {
                calc(i);
                if (i != idx[at]) continue;
                Console.WriteLine(i + ":\t" + p[i]);
                at++;
            }
        }
    }

    public class RowPrinter
        /* translated from Python */
    {
        List<List<int>> cache;
        public RowPrinter()
        {
            cache = new List<List<int>> { new List<int> { 1 } };
        }
        public List<int> cumu(int n)
        {
            for (int l = cache.Count; l < n + 1; l++)
            {
                var r = new List<int> { 0 };
                for (int x = 1; x < l + 1; x++)
                    r.Add(r.Last() + cache[l - x][Math.Min(x, l - x)]);
                cache.Add(r);
            }
            return cache[n];
        }
        public List<int> row(int n)
        {
            var r = cumu(n);
            return (from i in Enumerable.Range(0, n) select r[i + 1] - r[i]).ToList();
        }
        public void PrintRows()
        {
            var rows = Enumerable.Range(1, 25).Select(x => string.Join(" ", row(x))).ToList();
            var widest = rows.Last().Length;
            foreach (var r in rows)
                Console.WriteLine(new String(' ', (widest - r.Length) / 2) + r);
        }
    }

    class Program
    {
        static void Main(string[] args) 
        {
            var rpr = new RowPrinter();
            rpr.PrintRows();
            var ros = new RowSummer();
            ros.PrintSums();
            Console.ReadLine();
        }
    }
}
Output:
                                     1
                                    1 1
                                   1 1 1
                                  1 2 1 1
                                 1 2 2 1 1
                                1 3 3 2 1 1
                               1 3 4 3 2 1 1
                              1 4 5 5 3 2 1 1
                             1 4 7 6 5 3 2 1 1
                            1 5 8 9 7 5 3 2 1 1
                          1 5 10 11 10 7 5 3 2 1 1
                        1 6 12 15 13 11 7 5 3 2 1 1
                       1 6 14 18 18 14 11 7 5 3 2 1 1
                     1 7 16 23 23 20 15 11 7 5 3 2 1 1
                    1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
                  1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
                 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
               1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
              1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
            1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
         1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
       1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
     1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
  1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
23:     1255
123:    2552338241
1234:   156978797223733228787865722354959930
12345:  69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
20000:  252114813812529697916619533230470452281328949601811593436850314108034284423801564956623970731689824369192324789351994903016411826230578166735959242113097
30000:  42963584246325385174883157483005920912690248645401139066014480612764163986215458185192990173314832179564211367228855321718015074490598095469727784182254987592569621576375743614022636192786
40000:  22807728274470728289340571240816959704646220378351611859439499408672657828590548093703330014605000554127042566412316061732771683740688051264237478893869163586426487354600342477491620506603389595232890082673857997469797
50000:  3626186097141667844592140891595633728165383082527785049015872755414109904256712082718122747316610565824630881772910217544261659239432670671532413858378256188987333877121891586607957389750538447474712592979263719012461858719791627302489739548263
100000: 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519

C++

The Code

see [The Green Triangle].

// Calculate hypotenuse n of OTT assuming only nothingness, unity, and hyp[n-1] if n>1
// Nigel Galloway, May 6th., 2013
#include <gmpxx.h>
int N{123456};
mpz_class hyp[N-3];
const mpz_class G(const int n,const int g){return g>n?0:(g==1 or n-g<2)?1:hyp[n-g-2];};
void G_hyp(const int n){for(int i=0;i<N-2*n-1;i++) n==1?hyp[n-1+i]=1+G(i+n+1,n+1):hyp[n-1+i]+=G(i+n+1,n+1);}
}

The Alpha and Omega, Beauty

Before displaying the triangle the following code displays hyp as it is transformed by consequtive calls of G_hyp.

#include <iostream>
#include <iomanip>
int main(){
  N=25;
  for (int n=1; n<N/2; n++){
    G_hyp(n);
    for (int g=0; g<N-3; g++) std::cout << std::setw(4) << hyp[g];
    std::cout << std::endl;
  }
}
Output:
   2   2   3   3   4   4   5   5   6   6   7   7   8   8   9   9  10  10  11  11  12  12
   2   3   4   5   7   8  10  12  14  16  19  21  24  27  30  33  37  40  44  48  52  12
   2   3   5   6   9  11  15  18  23  27  34  39  47  54  64  72  84  94 108 120  52  12
   2   3   5   7  10  13  18  23  30  37  47  57  70  84 101 119 141 164 192 120  52  12
   2   3   5   7  11  14  20  26  35  44  58  71  90 110 136 163 199 235 192 120  52  12
   2   3   5   7  11  15  21  28  38  49  65  82 105 131 164 201 248 235 192 120  52  12
   2   3   5   7  11  15  22  29  40  52  70  89 116 146 186 230 248 235 192 120  52  12
   2   3   5   7  11  15  22  30  41  54  73  94 123 157 201 230 248 235 192 120  52  12
   2   3   5   7  11  15  22  30  42  55  75  97 128 164 201 230 248 235 192 120  52  12
   2   3   5   7  11  15  22  30  42  56  76  99 131 164 201 230 248 235 192 120  52  12
   2   3   5   7  11  15  22  30  42  56  77 100 131 164 201 230 248 235 192 120  52  12
The first row is the hypotenuse of the green triangle.
The second row cols 2 to 21 is the hypotenuse 1 in. Col 1 is the last entry in the horizontal edge of the grey triangle. Col 22 is the first entry of the horizontal edge of the green triangle.
With subsequent calls the horizontal edges expand until, on the final row, the sequence of hypotenuses is finished and hyp contains the horizontal edge of the OTT.

This must be the most beautiful thing on rosettacode!!! Note that the algorithm requires only this data, and requires only N/2 iterations with the nth iteration performing N-3-2*n calculations.

The One True Triangle, OTT

The following will display OTT(25).

int main(){
  N = 25;
  std::cout << std::setw(N+52) << "1" << std::endl;
  std::cout << std::setw(N+55) << "1     1" << std::endl;
  std::cout << std::setw(N+58) << "1     1     1" << std::endl;
  std::string ott[N-3];
  for (int n=1; n<N/2; n++) {
    G_hyp(n);
    for (int g=(n-1)*2; g<N-3; g++) {
      std::string t = hyp[g-(n-1)].get_str();
      //if (t.size()==1) t.insert(t.begin(),1,' ');
      ott[g].append(t);
      ott[g].append(6-t.size(),' ');
    }
  }
  for(int n = 0; n<N-3; n++) {
    std::cout <<std::setw(N+43-3*n) << 1 << "     " << ott[n];
    for (int g = (n+1)/2; g>0; g--) {
      std::string t{hyp[g-1].get_str()};
      t.append(6-t.size(),' ');
      std::cout << t;
    }
    std::cout << "1     1" << std::endl; 
  }
Output:
                                                                            1
                                                                         1     1
                                                                      1     1     1
                                                                   1     2     1     1
                                                                1     2     2     1     1
                                                             1     3     3     2     1     1
                                                          1     3     4     3     2     1     1
                                                       1     4     5     5     3     2     1     1
                                                    1     4     7     6     5     3     2     1     1
                                                 1     5     8     9     7     5     3     2     1     1
                                              1     5     10    11    10    7     5     3     2     1     1
                                           1     6     12    15    13    11    7     5     3     2     1     1
                                        1     6     14    18    18    14    11    7     5     3     2     1     1
                                     1     7     16    23    23    20    15    11    7     5     3     2     1     1
                                  1     7     19    27    30    26    21    15    11    7     5     3     2     1     1
                               1     8     21    34    37    35    28    22    15    11    7     5     3     2     1     1
                            1     8     24    39    47    44    38    29    22    15    11    7     5     3     2     1     1
                         1     9     27    47    57    58    49    40    30    22    15    11    7     5     3     2     1     1
                      1     9     30    54    70    71    65    52    41    30    22    15    11    7     5     3     2     1     1
                   1     10    33    64    84    90    82    70    54    42    30    22    15    11    7     5     3     2     1     1
                1     10    37    72    101   110   105   89    73    55    42    30    22    15    11    7     5     3     2     1     1
             1     11    40    84    119   136   131   116   94    75    56    42    30    22    15    11    7     5     3     2     1     1
          1     11    44    94    141   163   164   146   123   97    76    56    42    30    22    15    11    7     5     3     2     1     1
       1     12    48    108   164   199   201   186   157   128   99    77    56    42    30    22    15    11    7     5     3     2     1     1
    1     12    52    120   192   235   248   230   201   164   131   100   77    56    42    30    22    15    11    7     5     3     2     1     1

Values of Integer Partition Function

Values of the Integer Partition function may be extracted as follows:

#include <iostream>
int main(){
  for (int n=1; n<N/2; n++) G_hyp(n);
  std::cout << "G(23)     = " << hyp[21] << std::endl;
  std::cout << "G(123)    = " << hyp[121] << std::endl;
  std::cout << "G(1234)   = " << hyp[1232] << std::endl;
  std::cout << "G(12345)  = " << hyp[12343] << std::endl;
  mpz_class r{3};
  for (int i = 0; i<N-3; i++) r += hyp[i];
  std::cout << "G(123456) = " << r << std::endl;
}
Output:
G(23)     = 1255
G(123)    = 2552338241
G(1234)   = 156978797223733228787865722354959930
G(12345)  = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
G(123456) = 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989

Clojure

(defn nine-billion-names [row column]
  (cond (<= row 0) 0
        (<= column 0) 0
        (< row column) 0
        (= row 1) 1
        :else (let [addend (nine-billion-names (dec row) (dec column))
                    augend (nine-billion-names (- row column) column)]
	            (+ addend augend))))

(defn print-row [row]
  (doseq [x (range 1 (inc row))]
    (print (nine-billion-names row x) \space)) 
    (println))

(defn print-triangle [rows]
  (doseq [x (range 1 (inc rows))]
    (print-row x)))

(print-triangle 25)

Common Lisp

(defun 9-billion-names (row column)
  (cond ((<= row 0) 0)
        ((<= column 0) 0)
	((< row column) 0)
	((equal row 1) 1)
	(t (let ((addend (9-billion-names (1- row) (1- column)))
		 (augend (9-billion-names (- row column) column)))
	     (+ addend augend)))))
			     
(defun 9-billion-names-triangle (rows)
  (loop for row from 1 to rows
     collect (loop for column from 1 to row
		collect (9-billion-names row column))))

(9-billion-names-triangle 25)

Crystal

Translation of: Ruby

Naive Solution

def g(n, g)
  return 1 unless 1 < g && g < n-1
  (2..g).reduce(1){ |res, q| res + (q > n-g ? 0 : g(n-g, q)) }
end
 
(1..25).each { |n| puts (1..n).map { |g| "%4s" % g(n, g) }.join }
Output:
   1
   1   1
   1   1   1
   1   2   1   1
   1   2   2   1   1
   1   3   3   2   1   1
   1   3   4   3   2   1   1
   1   4   5   5   3   2   1   1
   1   4   7   6   5   3   2   1   1
   1   5   8   9   7   5   3   2   1   1
   1   5  10  11  10   7   5   3   2   1   1
   1   6  12  15  13  11   7   5   3   2   1   1
   1   6  14  18  18  14  11   7   5   3   2   1   1
   1   7  16  23  23  20  15  11   7   5   3   2   1   1
   1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
   1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
   1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
   1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
   1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
   1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
   1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
   1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
   1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
   1  12  48 108 164 199 201 186 157 128  99  77  56  42  30  22  15  11   7   5   3   2   1   1
   1  12  52 120 192 235 248 230 201 164 131 100  77  56  42  30  22  15  11   7   5   3   2   1   1

D

Producing rows

Translation of: Python
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);
}
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


Only partition functions

Translation of: C
import std.stdio, std.bigint, std.algorithm;

struct Names {
    BigInt[] p = [1.BigInt];

    int opApply(int delegate(ref immutable int, ref BigInt) dg) {
        int result;

        foreach (immutable n; 1 .. int.max) {
            p.assumeSafeAppend;
            p ~= 0.BigInt;

            foreach (immutable k; 1 .. n + 1) {
                auto d = n - k * (3 * k - 1) / 2;
                if (d < 0)
                    break;

                if (k & 1)
                    p[n] += p[d];
                else
                    p[n] -= p[d];

                d -= k;
                if (d < 0)
                    break;

                if (k & 1)
                    p[n] += p[d];
                else
                    p[n] -= p[d];
            }

            result = dg(n, p[n]);
            if (result) break;
        }

        return result;
    }
}

void main() {
    immutable ns = [23:0, 123:0, 1234:0, 12345:0];
    immutable maxNs = ns.byKey.reduce!max;

    foreach (immutable i, p; Names()) {
        if (i > maxNs)
            break;
        if (i in ns)
            writefln("%6d: %s", i, p);
    }
}
Output:
    23: 1255
   123: 2552338241
  1234: 156978797223733228787865722354959930
 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
Output:
for a larger input, with newlines
123456: 
3081765957853649667854531714653398085529661327450713921760877
6782063054452191537379312358383342446230621170608408020911309
2594076112571516833722219251283883871684519438000271280453696
5089022006090149454045908154544502080872691737169910282550803
9173543836338081612528477859613355349851184591540231790254269
9482787265485706601456910768199129721622629021508868189865551
27204165221706149989

Runtime up to 123456: about 56 seconds (about 50 with ldc2) because currently std.bigint is not fast.

Dart

Works with: Dart version 2
Translation of: Python
import 'dart:math';

List<BigInt> partitions(int n) {
  var cache = List<List<BigInt>>.filled(1, List<BigInt>.filled(1, BigInt.from(1)), growable: true);
  for(int length = cache.length; length < n + 1; length++) {
    var row = List<BigInt>.filled(1, BigInt.from(0), growable: true);
    for(int index = 1; index < length + 1; index++) {
      var partAtIndex = row[row.length - 1] + cache[length - index][min(index, length - index)];
      row.add(partAtIndex);
    }
    cache.add(row);
  }
  return cache[n];
}

List<BigInt> row(int n) {
  var parts = partitions(n);
  return List<BigInt>.generate(n, (int index) => parts[index + 1] - parts[index]);
}

void printRows({int min = 1, int max = 11}) {
  int maxDigits = max.toString().length;
  print('Rows:');
  for(int i in List.generate(max - min, (int index) => index + min)) {
    print((' ' * (maxDigits - i.toString().length)) + '$i: ${row(i)}');
  }
}

void printSums(List<int> args) {
  print('Sums:');
  for(int i in args) {
    print('$i: ${partitions(i)[i]}');
  }
}

In main:

 import 'package:DD1_NamesOfGod/DD1_NamesOfGod.dart' as names_of_god;

main(List<String> arguments) {
  names_of_god.printRows(min: 1, max: 11);
  names_of_god.printSums([23, 123, 1234, 12345]);
}
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
12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Dyalect

var cache = [[1]]
 
func namesOfGod(n) {
    for l in cache.Length()..n {
        var r = [0]
        if l == 1 {
            r.Add(r[r.Length() - 1] + cache[0][0])
        } else {
            for x in 1..l {
                r.Add(r[r.Length() - 1] + cache[l - x][min(x, l-x)])
            }
        }
        cache.Add(r)
    }
    return cache[n]
}
 
func row(n) {
    let r = namesOfGod(n)
    var xs = []
    for i in 0..<n {
        xs.Add(r[i + 1] - r[i])
    }
    return xs
}
 
for x in 1..25 {
    print("\(x): \(row(x))")
}

Output:

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]
11: [1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
12: [1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
13: [1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
14: [1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
15: [1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]
16: [1, 8, 21, 34, 37, 35, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1]
17: [1, 8, 24, 39, 47, 44, 38, 29, 22, 15, 11, 7, 5, 3, 2, 1, 1]
18: [1, 9, 27, 47, 57, 58, 49, 40, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
19: [1, 9, 30, 54, 70, 71, 65, 52, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
20: [1, 10, 33, 64, 84, 90, 82, 70, 54, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
21: [1, 10, 37, 72, 101, 110, 105, 89, 73, 55, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
22: [1, 11, 40, 84, 119, 136, 131, 116, 94, 75, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
23: [1, 11, 44, 94, 141, 163, 164, 146, 123, 97, 76, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
24: [1, 12, 48, 108, 164, 199, 201, 186, 157, 128, 99, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
25: [1, 12, 52, 120, 192, 235, 248, 230, 201, 164, 131, 100, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]

Elixir

Translation of: Ruby

Naive Solution

defmodule God do
  def g(n,g) when g == 1 or n < g, do: 1
  def g(n,g) do
    Enum.reduce(2..g, 1, fn q,res ->
      res + (if q > n-g, do: 0, else: g(n-g,q))
    end)
  end
end

Enum.each(1..25, fn n ->
  IO.puts Enum.map(1..n, fn g -> "#{God.g(n,g)} " end)
end)
Output:
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1
1 7 16 23 23 20 15 11 7 5 3 2 1 1
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

Erlang

Step 1: Print the pyramid for a smallish number of names. The P function is implement as described on partition function, (see 59 on that page). This is slow for N > 100, but works fine for the example: 10.

-module(triangle).
-export([start/1]).
start(N)->
  print(1,1,N).
print(N,N,N)->
1;
print(A,B,N) when A>=B->
   io:format("~p ",[formula(A,B)]),
   print(A,B+1,N);
print(A,B,N) when B>A->
   io:format("~n"),
   print(A+1,1,N).

formula(_,0)->
  0;
formula(B,B)->
  1;
formula(A,B) when B>A->
  0;
formula(A1,B1)->
  formula(A1-1,B1-1)+formula(A1-B1,B1).
Output:

If user inputs 25, the result shall be:

1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 
1 3 4 3 2 1 1 
1 4 5 5 3 2 1 1 
1 4 7 6 5 3 2 1 1 
1 5 8 9 7 5 3 2 1 1 
1 5 10 11 10 7 5 3 2 1 1 
1 6 12 15 13 11 7 5 3 2 1 1 
1 6 14 18 18 14 11 7 5 3 2 1 1 
1 7 16 23 23 20 15 11 7 5 3 2 1 1 
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 

Factor

Works with: Factor version 0.99 2020-01-23
USING: combinators io kernel math math.ranges memoize prettyprint
sequences ;

MEMO: p ( m n -- o )
    {
        { [ dup zero? ] [ nip ] }
        { [ 2dup = ] [ 2drop 1 ] }
        { [ 2dup < ] [ 2drop 0 ] }
        [ [ [ 1 - ] bi@ p ] [ [ - ] [ ] bi p + ] 2bi ]
    } cond ;

: row ( n -- seq ) dup [1,b] [ p ] with map ;

: .row ( n -- ) row [ pprint bl ] each nl ;

: .triangle ( n -- ) [1,b] [ .row ] each ;

: G ( n -- sum ) row sum ;

25 .triangle nl
"Sums:" print { 23 123 1234 12345 } [ dup pprint bl G . ] each
Output:
1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 
1 3 4 3 2 1 1 
1 4 5 5 3 2 1 1 
1 4 7 6 5 3 2 1 1 
1 5 8 9 7 5 3 2 1 1 
1 5 10 11 10 7 5 3 2 1 1 
1 6 12 15 13 11 7 5 3 2 1 1 
1 6 14 18 18 14 11 7 5 3 2 1 1 
1 7 16 23 23 20 15 11 7 5 3 2 1 1 
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 

Sums:
23 1255
123 2552338241
1234 156978797223733228787865722354959930
^C

Forth

NEEDS -xopg
ANEW -nbnog \ The Nine Billion Names of God
.arbitrary.p

#100000 =: N  
CREATE idx[ #23 , #123 , #1234 , #12345 , #20000 , #30000 , #40000 , #50000 , N , 0 ,
N GARRAY p

: CALC ( n -- )
	0 LOCALS| d n |
	n 1+ 1 ?DO  I 3 * 1-  I 2 */  n SWAP -  TO d   d 0< ?LEAVE
		    I 1 AND IF  LET p[n]=p[n]+p[d]: ELSE  LET p[n]=p[n]-p[d]: ENDIF
		    I -TO d   d 0< ?LEAVE
		    I 1 AND IF  LET p[n]=p[n]+p[d]: ELSE  LET p[n]=p[n]-p[d]: ENDIF
	      LOOP ;

: .GOD ( -- )
	0 LOCAL at  
	LET p[0]=1: N 1 DO  I CALC  
			    idx[ at CELL[] @ I = IF  CR I 5 .R ." : " LET. p[I]:  
			    			     1 +TO at  
			    		      ENDIF  
		      LOOP ;
	
: .ABOUT ( -- ) ." Try: .GOD" ;
Output:
FORTH> .god
   23:  1.2550000000000000000000000000000000000000e+0003
  123:  2.5523382410000000000000000000000000000000e+0009
 1234:  1.5697879722373322878786572235495993000000e+0035
12345:  6.9420357953926116819562977205209384460667e+0118
20000:  2.5211481381252969791661953323047045228132e+0152
30000:  4.2963584246325385174883157483005920912690e+0187
40000:  2.2807728274470728289340571240816959704646e+0217
50000:  3.6261860971416678445921408915956337281653e+0243 ok

FreeBASIC

Library: GMP
' version 03-11-2016
' compile with: fbc -s console

#Include Once "gmp.bi"

Sub partitions(max As ULong, p() As MpZ_ptr)
    ' based on Numericana code example
    Dim As ULong a, b, i, k
    Dim As Long j

    Dim As Mpz_ptr s = Allocate(Len(__mpz_struct)) : Mpz_init(s)

    Mpz_set_ui(p(0), 1)

    For i = 1 To max
        j = 1 : k = 1 : b = 2 : a = 5
        While j > 0
            ' j = i - (3*k*k+k) \ 2
            j = i - b : b = b + a : a = a + 3
            If j >= 0 Then
                If k And 1 Then Mpz_add(s, s, p(j)) Else Mpz_sub(s, s, p(j))
            End If
            j = j + k
            If j >= 0 Then
                If k And 1 Then Mpz_add(s, s, p(j)) Else Mpz_sub(s, s, p(j))
            End If
            k = k +1
        Wend
        Mpz_swap(p(i), s)
    Next

    Mpz_clear(s)

End Sub

' ------=< MAIN >=------

Dim As ULong n, k, max = 25              ' with max > 416 the numbers become
Dim As ULongInt p(max, max)              ' to big for a 64bit unsigned integer         

p(1, 1) = 1                              ' fill the first 3 rows
p(2, 1) = 1 : p(2, 2) = 1
p(3, 1) = 1 : p(3, 2) = 1 : p(3, 3) = 1

For n = 4 To max                         ' fill the rest
    For k = 1 To n
        If k * 2 > n  Then
           p(n,k)= p(n-1,k-1)
        Else 
           p(n,k) = p(n-1,k-1) + p(n-k, k)
        End If
    Next
Next

For n = 1 To 25                          ' print the triangle
    Print Space((max - n) * 2);
    For k = 1 To n
        Print Using "####"; p(n, k);
    Next
    Print
Next
Print : print

                                         ' calculate the integer partition
max = 123456                             ' 1234567 takes about ten minutes
Dim As ZString Ptr ans

ReDim big_p(max) As Mpz_ptr
For n = 0 To max
    big_p(n) = Allocate(Len(__mpz_struct)) : Mpz_init(big_p(n))
Next

partitions(max, big_p())

For n = 1 To Len(Str(max))
    k = Val(Left(Str(max), n))
    ans = Mpz_get_str (0, 10, big_p(k))
    Print Space(10 - n); "P("; Str(k); ") = "; *ans
Next

For n = 0 To max
    Mpz_clear(big_p(n))
Next

' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
                                                   1
                                                 1   1
                                               1   1   1
                                             1   2   1   1
                                           1   2   2   1   1
                                         1   3   3   2   1   1
                                       1   3   4   3   2   1   1
                                     1   4   5   5   3   2   1   1
                                   1   4   7   6   5   3   2   1   1
                                 1   5   8   9   7   5   3   2   1   1
                               1   5  10  11  10   7   5   3   2   1   1
                             1   6  12  15  13  11   7   5   3   2   1   1
                           1   6  14  18  18  14  11   7   5   3   2   1   1
                         1   7  16  23  23  20  15  11   7   5   3   2   1   1
                       1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
                     1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
                   1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
                 1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
               1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
             1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
           1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
         1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
       1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
     1  12  48 108 164 199 201 186 157 128  99  77  56  42  30  22  15  11   7   5   3   2   1   1
   1  12  52 120 192 235 248 230 201 164 131 100  77  56  42  30  22  15  11   7   5   3   2   1   1


         P(1) = 1
        P(12) = 77
       P(123) = 2552338241
      P(1234) = 156978797223733228787865722354959930
     P(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
    P(123456) = 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989

Frink

This demonstrates using a class that memoizes results to improve efficiency and reduce later calculation. It verifies its results against Frink's built-in and much more memory-and-space-efficient partitionCount function which uses Euler's pentagonal method for counting partitions.

class PartitionCount
{
   // Array of elements
   class var triangle = [[0],[0,1]]

   // Array of cumulative sums in each row.
   class var sumTriangle = [[1],[0,1]]

   class calcRowsTo[toRow] :=
   {
      for row = length[triangle] to toRow
      {
         triangle@row = workrow = new array[[row+1],0]
         sumTriangle@row = sumworkrow = new array[[row+1],0]
         oversum = 0
         for col = 1 to row
         {
            otherRow = row-col
            sum = sumTriangle@otherRow@min[col,otherRow]
            workrow@col = sum
            oversum = oversum + sum
            sumworkrow@col = oversum
         }
      }
   }

   class rowSum[row] :=
   {
      calcRowsTo[row]
      return sumTriangle@row@row
   }
}

PartitionCount.calcRowsTo[25]
for row=1 to 25
{
   for col=1 to row
      print[PartitionCount.triangle@row@col + " "]
   println[]
}

// Test against Frink's built-in much faster partitionCount function that uses
// Euler's pentagonal method for counting partitions.
testRow[row] :=
{
   sum = PartitionCount.rowSum[row]
   println["$row\t$sum\t" + (sum == partitionCount[row] ? "correct" : "incorrect")]
}

println[]
testRow[23]
testRow[123]
testRow[1234]
testRow[12345]
1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 
1 3 4 3 2 1 1 
1 4 5 5 3 2 1 1 
1 4 7 6 5 3 2 1 1 
1 5 8 9 7 5 3 2 1 1 
1 5 10 11 10 7 5 3 2 1 1 
1 6 12 15 13 11 7 5 3 2 1 1 
1 6 14 18 18 14 11 7 5 3 2 1 1 
1 7 16 23 23 20 15 11 7 5 3 2 1 1 
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 

23	1255	correct
123	2552338241	correct
1234	156978797223733228787865722354959930	correct
12345	69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736	correct

GAP

The partition function is built-in.

PrintArray(List([1 .. 25], n -> List([1 .. n], k -> NrPartitions(n, k))));

[ [    1 ],
  [    1,    1 ],
  [    1,    1,    1 ],
  [    1,    2,    1,    1 ],
  [    1,    2,    2,    1,    1 ],
  [    1,    3,    3,    2,    1,    1 ],
  [    1,    3,    4,    3,    2,    1,    1 ],
  [    1,    4,    5,    5,    3,    2,    1,    1 ],
  [    1,    4,    7,    6,    5,    3,    2,    1,    1 ],
  [    1,    5,    8,    9,    7,    5,    3,    2,    1,    1 ],
  [    1,    5,   10,   11,   10,    7,    5,    3,    2,    1,    1 ],
  [    1,    6,   12,   15,   13,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    6,   14,   18,   18,   14,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    7,   16,   23,   23,   20,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    7,   19,   27,   30,   26,   21,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    8,   21,   34,   37,   35,   28,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    8,   24,   39,   47,   44,   38,   29,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    9,   27,   47,   57,   58,   49,   40,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,    9,   30,   54,   70,   71,   65,   52,   41,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,   10,   33,   64,   84,   90,   82,   70,   54,   42,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,   10,   37,   72,  101,  110,  105,   89,   73,   55,   42,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,   11,   40,   84,  119,  136,  131,  116,   94,   75,   56,   42,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,   11,   44,   94,  141,  163,  164,  146,  123,   97,   76,   56,   42,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,   12,   48,  108,  164,  199,  201,  186,  157,  128,   99,   77,   56,   42,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ],
  [    1,   12,   52,  120,  192,  235,  248,  230,  201,  164,  131,  100,   77,   56,   42,   30,   22,   15,   11,    7,    5,    3,    2,    1,    1 ] ]


List([23, 123, 1234, 12345], NrPartitions);

[ 1255, 2552338241, 156978797223733228787865722354959930,
  69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 ]

Go

package main

import (
	"fmt"
	"math/big"
)

func main() {

	intMin := func(a, b int) int {
		if a < b {
			return a
		} else {
			return b
		}
	}

	var cache = [][]*big.Int{{big.NewInt(1)}}

	cumu := func(n int) []*big.Int {
		for y := len(cache); y <= n; y++ {
			row := []*big.Int{big.NewInt(0)}
			for x := 1; x <= y; x++ {
				cacheValue := cache[y-x][intMin(x, y-x)]
				row = append(row, big.NewInt(0).Add(row[len(row)-1], cacheValue))
			}
			cache = append(cache, row)
		}
		return cache[n]
	}

	row := func(n int) {
		e := cumu(n)
		for i := 0; i < n; i++ {
			fmt.Printf(" %v ", (big.NewInt(0).Sub(e[i+1], e[i])).Text(10))
		}
		fmt.Println()
	}

	fmt.Println("rows:")
	for x := 1; x < 11; x++ {
		row(x)
	}
	fmt.Println()
	
	fmt.Println("sums:")
	for _, num := range [...]int{23, 123, 1234, 12345} {
		r := cumu(num)
		fmt.Printf("%d %v\n", num, r[len(r)-1].Text(10))
	}
}
Output:
rows:
 1 
 1  1 
 1  1  1 
 1  2  1  1 
 1  2  2  1  1 
 1  3  3  2  1  1 
 1  3  4  3  2  1  1 
 1  4  5  5  3  2  1  1 
 1  4  7  6  5  3  2  1  1 
 1  5  8  9  7  5  3  2  1  1 

 sums:
23 1255 
123 2552338241 
1234 156978797223733228787865722354959930 
12345 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 

Groovy

def partitions(c)
{

    def p=[]; 
    int k = 0;   
     p[k] = c;   
    int counter=0;
    def counts=[];
	for (i in 0..c-1)
	{counts[i]=0;}
    while (true)
    {
     
        counter++;
		counts[p[0]-1]=counts[p[0]-1]+1;
		int rem_val = 0;
        while (k >= 0 && p[k] == 1)
        { rem_val += p[k];
            k--;}
        if (k < 0)  { break;}
        p[k]--;
        rem_val++;
        while (rem_val > p[k])
        {
            p[k+1] = p[k];
            rem_val = rem_val - p[k];
            k++;
        }
        p[k+1] = rem_val;
        k++;
    }
	println counts;
	return counter;
}


static void  main(String[] args)
{
for( i in 1..25 )
{partitions(i);}
}
Output:
[1]
[1, 1]
[1, 1, 1]
[1, 2, 1, 1]
[1, 2, 2, 1, 1]
[1, 3, 3, 2, 1, 1]
[1, 3, 4, 3, 2, 1, 1]
[1, 4, 5, 5, 3, 2, 1, 1]
[1, 4, 7, 6, 5, 3, 2, 1, 1]
[1, 5, 8, 9, 7, 5, 3, 2, 1, 1]
[1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
[1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
[1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
[1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 8, 21, 34, 37, 35, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 8, 24, 39, 47, 44, 38, 29, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 9, 27, 47, 57, 58, 49, 40, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 9, 30, 54, 70, 71, 65, 52, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 10, 33, 64, 84, 90, 82, 70, 54, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 10, 37, 72, 101, 110, 105, 89, 73, 55, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 11, 40, 84, 119, 136, 131, 116, 94, 75, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 11, 44, 94, 141, 163, 164, 146, 123, 97, 76, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 12, 48, 108, 164, 199, 201, 186, 157, 128, 99, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 12, 52, 120, 192, 235, 248, 230, 201, 164, 131, 100, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]


Haskell

import Data.List (mapAccumL)

cumu :: [[Integer]]
cumu = [1] : map (scanl (+) 0) rows

rows :: [[Integer]]
rows = snd $ mapAccumL f [] cumu where
    f r row = (rr, new_row) where
        new_row = map head rr
        rr = map tailKeepOne (row:r)
    tailKeepOne [x] = [x]
    tailKeepOne (_:xs) = xs

sums n = cumu !! n !! n
--curiously, the following seems to be faster
--sums = sum . (rows!!)

main :: IO ()
main = do
    mapM_ print $ take 10 rows
    mapM_ (print.sums) [23, 123, 1234, 12345]
Output:
[1]
[1,1]
[1,1,1]
[1,2,1,1]
[1,2,2,1,1]
[1,3,3,2,1,1]
[1,3,4,3,2,1,1]
[1,4,5,5,3,2,1,1]
[1,4,7,6,5,3,2,1,1]
[1,5,8,9,7,5,3,2,1,1]
1255
2552338241
156978797223733228787865722354959930
^C (probably don't have enough memory for 12345 anyway)

Icon and Unicon

This is a Unicon-specific solution.

Translation of: Python
procedure main(A)
    n := integer(!A) | 10
    every r := 2 to (n+1) do write(right(r-1,2),": ",showList(row(r)))
    write()
    every r := 23 | 123 | 1234 | 12345 do write(r," ",cumu(r+1)[-1])
end

procedure cumu(n)
    static cache
    initial cache := [[1]]
    every l := *cache to n do {
        every (r := [0], x := !l) do put(r, r[-1]+cache[1+l-x][1+min(x,l-x)])
        put(cache, r)
        }
    return cache[n]
end

procedure row(n)
    return (r := cumu(n), [: (i := !(*r-1), r[i+1]-r[i]) :]) | r
end

procedure showList(A)
    every (s := "[") ||:= (!A||", ")
    return s[1:-2]||"]"
end
Output:
(terminated without waiting for output of cumu(12345))
->9bnogti           
 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]

23 1255
123 2552338241
1234 156978797223733228787865722354959930
^C
->

J

Recursive calculation of a row element:

T=: 0:`1:`(($:&<:+ - $: ])`0:@.(0=]))@.(1+*@-) M. "0

Calculation of the triangle:

rows=: <@(#~0<])@({: T ])\@i.

Show triangle:

   ({.~1+1 i:~ '1'=])"1 ":> }.rows 1+10
1                  
1 1                
1 1 1              
1 2 1 1            
1 2 2 1 1          
1 3 3 2 1 1        
1 3 4 3 2 1 1      
1 4 5 5 3 2 1 1    
1 4 7 6 5 3 2 1 1  
1 5 8 9 7 5 3 2 1 1

Note that we've gone to extra work, here, in this show triangle example, to keep columns aligned when we have multi-digit values. But then we limited the result to one digit values because that is prettier.

Calculate row sums:

rowSums=: 3 :0"0
  z=. (y+1){. 1x
  for_ks. <\1+i.y do.
    n=.{: k=.>ks
    r=.#c=. ({.~* i._1:)(n,0.5 _1.5) p. k
    s=.#d=.({.~* i._1:)c-r{.k
    'v i'=.|: \:~(c,d),. r ,&({.&k) s
    a=. +/(n{z),(_1^1x+2|i) * v{z
    z=. a n}z 
  end.
)
Output:
   ({ [: rowSums >./) 3 23 123 1234
3 1255 2552338241 156978797223733228787865722354959930

Java

Translation of Python via D

Works with: Java version 8
import java.math.BigInteger;
import java.util.*;
import static java.util.Arrays.asList;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import static java.lang.Math.min;

public class Test {

    static List<BigInteger> cumu(int n) {
        List<List<BigInteger>> cache = new ArrayList<>();
        cache.add(asList(BigInteger.ONE));

        for (int L = cache.size(); L < n + 1; L++) {
            List<BigInteger> r = new ArrayList<>();
            r.add(BigInteger.ZERO);
            for (int x = 1; x < L + 1; x++)
                r.add(r.get(r.size() - 1).add(cache.get(L - x).get(min(x, L - x))));
            cache.add(r);
        }
        return cache.get(n);
    }

    static List<BigInteger> row(int n) {
        List<BigInteger> r = cumu(n);
        return range(0, n).mapToObj(i -> r.get(i + 1).subtract(r.get(i)))
                .collect(toList());
    }

    public static void main(String[] args) {
        System.out.println("Rows:");
        for (int x = 1; x < 11; x++)
            System.out.printf("%2d: %s%n", x, row(x));

        System.out.println("\nSums:");
        for (int x : new int[]{23, 123, 1234}) {
            List<BigInteger> c = cumu(x);
            System.out.printf("%s %s%n", x, c.get(c.size() - 1));
        }
    }
}
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

JavaScript

Solution 1

Translation of: Python
(function () {
    var cache = [
        [1]
    ];
//this was never needed.
   /* function PyRange(start, end, step) {
        step = step || 1;
        if (!end) {
            end = start;
            start = 0;
        }
        var arr = [];
        for (var i = start; i < end; i += step) arr.push(i);
        return arr;
    }*/ 

    function cumu(n) {
        var /*ra = PyRange(cache.length, n + 1),*/ //Seems there is a better version for this
            r, l, x, Aa, Mi;
       // for (ll in ra) { too pythony
       for (l=cache.length;l<n+1;l++) {
            r = [0];
//            l = ra[ll];
//            ran = PyRange(1, l + 1);
//            for (xx in ran) {
            for(x=1;x<l+1;x++){
//                x = ran[xx];
                r.push(r[r.length - 1] + (Aa = cache[l - x < 0 ? cache.length - (l - x) : l - x])[(Mi = Math.min(x, l - x)) < 0 ? Aa.length - Mi : Mi]);
            }
            cache.push(r);
        }
        return cache[n];
    }

    function row(n) {
        var r = cumu(n),
//            rra = PyRange(n),
            leArray = [],
            i;
//        for (ii in rra) {
        for (i=0;i<n;i++) {
//            i = rra[ii];
            leArray.push(r[i + 1] - r[i]);
        }
        return leArray;
    }

    console.log("Rows:");
    for (iterator = 1; iterator < 12; iterator++) {
        console.log(row(iterator));
    }

// PL clearly this was not tested:
//    console.log("Sums")[23, 123, 1234, 12345].foreach(function (a) {
    console.log("Sums");
    [23, 123, 1234, 12345].forEach(function (a) {
        var s = cumu(a);
        console.log(a, s[s.length - 1]);
    });
})()

Solution 2

Clean and straightforward solution

function genTriangle(n){ // O(n^3) time and O(n^2) space
    var a = new Array(n)
    
    for (let i = 0; i < n; i++){
        a[i] = new Array(i+1)
        for (let j = 0; j < i; j++){
            a[i][j] = 0
            let s = i-j-1, k = Math.min(s, j)
            while (k >= 0) a[i][j] += a[s][k--]
        }
        a[i][i] = 1
    }
    
    return a.map(x => x.join(" ")).join("\n")
}

function G(n){ // At least O(n^2) time and O(n) space
    var a = new Array(n+1)
    a[0] = 1n
    
    for (let i = 1; i <= n; i++){
        a[i] = 0n
        for (let k = 1, s = 1; s <= i;){
            a[i] += (k & 1 ? a[i-s]:-a[i-s])
            k > 0 ? (s += k, k = -k):(k = -k+1, s = k*(3*k-1)/2)
        }
    }
    
    return a[n]
}

console.log(genTriangle(25))
console.log("")

for (const x of [23, 123, 1234, 12345]){
    console.log("G(" + x + ") = " + G(x))
}
Output:
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1
1 7 16 23 23 20 15 11 7 5 3 2 1 1
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

G(23) = 1255
G(123) = 2552338241
G(1234) = 156978797223733228787865722354959930
G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

jq

Adapted from Wren

Works with gojq, the Go implementation of jq, and with fq.

This entry uses the same algorithm as Wren, but on my 16GM RAM machine, wren version 0.4.0 runs out of memory computing P(12345), so that goal has been excluded here.

The integer arithmetic supported by the C implementation of jq lacks the precision required for computing P(1234) accurately, so the output shown below is based on a run of gojq.

The values shown in the output agree with those obtained using the programs at Partition_function_P#jq.

def cumu:
  . as $n
  | reduce range(1; $n+1) as $l ( {cache: [[1]]};
      .r = [0]
      | reduce range(1; $l+1) as $x (.;
          .min = $l - $x
          | if ($x < .min) then .min = $x else . end
          | .r = .r + [.r[-1] + .cache[$l - $x][.min] ] )
      | .cache = .cache + [.r] )
  | .cache[$n] ;

def row:
  cumu as $r
  | reduce range(0; .) as $i ([]; . + [$r[$i+1] - $r[$i]] );

def task:
  "Rows:",
  (range(1; 26) |  [ ., row]),
  "\nSums:",
  ( (23, 123, 1234)   #  12345 is a stretch for memory even using wren
   | [., cumu[-1]] ) ;

Invocation: gojq -n -rcf 9-billion.jq

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]]
[11,[1,5,10,11,10,7,5,3,2,1,1]]
[12,[1,6,12,15,13,11,7,5,3,2,1,1]]
[13,[1,6,14,18,18,14,11,7,5,3,2,1,1]]
[14,[1,7,16,23,23,20,15,11,7,5,3,2,1,1]]
[15,[1,7,19,27,30,26,21,15,11,7,5,3,2,1,1]]
[16,[1,8,21,34,37,35,28,22,15,11,7,5,3,2,1,1]]
[17,[1,8,24,39,47,44,38,29,22,15,11,7,5,3,2,1,1]]
[18,[1,9,27,47,57,58,49,40,30,22,15,11,7,5,3,2,1,1]]
[19,[1,9,30,54,70,71,65,52,41,30,22,15,11,7,5,3,2,1,1]]
[20,[1,10,33,64,84,90,82,70,54,42,30,22,15,11,7,5,3,2,1,1]]
[21,[1,10,37,72,101,110,105,89,73,55,42,30,22,15,11,7,5,3,2,1,1]]
[22,[1,11,40,84,119,136,131,116,94,75,56,42,30,22,15,11,7,5,3,2,1,1]]
[23,[1,11,44,94,141,163,164,146,123,97,76,56,42,30,22,15,11,7,5,3,2,1,1]]
[24,[1,12,48,108,164,199,201,186,157,128,99,77,56,42,30,22,15,11,7,5,3,2,1,1]]
[25,[1,12,52,120,192,235,248,230,201,164,131,100,77,56,42,30,22,15,11,7,5,3,2,1,1]]

Sums:
[23,1255]
[123,2552338241]
[1234,156978797223733228787865722354959930]


Julia

using Combinatorics, StatsBase

namesofline(n) = counts([x[1] for x in integer_partitions(n)])

function centerjustpyramid(n)
    maxwidth = length(string(namesofline(n)))
    for i in 1:n
        s = string(namesofline(i))
        println(" " ^ div(maxwidth - length(s), 2), s)
    end
end

centerjustpyramid(25)

const cachecountpartitions = Dict{BigInt,BigInt}()
function countpartitions(n::BigInt)
    if n < 0
        0
    elseif n < 2
        1
    elseif (np = get(cachecountpartitions, n, 0)) > 0
        np
    else
        np = 0
        sgn = 1
        for k = 1:n
            np += sgn * (countpartitions(n - (k*(3k-1)) >> 1) + countpartitions(n - (k*(3k+1)) >> 1))
            sgn = -sgn
        end
        cachecountpartitions[n] = np
    end
end

G(n) = countpartitions(BigInt(n))

for g in [23, 123, 1234, 12345]
    @time println("\nG($g) is $(G(g))")
end
Output:

                                                [1]
                                               [1, 1]
                                             [1, 1, 1]
                                            [1, 2, 1, 1]
                                          [1, 2, 2, 1, 1]
                                         [1, 3, 3, 2, 1, 1]
                                       [1, 3, 4, 3, 2, 1, 1]
                                      [1, 4, 5, 5, 3, 2, 1, 1]
                                    [1, 4, 7, 6, 5, 3, 2, 1, 1]
                                   [1, 5, 8, 9, 7, 5, 3, 2, 1, 1]
                                [1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
                              [1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
                            [1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
                          [1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
                        [1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]
                      [1, 8, 21, 34, 37, 35, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1]
                    [1, 8, 24, 39, 47, 44, 38, 29, 22, 15, 11, 7, 5, 3, 2, 1, 1]
                  [1, 9, 27, 47, 57, 58, 49, 40, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
                [1, 9, 30, 54, 70, 71, 65, 52, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
             [1, 10, 33, 64, 84, 90, 82, 70, 54, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
          [1, 10, 37, 72, 101, 110, 105, 89, 73, 55, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
       [1, 11, 40, 84, 119, 136, 131, 116, 94, 75, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
     [1, 11, 44, 94, 141, 163, 164, 146, 123, 97, 76, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
  [1, 12, 48, 108, 164, 199, 201, 186, 157, 128, 99, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]

[1, 12, 52, 120, 192, 235, 248, 230, 201, 164, 131, 100, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]

G(23) is 1255

 0.043878 seconds (82.76 k allocations: 3.730 MiB)

G(123) is 2552338241

 0.064343 seconds (435.68 k allocations: 7.199 MiB)

G(1234) is 156978797223733228787865722354959930

 6.439370 seconds (43.57 M allocations: 723.421 MiB, 30.61% gc time)

G(12345) is 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 691.453611 seconds (4.32 G allocations: 71.973 GiB, 33.18% gc time)

Kotlin

Translation of: Swift
import java.lang.Math.min
import java.math.BigInteger
import java.util.ArrayList
import java.util.Arrays.asList

fun namesOfGod(n: Int): List<BigInteger> {
    val cache = ArrayList<List<BigInteger>>()
    cache.add(asList(BigInteger.ONE))

    (cache.size..n).forEach { l ->
        val r = ArrayList<BigInteger>()
        r.add(BigInteger.ZERO)

        (1..l).forEach { x ->
            r.add(r[r.size - 1] + cache[l - x][min(x, l - x)])
        }
        cache.add(r)
    }
    return cache[n]
}

fun row(n: Int) = namesOfGod(n).let { r -> (0 until n).map { r[it + 1] - r[it] } }

fun main(args: Array<String>) {
    println("Rows:")
    (1..25).forEach {
        System.out.printf("%2d: %s%n", it, row(it))
    }

    println("\nSums:")
    intArrayOf(23, 123, 1234, 1234).forEach {
        val c = namesOfGod(it)
        System.out.printf("%s %s%n", it, c[c.size - 1])
    }
}
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]
11: [1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
12: [1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
13: [1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
14: [1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
15: [1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]
16: [1, 8, 21, 34, 37, 35, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1]
17: [1, 8, 24, 39, 47, 44, 38, 29, 22, 15, 11, 7, 5, 3, 2, 1, 1]
18: [1, 9, 27, 47, 57, 58, 49, 40, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
19: [1, 9, 30, 54, 70, 71, 65, 52, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
20: [1, 10, 33, 64, 84, 90, 82, 70, 54, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
21: [1, 10, 37, 72, 101, 110, 105, 89, 73, 55, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
22: [1, 11, 40, 84, 119, 136, 131, 116, 94, 75, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
23: [1, 11, 44, 94, 141, 163, 164, 146, 123, 97, 76, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
24: [1, 12, 48, 108, 164, 199, 201, 186, 157, 128, 99, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
25: [1, 12, 52, 120, 192, 235, 248, 230, 201, 164, 131, 100, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]

Sums:
23 1255
123 2552338241
1234 156978797223733228787865722354959930

Lasso

This code is derived from the Python solution, as an illustration of the difference in array behaviour (indexes, syntax), and loop and query expression as alternative syntax to "for".

define cumu(n::integer) => {
	loop(-from=$cache->size,-to=#n+1) => {
		local(r = array(0), l = loop_count)
		loop(loop_count) => {
			protect => { #r->insert(#r->last + $cache->get(#l - loop_count)->get(math_min(loop_count+1, #l - loop_count))) }
		}
		#r->size > 1 ? $cache->insert(#r)
	}
	return $cache->get(#n)
}
define row(n::integer) => {
	// cache gets reset & rebuilt for each row, slower but more accurate
	var(cache = array(array(1))) 
	local(r = cumu(#n+1))
	local(o = array)
	loop(#n) => {
		protect => { #o->insert(#r->get(loop_count+1) - #r->get(loop_count)) }
	}	
	return #o
}
'rows:\r'
loop(25) => {^
	loop_count + ': '+ row(loop_count)->join(' ') + '\r'
^}

'sums:\r'
with x in array(23, 123, 1234) do => {^
	var(cache = array(array(1))) 
	cumu(#x+1)->last
	'\r'
^}
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
11: 1 5 10 11 10 7 5 3 2 1 1
12: 1 6 12 15 13 11 7 5 3 2 1 1
13: 1 6 14 18 18 14 11 7 5 3 2 1 1
14: 1 7 16 23 23 20 15 11 7 5 3 2 1 1
15: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
16: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
17: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
18: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
19: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
20: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
21: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
22: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
23: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
24: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
25: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

sums:
23: 1255
123: 2552338241
1234: 156978797223733228787865722354959930
12345: (ran long, timed out)

Lua

function nog(n)
  local tri = {{1}}
  for r = 2, n do
    tri[r] = {}
    for c = 1, r do
      tri[r][c] = (tri[r-1][c-1] or 0) + (tri[r-c] and tri[r-c][c] or 0)
    end
  end
  return tri
end

function G(n)
  local tri, sum = nog(n), 0
  for _, v in ipairs(tri[n]) do sum = sum + v end
  return sum
end

tri = nog(25)
for i, row in ipairs(tri) do
  print(i .. ":  " .. table.concat(row, " "))
end
print("G(23) = " .. G(23))
print("G(123) = " .. G(123))
Output:
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
11:  1 5 10 11 10 7 5 3 2 1 1
12:  1 6 12 15 13 11 7 5 3 2 1 1
13:  1 6 14 18 18 14 11 7 5 3 2 1 1
14:  1 7 16 23 23 20 15 11 7 5 3 2 1 1
15:  1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
16:  1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
17:  1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
18:  1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
19:  1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
20:  1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
21:  1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
22:  1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
23:  1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
24:  1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
25:  1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
G(23) = 1255
G(123) = 2552338241

Maple

TriangleLine(n) := map(rhs, Statistics :- Tally(map(x -> x[-1],  combinat:-partition(n)))):
Triangle := proc(m)  
            local i;  
            for i  from 1 to m do 
                print(op(TriangleLine(i)));  
            end do  
            end proc:
Output:
Triangle(7);
                               1
                              1, 1
                            1, 1, 1
                           1, 2, 1, 1
                         1, 2, 2, 1, 1
                        1, 3, 3, 2, 1, 1
                      1, 3, 4, 3, 2, 1, 1

Mathematica / Wolfram Language

Table[Last /@ Reverse@Tally[First /@ IntegerPartitions[n]], {n, 10}] // Grid
Output:
1									
1	1								
1	1	1							
1	2	1	1						
1	2	2	1	1					
1	3	3	2	1	1				
1	3	4	3	2	1	1			
1	4	5	5	3	2	1	1		
1	4	7	6	5	3	2	1	1	
1	5	8	9	7	5	3	2	1	1

Here I use the bulit-in function PartitionsP to calculate .

PartitionsP /@ {23, 123, 1234, 12345}
Output:
{1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736}
DiscretePlot[PartitionsP[n], {n, 1, 999}, PlotRange -> All]

Maxima

for n thru 25 do print(makelist(length(integer_partitions(n-k,k)),k,1,n))$
Output:
[1] 
[1,1] 
[1,1,1] 
[1,2,1,1] 
[1,2,2,1,1] 
[1,3,3,2,1,1] 
[1,3,4,3,2,1,1] 
[1,4,5,5,3,2,1,1] 
[1,4,7,6,5,3,2,1,1] 
[1,5,8,9,7,5,3,2,1,1] 
[1,5,10,11,10,7,5,3,2,1,1] 
[1,6,12,15,13,11,7,5,3,2,1,1] 
[1,6,14,18,18,14,11,7,5,3,2,1,1] 
[1,7,16,23,23,20,15,11,7,5,3,2,1,1] 
[1,7,19,27,30,26,21,15,11,7,5,3,2,1,1] 
[1,8,21,34,37,35,28,22,15,11,7,5,3,2,1,1] 
[1,8,24,39,47,44,38,29,22,15,11,7,5,3,2,1,1] 
[1,9,27,47,57,58,49,40,30,22,15,11,7,5,3,2,1,1] 
[1,9,30,54,70,71,65,52,41,30,22,15,11,7,5,3,2,1,1] 
[1,10,33,64,84,90,82,70,54,42,30,22,15,11,7,5,3,2,1,1] 
[1,10,37,72,101,110,105,89,73,55,42,30,22,15,11,7,5,3,2,1,1] 
[1,11,40,84,119,136,131,116,94,75,56,42,30,22,15,11,7,5,3,2,1,1] 
[1,11,44,94,141,163,164,146,123,97,76,56,42,30,22,15,11,7,5,3,2,1,1] 
[1,12,48,108,164,199,201,186,157,128,99,77,56,42,30,22,15,11,7,5,3,2,1,1] 
[1,12,52,120,192,235,248,230,201,164,131,100,77,56,42,30,22,15,11,7,5,3,2,1,1]

Using the built-in function to calculate :

makelist(num_partitions(n),n,[23,123,1234,12345]);
Output:
(%o1) [1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736]

Nim

Translation of: Python
import bigints

var cache = @[@[1.initBigInt]]

proc cumu(n: int): seq[BigInt] =
  for m in cache.len .. n:
    var r = @[0.initBigInt]
    for x in 1..m:
      r.add r[r.high] + cache[m-x][min(x, m-x)]
    cache.add r
  result = cache[n]

proc row(n: int): seq[BigInt] =
  let r = cumu n
  result = @[]
  for i in 0 .. <n:
    result.add r[i+1] - r[i]

echo "rows:"
for x in 1..10:
  echo row x

echo "sums:"
for x in [23, 123, 1234, 12345]:
  let c = cumu(x)
  echo x, " ", c[c.high]
Output:
@[1]
@[1, 1]
@[1, 1, 1]
@[1, 2, 1, 1]
@[1, 2, 2, 1, 1]
@[1, 3, 3, 2, 1, 1]
@[1, 3, 4, 3, 2, 1, 1]
@[1, 4, 5, 5, 3, 2, 1, 1]
@[1, 4, 7, 6, 5, 3, 2, 1, 1]
@[1, 5, 8, 9, 7, 5, 3, 2, 1, 1]
sums:
23 1255
123 2552338241
1234 156978797223733228787865722354959930
^C

Faster version:

Translation of: C
import bigints

var p = @[1.initBigInt]

proc partitions(n): BigInt =
  p.add 0.initBigInt

  for k in 1..n:
    var d = n - k * (3 * k - 1) div 2
    if d < 0:
      break

    if (k and 1) != 0:
      p[n] += p[d]
    else:
      p[n] -= p[d]

    d -= k
    if d < 0:
      break

    if (k and 1) != 0:
      p[n] += p[d]
    else:
      p[n] -= p[d]

  result = p[p.high]

const ns = [23, 123, 1234, 12345]
for i in 1 .. max(ns):
  let p = partitions(i)
  if i in ns:
    echo i,": ",p
Output:
23: 1255
123: 2552338241
1234: 156978797223733228787865722354959930
12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

OCaml

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]
Output:
2: 1 
3: 1 1 
4: 1 1 1 
5: 1 2 1 1 
6: 1 2 2 1 1 
7: 1 3 3 2 1 1 
8: 1 3 4 3 2 1 1 
9: 1 4 5 5 3 2 1 1 
10: 1 4 7 6 5 3 2 1 1 
11: 1 5 8 9 7 5 3 2 1 1 
12: 1 5 10 11 10 7 5 3 2 1 1 
13: 1 6 12 15 13 11 7 5 3 2 1 1 
14: 1 6 14 18 18 14 11 7 5 3 2 1 1 
15: 1 7 16 23 23 20 15 11 7 5 3 2 1 1 
16: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
17: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
18: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
19: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
20: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
21: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
22: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
23: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
24: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
25: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
26: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 
27: 1 13 56 136 221 282 300 288 252 212 169 133 101 77 56 42 30 22 15 11 7 5 3 2 1 1 
28: 1 13 61 150 255 331 364 352 318 267 219 172 134 101 77 56 42 30 22 15 11 7 5 3 2 1 1 
29: 1 14 65 169 291 391 436 434 393 340 278 224 174 135 101 77 56 42 30 22 15 11 7 5 3 2 1 1 
30: 1 14 70 185 333 454 522 525 488 423 355 285 227 175 135 101 77 56 42 30 22 15 11 7 5 3 2 1 1 
31: 1 15 75 206 377 532 618 638 598 530 445 366 290 229 176 135 101 77 56 42 30 22 15 11 7 5 3 2 1 1 

23: 1255 ?= 1255
123: 2552338241 ?= 2552338241
1234: 156978797223733228787865722354959930 ?= 156978797223733228787865722354959930
23: 1255
123: 2552338241
1234: 156978797223733228787865722354959930
12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
123456: 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989
./intnames  897.04s user 2.43s system 94% cpu 15:47.77 total

Ol

(define (nine-billion-names row column)
   (cond
      ((<= row 0) 0)
      ((<= column 0) 0)
      ((< row column) 0)
      ((= row 1) 1)
      (else
         (let ((addend (nine-billion-names (- row 1) (- column 1)))
               (augend (nine-billion-names (- row column) column)))
	         (+ addend augend)))))
 
(define (print-row row)
   (for-each (lambda (x)
         (display (nine-billion-names row x))
         (display " "))
      (iota row 1)))
 
(define (print-triangle rows)
   (for-each (lambda (x)
         (print-row x)
         (print))
      (iota rows 1)))
 
(print-triangle 25)
Output:
1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 
1 3 4 3 2 1 1 
1 4 5 5 3 2 1 1 
1 4 7 6 5 3 2 1 1 
1 5 8 9 7 5 3 2 1 1 
1 5 10 11 10 7 5 3 2 1 1 
1 6 12 15 13 11 7 5 3 2 1 1 
1 6 14 18 18 14 11 7 5 3 2 1 1 
1 7 16 23 23 20 15 11 7 5 3 2 1 1 
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

PARI/GP

row(n)=my(v=vector(n)); forpart(i=n,v[i[#i]]++); v;
show(n)=for(k=1,n,print(row(k)));
show(25)
apply(numbpart, [23,123,1234,12345])
plot(x=1,999.9, numbpart(x\1))
Output:
[1]
[1, 1]
[1, 1, 1]
[1, 2, 1, 1]
[1, 2, 2, 1, 1]
[1, 3, 3, 2, 1, 1]
[1, 3, 4, 3, 2, 1, 1]
[1, 4, 5, 5, 3, 2, 1, 1]
[1, 4, 7, 6, 5, 3, 2, 1, 1]
[1, 5, 8, 9, 7, 5, 3, 2, 1, 1]
[1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
[1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
[1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
[1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 8, 21, 34, 37, 35, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 8, 24, 39, 47, 44, 38, 29, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 9, 27, 47, 57, 58, 49, 40, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 9, 30, 54, 70, 71, 65, 52, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 10, 33, 64, 84, 90, 82, 70, 54, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 10, 37, 72, 101, 110, 105, 89, 73, 55, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 11, 40, 84, 119, 136, 131, 116, 94, 75, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2,1, 1]
[1, 11, 44, 94, 141, 163, 164, 146, 123, 97, 76, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 12, 48, 108, 164, 199, 201, 186, 157, 128, 99, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
[1, 12, 52, 120, 192, 235, 248, 230, 201, 164, 131, 100, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]

%1 = [1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736]

2.31e+031 |''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''"
          |                                                              :
          |                                                              :
          |                                                              :
          |                                                              :
          |                                                             :|
          |                                                             :|
          |                                                             :|
          |                                                             :|
          |                                                             _|
          |                                                             :|
          |                                                             :|
          |                                                            : |
          |                                                            : |
          |                                                            : |
          |                                                            x |
          |                                                            : |
          |                                                           :  |
          |                                                           x  |
          |                                                              |
          |                                                         _"   |
        1 ________________________________________________________xx,,,,,,
          1                                                          999.9

Using ploth in place of plot yields a nice image which cannot be uploaded at present.

Perl

Library: ntheory
use ntheory qw/:all/;

sub triangle_row {
  my($n,@row) = (shift);
  # Tally by first element of the unrestricted integer partitions.
  forpart { $row[ $_[0] - 1 ]++ } $n;
  @row;
}

printf "%2d: %s\n", $_, join(" ",triangle_row($_)) for 1..25;
print "\n";
say "P($_) = ", partitions($_) for (23, 123, 1234, 12345);
Output:

[rows are the same as below]

P(23) = 1255
P(123) = 2552338241
P(1234) = 156978797223733228787865722354959930
P(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
Translation of: Raku
use strict;
use warnings;

# Where Raku uses arbitrary precision integers everywhere
# that you don't tell it not to do so, Perl 5 will only use
# them where you *do* tell it do so.
use Math::BigInt;
use constant zero => Math::BigInt->bzero;
use constant one  => Math::BigInt->bone;

my @todo = [one];
my @sums = (zero);
sub nextrow {
   my $n = shift;
   for my $l (@todo .. $n) {
      $sums[$l] = zero;
      #print "$l\r" if $l < $n;
      my @r;
      for my $x (reverse 0 .. $l-1) {
         my $todo = $todo[$x];
         $sums[$x] += shift @$todo if @$todo;
         push @r, $sums[$x];
      }
      push @todo, \@r;
   }
   @{ $todo[$n] };
}

print "rows:\n";
for(1..25) {
   printf("%2d: ", $_);
   print join(' ', nextrow($_)), "\n";
}
print "\nsums:\n";
for (23, 123, 1234, 12345) {
   print $_, "." x (8 - length);
   my $i = 0;
   $i += $_ for nextrow($_);
   print $i, "\n";
}
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
11: 1 5 10 11 10 7 5 3 2 1 1
12: 1 6 12 15 13 11 7 5 3 2 1 1
13: 1 6 14 18 18 14 11 7 5 3 2 1 1
14: 1 7 16 23 23 20 15 11 7 5 3 2 1 1
15: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
16: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
17: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
18: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
19: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
20: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
21: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
22: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
23: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
24: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
25: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

sums:
23......1243
123.....2552338241
1234....156978797223733228787865722354959930
^C

Note: I didn't wait long enough to see what the next result was, and stopped the program.

Phix

-- demo\rosetta\9billionnames.exw
with javascript_semantics 
sequence cache = {{1}}
function cumu(integer n)
sequence r
    for l=length(cache) to n do
        r = {0}
        for x=1 to l do
            r = append(r,r[-1]+cache[l-x+1][min(x,l-x)+1])
        end for
        cache = append(cache,r)
    end for
    return cache[n]
end function
 
function row(integer n)
sequence r = cumu(n+1)
sequence res = repeat(0,n)
    for i=1 to n do
        res[i] = r[i+1]-r[i]
    end for
    return res
end function
 
for i=1 to 25 do
    puts(1,repeat(' ',50-2*i))
    sequence r = row(i)
    for j=1 to i do
        printf(1,"%4d",r[j])
    end for
    puts(1,"\n")
end for
Output:
                                                   1
                                                 1   1
                                               1   1   1
                                             1   2   1   1
                                           1   2   2   1   1
                                         1   3   3   2   1   1
                                       1   3   4   3   2   1   1
                                     1   4   5   5   3   2   1   1
                                   1   4   7   6   5   3   2   1   1
                                 1   5   8   9   7   5   3   2   1   1
                               1   5  10  11  10   7   5   3   2   1   1
                             1   6  12  15  13  11   7   5   3   2   1   1
                           1   6  14  18  18  14  11   7   5   3   2   1   1
                         1   7  16  23  23  20  15  11   7   5   3   2   1   1
                       1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
                     1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
                   1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
                 1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
               1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
             1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
           1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
         1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
       1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
     1  12  48 108 164 199 201 186 157 128  99  77  56  42  30  22  15  11   7   5   3   2   1   1
   1  12  52 120 192 235 248 230 201 164 131 100  77  56  42  30  22  15  11   7   5   3   2   1   1

Part 2

Translation of: C
Library: Phix/mpfr
with javascript_semantics 
include mpfr.e
 
sequence p
 
procedure calc(integer n)
    n += 1
    for k=1 to n-1 do
        integer d = n - k * (3 * k - 1) / 2;
        if d<1 then exit end if
        if and_bits(k,1) then mpz_add(p[n],p[n],p[d])
                         else mpz_sub(p[n],p[n],p[d]) end if
        d -= k;
        if d<1 then exit end if
        if and_bits(k,1) then mpz_add(p[n],p[n],p[d])
                         else mpz_sub(p[n],p[n],p[d]) end if
    end for
end procedure
 
constant cx = {23, 123, 1234, 12345}
puts(1,"sums:\n")
integer at = 1
p = mpz_inits(cx[$]+1)
mpz_set_si(p[1],1)
for i=1 to cx[$] do
    calc(i)
    if i=cx[at] then
        printf(1,"%2d:%s\n",{i,mpz_get_str(p[i+1])})
        at += 1
    end if
end for
Output:
sums:
23:1255
123:2552338241
1234:156978797223733228787865722354959930
12345:69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Third and last, a simple plot

Library: Phix/pGUI
include pGUI.e
IupOpen()
IupControlsOpen()
Ihandle plot = IupPlot("MENUITEMPROPERTIES=Yes, SIZE=640x320")
IupSetAttribute(plot, "TITLE", "9 Billion Names");
IupSetAttribute(plot, "TITLEFONTSIZE", "10");
IupSetAttribute(plot, "TITLEFONTSTYLE", "ITALIC");
IupSetAttribute(plot, "GRIDLINESTYLE", "DOTTED");
IupSetAttribute(plot, "GRID", "YES");
IupSetAttribute(plot, "AXS_XLABEL", "x");
IupSetAttribute(plot, "AXS_YLABEL", "G(x)");
IupSetAttribute(plot, "AXS_XFONTSTYLE", "ITALIC");
IupSetAttribute(plot, "AXS_YFONTSTYLE", "ITALIC");
IupSetAttribute(plot, "AXS_XSCALE", "LOG10");
IupSetAttribute(plot, "AXS_YSCALE", "LOG10");
IupSetAttribute(plot, "AXS_YTICKSIZEAUTO", "NO");
IupSetAttribute(plot, "AXS_YTICKMAJORSIZE", "8");
IupSetAttribute(plot, "AXS_YTICKMINORSIZE", "0");
IupPlotBegin(plot)
for x=1 to 999 do
    IupPlotAdd(plot, x, sum(row(x))) -- (row() from part 1)
end for
{} = IupPlotEnd(plot)
Ihandle dlg = IupDialog(plot)
IupSetAttribute(dlg, "TITLE", "9 Billion Names")
IupMap(dlg)
IupShowXY(dlg,IUP_CENTER,IUP_CENTER)
if platform()!=JS then
    IupMainLoop()
    IupClose()
end if

Phixmonti

Translation of: Yabasic
/# Rosetta Code problem: http://rosettacode.org/wiki/9_billion_names_of_God_the_integer
by Galileo, 05/2022 #/

include ..\Utilitys.pmt

cls
 
def nine_billion_names >ps
    0 ( tps dup ) dim
 
    1 ( 1 1 ) sset
    
    ( 2 tps ) for var i
        ( 1 i ) for var j
            ( i 1 - j 1 - ) sget >ps ( i j - j ) sget ps> + ( i j ) sset
        endfor
    endfor
 
    ( 1 tps ) for var i
        tps 2 * i 2 * 2 - - >ps
        ( 1 i ) for var j
            ( i j ) sget tostr len nip 1 swap - tps j 4 * + + i locate ( i j ) sget print
        endfor
        nl
        ps> drop
    endfor
    ps> drop drop
enddef
 
20 nine_billion_names
Output:
                                           1
                                         1   1
                                       1   1   1
                                     1   2   1   1
                                   1   2   2   1   1
                                 1   3   3   2   1   1
                               1   3   4   3   2   1   1
                             1   4   5   5   3   2   1   1
                           1   4   7   6   5   3   2   1   1
                         1   5   8   9   7   5   3   2   1   1
                       1   5  10  11  10   7   5   3   2   1   1
                     1   6  12  15  13  11   7   5   3   2   1   1
                   1   6  14  18  18  14  11   7   5   3   2   1   1
                 1   7  16  23  23  20  15  11   7   5   3   2   1   1
               1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
             1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
           1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
         1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
       1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
     1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1

=== Press any key to exit ===

Picat

The triangle, using constraint modelling

Using constraint modeling to generate all the partitions 1..25.

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.
Output:
[1] = 1
[1,1] = 2
[1,1,1] = 3
[1,2,1,1] = 5
[1,2,2,1,1] = 7
[1,3,3,2,1,1] = 11
[1,3,4,3,2,1,1] = 15
[1,4,5,5,3,2,1,1] = 22
[1,4,7,6,5,3,2,1,1] = 30
[1,5,8,9,7,5,3,2,1,1] = 42
[1,5,10,11,10,7,5,3,2,1,1] = 56
[1,6,12,15,13,11,7,5,3,2,1,1] = 77
[1,6,14,18,18,14,11,7,5,3,2,1,1] = 101
[1,7,16,23,23,20,15,11,7,5,3,2,1,1] = 135
[1,7,19,27,30,26,21,15,11,7,5,3,2,1,1] = 176
[1,8,21,34,37,35,28,22,15,11,7,5,3,2,1,1] = 231
[1,8,24,39,47,44,38,29,22,15,11,7,5,3,2,1,1] = 297
[1,9,27,47,57,58,49,40,30,22,15,11,7,5,3,2,1,1] = 385
[1,9,30,54,70,71,65,52,41,30,22,15,11,7,5,3,2,1,1] = 490
[1,10,33,64,84,90,82,70,54,42,30,22,15,11,7,5,3,2,1,1] = 627
[1,10,37,72,101,110,105,89,73,55,42,30,22,15,11,7,5,3,2,1,1] = 792
[1,11,40,84,119,136,131,116,94,75,56,42,30,22,15,11,7,5,3,2,1,1] = 1002
[1,11,44,94,141,163,164,146,123,97,76,56,42,30,22,15,11,7,5,3,2,1,1] = 1255
[1,12,48,108,164,199,201,186,157,128,99,77,56,42,30,22,15,11,7,5,3,2,1,1] = 1575
[1,12,52,120,192,235,248,230,201,164,131,100,77,56,42,30,22,15,11,7,5,3,2,1,1] = 1958
Num partitions == sum of rows:
[1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958]

Number of partitions

This is the Picat solution of Partition_function_P.

% 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.
Output:
23 = 1255
123 = 2552338241
1234 = 156978797223733228787865722354959930
12345 = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
123456 = 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989

Recursion

Here is a port of the Haskell code from oeis.org/A000041. Though for 12345 it's too slow (and eats much RAM).

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

PicoLisp

Translation of: Python
(de row (N)
   (let C '((1))
      (do N
         (push 'C (grow C)) )
      (mapcon
         '((L)
            (when (cdr L)
               (cons (- (cadr L) (car L))) ) )
         (car C) ) ) )
            
(de grow (Lst)
   (let (L (length Lst)  S 0)
      (cons
         0
         (mapcar
            '((I X)
               (inc 'S
                  (get I (inc (min X (- L X)))) ) )
            Lst
            (range 1 L) ) ) ) )
            
(de sumr (N)
   (let 
      (K 1 
         S 1
         O (cons 1 (need N 0))
         D
         (make
            (while
               (<
                  (* K (dec (* 3 K)))
                  (* 2 N) )
               (link (list (dec (* 2 K)) S))
               (link (list K S))
               (inc 'K)
               (setq S (- S)) ) ) )
      (for (Y O (cdr Y) (cdr Y))
         (let Z Y
            (for L D
               (inc
                  (setq Z (cdr (nth Z (car L))))
                  (* (car Y) (cadr L)) ) ) ) )
      (last O) ) )

(for I 25            
   (println (row I)) )
   
(bench
   (for I '(23 123 1234 12345)
      (println (sumr I)) ) )

(bye)
Output:
(1)
(1 1)
(1 1 1)
(1 2 1 1)
(1 2 2 1 1)
(1 3 3 2 1 1)
(1 3 4 3 2 1 1)
(1 4 5 5 3 2 1 1)
(1 4 7 6 5 3 2 1 1)
(1 5 8 9 7 5 3 2 1 1)
(1 5 10 11 10 7 5 3 2 1 1)
(1 6 12 15 13 11 7 5 3 2 1 1)
(1 6 14 18 18 14 11 7 5 3 2 1 1)
(1 7 16 23 23 20 15 11 7 5 3 2 1 1)
(1 7 19 27 30 26 21 15 11 7 5 3 2 1 1)
(1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1)
(1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1)
(1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1)
(1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1)
(1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1)
(1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1)
(1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1)
(1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1)
(1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1)
(1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1)
1255
2552338241
156978797223733228787865722354959930
69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
0.626 sec

Pike

Translation of: Python
array cumu(int n) {
	array(array(int)) cache = ({({1})});

	for(int l = sizeof(cache); l < n + 1; l++) {
		array(int) r = ({0});
		for(int x = 1; x < l + 1; x++) {
			r = Array.push(r, r[-1] + cache[l - x][min(x, l-x)]);
		}
		cache = Array.push(cache, r);
	}
	return cache[n];
}

array row(int n) {
	array r = cumu(n);
	array res = ({});
	for (int i = 0; i < n; i++) {
		res = Array.push(res, r[i+1] - r[i]);
	}
	return res;
}

int main() {
	write("rows:\n");
	for(int x = 1; x < 11; x++) {
		write("%2d: ", x);
		for(int i = 0; i < sizeof(row(x)); i++) {
			write((string)row(x)[i] + " ");
		}
		write("\n");
	}

	array(int) sum_n = ({23, 123, 1234, 12345});
	write("\nsums:\n");
	for (int x = 0; x < sizeof(sum_n); x++) {
		write((string)sum_n[x] + " " + (string)cumu(sum_n[x])[-1] + "\n");
	}
	return 0;
}
Output:
Not wait for "12345" 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
^C

PureBasic

Define nMax.i=25, n.i, k.i
Dim pfx.s(1)

Procedure.s Sigma(sx.s, sums.s)
  Define i.i, v1.i, v2.i, r.i
  Define s.s, sa.s
  sums=ReverseString(sums) : s=ReverseString(sx)
  For i=1 To Len(s)*Bool(Len(s)>Len(sums))+Len(sums)*Bool(Len(sums)>=Len(s))
    v1=Val(Mid(s,i,1))
    v2=Val(Mid(sums,i,1))
    r+v1+v2    
    sa+Str(r%10)
    r/10
  Next i  
  If r : sa+Str(r%10) : EndIf
  ProcedureReturn ReverseString(sa)
EndProcedure

Procedure.i Adr(row.i,col.i)
  ProcedureReturn ((row-1)*row/2+col)*Bool(row>0 And col>0)
EndProcedure

Procedure Triangle(row.i,Array pfx.s(1))
  Define n.i,k.i
  Define zs.s
  nMax=row
  ReDim pfx(Adr(nMax,nMax))
  For n=1 To nMax
    For k=1 To n    
      If k>n    : pfx(Adr(n,k))="0"    : Continue : EndIf
      If n=k    : pfx(Adr(n,k))="1"    : Continue : EndIf    
      If k<=n/2
        zs=""
        zs=Sigma(pfx(Adr(n-k,k)),zs)
        zs=Sigma(pfx(Adr(n-1,k-1)),zs)
        pfx(Adr(n,k))=zs
      Else
        pfx(Adr(n,k))=pfx(Adr(n-1,k-1))
      EndIf
    Next k
  Next n
EndProcedure

Procedure.s sum(row.i, Array pfx.s(1))
  Define s.s
  Triangle(row, pfx())
  For n=1 To row
    s=Sigma(pfx(Adr(row,n)),s)
  Next n
  ProcedureReturn RSet(Str(row),5,Chr(32))+" : "+s
EndProcedure

OpenConsole()

Triangle(nMax, pfx())
For n=1 To nMax
  Print(Space(((nMax*4-1)-(n*4-1))/2))
  For k=1 To n    
    Print(RSet(pfx(Adr(n,k)),3,Chr(32))+Space(1))
  Next k
  PrintN("")
Next n
PrintN("")
PrintN(sum(23,pfx()))
PrintN(sum(123,pfx()))
PrintN(sum(1234,pfx()))
PrintN(sum(12345,pfx()))
Input()
Output:
                                                  1
                                                1   1
                                              1   1   1
                                            1   2   1   1
                                          1   2   2   1   1
                                        1   3   3   2   1   1
                                      1   3   4   3   2   1   1
                                    1   4   5   5   3   2   1   1
                                  1   4   7   6   5   3   2   1   1
                                1   5   8   9   7   5   3   2   1   1
                              1   5  10  11  10   7   5   3   2   1   1
                            1   6  12  15  13  11   7   5   3   2   1   1
                          1   6  14  18  18  14  11   7   5   3   2   1   1
                        1   7  16  23  23  20  15  11   7   5   3   2   1   1
                      1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
                    1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
                  1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
                1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
              1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
            1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
          1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
        1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
      1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
    1  12  48 108 164 199 201 186 157 128  99  77  56  42  30  22  15  11   7   5   3   2   1   1
  1  12  52 120 192 235 248 230 201 164 131 100  77  56  42  30  22  15  11   7   5   3   2   1   1

   23 : 1255
  123 : 2552338241
 1234 : 156978797223733228787865722354959930
12345 : 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

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

To calculate partition functions only:

def partitions(N):
    diffs,k,s = [],1,1
    while k * (3*k-1) < 2*N:
        diffs.extend([(2*k - 1, s), (k, s)])
	k,s = k+1,-s

    out = [1] + [0]*N
    for p in range(0, N+1):
        x = out[p]
	for (o,s) in diffs:
           p += o
           if p > N: break
           out[p] += x*s

    return out

p = partitions(12345)
for x in [23,123,1234,12345]: print x, p[x]

This version uses only a fraction of the memory and of the running time, compared to the first one that has to generate all the rows:

Translation of: C
def partitions(n):
    partitions.p.append(0)

    for k in xrange(1, n + 1):
        d = n - k * (3 * k - 1) // 2
        if d < 0:
            break

        if k & 1:
            partitions.p[n] += partitions.p[d]
        else:
            partitions.p[n] -= partitions.p[d]

        d -= k
        if d < 0:
            break

        if k & 1:
            partitions.p[n] += partitions.p[d]
        else:
            partitions.p[n] -= partitions.p[d]

    return partitions.p[-1]

partitions.p = [1]

def main():
    ns = set([23, 123, 1234, 12345])
    max_ns = max(ns)

    for i in xrange(1, max_ns + 1):
        if i > max_ns:
            break
        p = partitions(i)
        if i in ns:
            print "%6d: %s" % (i, p)

main()
Output:
    23: 1255
   123: 2552338241
  1234: 156978797223733228787865722354959930
 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

R

library(partitions)
library(stringi)

get_row <- function(x) unname(table(parts(x)[1,]))

center_string <- function(s,pad_len=80) stri_pad_both(s,(pad_len - length(s))," ")
  
for (i in 1:25) cat(center_string(stri_c(get_row(i),collapse = " "),80),"\n")

cat("The sum of G(25) is:", sum(get_row(25)),"\n")
Output:
                                       1                                        
                                      1 1                                       
                                     1 1 1                                      
                                    1 2 1 1                                     
                                   1 2 2 1 1                                    
                                  1 3 3 2 1 1                                   
                                 1 3 4 3 2 1 1                                  
                                1 4 5 5 3 2 1 1                                 
                               1 4 7 6 5 3 2 1 1                                
                              1 5 8 9 7 5 3 2 1 1                               
                           1 5 10 11 10 7 5 3 2 1 1                             
                          1 6 12 15 13 11 7 5 3 2 1 1                           
                        1 6 14 18 18 14 11 7 5 3 2 1 1                          
                       1 7 16 23 23 20 15 11 7 5 3 2 1 1                        
                     1 7 19 27 30 26 21 15 11 7 5 3 2 1 1                       
                    1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1                     
                  1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1                    
                 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1                  
               1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1                 
             1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1               
          1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1            
        1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1          
      1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1        
    1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1     
 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 

The sum of G(25) is: 1958 

Racket

#lang racket

(define (cdr-empty ls) (if (empty? ls) empty (cdr ls)))

(define (names-of n)
  (define (names-of-tail ans raws-rest n)
    (if (zero? n)
        ans
        (names-of-tail (cons 1 (append (map + 
                                            (take ans (length raws-rest)) 
                                            (map car raws-rest))
                                       (drop ans (length raws-rest))))
                       (filter (compose not empty?)
                               (map cdr-empty (cons ans raws-rest)))
                       (sub1 n))))
  (names-of-tail '() '() n))

(define (G n) (foldl + 0 (names-of n)))

(module+ main
  (build-list 25 (compose names-of add1))
  (newline)
  (map G '(23 123 1234)))
Output:
'((1)
  (1 1)
  (1 1 1)
  (1 2 1 1)
  (1 2 2 1 1)
  (1 3 3 2 1 1)
  (1 3 4 3 2 1 1)
  (1 4 5 5 3 2 1 1)
  (1 4 7 6 5 3 2 1 1)
  (1 5 8 9 7 5 3 2 1 1)
  (1 5 10 11 10 7 5 3 2 1 1)
  (1 6 12 15 13 11 7 5 3 2 1 1)
  (1 6 14 18 18 14 11 7 5 3 2 1 1)
  (1 7 16 23 23 20 15 11 7 5 3 2 1 1)
  (1 7 19 27 30 26 21 15 11 7 5 3 2 1 1)
  (1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1)
  (1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1)
  (1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1)
  (1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1)
  (1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1)
  (1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1)
  (1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1)
  (1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1)
  (1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1)
  (1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1))

'(1255 2552338241 156978797223733228787865722354959930)

Raku

(formerly Perl 6) To save a bunch of memory, this algorithm throws away all the numbers that it knows it's not going to use again, on the assumption that the function will only be called with increasing values of $n. (It could easily be made to recalculate if it notices a regression.)

my @todo = $[1];
my @sums = 0;
sub nextrow($n) {
    for +@todo .. $n -> $l {
        my $r = [];
        for reverse ^$l -> $x {
            my @x := @todo[$x];
            if @x {
                $r.push: @sums[$x] += @x.shift;
            }
            else {
                $r.push: @sums[$x];
            }
        }
        @todo.push($r);
    }
    @todo[$n];
}

say "rows:";
say .fmt('%2d'), ": ", nextrow($_)[] for 1..25;


my @names-of-God = 1, { partition-sum ++$ } … *;
my @names-of-God-adder = lazy [\+] flat 1, ( (1 .. *) Z (1 .. *).map: * × 2 + 1 );
sub partition-sum ($n) {
    sum @names-of-God[$n X- @names-of-God-adder[^(@names-of-God-adder.first: * > $n, :k)]]
        Z× (flat (1, 1, -1, -1) xx *)
}

say "\nsums:";
for 23, 123, 1234, 12345 {
    put $_, "\t",  @names-of-God[$_];
}
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]
11: [1 5 10 11 10 7 5 3 2 1 1]
12: [1 6 12 15 13 11 7 5 3 2 1 1]
13: [1 6 14 18 18 14 11 7 5 3 2 1 1]
14: [1 7 16 23 23 20 15 11 7 5 3 2 1 1]
15: [1 7 19 27 30 26 21 15 11 7 5 3 2 1 1]
16: [1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1]
17: [1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1]
18: [1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1]
19: [1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1]
20: [1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1]
21: [1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1]
22: [1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1]
23: [1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1]
24: [1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1]
25: [1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1]

sums:
23	1255
123	2552338241
1234	156978797223733228787865722354959930
12345	69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Red

Red []

context [
    sum-part: function [nums [block!] count [integer!]][
        out: 0.0
        loop count [
            out: out + nums/1 
            if empty? nums: next nums [break]
        ]
        out
    ]
    nums: make map! [1 [1] 2 [1 1]]
    sums: make map! [1 1 2 2]
    set 'names function [row /show /all][
        if row < 1 [cause-error 'user 'message "Argument needs to be >= 1"]
        if show [
            unless nums/:row [names row]
            repeat i row [either all [probe reduce [i nums/:i sums/:i]][print nums/:i]]
        ]
        either sums/:row [sums/:row][
            out: clear []
            half: to integer! row / 2
            if row - 1 > last: length? nums [
                repeat i row - last - 1 [names last + i]
            ]
            repeat col row - 1 [
                either col = (half + 1) [
                    append out at nums/(row - 1) half
                    break
                ][
                    append out sum-part nums/(row - col) col
                ]
            ]
            also sums/:row: sum nums/:row: copy out  clear out
        ]
    ]
]

print "rows: ^/"
names/show 25
print "^/sums: ^/"
probe names 23
probe names 123 
probe names 1234
Output:
rows:

1
1 1
1.0 1 1
1.0 2.0 1 1
1.0 2.0 2.0 1 1
1.0 3.0 3.0 2.0 1 1
1.0 3.0 4.0 3.0 2.0 1 1
1.0 4.0 5.0 5.0 3.0 2.0 1 1
1.0 4.0 7.0 6.0 5.0 3.0 2.0 1 1
1.0 5.0 8.0 9.0 7.0 5.0 3.0 2.0 1 1
1.0 5.0 10.0 11.0 10.0 7.0 5.0 3.0 2.0 1 1
1.0 6.0 12.0 15.0 13.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 6.0 14.0 18.0 18.0 14.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 7.0 16.0 23.0 23.0 20.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 7.0 19.0 27.0 30.0 26.0 21.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 8.0 21.0 34.0 37.0 35.0 28.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 8.0 24.0 39.0 47.0 44.0 38.0 29.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 9.0 27.0 47.0 57.0 58.0 49.0 40.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 9.0 30.0 54.0 70.0 71.0 65.0 52.0 41.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 10.0 33.0 64.0 84.0 90.0 82.0 70.0 54.0 42.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 10.0 37.0 72.0 101.0 110.0 105.0 89.0 73.0 55.0 42.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 11.0 40.0 84.0 119.0 136.0 131.0 116.0 94.0 75.0 56.0 42.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 11.0 44.0 94.0 141.0 163.0 164.0 146.0 123.0 97.0 76.0 56.0 42.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 12.0 48.0 108.0 164.0 199.0 201.0 186.0 157.0 128.0 99.0 77.0 56.0 42.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1
1.0 12.0 52.0 120.0 192.0 235.0 248.0 230.0 201.0 164.0 131.0 100.0 77.0 56.0 42.0 30.0 22.0 15.0 11.0 7.0 5.0 3.0 2.0 1 1

sums:

1255.0
2552338241.0
1.5697879722373306e35

REXX

This REXX version displays a nicely "balanced" numbers triangle as per this task's requirement.

If the number of rows is entered as a signed positive integer, only the number of partitions is shown,
(that is, the sum of the numbers on the last line of the number triangle).

If the number of rows is entered as a signed integer, the triangle isn't shown.

Memoization is used to quickly obtain information of previously calculated numbers in the left-hand side of
the triangle and also previous calculated partitions.

The right half of the triangle isn't calculated but rather the value is taken from a previous row and column.

Also, the left two columns of the triangle are computed directly   [either   1   or   row%2   (integer divide)]
as well as the rightmost three columns   (either   1   or   2).

The formula used is:

which is derived from Euler's generating function.

/*REXX program  generates and displays a  number triangle  for partitions of a number.  */
numeric digits 400                               /*be able to handle larger numbers.    */
parse arg N .                                    /*obtain optional argument from the CL.*/
if N==''  then N= 25                             /*N  specified?  Then use the default. */
@.= 0;          @.0= 1;       aN= abs(N)         /*initialize a partition number; AN abs*/
if N==N+0  then say  '         G('aN"):"   G(N)  /*just do this for well formed numbers.*/
                say  'partitions('aN"):"   partitions(aN)          /*do it the easy way.*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
G: procedure; parse arg nn;  !.= 0;    !.4.2= 2;     mx= 1;    aN= abs(nn);    build= nn>0
                do j=1  for aN%2;      !.j.j= 1      /*gen shortcuts for unity elements.*/
                end   /*j*/

                do     t=1  for 1+build;        #.=1 /*generate triangle once or twice. */
                  do   r=1  for aN;   #.2= r % 2     /*#.2  is a shortcut calculation.  */
                    do c=3  to  r-2;  #.c= gen#(r,c)
                    end   /*c*/
                  L= length(mx);      p= 0;     __=  /*__  will be a row of the triangle*/
                      do cc=1  for r; p= p + #.cc    /*only sum the last row of numbers.*/
                      if \build  then iterate        /*should we skip building triangle?*/
                      mx= max(mx, #.cc)              /*used to build the symmetric #s.  */
                      __= __  right(#.cc, L)         /*construct a row of the triangle. */
                      end   /*cc*/
                  if t==1  then iterate              /*Is this 1st time through? No show*/
                  say  center( strip(__),  2 + (aN-1) * (length(mx) + 1) )
                  end       /*r*/                    /* [↑]  center row of the triangle.*/
                end         /*t*/
              return p                               /*return with the generated number.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen#: procedure expose !.;   parse arg x,y             /*obtain the  X and Y  arguments.*/
      if !.x.y\==0  then  return !.x.y                 /*was number generated before ?  */
      if y>x%2  then do;  nx= x+1-(y-x%2)*2-(x//2==0)
                          ny= nx % 2;  !.x.y= !.nx.ny
                          return !.x.y                 /*return the calculated number.  */
                     end                               /* [↑]  right half of triangle.  */
      $= 1                                             /* [↓]   left   "   "     "      */
                          do q=2  for y-1;   xy= x-y;   if q>xy  then iterate
                          if q==2  then $= $  +  xy % 2
                                   else if q==xy-1  then $= $ + 1
                                                    else $= $ + gen#(xy,q)    /*recurse.*/
                          end   /*q*/
      !.x.y=$; return $                                /*use memoization; return with #.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
partitions: procedure expose @.; parse arg n;   if @.n\==0  then return @.n   /* ◄─────┐*/
            $= 0                                         /*Already known?  Return ►────┘*/
                     do k=1  for n                       /*process  N  partitions.      */
                     #= n - (k*3-1) * k % 2              /*calculate a partition number.*/
                     if #<0  then leave                  /*Is it negative?  Then leave. */
                     if @.#==0  then x= partitions(#)    /* [◄] this is a recursive call*/
                                else x= @.#              /*the value is already known.  */
                     #= # - k
                     if #<0  then  y= 0                  /*Is negative?   Then use zero.*/
                             else  if @.#==0  then y= partitions(p)    /*recursive call.*/
                                              else y= @.#
                     if k//2  then $= $ + x + y          /*use this method if K is odd. */
                              else $= $ - x - y          /* "    "     "    " "  " even.*/
                     end   /*k*/                         /* [↑]  Euler's recursive func.*/
            @.n= $;             return $                 /*use memoization;  return num.*/
output   when using the default input   (of 25 rows):
                                                1
                                              1   1
                                            1   1   1
                                          1   2   1   1
                                        1   2   2   1   1
                                      1   3   3   2   1   1
                                    1   3   4   3   2   1   1
                                  1   4   5   5   3   2   1   1
                                1   4   7   6   5   3   2   1   1
                              1   5   8   9   7   5   3   2   1   1
                            1   5  10  11  10   7   5   3   2   1   1
                          1   6  12  15  13  11   7   5   3   2   1   1
                        1   6  14  18  18  14  11   7   5   3   2   1   1
                      1   7  16  23  23  20  15  11   7   5   3   2   1   1
                    1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
                  1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
                1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
              1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
            1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
          1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
        1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
      1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
    1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
  1  12  48 108 164 199 201 186 157 128  99  77  56  42  30  22  15  11   7   5   3   2   1   1
1  12  52 120 192 235 248 230 201 164 131 100  77  56  42  30  22  15  11   7   5   3   2   1   1
         G(25): 1958
partitions(25): 1958
output   when using the input:   -23
         G(23): 1255
partitions(23): 1255
output   when using the input:   -123
         G(123): 2552338241
partitions(123): 2552338241
output   when using the input:   -1234
         G(1234): 156978797223733228787865722354959930
partitions(1234): 156978797223733228787865722354959930
output   when using the input:   -12345
         G(12345): 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
partitions(12345): 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
output   when using the input:   +123456
partitions(123456): 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989

(For the extra credit part)   to view a horizontal histogram (plot) for the values for the number of partitions of   1 ──► 999   here at:

9 billion names of God the integer (REXX) histogram.

Ruby

Naive Solution

# Generate IPF triangle
# Nigel_Galloway: May 1st., 2013.
def g(n,g)
  return 1 unless 1 < g and g < n-1
  (2..g).inject(1){|res,q| res + (q > n-g ? 0 : g(n-g,q))}
end
 
(1..25).each {|n|
  puts (1..n).map {|g| "%4s" % g(n,g)}.join
}
Output:
   1
   1   1
   1   1   1
   1   2   1   1
   1   2   2   1   1
   1   3   3   2   1   1
   1   3   4   3   2   1   1
   1   4   5   5   3   2   1   1
   1   4   7   6   5   3   2   1   1
   1   5   8   9   7   5   3   2   1   1
   1   5  10  11  10   7   5   3   2   1   1
   1   6  12  15  13  11   7   5   3   2   1   1
   1   6  14  18  18  14  11   7   5   3   2   1   1
   1   7  16  23  23  20  15  11   7   5   3   2   1   1
   1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
   1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
   1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
   1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
   1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
   1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
   1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
   1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
   1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
   1  12  48 108 164 199 201 186 157 128  99  77  56  42  30  22  15  11   7   5   3   2   1   1
   1  12  52 120 192 235 248 230 201 164 131 100  77  56  42  30  22  15  11   7   5   3   2   1   1

Full Solution

# Find large values of IPF
# Nigel_Galloway: May 1st., 2013.
N = 12345
@ng = []
@ipn1 = []
@ipn2 = []
def g(n,g)
  t = n-g-2
  return 1 if n<4 or t<0
  return @ng[g-2][n-4] unless n/2<g
  return @ipn1[t]
end
@ng[0] = []
(4..N).each {|q| @ng[0][q-4] = 1 + g(q-2,2)}
@ipn1[0] = @ng[0][0]
@ipn2[0] = @ng[0][N-4]
(1...(N/2-1)).each {|n|
  @ng[n] = []
  (n*2+4..N).each {|q| @ng[n][q-4] = g(q-1,n+1) + g(q-n-2,n+2)}
  @ipn1[n] = @ng[n][n*2]
  @ipn2[n] = @ng[n][N-4]
  @ng[n-1] = nil
}
@ipn2.pop if N.even?
 
puts "G(23) = #{@ipn1[21]}"
puts "G(123) = #{@ipn1[121]}"
puts "G(1234) = #{@ipn1[1232]}"
n = 3 + @ipn1.inject(:+) + @ipn2.inject(:+)
puts "G(12345) = #{n}"
Output:
G(23) = 1255
G(123) = 2552338241
G(1234) = 156978797223733228787865722354959930
G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Rust

Translation of: Python
extern crate num;

use std::cmp;
use num::bigint::BigUint;

fn cumu(n: usize, cache: &mut Vec<Vec<BigUint>>) {
    for l in cache.len()..n+1 {
        let mut r = vec![BigUint::from(0u32)];
        for x in 1..l+1 {
            let prev = r[r.len() - 1].clone();
            r.push(prev + cache[l-x][cmp::min(x, l-x)].clone());
        }
        cache.push(r);
    }
}

fn row(n: usize, cache: &mut Vec<Vec<BigUint>>) -> Vec<BigUint> {
    cumu(n, cache);
    let r = &cache[n];
    let mut v: Vec<BigUint> = Vec::new();

    for i in 0..n {
        v.push(&r[i+1] - &r[i]);
    }
    v
}

fn main() {
    let mut cache = vec![vec![BigUint::from(1u32)]];

    println!("rows:");
    for x in 1..26 {
        let v: Vec<String> = row(x, &mut cache).iter().map(|e| e.to_string()).collect();
        let s: String = v.join(" ");
        println!("{}: {}", x, s);
    }

    println!("sums:");
    for x in vec![23, 123, 1234, 12345] {
        cumu(x, &mut cache);
        let v = &cache[x];
        let s = v[v.len() - 1].to_string();
        println!("{}: {}", x, s);
    }
}
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
11: 1 5 10 11 10 7 5 3 2 1 1
12: 1 6 12 15 13 11 7 5 3 2 1 1
13: 1 6 14 18 18 14 11 7 5 3 2 1 1
14: 1 7 16 23 23 20 15 11 7 5 3 2 1 1
15: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
16: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
17: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
18: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
19: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
20: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
21: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
22: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
23: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
24: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
25: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
sums:
23: 1255
123: 2552338241
1234: 156978797223733228787865722354959930
12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Scala

Naive Solution

object Main {

  // This is a special class for memoization
  case class Memo[A,B](f: A => B) extends (A => B) {
	  private val cache = Map.empty[A, B]
	  def apply(x: A) = cache getOrElseUpdate (x, f(x))
  }

  // Naive, but memoized solution
  lazy val namesStartingMemo : Memo[Tuple2[Int, Int], BigInt] = Memo {
    case (1, 1) => 1
    case (a, n) => 
	    if (a > n/2) namesStartingMemo(a - 1, n - 1)
	    else if (n < a) 0
	    else if (n == a) 1
	    else (1 to a).map(i => namesStartingMemo(i, n - a)).sum
    
  }
  
  def partitions(n: Int) = (1 to n).map(namesStartingMemo(_, n)).sum
  
  // main method
  def main(args: Array[String]): Unit = {
    for (i <- 1 to 25) {
    	for (j <- 1 to i) { 
	      print(namesStartingMemo(j, i));
	      print(' ');
	    }
    	println()
    }
    println(partitions(23))
    println(partitions(123))
    println(partitions(1234))
    println(partitions(12345))
  }
}
Output:
1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 
1 3 4 3 2 1 1 
1 4 5 5 3 2 1 1 
1 4 7 6 5 3 2 1 1 
1 5 8 9 7 5 3 2 1 1 
1 5 10 11 10 7 5 3 2 1 1 
1 6 12 15 13 11 7 5 3 2 1 1 
1 6 14 18 18 14 11 7 5 3 2 1 1 
1 7 16 23 23 20 15 11 7 5 3 2 1 1 
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 
1255
2552338241
156978797223733228787865722354959930
Exception in thread "main" java.lang.StackOverflowError
	at scala.collection.mutable.HashTable$class.findEntry(HashTable.scala:130)
	at scala.collection.mutable.HashMap.findEntry(HashMap.scala:39)
	at scala.collection.mutable.HashMap.get(HashMap.scala:69)
	at scala.collection.mutable.MapLike$class.getOrElseUpdate(MapLike.scala:187)
	at scala.collection.mutable.AbstractMap.getOrElseUpdate(Map.scala:91)
	at Main$Memo.apply(Main.scala:14)
        ...

(As you see, partitions(12345) fails with StackOverflowError)

Full Solution

val cache = new Array[BigInt](15000)
cache(0) = 1
val cacheNaive = scala.collection.mutable.Map[Tuple2[Int, Int], BigInt]()

def p(n: Int, k: Int): BigInt = cacheNaive.getOrElseUpdate((n, k), (n, k) match {
    case (n, 1) => 1
    case (n, k) if n < k => 0
    case (n, k) if n == k => 1
    case (n, k) =>
        if (k > n/2) p(n - 1, k - 1)
        else p(n - 1, k - 1) + p(n - k, k)
})

def partitions(n: Int) = (1 to n).map(p(n, _)).sum

def updateCache(n: Int, d: Int, k: Int) =
    if ((k & 1) == 1) cache(n) = cache(n) + cache(d)
    else cache(n) = cache(n) - cache(d)

def quickPartitions(n: Int): BigInt = {
    cache(n) = 0
    for (k <- 1 to n) {
        val d = n - k * (3 * k - 1) / 2
        if (d >= 0) {
            updateCache(n, d, k)

            val e = d - k
            if (e >= 0) {
                updateCache(n, e, k)
            }
        }
    }
    cache(n)
}

for (i <- 1 to 23) {
    for (j <- 1 to i) {
        print(f"${p(i, j)}%4d")
    }
    println
}
println(partitions(23))

for (i <- 1 until cache.length) {
    quickPartitions(i)
}
println(quickPartitions(123))
println(quickPartitions(1234))
println(quickPartitions(12345))
Output:
   1
   1   1
   1   1   1
   1   2   1   1
   1   2   2   1   1
   1   3   3   2   1   1
   1   3   4   3   2   1   1
   1   4   5   5   3   2   1   1
   1   4   7   6   5   3   2   1   1
   1   5   8   9   7   5   3   2   1   1
   1   5  10  11  10   7   5   3   2   1   1
   1   6  12  15  13  11   7   5   3   2   1   1
   1   6  14  18  18  14  11   7   5   3   2   1   1
   1   7  16  23  23  20  15  11   7   5   3   2   1   1
   1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
   1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
   1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
   1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
   1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1
   1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1
   1  10  37  72 101 110 105  89  73  55  42  30  22  15  11   7   5   3   2   1   1
   1  11  40  84 119 136 131 116  94  75  56  42  30  22  15  11   7   5   3   2   1   1
   1  11  44  94 141 163 164 146 123  97  76  56  42  30  22  15  11   7   5   3   2   1   1
1255
2552338241
156978797223733228787865722354959930
69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

scheme

(define (f m n)
  (define (sigma g x y)
    (define (sum i)
      (if (< i 0) 0 (+ (f x (- y i) ) (sum (- i 1)))))
    (sum y))
  (cond ((eq? m n) 1)
        ((eq? n 1) 1)
        ((eq? n 0) 0)
        ((< m n) (f m m))
        ((< (/ m 2) n) (sigma f (- m n) (- m n)))
        (else (sigma f (- m n) n))))
(define (line m)
  (define (connect i)
    (if (> i m) '() (cons (f m i) (connect (+ i 1)))))
  (connect 1))
(define (print x)
  (define (print-loop i)
    (cond ((< i x) (begin (display (line i)) (display "\n") (print-loop (+ i 1)) ))))
  (print-loop 1))
(print 25)
Output:
(1)
(1 1)
(1 1 1)
(1 2 1 1)
(1 2 2 1 1)
(1 3 3 2 1 1)
(1 3 4 3 2 1 1)
(1 4 5 5 3 2 1 1)
(1 4 7 6 5 3 2 1 1)
(1 5 8 9 7 5 3 2 1 1)
(1 5 10 11 10 7 5 3 2 1 1)
(1 6 12 15 13 11 7 5 3 2 1 1)
(1 6 14 18 18 14 11 7 5 3 2 1 1)
(1 7 16 23 23 20 15 11 7 5 3 2 1 1)
(1 7 19 27 30 26 21 15 11 7 5 3 2 1 1)
(1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1)
(1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1)
(1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1)
(1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1)
(1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1)
(1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1)
(1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1)
(1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1)
(1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1)

Sidef

var cache = [[1]]

func cumu (n) {
    for l (cache.len .. n) {
        var r = [0]
        for i (1..l) {
            r << (r[-1] + cache[l-i][min(i, l-i)])
        }
        cache << r
    }
    cache[n]
}

func row (n) {
    var r = cumu(n)
    n.of {|i| r[i+1] - r[i] }
}

say "rows:"
for i (1..15) {
    "%2s: %s\n".printf(i, row(i))
}

say "\nsums:"

for i in [23, 123, 1234, 12345] {
    "%2s : %4s\n".printf(i, cumu(i)[-1])
}
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]
11: [1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
12: [1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
13: [1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
14: [1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
15: [1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]

sums:
23 : 1255
123 : 2552338241
1234 : 156978797223733228787865722354959930
^C

SPL

'print triangle
> n, 1..25
  k = 50-n*2
  #.output(#.str("","<"+k+"<"),#.rs)
  > k, 1..n
    i = p(n,k)
    s = #.str(i,">3<")
    ? k<n, s += " "+#.rs
    #.output(s)
  <
<
p(n,k)=
  ? k=0 | k>n, <= 0
  ? k=n, <= 1
  <= p(n-1,k-1)+p(n-k,k)
.

'calculate partition function
#.output()
#.output("G(23) =    ",g(23))
#.output("G(123) =   ",g(123))
#.output("G(1234) =  ",g(1234))
#.output("G(12345) = ",g(12345))
g(n)=
  p[1] = 1
  > i, 2..n+1
    j = 2
    k,p[i] = 0
    > j>1
      k += 1
      j = i-#.lower((3*k*k+k)/2)
      ? j!<1, p[i] -= (-1)^k*p[j]
      j = i-#.lower((3*k*k-k)/2)
      ? j!<1, p[i] -= (-1)^k*p[j]
    <
  <
  <= p[n+1]
.
Output:
                                                 1 
                                               1   1 
                                             1   1   1 
                                           1   2   1   1 
                                         1   2   2   1   1 
                                       1   3   3   2   1   1 
                                     1   3   4   3   2   1   1 
                                   1   4   5   5   3   2   1   1 
                                 1   4   7   6   5   3   2   1   1 
                               1   5   8   9   7   5   3   2   1   1 
                             1   5  10  11  10   7   5   3   2   1   1 
                           1   6  12  15  13  11   7   5   3   2   1   1 
                         1   6  14  18  18  14  11   7   5   3   2   1   1 
                       1   7  16  23  23  20  15  11   7   5   3   2   1   1 
                     1   7  19  27  30  26  21  15  11   7   5   3   2   1   1 
                   1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1 
                 1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1 
               1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1 
             1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1 
           1  10  33  64  84  90  82  70  54  42  30  22  15  11   7   5   3   2   1   1 
         1  10  37  72  101 110 105 89  73  55  42  30  22  15  11   7   5   3   2   1   1 
       1  11  40  84  119 136 131 116 94  75  56  42  30  22  15  11   7   5   3   2   1   1 
     1  11  44  94  141 163 164 146 123 97  76  56  42  30  22  15  11   7   5   3   2   1   1 
   1  12  48  108 164 199 201 186 157 128 99  77  56  42  30  22  15  11   7   5   3   2   1   1 
 1  12  52  120 192 235 248 230 201 164 131 100 77  56  42  30  22  15  11   7   5   3   2   1   1 

G(23) =    1255
G(123) =   2552338241
G(1234) =  156978797223733228787865722354959930
G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Stata

mata
function part(n) {
	a = J(n,n,.)
	for (i=1;i<=n;i++) a[i,1] = a[i,i] = 1
	for (i=3;i<=n;i++) {
		for (j=2;j<i;j++) a[i,j] = sum(a[i-j,1..min((j,i-j))])
	}
	return(a)
}
end

The result is shown for n=10 to keep it small. Due to computations being done in floating point, the result is exact up to n=299, and suffers rounding for larger values of n. Compare the array with OEIS A008284 and row sums with OEIS A000041.

Output

: a = part(10)
: a
         1    2    3    4    5    6    7    8    9   10
     +---------------------------------------------------+
   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  |
     +---------------------------------------------------+

: rowsum(a)'
        1    2    3    4    5    6    7    8    9   10
    +---------------------------------------------------+
  1 |   1    2    3    5    7   11   15   22   30   42  |
    +---------------------------------------------------+

Swift

Translation of: Python
var cache = [[1]]
func namesOfGod(n:Int) -> [Int] {
    for l in cache.count...n {
        var r = [0]
        for x in 1...l {
            r.append(r[r.count - 1] + cache[l - x][min(x, l-x)])
        }
        cache.append(r)
    }
    return cache[n]
}

func row(n:Int) -> [Int] {
    let r = namesOfGod(n)
    var returnArray = [Int]()
    for i in 0...n - 1 {
        returnArray.append(r[i + 1] - r[i])
    }
    return returnArray
}

println("rows:")
for x in 1...25 {
    println("\(x): \(row(x))")
}

println("\nsums: ")

for x in [23, 123, 1234, 12345] {
    cache = [[1]]
    var array = namesOfGod(x)
    var numInt = array[array.count - 1]
    println("\(x): \(numInt)")
}
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]
11: [1, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1]
12: [1, 6, 12, 15, 13, 11, 7, 5, 3, 2, 1, 1]
13: [1, 6, 14, 18, 18, 14, 11, 7, 5, 3, 2, 1, 1]
14: [1, 7, 16, 23, 23, 20, 15, 11, 7, 5, 3, 2, 1, 1]
15: [1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1]
16: [1, 8, 21, 34, 37, 35, 28, 22, 15, 11, 7, 5, 3, 2, 1, 1]
17: [1, 8, 24, 39, 47, 44, 38, 29, 22, 15, 11, 7, 5, 3, 2, 1, 1]
18: [1, 9, 27, 47, 57, 58, 49, 40, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
19: [1, 9, 30, 54, 70, 71, 65, 52, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
20: [1, 10, 33, 64, 84, 90, 82, 70, 54, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
21: [1, 10, 37, 72, 101, 110, 105, 89, 73, 55, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
22: [1, 11, 40, 84, 119, 136, 131, 116, 94, 75, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
23: [1, 11, 44, 94, 141, 163, 164, 146, 123, 97, 76, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
24: [1, 12, 48, 108, 164, 199, 201, 186, 157, 128, 99, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]
25: [1, 12, 52, 120, 192, 235, 248, 230, 201, 164, 131, 100, 77, 56, 42, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1]

sums: 
    23: 1255
   123: 2552338241
  1234: 156978797223733228787865722354959930
 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Tcl

Translation of: Python
set cache 1
proc cumu {n} {
    global cache
    for {set l [llength $cache]} {$l <= $n} {incr l} {
	set r 0
	for {set x 1; set y [expr {$l-1}]} {$y >= 0} {incr x; incr y -1} {
	    lappend r [expr {
		[lindex $r end] + [lindex $cache $y [expr {min($x, $y)}]]
	    }]
	}
	lappend cache $r
    }
    return [lindex $cache $n]
}
proc row {n} {
    set r [cumu $n]
    for {set i 0; set j 1} {$j < [llength $r]} {incr i; incr j} {
	lappend result [expr {[lindex $r $j] - [lindex $r $i]}]
    }
    return $result
}

puts "rows:"
foreach x {1 2 3 4 5 6 7 8 9 10} {
    puts "${x}: \[[join [row $x] {, }]\]"
}
puts "\nsums:"
foreach x {23 123 1234 12345} {
    puts "${x}: [lindex [cumu $x] end]"
}
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
^C

(I killed the run when it started to take a significant proportion of my system's memory.)

uBasic/4tH

Translation of: VBA

Since uBasic/4tH features a single array of 256 elements, level "15" is the best that can be achieved.

Proc _NineBillionNames(15)
End

_NineBillionNames
  Param (1)
  Local (3)
  
  @(1*a@ + 1) = 1
 
  For b@ = 2 To a@
    For c@ = 1 To b@
      @(b@*a@ + c@) = @((b@ - 1)*a@ + (c@ - 1)) + @((b@ - c@)*a@ + c@)
    Next
  Next
  
  For b@ = 1 To a@
    d@ = a@ * 2 - 2 * b@ - 2
    For c@ = 1 To b@
      Print Tab(d@ + c@ * 4 + (1 - Len(Str(@(b@*a@ + c@))))); @(b@*a@ + c@);
    Next
  Next
  
  Print
Return
Output:
                              1
                            1   1
                          1   1   1
                        1   2   1   1
                      1   2   2   1   1
                    1   3   3   2   1   1
                  1   3   4   3   2   1   1
                1   4   5   5   3   2   1   1
              1   4   7   6   5   3   2   1   1
            1   5   8   9   7   5   3   2   1   1
          1   5  10  11  10   7   5   3   2   1   1
        1   6  12  15  13  11   7   5   3   2   1   1
      1   6  14  18  18  14  11   7   5   3   2   1   1
    1   7  16  23  23  20  15  11   7   5   3   2   1   1
  1   7  19  27  30  26  21  15  11   7   5   3   2   1   1

0 OK, 0:30 

VBA

Public Sub nine_billion_names()
    Dim p(25, 25) As Long
    p(1, 1) = 1
    For i = 2 To 25
        For j = 1 To i
            p(i, j) = p(i - 1, j - 1) + p(i - j, j)
        Next j
    Next i
    For i = 1 To 25
        Debug.Print String$(50 - 2 * i, " ");
        For j = 1 To i
            Debug.Print String$(4 - Len(CStr(p(i, j))), " ") & p(i, j);
        Next j
        Debug.Print
    Next i
End Sub
Output:
                                                   1
                                                 1   1
                                               1   1   1
                                             1   2   1   1
                                           1   2   2   1   1
                                         1   3   3   2   1   1
                                       1   3   4   3   2   1   1
                                     1   4   5   5   3   2   1   1
                                   1   4   7   6   5   3   2   1   1
                                 1   5   8   9   7   5   3   2   1   1
                               1   5  10  11  10   7   5   3   2   1   1
                             1   6  12  15  13  11   7   5   3   2   1   1
                           1   6  14  18  18  14  11   7   5   3   2   1   1
                         1   7  16  23  23  20  15  11   7   5   3   2   1   1
                       1   7  19  27  30  26  21  15  11   7   5   3   2   1   1
                     1   8  21  34  37  35  28  22  15  11   7   5   3   2   1   1
                   1   8  24  39  47  44  38  29  22  15  11   7   5   3   2   1   1
                 1   9  27  47  57  58  49  40  30  22  15  11   7   5   3   2   1   1
               1   9  30  54  70  71  65  52  41  30  22  15  11   7   5   3   2   1   1

V (Vlang)

Translation of: Go
import math.big

fn int_min(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

fn cumu (mut cache [][]big.Integer, n int) []big.Integer {
    for y := cache.len; y <= n; y++ {
        mut row := [big.zero_int]
        for x := 1; x <= y; x++ {
            cache_value := cache[y-x][int_min(x, y-x)]
            row << row[row.len-1] + cache_value
        }
        cache << row
    }
    return cache[n]
}
fn main() {
 
	mut cache := [[big.one_int]]
 
 
	row := fn[mut cache](n int) {
		e := cumu(mut cache, n)
		for i := 0; i < n; i++ {
			print(" ${e[i+1]-e[i]} ")
		}
		println('')
	}
 
	println("rows:")
	for x := 1; x < 11; x++ {
		row(x)
	}
	println('')
 
	println("sums:")
	for num in [23, 123, 1234, 12345] {
		r := cumu(mut cache, num)
		println("$num ${r[r.len-1]}")
	}
}
Output:
rows:
 1 
 1  1 
 1  1  1 
 1  2  1  1 
 1  2  2  1  1 
 1  3  3  2  1  1 
 1  3  4  3  2  1  1 
 1  4  5  5  3  2  1  1 
 1  4  7  6  5  3  2  1  1 
 1  5  8  9  7  5  3  2  1  1 

sums:
23 1255
123 2552338241
1234 156978797223733228787865722354959930
12345 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Wren

Translation of: Python
Library: Wren-big
Library: Wren-fmt
import "./big" for BigInt
import "./fmt" for Fmt

var cache = [[BigInt.one]]
var cumu = Fn.new { |n|
    if (cache.count <= n) {
        (cache.count..n).each { |l|
            var r = [BigInt.zero]
            (1..l).each { |x|
                var min = l - x
                if (x < min) min = x
                r.add(r[-1] + cache[l - x][min])
            }
            cache.add(r)
        }
    }
    return cache[n]
}

var row = Fn.new { |n|
    var r = cumu.call(n)
    return (0...n).map { |i| r[i+1] - r[i] }.toList
}

System.print("Rows:")
(1..25).each { |i|
    Fmt.print("$2d: $s", i, row.call(i))
}

System.print("\nSums:")
[23, 123, 1234, 12345].each { |i|
    Fmt.print("$5s: $s", i, cumu.call(i)[-1])
}
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
11: 1 5 10 11 10 7 5 3 2 1 1
12: 1 6 12 15 13 11 7 5 3 2 1 1
13: 1 6 14 18 18 14 11 7 5 3 2 1 1
14: 1 7 16 23 23 20 15 11 7 5 3 2 1 1
15: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
16: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
17: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
18: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
19: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
20: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
21: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
22: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
23: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
24: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
25: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1

Sums:
   23: 1255
  123: 2552338241
 1234: 156978797223733228787865722354959930
12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

Yabasic

Translation of: VBA
clear screen

Sub nine_billion_names(rows)
    local p(rows, rows), i, j, column
    
    p(1, 1) = 1
    
    For i = 2 To rows
        For j = 1 To i
            p(i, j) = p(i - 1, j - 1) + p(i - j, j)
        Next j
    Next i
    For i = 1 To rows
        column = rows * 2 - 2 * i - 2
        For j = 1 To i
            Print at(column + j * 4 + (1 - len(str$(p(i, j)))), i), p(i, j)
        Next j
    Next i
End Sub

nine_billion_names(20)

zkl

Translation of: C

Takes its time getting to 100,000 but it does. Uses the GMP big int library. Does the big int math in place to avoid garbage creation.

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();
}

The .fp/.fp1 methods create a closure, fixing the first or second parameter.

Output:
23:	1255
123:	2552338241
1234:	156978797223733228787865722354959930
12345:	69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
...
100000:	27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519