9 billion names of God the integer: Difference between revisions
(→{{header|Lasso}}: adding Lasso implementation) |
|||
| Line 438: | Line 438: | ||
=={{header|Lasso}}== |
=={{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". |
|||
<lang Lasso>define cumu(n::integer) => { |
<lang Lasso>define cumu(n::integer) => { |
||
loop(-from=$cache->size,-to=#n+1) => { |
loop(-from=$cache->size,-to=#n+1) => { |
||
local(r = array(0), l = loop_count) |
local(r = array(0), l = loop_count) |
||
loop(loop_count) => { |
loop(loop_count) => { |
||
protect => { #r->insert(#r->last + $cache->get(#l - loop_count)->get(math_min(loop_count+1, #l - loop_count))) } |
protect => { #r->insert(#r->last + $cache->get(#l - loop_count)->get(math_min(loop_count+1, #l - loop_count))) } |
||
} |
} |
||
Revision as of 02:25, 10 November 2013
You are encouraged to solve this task according to the task description, using any language you may know.
This task is a variation of the short story by Arthur C. Clark. (Solvers should be aware of the consequences of completing this task.) In detail, to specify what is meant by a “name”:
- The integer 1 has 1 name “1”.
- The integer 2 has 2 names “1+1”, and “2”.
- The integer 3 has 3 names “1+1+1”, “2+1”, and “3”.
- The integer 4 has 5 names “1+1+1+1”, “2+1+1”, “2+2”, “3+1”, “4”.
- The integer 5 has 7 names “1+1+1+1+1”, “2+1+1+1”, “2+2+1”, “3+1+1”, “3+2”, “4+1”, “5”.
- Task
The task is to display the first 25 rows of a number triangle which begins:
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
Where row corresponds to integer , and each column in row from left to right corresponds to the number of names begining with .
A function should return the sum of the -th row. Demonstrate this function by displaying: , , , and . Optionally note that the sum of the -th row is the integer partition function. Demonstrate this is equvalent to by displaying: , , , and .
- Extra credit
If your environment is able, plot against for .
C
If we forgo the rows and only want to calculate , using the recurrence relation is a better way. This requires storage for caching instead the -ish for storing all the rows. <lang c>#include <stdio.h>
- include <gmp.h>
- define N 100000
mpz_t p[N + 1];
void calc(int n) { mpz_init_set_ui(p[n], 0);
for (int k = 1; k <= n; k++) { int d = n - k * (3 * k - 1) / 2; if (d < 0) break;
if (k&1)mpz_add(p[n], p[n], p[d]); else mpz_sub(p[n], p[n], p[d]);
d -= k; if (d < 0) break;
if (k&1)mpz_add(p[n], p[n], p[d]); else mpz_sub(p[n], p[n], p[d]); } }
int main(void) { int idx[] = { 23, 123, 1234, 12345, 20000, 30000, 40000, 50000, N, 0 }; int at = 0;
mpz_init_set_ui(p[0], 1);
for (int i = 1; idx[at]; i++) { calc(i); if (i != idx[at]) continue;
gmp_printf("%2d:\t%Zd\n", i, p[i]); at++; } }</lang>
- Output:
23: 1255 123: 2552338241 1234: 156978797223733228787865722354959930 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 ...
C++
The Code
see [The Green Triangle]. <lang cpp> // Calculate hypotenuse n of OTT assuming only nothingness, unity, and hyp[n-1] if n>1 // Nigel Galloway, May 6th., 2013
- include <gmpxx.h>
int N{123456}; mpz_class hyp[N-3]; const mpz_class G(const int n,const int g){return g>n?0:(g==1 or n-g<2)?1:hyp[n-g-2];}; void G_hyp(const int n){for(int i=0;i<N-2*n-1;i++) n==1?hyp[n-1+i]=1+G(i+n+1,n+1):hyp[n-1+i]+=G(i+n+1,n+1);} } </lang>
The Alpha and Omega, Beauty
Before displaying the triangle the following code displays hyp as it is transformed by consequtive calls of G_hyp. <lang cpp>
- include <iostream>
- include <iomanip>
int main(){
N=25;
for (int n=1; n<N/2; n++){
G_hyp(n);
for (int g=0; g<N-3; g++) std::cout << std::setw(4) << hyp[g];
std::cout << std::endl;
}
} </lang>
- Output:
2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 2 3 4 5 7 8 10 12 14 16 19 21 24 27 30 33 37 40 44 48 52 12 2 3 5 6 9 11 15 18 23 27 34 39 47 54 64 72 84 94 108 120 52 12 2 3 5 7 10 13 18 23 30 37 47 57 70 84 101 119 141 164 192 120 52 12 2 3 5 7 11 14 20 26 35 44 58 71 90 110 136 163 199 235 192 120 52 12 2 3 5 7 11 15 21 28 38 49 65 82 105 131 164 201 248 235 192 120 52 12 2 3 5 7 11 15 22 29 40 52 70 89 116 146 186 230 248 235 192 120 52 12 2 3 5 7 11 15 22 30 41 54 73 94 123 157 201 230 248 235 192 120 52 12 2 3 5 7 11 15 22 30 42 55 75 97 128 164 201 230 248 235 192 120 52 12 2 3 5 7 11 15 22 30 42 56 76 99 131 164 201 230 248 235 192 120 52 12 2 3 5 7 11 15 22 30 42 56 77 100 131 164 201 230 248 235 192 120 52 12
- The first row is the hypotenuse of the green triangle.
- The second row cols 2 to 21 is the hypotenuse 1 in. Col 1 is the last entry in the horizontal edge of the grey triangle. Col 22 is the first entry of the horizontal edge of the green triangle.
- With subsequent calls the horizontal edges expand until, on the final row, the sequence of hypotenuses is finished and hyp contains the horizontal edge of the OTT.
This must be the most beautiful thing on rosettacode!!! Note that the algorithm requires only this data, and requires only N/2 iterations with the nth iteration performing N-3-2*n calculations.
The One True Triangle, OTT
The following will display OTT(25). <lang cpp> int main(){
N = 25;
std::cout << std::setw(N+52) << "1" << std::endl;
std::cout << std::setw(N+55) << "1 1" << std::endl;
std::cout << std::setw(N+58) << "1 1 1" << std::endl;
std::string ott[N-3];
for (int n=1; n<N/2; n++) {
G_hyp(n);
for (int g=(n-1)*2; g<N-3; g++) {
std::string t = hyp[g-(n-1)].get_str();
//if (t.size()==1) t.insert(t.begin(),1,' ');
ott[g].append(t);
ott[g].append(6-t.size(),' ');
}
}
for(int n = 0; n<N-3; n++) {
std::cout <<std::setw(N+43-3*n) << 1 << " " << ott[n];
for (int g = (n+1)/2; g>0; g--) {
std::string t{hyp[g-1].get_str()};
t.append(6-t.size(),' ');
std::cout << t;
}
std::cout << "1 1" << std::endl;
}
</lang>
- Output:
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1
1 7 16 23 23 20 15 11 7 5 3 2 1 1
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
Values of Integer Partition Function
Values of the Integer Partition function may be extracted as follows: <lang cpp>
- include <iostream>
int main(){
for (int n=1; n<N/2; n++) G_hyp(n);
std::cout << "G(23) = " << hyp[21] << std::endl;
std::cout << "G(123) = " << hyp[121] << std::endl;
std::cout << "G(1234) = " << hyp[1232] << std::endl;
std::cout << "G(12345) = " << hyp[12343] << std::endl;
mpz_class r{3};
for (int i = 0; i<N-3; i++) r += hyp[i];
std::cout << "G(123456) = " << r << std::endl;
} </lang>
- Output:
G(23) = 1255 G(123) = 2552338241 G(1234) = 156978797223733228787865722354959930 G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 G(123456) = 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989
D
Producing rows
<lang d>import std.stdio, std.bigint, std.algorithm, std.range;
auto cumu(in uint n) {
__gshared cache = 1.BigInt; foreach (l; cache.length .. n + 1) { auto r = [0.BigInt]; foreach (x; 1 .. l + 1) r ~= r.back + cache[l - x][min(x, l - x)]; cache ~= r; } return cache[n];
}
auto row(in uint n) {
auto r = n.cumu; return n.iota.map!(i => r[i + 1] - r[i]);
}
void main() {
writeln("Rows:");
foreach (x; 1 .. 11)
writefln("%2d: %s", x, x.row);
writeln("\nSums:");
foreach (x; [23, 123, 1234])
writeln(x, " ", x.cumu.back);
}</lang>
- Output:
Rows: 1: [1] 2: [1, 1] 3: [1, 1, 1] 4: [1, 2, 1, 1] 5: [1, 2, 2, 1, 1] 6: [1, 3, 3, 2, 1, 1] 7: [1, 3, 4, 3, 2, 1, 1] 8: [1, 4, 5, 5, 3, 2, 1, 1] 9: [1, 4, 7, 6, 5, 3, 2, 1, 1] 10: [1, 5, 8, 9, 7, 5, 3, 2, 1, 1] Sums: 23 1255 123 2552338241 1234 156978797223733228787865722354959930
Only partition functions
<lang d>import std.stdio, std.bigint, std.algorithm;
struct Names {
BigInt[] p = [1.BigInt];
int opApply(int delegate(ref immutable int, ref BigInt) dg) {
int result;
foreach (immutable n; 1 .. int.max) {
p.assumeSafeAppend;
p ~= 0.BigInt;
foreach (immutable k; 1 .. n + 1) {
auto d = n - k * (3 * k - 1) / 2;
if (d < 0)
break;
if (k & 1)
p[n] += p[d];
else
p[n] -= p[d];
d -= k;
if (d < 0)
break;
if (k & 1)
p[n] += p[d];
else
p[n] -= p[d];
}
result = dg(n, p[n]);
if (result) break;
}
return result; }
}
void main() {
immutable ns = [23:0, 123:0, 1234:0, 12345:0]; immutable maxNs = ns.byKey.reduce!max;
foreach (immutable i, p; Names()) {
if (i > maxNs)
break;
if (i in ns)
writefln("%6d: %s", i, p);
}
}</lang>
- Output:
23: 1255 123: 2552338241 1234: 156978797223733228787865722354959930 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
Output for a larger input, with newlines:
123456: 3081765957853649667854531714653398085529661327450713921760877 6782063054452191537379312358383342446230621170608408020911309 2594076112571516833722219251283883871684519438000271280453696 5089022006090149454045908154544502080872691737169910282550803 9173543836338081612528477859613355349851184591540231790254269 9482787265485706601456910768199129721622629021508868189865551 27204165221706149989
Runtime up to 123456: about 56 seconds (about 50 with ldc2) because currently std.bigint is not fast.
Erlang
Step 1: Print the pyramid for a smallish number of names. The P function is implement as described on partition function, (see 59 on that page). This is slow for N > 100, but works fine for the example: 10. <lang Erlang> -module(god_the_integer). -export([example/0, names/1, print_pyramid/1]).
example() -> Names = names( 10 ), print_pyramid( Names ).
names( N ) -> [names_row(X) || X <- lists:seq(1, N)].
print_pyramid( Names ) -> Width = erlang:length( lists:last(Names) ), [print_pyramid_row(Width, X) || X <- Names].
names_row( M ) -> [p(M, X) || X <- lists:seq(1, M)].
p( N, K ) when K > N -> 0; p( N, N ) -> 1; p( _N, 0 ) -> 0; p( N, K ) -> p( N - 1, K - 1 ) + p( N - K, K ).
print_pyramid_row( Width, Row ) -> io:fwrite( "~*s", [Width - erlang:length(Row), " "] ), [io:fwrite("~p ", [X]) || X <- Row], io:nl(). </lang>
Haskell
<lang haskell>import Data.List (mapAccumL)
cumu :: Integer cumu = [1] : map (scanl (+) 0) rows
rows :: Integer rows = snd $ mapAccumL f [] cumu where
f r row = (rr, new_row) where
new_row = map head rr
rr = map tailKeepOne (row:r)
tailKeepOne [x] = [x]
tailKeepOne (_:xs) = xs
sums n = cumu !! n !! n --curiously, the following seems to be faster --sums = sum . (rows!!)
main :: IO () main = do
mapM_ print $ take 10 rows mapM_ (print.sums) [23, 123, 1234, 12345]</lang>
- Output:
[1] [1,1] [1,1,1] [1,2,1,1] [1,2,2,1,1] [1,3,3,2,1,1] [1,3,4,3,2,1,1] [1,4,5,5,3,2,1,1] [1,4,7,6,5,3,2,1,1] [1,5,8,9,7,5,3,2,1,1] 1255 2552338241 156978797223733228787865722354959930 ^C (probably don't have enough memory for 12345 anyway)
J
Recursive calculation of a row element: <lang j>T=: 0:`1:`(($:&<:+ - $: ])`0:@.(0=]))@.(1+*@-) M. "0</lang> Calculation of the triangle: <lang j>rows=: <@(#~0<])@({: T ])\@i.</lang> Show triangle: <lang j> ({.~1+1 i:~ '1'=])"1 ":> }.rows 1+10 1 1 1 1 1 1 1 2 1 1 1 2 2 1 1 1 3 3 2 1 1 1 3 4 3 2 1 1 1 4 5 5 3 2 1 1 1 4 7 6 5 3 2 1 1 1 5 8 9 7 5 3 2 1 1</lang>
Calculate row sums: <lang j>rowSums=: 3 :0"0 z=. (y+1){. 1x for_ks. <\1+i.y do.
n=.{: k=.>ks
r=.#c=. ({.~* i._1:)(n,0.5 _1.5) p. k
s=.#d=.({.~* i._1:)c-r{.k
'v i'=.|: \:~(c,d),. r ,&({.&k) s
a=. +/(n{z),(_1^1x+2|i) * v{z
z=. a n}z
end. )</lang> Output <lang j> ({ [: rowSums >./) 3 23 123 1234 3 1255 2552338241 156978797223733228787865722354959930</lang>
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". <lang Lasso>define cumu(n::integer) => { loop(-from=$cache->size,-to=#n+1) => { local(r = array(0), l = loop_count) loop(loop_count) => { protect => { #r->insert(#r->last + $cache->get(#l - loop_count)->get(math_min(loop_count+1, #l - loop_count))) } } #r->size > 1 ? $cache->insert(#r) } return $cache->get(#n) } define row(n::integer) => { // cache gets reset & rebuilt for each row, slower but more accurate var(cache = array(array(1))) local(r = cumu(#n+1)) local(o = array) loop(#n) => { protect => { #o->insert(#r->get(loop_count+1) - #r->get(loop_count)) } } return #o } 'rows:\r' loop(25) => {^ loop_count + ': '+ row(loop_count)->join(' ') + '\r' ^}
'sums:\r' with x in array(23, 123, 1234) do => {^ var(cache = array(array(1))) cumu(#x+1)->last '\r' ^}</lang>
- Output:
rows: 1: 1 2: 1 1 3: 1 1 1 4: 1 2 1 1 5: 1 2 2 1 1 6: 1 3 3 2 1 1 7: 1 3 4 3 2 1 1 8: 1 4 5 5 3 2 1 1 9: 1 4 7 6 5 3 2 1 1 10: 1 5 8 9 7 5 3 2 1 1 11: 1 5 10 11 10 7 5 3 2 1 1 12: 1 6 12 15 13 11 7 5 3 2 1 1 13: 1 6 14 18 18 14 11 7 5 3 2 1 1 14: 1 7 16 23 23 20 15 11 7 5 3 2 1 1 15: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 16: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 17: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 18: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 19: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 20: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 21: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 22: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 23: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 24: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 25: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 sums: 23: 1255 123: 2552338241 1234: 156978797223733228787865722354959930 12345: (ran long, timed out)
Mathematica
<lang mathematica>Table[Last /@ Reverse@Tally[First /@ IntegerPartitions[n]], {n, 10}] // Grid</lang>
- Output:
1 1 1 1 1 1 1 2 1 1 1 2 2 1 1 1 3 3 2 1 1 1 3 4 3 2 1 1 1 4 5 5 3 2 1 1 1 4 7 6 5 3 2 1 1 1 5 8 9 7 5 3 2 1 1
Here I use the bulit-in function PartitionsP to calculate . <lang mathematica>PartitionsP /@ {23, 123, 1234, 12345}</lang>
- Output:
{1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736}
<lang mathematica>DiscretePlot[PartitionsP[n], {n, 1, 999}, PlotRange -> All]</lang>
Perl
<lang perl> use strict; use warnings;
- Where perl6 uses arbitrary precision integers everywhere
- that you don't tell it not to do so, perl5 will only use
- them where you *do* tell it do so.
use Math::BigInt; use constant zero => Math::BigInt->bzero; use constant one => Math::BigInt->bone;
my @todo = [one]; my @sums = (zero); sub nextrow {
my $n = shift;
for my $l (@todo .. $n) {
$sums[$l] = zero;
#print "$l\r" if $l < $n;
my @r;
for my $x (reverse 0 .. $l-1) {
my $todo = $todo[$x];
$sums[$x] += shift @$todo if @$todo;
push @r, $sums[$x];
}
push @todo, \@r;
}
@{ $todo[$n] };
}
print "rows:\n"; for(1..25) {
printf("%2d: ", $_);
print join(' ', nextrow($_)), "\n";
} print "\nsums:\n"; for (23, 123, 1234, 12345) {
print $_, "." x (8 - length); my $i = 0; $i += $_ for nextrow($_); print $i, "\n";
} </lang>
- Output:
rows: 1: 1 2: 1 1 3: 1 1 1 4: 1 2 1 1 5: 1 2 2 1 1 6: 1 3 3 2 1 1 7: 1 3 4 3 2 1 1 8: 1 4 5 5 3 2 1 1 9: 1 4 7 6 5 3 2 1 1 10: 1 5 8 9 7 5 3 2 1 1 11: 1 5 10 11 10 7 5 3 2 1 1 12: 1 6 12 15 13 11 7 5 3 2 1 1 13: 1 6 14 18 18 14 11 7 5 3 2 1 1 14: 1 7 16 23 23 20 15 11 7 5 3 2 1 1 15: 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 16: 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 17: 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 18: 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 19: 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 20: 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 21: 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 22: 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 23: 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 24: 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 25: 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1 sums: 23......1243 123.....2552338241 1234....156978797223733228787865722354959930 ^C
Note: I didn't wait long enough to see what the next result was, and stopped the program.
Perl 6
To save a bunch of memory, this algorithm throws away all the numbers that it knows it's not going to use again, on the assumption that the function will only be called with increasing values of $n. (It could easily be made to recalculate if it notices a regression.)
Note: We only run to 10000 currently because mono gets major GC indigestion at 10200 or so... <lang perl6>my @todo = [1]; my @sums = 0; sub nextrow($n) {
for +@todo .. $n -> $l {
@sums[$l] = 0;
print $l,"\r" if $l < $n;
my $r = [];
for reverse ^$l -> $x {
my @x := @todo[$x];
if @x {
$r.push: @sums[$x] += @x.shift;
}
else {
$r.push: @sums[$x];
}
}
@todo.push($r);
}
@todo[$n];
}
say "rows:"; say .fmt('%2d'), ": ", nextrow($_)[] for 1..10;
say "\nsums:";
for 23, 123, 1234, 10000 {
say $_, "\t", [+] nextrow($_)[];
}</lang>
- Output:
rows: 1: 1 2: 1 1 3: 1 1 1 4: 1 2 1 1 5: 1 2 2 1 1 6: 1 3 3 2 1 1 7: 1 3 4 3 2 1 1 8: 1 4 5 5 3 2 1 1 9: 1 4 7 6 5 3 2 1 1 10: 1 5 8 9 7 5 3 2 1 1 sums: 23 1255 123 2552338241 1234 156978797223733228787865722354959930 10000 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144
Python
<lang python>cache = 1 def cumu(n):
for l in range(len(cache), n+1):
r = [0]
for x in range(1, l+1):
r.append(r[-1] + cache[l-x][min(x, l-x)])
cache.append(r)
return cache[n]
def row(n):
r = cumu(n) return [r[i+1] - r[i] for i in range(n)]
print "rows:" for x in range(1, 11): print "%2d:"%x, row(x)
print "\nsums:"
for x in [23, 123, 1234, 12345]: print x, cumu(x)[-1]</lang>
- Output:
(I didn't actually wait long enough to see what the sum for 12345 is)
rows: 1: [1] 2: [1, 1] 3: [1, 1, 1] 4: [1, 2, 1, 1] 5: [1, 2, 2, 1, 1] 6: [1, 3, 3, 2, 1, 1] 7: [1, 3, 4, 3, 2, 1, 1] 8: [1, 4, 5, 5, 3, 2, 1, 1] 9: [1, 4, 7, 6, 5, 3, 2, 1, 1] 10: [1, 5, 8, 9, 7, 5, 3, 2, 1, 1] sums: 23 1255 123 2552338241 1234 156978797223733228787865722354959930 ^C
To calculate partition functions only: <lang python>def partitions(N):
diffs,k,s = [],1,1
while k * (3*k-1) < 2*N:
diffs.extend([(2*k - 1, s), (k, s)])
k,s = k+1,-s
out = [1] + [0]*N
for p in range(0, N+1):
x = out[p]
for (o,s) in diffs:
p += o
if p > N: break
out[p] += x*s
return out
p = partitions(12345) for x in [23,123,1234,12345]: print x, p[x]</lang>
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:
<lang python>def partitions(n):
partitions.p.append(0)
for k in xrange(1, n + 1):
d = n - k * (3 * k - 1) // 2
if d < 0:
break
if k & 1:
partitions.p[n] += partitions.p[d]
else:
partitions.p[n] -= partitions.p[d]
d -= k
if d < 0:
break
if k & 1:
partitions.p[n] += partitions.p[d]
else:
partitions.p[n] -= partitions.p[d]
return partitions.p[-1]
partitions.p = [1]
def main():
ns = set([23, 123, 1234, 12345]) max_ns = max(ns)
for i in xrange(1, max_ns + 1):
if i > max_ns:
break
p = partitions(i)
if i in ns:
print "%6d: %s" % (i, p)
main()</lang>
- Output:
23: 1255 123: 2552338241 1234: 156978797223733228787865722354959930 12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
Racket
<lang racket>#lang racket
(define (cdr-empty ls) (if (empty? ls) empty (cdr ls)))
(define (names-of n)
(define (names-of-tail ans raws-rest n)
(if (zero? n)
ans
(names-of-tail (cons 1 (append (map +
(take ans (length raws-rest))
(map car raws-rest))
(drop ans (length raws-rest))))
(filter (compose not empty?)
(map cdr-empty (cons ans raws-rest)))
(sub1 n))))
(names-of-tail '() '() n))
(define (G n) (foldl + 0 (names-of n)))
(module+ main
(build-list 25 (compose names-of add1)) (newline) (map G '(23 123 1234)))
</lang>
- Output:
'((1) (1 1) (1 1 1) (1 2 1 1) (1 2 2 1 1) (1 3 3 2 1 1) (1 3 4 3 2 1 1) (1 4 5 5 3 2 1 1) (1 4 7 6 5 3 2 1 1) (1 5 8 9 7 5 3 2 1 1) (1 5 10 11 10 7 5 3 2 1 1) (1 6 12 15 13 11 7 5 3 2 1 1) (1 6 14 18 18 14 11 7 5 3 2 1 1) (1 7 16 23 23 20 15 11 7 5 3 2 1 1) (1 7 19 27 30 26 21 15 11 7 5 3 2 1 1) (1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1) (1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1) (1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1) (1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1) (1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1) (1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1) (1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1) (1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1) (1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1) (1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1)) '(1255 2552338241 156978797223733228787865722354959930)
REXX
This REXX version displays nicely "balanced" numbers triangle as per the task's requirement.
If the number of rows is entered as a signed positive number, only the number of partitions is shown
(the sum of the numbers on the last line of the number triangle).
If the number of rows is entered as a signed number, the triangle isn't shown.
Memoization is used to quickly obtain information of previously calculated numbers in the
left-hand side of the triangle and also previous calculated partitions.
The right half of the triangle isn't calculated but rather the value is taken from a previous row and column.
Also, the left two columns of the triangle are computed directly [either 1 or row%2 (integer divide)]
as well as the rightmost three columns (either 1 or 2).
The formula used is:
which is derived from Euler's generating function. <lang rexx>/*REXX program generates a number triangle for partitions of a number.*/ numeric digits 400 /*be able to handle large numbers*/ parse arg N .; if N== then N=25 /*No input? Then use the default*/ @.=0; @.0=1; aN=abs(N) if N==N+0 then say ' G('aN"):" G(N) /*just for well formed #s*/
say 'partitions('aN"):" partitions(aN) /*the easy way*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────G subroutine────────────────────────*/ G: procedure; parse arg nn; !.=0; mx=1; aN=abs(nn); build=nn>0 !.4.2=2; do j=1 for aN%2; !.j.j=1; end /*j*/ /*shortcuts.*/
do t=1 for 1+build; #.=1 /*gen triangle once or twice ∙∙∙*/
do r=1 for aN; #.2=r%2 /*#.2 is a shortcut calc.*/
do c=3 to r-2; #.c=gen#(r,c); end /*c*/
L=length(mx); p=0; aLine=
do cc=1 for r /*only sum last row of numbers. */
p=p+#.cc /*add last row of the triangle. */
if \build then iterate /*skip building the triangle? */
mx=max(mx,#.cc) /*used to build symmetric numbers*/
aLine=aLine right(#.cc,L) /*build a row of the triangle. */
end /*cc*/
if t==1 then iterate /*Is first time through? No show*/
L=length(mx); say centre(strip(aLine,'L'), 2+(aN-1)*(L+1))
end /*r*/ /* [↑] centre the row (triangle).*/
end /*t*/
return p /*return with generated number. */ /*──────────────────────────────────GEN# subroutine─────────────────────*/ gen#: procedure expose !.; parse arg x,y /*obtain X and Y arguments.*/ if !.x.y\==0 then return !.x.y /*was this # generated before? */ if y>x%2 then do; nx=x+1-2*(y-x%2)-(x//2==0); ny=nx%2; !.x.y=!.nx.ny
return !.x.y /*return with the calculated num.*/
end /*[↑] right half of the triangle.*/
$=1 /*[↓] left half of the triangle.*/
do q=2 to y; xy=x-y; if q>xy then iterate
if q==2 then $=$+xy%2
else if q==xy-1 then $=$+1
else $=$+gen#(xy,q)
end /*q*/
!.x.y=$; return $ /*remember #, return with number.*/ /*──────────────────────────────────PARTITIONS subroutine───────────────*/ partitions: procedure expose @.; parse arg n if @.n\==0 then return @.n /*Already computed? Return it. */ $=0 /*[↓] Euler's recursive function.*/
do k=1 for n; _=n-(k*3-1)*k%2; if _<0 then leave
if @._==0 then x=partitions(_); else x=@._
_=_-k; if _<0 then y=0
else if @._==0 then y=partitions(_)
else y=@._
if k//2 then $=$+x+y /*sum this way if K is odd ···*/
else $=$-x-y /* " " " " " " even ···*/
end /*k*/
@.n=$; return $</lang> output when using the default input (25 rows):
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1
1 7 16 23 23 20 15 11 7 5 3 2 1 1
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
G(25): 1958
partitions(25): 1958
output when using the input: -23
G(23): 1255 partitions(23): 1255
output when using the input: -123
G(123): 2552338241 partitions(123): 2552338241
output when using the input: -1234
G(1234): 156978797223733228787865722354959930 partitions(1234): 156978797223733228787865722354959930
output when using the input: -12345
G(12345): 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 partitions(12345): 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
output when using the input: +123456
partitions(123456): 30817659578536496678545317146533980855296613274507139217608776782063054452191537379312358383342446230621170608408020911309259407611257151683372221925128388387168451943800027128045369650890220060901494540459081545445020808726917371699102825508039173543836338081612528477859613355349851184591540231790254269948278726548570660145691076819912972162262902150886818986555127204165221706149989
(For the extra credit part) to view a horizontal histogram (plot) for the values for the number of partitions of 1 ──► 999 here at: 9 billion names of God the integer (REXX) histogram.
Ruby
Naive Solution
<lang ruby>
- Generate IPF triangle
- Nigel_Galloway: May 1st., 2013.
def g(n,g)
return 1 unless 1 < g and g < n-1
(2..g).inject(1){|res,q| res + (q > n-g ? 0 : g(n-g,q))}
end
(1..25).each {|n|
puts (1..n).map {|g| "%4s" % g(n,g)}.join
} </lang>
- Output:
1 1 1 1 1 1 1 2 1 1 1 2 2 1 1 1 3 3 2 1 1 1 3 4 3 2 1 1 1 4 5 5 3 2 1 1 1 4 7 6 5 3 2 1 1 1 5 8 9 7 5 3 2 1 1 1 5 10 11 10 7 5 3 2 1 1 1 6 12 15 13 11 7 5 3 2 1 1 1 6 14 18 18 14 11 7 5 3 2 1 1 1 7 16 23 23 20 15 11 7 5 3 2 1 1 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
Full Solution
<lang ruby>
- Find large values of IPF
- Nigel_Galloway: May 1st., 2013.
N = 12345 @ng = [] @ipn1 = [] @ipn2 = [] def g(n,g)
t = n-g-2 return 1 if n<4 or t<0 return @ng[g-2][n-4] unless n/2<g return @ipn1[t]
end @ng[0] = [] (4..N).each {|q| @ng[0][q-4] = 1 + g(q-2,2)} @ipn1[0] = @ng[0][0] @ipn2[0] = @ng[0][N-4] (1...(N/2-1)).each {|n|
@ng[n] = []
(n*2+4..N).each {|q| @ng[n][q-4] = g(q-1,n+1) + g(q-n-2,n+2)}
@ipn1[n] = @ng[n][n*2]
@ipn2[n] = @ng[n][N-4]
@ng[n-1] = nil
} @ipn2.pop if N.even?
puts "G(23) = #{@ipn1[21]}" puts "G(123) = #{@ipn1[121]}" puts "G(1234) = #{@ipn1[1232]}" n = 3 + @ipn1.inject(:+) + @ipn2.inject(:+) puts "G(12345) = #{n}" </lang>
- Output:
G(23) = 1255 G(123) = 2552338241 G(1234) = 156978797223733228787865722354959930 G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736
Scala
<lang scala> object Main {
// This is a special class for memoization
case class Memo[A,B](f: A => B) extends (A => B) {
private val cache = Map.empty[A, B] def apply(x: A) = cache getOrElseUpdate (x, f(x))
}
// Naive, but memoized solution
lazy val namesStartingMemo : Memo[Tuple2[Int, Int], BigInt] = Memo {
case (1, 1) => 1
case (a, n) =>
if (a > n/2) namesStartingMemo(a - 1, n - 1) else if (n < a) 0 else if (n == a) 1 else (1 to a).map(i => namesStartingMemo(i, n - a)).sum
}
def partitions(n: Int) = (1 to n).map(namesStartingMemo(_, n)).sum
// main method
def main(args: Array[String]): Unit = {
for (i <- 1 to 25) {
for (j <- 1 to i) {
print(namesStartingMemo(j, i)); print(' '); }
println() } println(partitions(23)) println(partitions(123)) println(partitions(1234)) println(partitions(12345)) }
} </lang>
- Output:
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1
1 5 8 9 7 5 3 2 1 1
1 5 10 11 10 7 5 3 2 1 1
1 6 12 15 13 11 7 5 3 2 1 1
1 6 14 18 18 14 11 7 5 3 2 1 1
1 7 16 23 23 20 15 11 7 5 3 2 1 1
1 7 19 27 30 26 21 15 11 7 5 3 2 1 1
1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1
1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1
1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1
1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1
1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1
1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1
1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1
1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1
1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1
1 12 52 120 192 235 248 230 201 164 131 100 77 56 42 30 22 15 11 7 5 3 2 1 1
1255
2552338241
156978797223733228787865722354959930
Exception in thread "main" java.lang.StackOverflowError
at scala.collection.mutable.HashTable$class.findEntry(HashTable.scala:130)
at scala.collection.mutable.HashMap.findEntry(HashMap.scala:39)
at scala.collection.mutable.HashMap.get(HashMap.scala:69)
at scala.collection.mutable.MapLike$class.getOrElseUpdate(MapLike.scala:187)
at scala.collection.mutable.AbstractMap.getOrElseUpdate(Map.scala:91)
at Main$Memo.apply(Main.scala:14)
...
(As you see, partitions(12345) fails with StackOverflowError)
Tcl
<lang tcl>set cache 1 proc cumu {n} {
global cache
for {set l [llength $cache]} {$l <= $n} {incr l} {
set r 0 for {set x 1; set y [expr {$l-1}]} {$y >= 0} {incr x; incr y -1} { lappend r [expr { [lindex $r end] + [lindex $cache $y [expr {min($x, $y)}]] }] } lappend cache $r
} return [lindex $cache $n]
} proc row {n} {
set r [cumu $n]
for {set i 0; set j 1} {$j < [llength $r]} {incr i; incr j} {
lappend result [expr {[lindex $r $j] - [lindex $r $i]}]
} return $result
}
puts "rows:" foreach x {1 2 3 4 5 6 7 8 9 10} {
puts "${x}: \[[join [row $x] {, }]\]"
} puts "\nsums:" foreach x {23 123 1234 12345} {
puts "${x}: [lindex [cumu $x] end]"
}</lang>
- Output:
rows: 1: [1] 2: [1, 1] 3: [1, 1, 1] 4: [1, 2, 1, 1] 5: [1, 2, 2, 1, 1] 6: [1, 3, 3, 2, 1, 1] 7: [1, 3, 4, 3, 2, 1, 1] 8: [1, 4, 5, 5, 3, 2, 1, 1] 9: [1, 4, 7, 6, 5, 3, 2, 1, 1] 10: [1, 5, 8, 9, 7, 5, 3, 2, 1, 1] sums: 23: 1255 123: 2552338241 1234: 156978797223733228787865722354959930 ^C
(I killed the run when it started to take a significant proportion of my system's memory.)
JavaScript
<lang JavaScript> (function () {
var cache = [
[1]
];
//this was never needed.
/* function PyRange(start, end, step) {
step = step || 1;
if (!end) {
end = start;
start = 0;
}
var arr = [];
for (var i = start; i < end; i += step) arr.push(i);
return arr;
}*/
function cumu(n) {
var /*ra = PyRange(cache.length, n + 1),*/ //Seems there is a better version for this
r, l, x, Aa, Mi;
// for (ll in ra) { too pythony
for (l=cache.length;l<n+1;l++) {
r = [0];
// l = ra[ll]; // ran = PyRange(1, l + 1); // for (xx in ran) {
for(x=1;x<l+1;x++){
// x = ran[xx];
r.push(r[r.length - 1] + (Aa = cache[l - x < 0 ? cache.length - (l - x) : l - x])[(Mi = Math.min(x, l - x)) < 0 ? Aa.length - Mi : Mi]);
}
cache.push(r);
}
return cache[n];
}
function row(n) {
var r = cumu(n),
// rra = PyRange(n),
leArray = [],
i;
// for (ii in rra) {
for (i=0;i<n;i++) {
// i = rra[ii];
leArray.push(r[i + 1] - r[i]);
}
return leArray;
}
console.log("Rows:");
for (iterator = 1; iterator < 12; iterator++) {
console.log(row(iterator));
}
console.log("Sums")[23, 123, 1234, 12345].foreach(function (a) {
var s = cumu(a);
console.log(a, s[s.length - 1]);
});
})() </lang>