9 billion names of God the integer: Difference between revisions
Implementation for R
(+add Pike) |
(Implementation for R) |
||
| (10 intermediate revisions by 9 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 46 ⟶ 45:
{{trans|Python}}
<
F cumu(n)
L(l) :cache.len .. n
Line 99 ⟶ 98:
V p = partitions(i)
I i C ns
print(‘#6: #.’.format(i, p))</
{{out}}
Line 124 ⟶ 123:
=={{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 */
Line 290 ⟶ 289:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
{{out}}
<pre>
Line 304 ⟶ 303:
{{libheader|Ada.Numerics.Big_Numbers.Big_Integers}}
<
with Ada.Numerics.Big_Numbers.Big_Integers;
Line 445 ⟶ 444:
Triangle.Print;
Row_Summer.Put_Sums;
end Names_Of_God;</
{{out}}
Line 503 ⟶ 502:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program integerName.s */
Line 654 ⟶ 653:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{out}}
<pre>
Line 664 ⟶ 663:
=={{header|AutoHotkey}}==
<
InputBox, Enter_value, Enter the no. of lines sought
Line 721 ⟶ 720:
}
~Esc::ExitApp</
{{out}}
If user inputs 25, the result shall be:
Line 756 ⟶ 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 795 ⟶ 794:
at++;
}
}</
{{out}}
<pre>
Line 810 ⟶ 809:
(this requires a System.Numerics registry reference)
<
using System.Collections.Generic;
using System.Linq;
Line 907 ⟶ 906:
}
}
</syntaxhighlight>
{{out}}
<pre> 1
Line 948 ⟶ 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 957 ⟶ 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 972 ⟶ 971:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 996 ⟶ 995:
===The One True Triangle, OTT===
The following will display OTT(25).
<
int main(){
N = 25;
Line 1,021 ⟶ 1,020:
std::cout << "1 1" << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,053 ⟶ 1,052:
===Values of Integer Partition Function===
Values of the Integer Partition function may be extracted as follows:
<
#include <iostream>
int main(){
Line 1,065 ⟶ 1,064:
std::cout << "G(123456) = " << r << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,076 ⟶ 1,075:
=={{header|Clojure}}==
<
(cond (<= row 0) 0
(<= column 0) 0
Line 1,094 ⟶ 1,093:
(print-row x)))
(print-triangle 25)</
=={{header|Common Lisp}}==
<
(cond ((<= row 0) 0)
((<= column 0) 0)
Line 1,112 ⟶ 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 1,155 ⟶ 1,154:
===Producing rows===
{{trans|Python}}
<
auto cumu(in uint n) {
Line 1,181 ⟶ 1,180:
foreach (x; [23, 123, 1234])
writeln(x, " ", x.cumu.back);
}</
{{out}}
<pre>Rows:
Line 1,203 ⟶ 1,202:
===Only partition functions===
{{trans|C}}
<
struct Names {
Line 1,253 ⟶ 1,252:
writefln("%6d: %s", i, p);
}
}</
{{out}}
<pre> 23: 1255
Line 1,276 ⟶ 1,275:
{{trans|Python}}
<
List<BigInt> partitions(int n) {
Line 1,309 ⟶ 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 1,340 ⟶ 1,339:
=={{header|Dyalect}}==
<
func namesOfGod(n) {
Line 1,368 ⟶ 1,367:
for x in 1..25 {
print("\(x): \(row(x))")
}</
Output:
Line 1,401 ⟶ 1,400:
{{trans|Ruby}}
Naive Solution
<
def g(n,g) when g == 1 or n < g, do: 1
def g(n,g) do
Line 1,412 ⟶ 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,446 ⟶ 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,468 ⟶ 1,467:
formula(A1,B1)->
formula(A1-1,B1-1)+formula(A1-B1,B1).
</syntaxhighlight>
{{out}}
Line 1,502 ⟶ 1,501:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<
sequences ;
Line 1,522 ⟶ 1,521:
25 .triangle nl
"Sums:" print { 23 123 1234 12345 } [ dup pprint bl G . ] each</
{{out}}
<pre>
Line 1,603 ⟶ 1,602:
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<
' compile with: fbc -s console
Line 1,691 ⟶ 1,690:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 1
Line 1,730 ⟶ 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,785 ⟶ 1,784:
testRow[1234]
testRow[12345]
</syntaxhighlight>
<pre>
Line 1,822 ⟶ 1,821:
=={{header|GAP}}==
The partition function is built-in.
<
[ [ 1 ],
Line 1,854 ⟶ 1,853:
[ 1255, 2552338241, 156978797223733228787865722354959930,
69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 ]</
=={{header|Go}}==
<
import (
Line 1,907 ⟶ 1,906:
fmt.Printf("%d %v\n", num, r[len(r)-1].Text(10))
}
}</
{{out}}
<pre>
Line 1,930 ⟶ 1,929:
=={{header|Groovy}}==
<
def partitions(c)
{
Line 1,972 ⟶ 1,971:
{partitions(i);}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,005 ⟶ 2,004:
=={{header|Haskell}}==
<
cumu :: [[Integer]]
Line 2,025 ⟶ 2,024:
main = do
mapM_ print $ take 10 rows
mapM_ (print.sums) [23, 123, 1234, 12345]</
{{out}}
<pre>
Line 2,049 ⟶ 2,048:
{{trans|Python}}
<
n := integer(!A) | 10
every r := 2 to (n+1) do write(right(r-1,2),": ",showList(row(r)))
Line 2,073 ⟶ 2,072:
every (s := "[") ||:= (!A||", ")
return s[1:-2]||"]"
end</
{{out}} (terminated without waiting for output of cumu(12345)):
Line 2,098 ⟶ 2,097:
=={{header|J}}==
Recursive calculation of a row element:
<
Calculation of the triangle:
<
'''Show triangle''':
<
1
1 1
Line 2,112 ⟶ 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 2,127 ⟶ 2,126:
z=. a n}z
end.
)</
{{out}}
<pre> ({ [: rowSums >./) 3 23 123 1234
Line 2,135 ⟶ 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 2,175 ⟶ 2,174:
}
}
}</
<pre>Rows:
Line 2,197 ⟶ 2,196:
===Solution 1===
{{trans|Python}}
<syntaxhighlight lang="javascript">
(function () {
var cache = [
Line 2,258 ⟶ 2,257:
});
})()
</syntaxhighlight>
===Solution 2===
Clean and straightforward solution
<
function genTriangle(n){ // O(n^3) time and O(n^2) space
var a = new Array(n)
Line 2,300 ⟶ 2,299:
console.log("G(" + x + ") = " + G(x))
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,334 ⟶ 2,333:
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 2,376 ⟶ 2,451:
end
</
[1]
[1, 1]
Line 2,418 ⟶ 2,493:
=={{header|Kotlin}}==
{{trans|Swift}}
<
import java.math.BigInteger
import java.util.ArrayList
Line 2,452 ⟶ 2,527:
System.out.printf("%s %s%n", it, c[c.size - 1])
}
}</
<pre>
Line 2,490 ⟶ 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,520 ⟶ 2,595:
cumu(#x+1)->last
'\r'
^}</
{{out}}
Line 2,557 ⟶ 2,632:
=={{header|Lua}}==
<
local tri = {{1}}
for r = 2, n do
Line 2,579 ⟶ 2,654:
end
print("G(23) = " .. G(23))
print("G(123) = " .. G(123))</
{{out}}
<pre>1: 1
Line 2,610 ⟶ 2,685:
=={{header|Maple}}==
<
Triangle := proc(m)
local i;
Line 2,617 ⟶ 2,692:
end do
end proc:
</syntaxhighlight>
{{out}}
Line 2,631 ⟶ 2,706:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
{{out}}
<pre>1
Line 2,645 ⟶ 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,682 ⟶ 2,757:
Using the built-in function to calculate <math>P(n)</math>:
<
{{out}}
<pre>(%o1) [1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736]</pre>
Line 2,688 ⟶ 2,763:
=={{header|Nim}}==
{{trans|Python}}
<
var cache = @[@[1.initBigInt]]
Line 2,713 ⟶ 2,788:
for x in [23, 123, 1234, 12345]:
let c = cumu(x)
echo x, " ", c[c.high]</
{{out}}
<pre>@[1]
Line 2,733 ⟶ 2,808:
Faster version:
{{trans|C}}
<
var p = @[1.initBigInt]
Line 2,765 ⟶ 2,840:
let p = partitions(i)
if i in ns:
echo i,": ",p</
{{out}}
<pre>23: 1255
Line 2,773 ⟶ 2,848:
=={{header|OCaml}}==
<
let get, sum_unto =
let cache = ref [||]
Line 2,852 ⟶ 2,927:
end
[23;123;1234;12345;123456]
</syntaxhighlight>
{{out}}
<pre>
Line 2,898 ⟶ 2,973:
=={{header|Ol}}==
<
(define (nine-billion-names row column)
(cond
Line 2,923 ⟶ 2,998:
(print-triangle 25)
</syntaxhighlight>
{{Out}}
<pre>
Line 2,955 ⟶ 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 3,017 ⟶ 3,092:
=={{header|Perl}}==
{{libheader|ntheory}}
<
sub triangle_row {
Line 3,028 ⟶ 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 3,037 ⟶ 3,112:
{{trans|Raku}}
<
use strict;
use warnings;
Line 3,078 ⟶ 3,153:
print $i, "\n";
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,117 ⟶ 3,192:
=={{header|Phix}}==
<!--<
<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>
Line 3,150 ⟶ 3,225:
<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>
<!--</
{{out}}
<pre>
Line 3,182 ⟶ 3,257:
{{trans|C}}
{{libheader|Phix/mpfr}}
<!--<
<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>
Line 3,214 ⟶ 3,289:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{Out}}
<pre>
Line 3,226 ⟶ 3,301:
=== Third and last, a simple plot ===
{{libheader|Phix/pGUI}}
<!--<
<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>
Line 3,258 ⟶ 3,333:
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
=={{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 3,313 ⟶ 3,548:
(println (sumr I)) ) )
(bye)</
{{out}}
Line 3,350 ⟶ 3,585:
{{trans|Python}}
<
array(array(int)) cache = ({({1})});
Line 3,388 ⟶ 3,623:
}
return 0;
}</
{{out}} Not wait for "12345" output.
<pre>rows:
Line 3,409 ⟶ 3,644:
=={{header|PureBasic}}==
<
Define nMax.i=25, n.i, k.i
Dim pfx.s(1)
Line 3,478 ⟶ 3,713:
PrintN(sum(12345,pfx()))
Input()
</syntaxhighlight>
{{out}}
<pre>
Line 3,514 ⟶ 3,749:
=={{header|Python}}==
<
def cumu(n):
for l in range(len(cache), n+1):
Line 3,532 ⟶ 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 3,554 ⟶ 3,789:
</pre>
To calculate partition functions only:
<
diffs,k,s = [],1,1
while k * (3*k-1) < 2*N:
Line 3,571 ⟶ 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,612 ⟶ 3,847:
print "%6d: %s" % (i, p)
main()</
{{out}}
<pre> 23: 1255
Line 3,618 ⟶ 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,643 ⟶ 3,924:
(newline)
(map G '(23 123 1234)))
</syntaxhighlight>
{{out}}
Line 3,680 ⟶ 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) {
Line 3,713 ⟶ 3,994:
for 23, 123, 1234, 12345 {
put $_, "\t", @names-of-God[$_];
}</
{{out}}
<pre>rows:
Line 3,749 ⟶ 4,030:
=={{header|Red}}==
<syntaxhighlight lang="rebol">
Red []
Line 3,795 ⟶ 4,076:
probe names 1234
</syntaxhighlight>
{{out}}
Line 3,864 ⟶ 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,921 ⟶ 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,981 ⟶ 4,262:
=={{header|Ruby}}==
===Naive Solution===
<
# Generate IPF triangle
# Nigel_Galloway: May 1st., 2013.
Line 3,992 ⟶ 4,273:
puts (1..n).map {|g| "%4s" % g(n,g)}.join
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,023 ⟶ 4,304:
===Full Solution===
<
# Find large values of IPF
# Nigel_Galloway: May 1st., 2013.
Line 4,054 ⟶ 4,335:
n = 3 + @ipn1.inject(:+) + @ipn2.inject(:+)
puts "G(12345) = #{n}"
</syntaxhighlight>
{{out}}
<pre>
Line 4,065 ⟶ 4,346:
=={{header|Rust}}==
{{trans|Python}}
<
use std::cmp;
Line 4,109 ⟶ 4,390:
println!("{}: {}", x, s);
}
}</
{{out}}
<pre>rows:
Line 4,146 ⟶ 4,427:
=={{header|Scala}}==
===Naive Solution===
<
object Main {
Line 4,183 ⟶ 4,464:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,226 ⟶ 4,507:
===Full Solution===
<
cache(0) = 1
val cacheNaive = scala.collection.mutable.Map[Tuple2[Int, Int], BigInt]()
Line 4,274 ⟶ 4,555:
println(quickPartitions(123))
println(quickPartitions(1234))
println(quickPartitions(12345))</
{{out}}
<pre> 1
Line 4,305 ⟶ 4,586:
=={{header|scheme}}==
<
(define (sigma g x y)
(define (sum i)
Line 4,324 ⟶ 4,605:
(cond ((< i x) (begin (display (line i)) (display "\n") (print-loop (+ i 1)) ))))
(print-loop 1))
(print 25)</
{{out}}
Line 4,355 ⟶ 4,636:
=={{header|Sidef}}==
<
func cumu (n) {
Line 4,382 ⟶ 4,663:
for i in [23, 123, 1234, 12345] {
"%2s : %4s\n".printf(i, cumu(i)[-1])
}</
{{out}}
Line 4,411 ⟶ 4,692:
=={{header|SPL}}==
<
> n, 1..25
k = 50-n*2
Line 4,448 ⟶ 4,729:
<
<= p[n+1]
.</
{{out}}
<pre>
Line 4,484 ⟶ 4,765:
=={{header|Stata}}==
<
function part(n) {
a = J(n,n,.)
Line 4,493 ⟶ 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 [[oeis:A008284|OEIS A008284]] and row sums with [[oeis:A000041|OEIS A000041]].
Line 4,523 ⟶ 4,804:
=={{header|Swift}}==
{{trans|Python}}
<
func namesOfGod(n:Int) -> [Int] {
for l in cache.count...n {
Line 4,556 ⟶ 4,837:
var numInt = array[array.count - 1]
println("\(x): \(numInt)")
}</
{{out}}
<pre>
Line 4,595 ⟶ 4,876:
=={{header|Tcl}}==
{{trans|Python}}
<
proc cumu {n} {
global cache
Line 4,624 ⟶ 4,905:
foreach x {23 123 1234 12345} {
puts "${x}: [lindex [cumu $x] end]"
}</
{{out}}
<pre>
Line 4,647 ⟶ 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 4,663 ⟶ 4,989:
Debug.Print
Next i
End Sub</
<pre> 1
1 1
Line 4,683 ⟶ 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}}==
Line 4,688 ⟶ 5,083:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var cache = [[BigInt.one]]
Line 4,720 ⟶ 5,115:
[23, 123, 1234, 12345].each { |i|
Fmt.print("$5s: $s", i, cumu.call(i)[-1])
}</
{{out}}
Line 4,760 ⟶ 5,155:
=={{header|Yabasic}}==
{{trans|VBA}}
<
Sub nine_billion_names(rows)
Line 4,780 ⟶ 5,175:
End Sub
nine_billion_names(20)</
=={{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,801 ⟶ 5,196:
}
}
}</
<
p[0].set(1);
Line 4,808 ⟶ 5,203:
(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,819 ⟶ 5,214:
100000: 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
</pre>
{{omit from|6502 Assembly|Good luck doing this with only 64K of addressable memory}}
{{omit from|Z80 Assembly|See above}}
| |||