9 billion names of God the integer: Difference between revisions
Content deleted Content added
→{{header|Lua}}: added Lua solution |
|||
(47 intermediate revisions by 21 users not shown) | |||
Line 1:
{{task}}
This task is a variation of the [[wp:The Nine Billion Names of God#Plot_summary|short story by Arthur C. Clarke]].
Line 37 ⟶ 38:
If your environment is able, plot <math>P(n)</math> against <math>n</math> for <math>n=1\ldots 999</math>.
;Related tasks
* [[Partition function P]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">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))</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* 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"
</syntaxhighlight>
{{out}}
<pre>
Total : 7 pour 5
Total : 1255 pour 23
Total : 2552338241 pour 123
Total : 18324532310194337942 pour 524
Number too large !!.
</pre>
=={{header|Ada}}==
Line 43 ⟶ 303:
{{libheader|Ada.Numerics.Big_Numbers.Big_Integers}}
<
with Ada.Numerics.Big_Numbers.Big_Integers;
Line 184 ⟶ 444:
Triangle.Print;
Row_Summer.Put_Sums;
end Names_Of_God;</
{{out}}
Line 239 ⟶ 499:
9227311238999702284408609370935531629697851569569892196108480158600
569421098519
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* 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"
</syntaxhighlight>
{{out}}
<pre>
Total : 7
Total : 1255
Total : 2552338241
Number too large !!.
</pre>
=={{header|AutoHotkey}}==
<
InputBox, Enter_value, Enter the no. of lines sought
Line 299 ⟶ 720:
}
~Esc::ExitApp</
{{out}}
If user inputs 25, the result shall be:
Line 334 ⟶ 755:
If we forgo the rows and only want to calculate <math>P(n)</math>, using the recurrence relation <math>P_n = \sum_{k=1}^n (-1)^{k+1} \Big(P_{n-k(3k-1)/2} + P_{n-k(3k+1)/2}\Big)</math> is a better way. This requires <math>O(n^2)</math> storage for caching instead the <math>O(n^3)</math>-ish for storing all the rows.
<
#include <gmp.h>
Line 373 ⟶ 794:
at++;
}
}</
{{out}}
<pre>
Line 388 ⟶ 809:
(this requires a System.Numerics registry reference)
<
using System.Collections.Generic;
using System.Linq;
Line 485 ⟶ 906:
}
}
</syntaxhighlight>
{{out}}
<pre> 1
Line 526 ⟶ 947:
===The Code===
see [[http://rosettacode.org/wiki/Talk:9_billion_names_of_God_the_integer#The_Green_Triangle The Green Triangle]].
<
// Calculate hypotenuse n of OTT assuming only nothingness, unity, and hyp[n-1] if n>1
// Nigel Galloway, May 6th., 2013
Line 535 ⟶ 956:
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);}
}
</syntaxhighlight>
===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>
Line 550 ⟶ 971:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 574 ⟶ 995:
===The One True Triangle, OTT===
The following will display OTT(25).
<
int main(){
N = 25;
Line 599 ⟶ 1,020:
std::cout << "1 1" << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 631 ⟶ 1,052:
===Values of Integer Partition Function===
Values of the Integer Partition function may be extracted as follows:
<
#include <iostream>
int main(){
Line 643 ⟶ 1,064:
std::cout << "G(123456) = " << r << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 654 ⟶ 1,075:
=={{header|Clojure}}==
<
(cond (<= row 0) 0
(<= column 0) 0
Line 672 ⟶ 1,093:
(print-row x)))
(print-triangle 25)</
=={{header|Common Lisp}}==
<
(cond ((<= row 0) 0)
((<= column 0) 0)
Line 690 ⟶ 1,111:
(9-billion-names-triangle 25)
</syntaxhighlight>
=={{header|Crystal}}==
{{trans|Ruby}}
===Naive Solution===
<
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 }</
{{out}}
<pre>
Line 733 ⟶ 1,154:
===Producing rows===
{{trans|Python}}
<
auto cumu(in uint n) {
Line 759 ⟶ 1,180:
foreach (x; [23, 123, 1234])
writeln(x, " ", x.cumu.back);
}</
{{out}}
<pre>Rows:
Line 781 ⟶ 1,202:
===Only partition functions===
{{trans|C}}
<
struct Names {
Line 831 ⟶ 1,252:
writefln("%6d: %s", i, p);
}
}</
{{out}}
<pre> 23: 1255
Line 854 ⟶ 1,275:
{{trans|Python}}
<
List<BigInt> partitions(int n) {
Line 887 ⟶ 1,308:
print('$i: ${partitions(i)[i]}');
}
}</
In main:
<
main(List<String> arguments) {
names_of_god.printRows(min: 1, max: 11);
names_of_god.printSums([23, 123, 1234, 12345]);
}</
{{out}}
Line 918 ⟶ 1,339:
=={{header|Dyalect}}==
<
func namesOfGod(n) {
for l in cache.
var r = [0]
r.
} else {
for x in 1..l {
r.Add(r[r.Length() - 1] + cache[l - x][min(x, l-x)])
}
}
cache.
}
return cache[n]
}
func row(n) {
var
for i in 0..
}
return
}
for x in 1..25 {
print("\(x): \(row(x))")
}</
Output:
Line 983 ⟶ 1,400:
{{trans|Ruby}}
Naive Solution
<
def g(n,g) when g == 1 or n < g, do: 1
def g(n,g) do
Line 994 ⟶ 1,411:
Enum.each(1..25, fn n ->
IO.puts Enum.map(1..n, fn g -> "#{God.g(n,g)} " end)
end)</
{{out}}
Line 1,028 ⟶ 1,445:
Step 1: Print the pyramid for a smallish number of names. The P function is implement as described on [http://mathworld.wolfram.com/PartitionFunctionP.html partition function], (see 59 on that page). This is slow for N > 100, but works fine for the example: 10.
<syntaxhighlight lang="erlang">
-module(triangle).
-export([start/1]).
Line 1,050 ⟶ 1,467:
formula(A1,B1)->
formula(A1-1,B1-1)+formula(A1-B1,B1).
</syntaxhighlight>
{{out}}
Line 1,084 ⟶ 1,501:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<
sequences ;
Line 1,104 ⟶ 1,521:
25 .triangle nl
"Sums:" print { 23 123 1234 12345 } [ dup pprint bl G . ] each</
{{out}}
<pre>
Line 1,185 ⟶ 1,602:
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<
' compile with: fbc -s console
Line 1,222 ⟶ 1,639:
' ------=< MAIN >=------
Dim As ULong n, k, max = 25 ' with max >
Dim As ULongInt p(max, max) ' to big for a 64bit unsigned integer
Line 1,273 ⟶ 1,690:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 1
Line 1,312 ⟶ 1,729:
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
{
Line 1,367 ⟶ 1,784:
testRow[1234]
testRow[12345]
</syntaxhighlight>
<pre>
Line 1,402 ⟶ 1,819:
</pre>
==
The partition function is built-in.
<
[ [ 1 ],
Line 1,436 ⟶ 1,853:
[ 1255, 2552338241, 156978797223733228787865722354959930,
69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 ]</
=={{header|Go}}==
<
import (
Line 1,489 ⟶ 1,906:
fmt.Printf("%d %v\n", num, r[len(r)-1].Text(10))
}
}</
{{out}}
<pre>
Line 1,512 ⟶ 1,929:
=={{header|Groovy}}==
<
def partitions(c)
{
Line 1,554 ⟶ 1,971:
{partitions(i);}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,587 ⟶ 2,004:
=={{header|Haskell}}==
<
cumu :: [[Integer]]
Line 1,607 ⟶ 2,024:
main = do
mapM_ print $ take 10 rows
mapM_ (print.sums) [23, 123, 1234, 12345]</
{{out}}
<pre>
Line 1,631 ⟶ 2,048:
{{trans|Python}}
<
n := integer(!A) | 10
every r := 2 to (n+1) do write(right(r-1,2),": ",showList(row(r)))
Line 1,655 ⟶ 2,072:
every (s := "[") ||:= (!A||", ")
return s[1:-2]||"]"
end</
{{out}} (terminated without waiting for output of cumu(12345)):
Line 1,680 ⟶ 2,097:
=={{header|J}}==
Recursive calculation of a row element:
<
Calculation of the triangle:
<
'''Show triangle''':
<
1
1 1
Line 1,694 ⟶ 2,111:
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:
<
z=. (y+1){. 1x
for_ks. <\1+i.y do.
Line 1,709 ⟶ 2,126:
z=. a n}z
end.
)</
{{out}}
<pre> ({ [: rowSums >./) 3 23 123 1234
Line 1,717 ⟶ 2,134:
Translation of [[9_billion_names_of_God_the_integer#Python|Python]] via [[9_billion_names_of_God_the_integer#D|D]]
{{works with|Java|8}}
<
import java.util.*;
import static java.util.Arrays.asList;
Line 1,757 ⟶ 2,174:
}
}
}</
<pre>Rows:
Line 1,777 ⟶ 2,194:
=={{header|JavaScript}}==
===Solution 1===
{{trans|Python}}
<syntaxhighlight lang="javascript">
(function () {
var cache = [
Line 1,831 ⟶ 2,249:
}
// 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]);
});
})()
</syntaxhighlight>
===Solution 2===
Clean and straightforward solution
<syntaxhighlight lang="javascript">
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))
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|jq}}==
''Adapted from [[#Wren|Wren]]''
'''Works with gojq, the Go implementation of jq, and with fq.'''
This entry uses the same algorithm as [[#Wren|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]].
<syntaxhighlight lang=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]] ) ;
</syntaxhighlight>
'''Invocation''': gojq -n -rcf 9-billion.jq
{{output}}
<pre>
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]
</pre>
=={{header|Julia}}==
<
using Combinatorics, StatsBase
Line 1,879 ⟶ 2,451:
end
</
[1]
[1, 1]
Line 1,921 ⟶ 2,493:
=={{header|Kotlin}}==
{{trans|Swift}}
<
import java.math.BigInteger
import java.util.ArrayList
Line 1,955 ⟶ 2,527:
System.out.printf("%s %s%n", it, c[c.size - 1])
}
}</
<pre>
Line 1,993 ⟶ 2,565:
=={{header|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".
<
loop(-from=$cache->size,-to=#n+1) => {
local(r = array(0), l = loop_count)
Line 2,023 ⟶ 2,595:
cumu(#x+1)->last
'\r'
^}</
{{out}}
Line 2,060 ⟶ 2,632:
=={{header|Lua}}==
<
local tri = {{1}}
for r = 2, n do
Line 2,082 ⟶ 2,654:
end
print("G(23) = " .. G(23))
print("G(123) = " .. G(123))</
{{out}}
<pre>1: 1
Line 2,113 ⟶ 2,685:
=={{header|Maple}}==
<
Triangle := proc(m)
local i;
Line 2,120 ⟶ 2,692:
end do
end proc:
</syntaxhighlight>
{{out}}
Line 2,134 ⟶ 2,706:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
{{out}}
<pre>1
Line 2,148 ⟶ 2,720:
Here I use the bulit-in function PartitionsP to calculate <math>P(n)</math>.
<
{{out}}
<pre>{1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736}</pre>
<
[[File:9 billion names of God the integer Mathematica.png]]
=={{header|Maxima}}==
<
{{out}}
<pre>[1]
Line 2,185 ⟶ 2,757:
Using the built-in function to calculate <math>P(n)</math>:
<
{{out}}
<pre>(%o1) [1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736]</pre>
Line 2,191 ⟶ 2,763:
=={{header|Nim}}==
{{trans|Python}}
<
var cache = @[@[1.initBigInt]]
Line 2,216 ⟶ 2,788:
for x in [23, 123, 1234, 12345]:
let c = cumu(x)
echo x, " ", c[c.high]</
{{out}}
<pre>@[1]
Line 2,236 ⟶ 2,808:
Faster version:
{{trans|C}}
<
var p = @[1.initBigInt]
Line 2,268 ⟶ 2,840:
let p = partitions(i)
if i in ns:
echo i,": ",p</
{{out}}
<pre>23: 1255
Line 2,276 ⟶ 2,848:
=={{header|OCaml}}==
<
let get, sum_unto =
let cache = ref [||]
Line 2,355 ⟶ 2,927:
end
[23;123;1234;12345;123456]
</syntaxhighlight>
{{out}}
<pre>
Line 2,401 ⟶ 2,973:
=={{header|Ol}}==
<
(define (nine-billion-names row column)
(cond
Line 2,426 ⟶ 2,998:
(print-triangle 25)
</syntaxhighlight>
{{Out}}
<pre>
Line 2,458 ⟶ 3,030:
=={{header|PARI/GP}}==
<
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))</
{{out}}
<pre>[1]
Line 2,520 ⟶ 3,092:
=={{header|Perl}}==
{{libheader|ntheory}}
<
sub triangle_row {
Line 2,531 ⟶ 3,103:
printf "%2d: %s\n", $_, join(" ",triangle_row($_)) for 1..25;
print "\n";
say "P($_) = ", partitions($_) for (23, 123, 1234, 12345);</
{{out}}
[rows are the same as below]
Line 2,540 ⟶ 3,112:
{{trans|Raku}}
<
use strict;
use warnings;
Line 2,581 ⟶ 3,153:
print $i, "\n";
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,620 ⟶ 3,192:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\9billionnames.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cumu</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cumu</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">25</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">i</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,683 ⟶ 3,257:
{{trans|C}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">calc</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">*</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">3</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">else</span> <span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">else</span> <span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">cx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">123</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1234</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12345</span><span style="color: #0000FF;">}</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"sums:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">at</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cx</span><span style="color: #0000FF;">[$]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">cx</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">calc</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">cx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">at</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])})</span>
<span style="color: #000000;">at</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
Line 2,724 ⟶ 3,301:
=== Third and last, a simple plot ===
{{libheader|Phix/pGUI}}
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupControlsOpen</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupPlot</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"MENUITEMPROPERTIES=Yes, SIZE=640x320"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"9 Billion Names"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLEFONTSIZE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"10"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLEFONTSTYLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ITALIC"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"GRIDLINESTYLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DOTTED"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"GRID"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"YES"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_XLABEL"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"x"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_YLABEL"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"G(x)"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_XFONTSTYLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ITALIC"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_YFONTSTYLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ITALIC"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_XSCALE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"LOG10"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_YSCALE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"LOG10"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_YTICKSIZEAUTO"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"NO"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_YTICKMAJORSIZE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"8"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"AXS_YTICKMINORSIZE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"0"</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">IupPlotBegin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">999</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">IupPlotAdd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">row</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)))</span> <span style="color: #000080;font-style:italic;">-- (row() from part 1)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupPlotEnd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"9 Billion Names"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupMap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupShowXY</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #004600;">IUP_CENTER</span><span style="color: #0000FF;">,</span><span style="color: #004600;">IUP_CENTER</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</syntaxhighlight>-->
=={{header|Phixmonti}}==
{{trans|Yabasic}}
<syntaxhighlight lang="phixmonti">/# 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</syntaxhighlight>
{{out}}
<pre> 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 ===</pre>
=={{header|Picat}}==
===The triangle, using constraint modelling===
Using constraint modeling to generate all the partitions 1..25.
<syntaxhighlight lang="picat">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.</syntaxhighlight>
{{out}}
<pre>[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]</pre>
===Number of partitions===
This is the Picat solution of [http://rosettacode.org/wiki/Partition_function_P Partition_function_P].
<syntaxhighlight lang="picat">% 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.</syntaxhighlight>
{{out}}
<pre>23 = 1255
123 = 2552338241
1234 = 156978797223733228787865722354959930
12345 = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
123456 = 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989</pre>
===Recursion===
Here is a port of the Haskell code from [http://oeis.org/A000041 oeis.org/A000041]. Though for 12345 it's too slow (and eats much RAM).
<syntaxhighlight lang="picat">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)).</syntaxhighlight>
=={{header|PicoLisp}}==
{{trans|Python}}
<
(let C '((1))
(do N
Line 2,808 ⟶ 3,548:
(println (sumr I)) ) )
(bye)</
{{out}}
Line 2,841 ⟶ 3,581:
69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
0.626 sec</pre>
=={{header|Pike}}==
{{trans|Python}}
<syntaxhighlight lang="pike">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;
}</syntaxhighlight>
{{out}} Not wait for "12345" output.
<pre>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</pre>
=={{header|PureBasic}}==
<
Define nMax.i=25, n.i, k.i
Dim pfx.s(1)
Line 2,912 ⟶ 3,713:
PrintN(sum(12345,pfx()))
Input()
</syntaxhighlight>
{{out}}
<pre>
Line 2,948 ⟶ 3,749:
=={{header|Python}}==
<
def cumu(n):
for l in range(len(cache), n+1):
Line 2,966 ⟶ 3,767:
print "\nsums:"
for x in [23, 123, 1234, 12345]: print x, cumu(x)[-1]</
{{out}} (I didn't actually wait long enough to see what the sum for 12345 is)
<pre>
Line 2,988 ⟶ 3,789:
</pre>
To calculate partition functions only:
<
diffs,k,s = [],1,1
while k * (3*k-1) < 2*N:
Line 3,005 ⟶ 3,806:
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:
{{trans|C}}
<
partitions.p.append(0)
Line 3,046 ⟶ 3,847:
print "%6d: %s" % (i, p)
main()</
{{out}}
<pre> 23: 1255
Line 3,052 ⟶ 3,853:
1234: 156978797223733228787865722354959930
12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736</pre>
=={{header|R}}==
<syntaxhighlight lang="racket">
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")
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Racket}}==
<
(define (cdr-empty ls) (if (empty? ls) empty (cdr ls)))
Line 3,077 ⟶ 3,924:
(newline)
(map G '(23 123 1234)))
</syntaxhighlight>
{{out}}
Line 3,114 ⟶ 3,961:
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.)
<syntaxhighlight lang="raku"
my @sums = 0;
sub nextrow($n) {
for +@todo .. $n -> $l {
my $r = [];
for reverse ^$l -> $x {
Line 3,136 ⟶ 3,981:
say "rows:";
say .fmt('%2d'), ": ", nextrow($_)[] for 1..
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 {
}</
{{out}}
<pre>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:
Line 3,161 ⟶ 4,028:
1234 156978797223733228787865722354959930
12345 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736</pre>
=={{header|Red}}==
<syntaxhighlight lang="rebol">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|REXX}}==
Line 3,192 ⟶ 4,145:
</big>
which is derived from Euler's generating function.
<
numeric digits 400 /*be able to handle larger numbers. */
parse arg N . /*obtain optional argument from the CL.*/
Line 3,249 ⟶ 4,202:
else $= $ - x - y /* " " " " " " even.*/
end /*k*/ /* [↑] Euler's recursive func.*/
@.n= $; return $ /*use memoization; return num.*/</
{{out|output|text= when using the default input (of 25 rows):}}
<pre>
Line 3,309 ⟶ 4,262:
=={{header|Ruby}}==
===Naive Solution===
<
# Generate IPF triangle
# Nigel_Galloway: May 1st., 2013.
Line 3,320 ⟶ 4,273:
puts (1..n).map {|g| "%4s" % g(n,g)}.join
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,351 ⟶ 4,304:
===Full Solution===
<
# Find large values of IPF
# Nigel_Galloway: May 1st., 2013.
Line 3,382 ⟶ 4,335:
n = 3 + @ipn1.inject(:+) + @ipn2.inject(:+)
puts "G(12345) = #{n}"
</syntaxhighlight>
{{out}}
<pre>
Line 3,393 ⟶ 4,346:
=={{header|Rust}}==
{{trans|Python}}
<
use std::cmp;
Line 3,437 ⟶ 4,390:
println!("{}: {}", x, s);
}
}</
{{out}}
<pre>rows:
Line 3,474 ⟶ 4,427:
=={{header|Scala}}==
===Naive Solution===
<
object Main {
Line 3,511 ⟶ 4,464:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,554 ⟶ 4,507:
===Full Solution===
<
cache(0) = 1
val cacheNaive = scala.collection.mutable.Map[Tuple2[Int, Int], BigInt]()
Line 3,602 ⟶ 4,555:
println(quickPartitions(123))
println(quickPartitions(1234))
println(quickPartitions(12345))</
{{out}}
<pre> 1
Line 3,633 ⟶ 4,586:
=={{header|scheme}}==
<
(define (sigma g x y)
(define (sum i)
Line 3,652 ⟶ 4,605:
(cond ((< i x) (begin (display (line i)) (display "\n") (print-loop (+ i 1)) ))))
(print-loop 1))
(print 25)</
{{out}}
Line 3,683 ⟶ 4,636:
=={{header|Sidef}}==
<
func cumu (n) {
Line 3,710 ⟶ 4,663:
for i in [23, 123, 1234, 12345] {
"%2s : %4s\n".printf(i, cumu(i)[-1])
}</
{{out}}
Line 3,739 ⟶ 4,692:
=={{header|SPL}}==
<
> n, 1..25
k = 50-n*2
Line 3,776 ⟶ 4,729:
<
<= p[n+1]
.</
{{out}}
<pre>
Line 3,812 ⟶ 4,765:
=={{header|Stata}}==
<
function part(n) {
a = J(n,n,.)
Line 3,821 ⟶ 4,774:
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 [
'''Output'''
Line 3,851 ⟶ 4,804:
=={{header|Swift}}==
{{trans|Python}}
<
func namesOfGod(n:Int) -> [Int] {
for l in cache.count...n {
Line 3,884 ⟶ 4,837:
var numInt = array[array.count - 1]
println("\(x): \(numInt)")
}</
{{out}}
<pre>
Line 3,923 ⟶ 4,876:
=={{header|Tcl}}==
{{trans|Python}}
<
proc cumu {n} {
global cache
Line 3,952 ⟶ 4,905:
foreach x {23 123 1234 12345} {
puts "${x}: [lindex [cumu $x] end]"
}</
{{out}}
<pre>
Line 3,975 ⟶ 4,928:
<small>(I killed the run when it started to take a significant proportion of my system's memory.)</small>
=={{header|uBasic/4tH}}==
{{trans|VBA}}
Since uBasic/4tH features a single array of 256 elements, level "15" is the best that can be achieved.
<syntaxhighlight lang="text">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</syntaxhighlight>
{{Out}}
<pre> 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 </pre>
=={{header|VBA}}==
<
Dim p(25, 25) As Long
p(1, 1) = 1
Line 3,991 ⟶ 4,989:
Debug.Print
Next i
End Sub</
<pre> 1
1 1
Line 4,011 ⟶ 5,009:
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</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">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]}")
}
}</syntaxhighlight>
{{out}}
<pre>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
</pre>
=={{header|Wren}}==
{{trans|Python}}
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">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])
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Yabasic}}==
{{trans|VBA}}
<
Sub nine_billion_names(rows)
Line 4,034 ⟶ 5,175:
End Sub
nine_billion_names(20)</
=={{header|Zig}}==
===Standard triangle solution===
<syntaxhighlight lang="zig">const std = @import("std");
const print = std.debug.print;
const bigint = std.math.big.int.Managed;
const eql = std.mem.eql;
const Array = std.ArrayList;
const Array1 = Array(bigint);
const Array2 = Array(Array1);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
fn cumu(cache: *Array2, n: usize) !*Array1 {
var y = cache.items.len;
while (cache.items.len <= n) : (y += 1) {
var roww = Array1.init(allocator);
try roww.append(try bigint.init(allocator));
for (1..y + 1) |x| {
var cache_value = try cache.items[y - x].items[@min(x, y - x)].clone();
try cache_value.add(&cache_value, &roww.getLast());
try roww.append(cache_value);
}
try cache.append(roww);
}
return &(cache.items[n]);
}
fn row(cache: *Array2, n: usize) !void {
const e = try cumu(cache, n);
var v = try bigint.init(allocator);
for (0..n) |i| {
try v.sub(&e.items[i + 1], &e.items[i]);
print(" {} ", .{v});
}
v.deinit();
print("\n", .{});
}
pub fn main() !void {
var cache = Array2.init(allocator);
defer {
cache.deinit();
}
defer {
while (cache.popOrNull()) |l| {
l.deinit();
}
}
var cache0 = Array1.init(allocator);
var v = try bigint.init(allocator);
try v.set(1);
try cache0.append(v);
try cache.append(cache0);
print("rows:\n", .{});
for (1..1000) |x| {
try row(&cache, x);
}
print("\nsums:\n", .{});
for ([_]usize{ 23, 123, 999 }) |num| {
const r = try cumu(&cache, num);
print("{d: >4} {d}\n", .{ num, r.getLast() });
}
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
===Here is faster version===
<syntaxhighlight lang="zig">const std = @import("std");
const print = std.debug.print;
const bigint = std.math.big.int.Managed;
const eql = std.mem.eql;
const Array = std.ArrayList;
const Array1 = Array(bigint);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
fn calc ( n:usize, p:*Array1) !void {
for ( 1..n+1 ) |k| {
var d:i64 = @intCast(n);
d -= @intCast(k*(3*k - 1)/2);
inline for ( 0..2 ) |_| {
if ( d < 0 ) return;
if (k&1>0) try p.items[n].add ( &p.items[n], &p.items[@intCast(d)] )
else try p.items[n].sub ( &p.items[n], &p.items[@intCast(d)] );
d -= @intCast(k);
}
}
}
fn main() !void {
const s = [_]usize{ 23, 123, 1234, 12345, 123456 };
var p = Array1.init ( allocator );
try p.append ( try bigint.initSet ( allocator, 1 ) );
var i:usize=1;
for ( s )|m|{
while (i<=m):(i+=1){
try p.append( try bigint.init(allocator) );
try calc( i, &p );
}
print("P({d}) = {d}\n", .{m,p.items[m]} );
}
}
</syntaxhighlight>
{{out}}
<pre>
P(23) = 1255
P(123) = 2552338241
P(1234) = 156978797223733228787865722354959930
P(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
P(123456) = 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989
</pre>
=={{header|zkl}}==
{{trans|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.
<
const N=0d100_000;
Line 4,055 ⟶ 5,338:
}
}
}</
<
p[0].set(1);
Line 4,062 ⟶ 5,345:
(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.
{{out}}
Line 4,073 ⟶ 5,356:
100000: 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
</pre>
{{omit from|6502 Assembly|Good luck doing this with only 64K of addressable memory}}
{{omit from|Z80 Assembly|See above}}
|