9 billion names of God the integer: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|FreeBASIC}}: syntaxhighlight) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 46:
{{trans|Python}}
<
F cumu(n)
L(l) :cache.len .. n
Line 99:
V p = partitions(i)
I i C ns
print(‘#6: #.’.format(i, p))</
{{out}}
Line 124:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program integerName64.s */
Line 290:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
{{out}}
<pre>
Line 304:
{{libheader|Ada.Numerics.Big_Numbers.Big_Integers}}
<
with Ada.Numerics.Big_Numbers.Big_Integers;
Line 445:
Triangle.Print;
Row_Summer.Put_Sums;
end Names_Of_God;</
{{out}}
Line 503:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<
/* ARM assembly Raspberry PI */
/* program integerName.s */
Line 654:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{out}}
<pre>
Line 664:
=={{header|AutoHotkey}}==
<
InputBox, Enter_value, Enter the no. of lines sought
Line 721:
}
~Esc::ExitApp</
{{out}}
If user inputs 25, the result shall be:
Line 756:
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:
at++;
}
}</
{{out}}
<pre>
Line 810:
(this requires a System.Numerics registry reference)
<
using System.Collections.Generic;
using System.Linq;
Line 907:
}
}
</syntaxhighlight>
{{out}}
<pre> 1
Line 948:
===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:
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:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 996:
===The One True Triangle, OTT===
The following will display OTT(25).
<
int main(){
N = 25;
Line 1,021:
std::cout << "1 1" << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,053:
===Values of Integer Partition Function===
Values of the Integer Partition function may be extracted as follows:
<
#include <iostream>
int main(){
Line 1,065:
std::cout << "G(123456) = " << r << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,076:
=={{header|Clojure}}==
<
(cond (<= row 0) 0
(<= column 0) 0
Line 1,094:
(print-row x)))
(print-triangle 25)</
=={{header|Common Lisp}}==
<
(cond ((<= row 0) 0)
((<= column 0) 0)
Line 1,112:
(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:
===Producing rows===
{{trans|Python}}
<
auto cumu(in uint n) {
Line 1,181:
foreach (x; [23, 123, 1234])
writeln(x, " ", x.cumu.back);
}</
{{out}}
<pre>Rows:
Line 1,203:
===Only partition functions===
{{trans|C}}
<
struct Names {
Line 1,253:
writefln("%6d: %s", i, p);
}
}</
{{out}}
<pre> 23: 1255
Line 1,276:
{{trans|Python}}
<
List<BigInt> partitions(int n) {
Line 1,309:
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:
=={{header|Dyalect}}==
<
func namesOfGod(n) {
Line 1,368:
for x in 1..25 {
print("\(x): \(row(x))")
}</
Output:
Line 1,401:
{{trans|Ruby}}
Naive Solution
<
def g(n,g) when g == 1 or n < g, do: 1
def g(n,g) do
Line 1,412:
Enum.each(1..25, fn n ->
IO.puts Enum.map(1..n, fn g -> "#{God.g(n,g)} " end)
end)</
{{out}}
Line 1,446:
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.
<
-module(triangle).
-export([start/1]).
Line 1,468:
formula(A1,B1)->
formula(A1-1,B1-1)+formula(A1-B1,B1).
</syntaxhighlight>
{{out}}
Line 1,502:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<
sequences ;
Line 1,522:
25 .triangle nl
"Sums:" print { 23 123 1234 12345 } [ dup pprint bl G . ] each</
{{out}}
<pre>
Line 1,730:
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:
testRow[1234]
testRow[12345]
</syntaxhighlight>
<pre>
Line 1,822:
=={{header|GAP}}==
The partition function is built-in.
<
[ [ 1 ],
Line 1,854:
[ 1255, 2552338241, 156978797223733228787865722354959930,
69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736 ]</
=={{header|Go}}==
<
import (
Line 1,907:
fmt.Printf("%d %v\n", num, r[len(r)-1].Text(10))
}
}</
{{out}}
<pre>
Line 1,930:
=={{header|Groovy}}==
<
def partitions(c)
{
Line 1,972:
{partitions(i);}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,005:
=={{header|Haskell}}==
<
cumu :: [[Integer]]
Line 2,025:
main = do
mapM_ print $ take 10 rows
mapM_ (print.sums) [23, 123, 1234, 12345]</
{{out}}
<pre>
Line 2,049:
{{trans|Python}}
<
n := integer(!A) | 10
every r := 2 to (n+1) do write(right(r-1,2),": ",showList(row(r)))
Line 2,073:
every (s := "[") ||:= (!A||", ")
return s[1:-2]||"]"
end</
{{out}} (terminated without waiting for output of cumu(12345)):
Line 2,098:
=={{header|J}}==
Recursive calculation of a row element:
<
Calculation of the triangle:
<
'''Show triangle''':
<
1
1 1
Line 2,112:
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:
z=. a n}z
end.
)</
{{out}}
<pre> ({ [: rowSums >./) 3 23 123 1234
Line 2,135:
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:
}
}
}</
<pre>Rows:
Line 2,197:
===Solution 1===
{{trans|Python}}
<
(function () {
var cache = [
Line 2,258:
});
})()
</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:
console.log("G(" + x + ") = " + G(x))
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,336:
=={{header|Julia}}==
<
using Combinatorics, StatsBase
Line 2,376:
end
</
[1]
[1, 1]
Line 2,418:
=={{header|Kotlin}}==
{{trans|Swift}}
<
import java.math.BigInteger
import java.util.ArrayList
Line 2,452:
System.out.printf("%s %s%n", it, c[c.size - 1])
}
}</
<pre>
Line 2,490:
=={{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:
cumu(#x+1)->last
'\r'
^}</
{{out}}
Line 2,557:
=={{header|Lua}}==
<
local tri = {{1}}
for r = 2, n do
Line 2,579:
end
print("G(23) = " .. G(23))
print("G(123) = " .. G(123))</
{{out}}
<pre>1: 1
Line 2,610:
=={{header|Maple}}==
<
Triangle := proc(m)
local i;
Line 2,617:
end do
end proc:
</syntaxhighlight>
{{out}}
Line 2,631:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
{{out}}
<pre>1
Line 2,645:
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:
Using the built-in function to calculate <math>P(n)</math>:
<
{{out}}
<pre>(%o1) [1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736]</pre>
Line 2,688:
=={{header|Nim}}==
{{trans|Python}}
<
var cache = @[@[1.initBigInt]]
Line 2,713:
for x in [23, 123, 1234, 12345]:
let c = cumu(x)
echo x, " ", c[c.high]</
{{out}}
<pre>@[1]
Line 2,733:
Faster version:
{{trans|C}}
<
var p = @[1.initBigInt]
Line 2,765:
let p = partitions(i)
if i in ns:
echo i,": ",p</
{{out}}
<pre>23: 1255
Line 2,773:
=={{header|OCaml}}==
<
let get, sum_unto =
let cache = ref [||]
Line 2,852:
end
[23;123;1234;12345;123456]
</syntaxhighlight>
{{out}}
<pre>
Line 2,898:
=={{header|Ol}}==
<
(define (nine-billion-names row column)
(cond
Line 2,923:
(print-triangle 25)
</syntaxhighlight>
{{Out}}
<pre>
Line 2,955:
=={{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:
=={{header|Perl}}==
{{libheader|ntheory}}
<
sub triangle_row {
Line 3,028:
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:
{{trans|Raku}}
<
use strict;
use warnings;
Line 3,078:
print $i, "\n";
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,117:
=={{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:
<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:
{{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:
<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:
=== 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:
<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}}
<
by Galileo, 05/2022 #/
Line 3,291:
enddef
20 nine_billion_names</
{{out}}
<pre> 1
Line 3,319:
===The triangle, using constraint modelling===
Using constraint modeling to generate all the partitions 1..25.
<
main =>
Line 3,345:
foreach(I in L)
Map.put(I,Map.get(I,0)+1)
end.</
{{out}}
Line 3,378:
===Number of partitions===
This is the Picat solution of [http://rosettacode.org/wiki/Partition_function_P Partition_function_P].
<
go2 =>
foreach(N in [23,123,1234,12345,123456])
Line 3,403:
M := (K*(3*K+1)) // 2
end,
P = S.</
{{out}}
Line 3,414:
===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).
<
table
pc(_,0) = 1.
pc(1,1) = 1.
pc(K,M) = cond(M < K, 0, pc(K, M-K) + pc(K + 1,M)).</
=={{header|PicoLisp}}==
{{trans|Python}}
<
(let C '((1))
(do N
Line 3,473:
(println (sumr I)) ) )
(bye)</
{{out}}
Line 3,510:
{{trans|Python}}
<
array(array(int)) cache = ({({1})});
Line 3,548:
}
return 0;
}</
{{out}} Not wait for "12345" output.
<pre>rows:
Line 3,569:
=={{header|PureBasic}}==
<
Define nMax.i=25, n.i, k.i
Dim pfx.s(1)
Line 3,638:
PrintN(sum(12345,pfx()))
Input()
</syntaxhighlight>
{{out}}
<pre>
Line 3,674:
=={{header|Python}}==
<
def cumu(n):
for l in range(len(cache), n+1):
Line 3,692:
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,714:
</pre>
To calculate partition functions only:
<
diffs,k,s = [],1,1
while k * (3*k-1) < 2*N:
Line 3,731:
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,772:
print "%6d: %s" % (i, p)
main()</
{{out}}
<pre> 23: 1255
Line 3,780:
=={{header|Racket}}==
<
(define (cdr-empty ls) (if (empty? ls) empty (cdr ls)))
Line 3,803:
(newline)
(map G '(23 123 1234)))
</syntaxhighlight>
{{out}}
Line 3,840:
To save a bunch of memory, this algorithm throws away all the numbers that it knows it's not going to use again, on the assumption that the function will only be called with increasing values of $n. (It could easily be made to recalculate if it notices a regression.)
<
my @sums = 0;
sub nextrow($n) {
Line 3,873:
for 23, 123, 1234, 12345 {
put $_, "\t", @names-of-God[$_];
}</
{{out}}
<pre>rows:
Line 3,909:
=={{header|Red}}==
<
Red []
Line 3,955:
probe names 1234
</syntaxhighlight>
{{out}}
Line 4,024:
</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 4,081:
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 4,141:
=={{header|Ruby}}==
===Naive Solution===
<
# Generate IPF triangle
# Nigel_Galloway: May 1st., 2013.
Line 4,152:
puts (1..n).map {|g| "%4s" % g(n,g)}.join
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,183:
===Full Solution===
<
# Find large values of IPF
# Nigel_Galloway: May 1st., 2013.
Line 4,214:
n = 3 + @ipn1.inject(:+) + @ipn2.inject(:+)
puts "G(12345) = #{n}"
</syntaxhighlight>
{{out}}
<pre>
Line 4,225:
=={{header|Rust}}==
{{trans|Python}}
<
use std::cmp;
Line 4,269:
println!("{}: {}", x, s);
}
}</
{{out}}
<pre>rows:
Line 4,306:
=={{header|Scala}}==
===Naive Solution===
<
object Main {
Line 4,343:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,386:
===Full Solution===
<
cache(0) = 1
val cacheNaive = scala.collection.mutable.Map[Tuple2[Int, Int], BigInt]()
Line 4,434:
println(quickPartitions(123))
println(quickPartitions(1234))
println(quickPartitions(12345))</
{{out}}
<pre> 1
Line 4,465:
=={{header|scheme}}==
<
(define (sigma g x y)
(define (sum i)
Line 4,484:
(cond ((< i x) (begin (display (line i)) (display "\n") (print-loop (+ i 1)) ))))
(print-loop 1))
(print 25)</
{{out}}
Line 4,515:
=={{header|Sidef}}==
<
func cumu (n) {
Line 4,542:
for i in [23, 123, 1234, 12345] {
"%2s : %4s\n".printf(i, cumu(i)[-1])
}</
{{out}}
Line 4,571:
=={{header|SPL}}==
<
> n, 1..25
k = 50-n*2
Line 4,608:
<
<= p[n+1]
.</
{{out}}
<pre>
Line 4,644:
=={{header|Stata}}==
<
function part(n) {
a = J(n,n,.)
Line 4,653:
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,683:
=={{header|Swift}}==
{{trans|Python}}
<
func namesOfGod(n:Int) -> [Int] {
for l in cache.count...n {
Line 4,716:
var numInt = array[array.count - 1]
println("\(x): \(numInt)")
}</
{{out}}
<pre>
Line 4,755:
=={{header|Tcl}}==
{{trans|Python}}
<
proc cumu {n} {
global cache
Line 4,784:
foreach x {23 123 1234 12345} {
puts "${x}: [lindex [cumu $x] end]"
}</
{{out}}
<pre>
Line 4,833:
Print
Return</
{{Out}}
<pre> 1
Line 4,853:
0 OK, 0:30 </pre>
=={{header|VBA}}==
<
Dim p(25, 25) As Long
p(1, 1) = 1
Line 4,868:
Debug.Print
Next i
End Sub</
<pre> 1
1 1
Line 4,891:
=={{header|Vlang}}==
{{trans|Go}}
<
fn int_min(a int, b int) int {
Line 4,936:
println("$num ${r[r.len-1]}")
}
}</
{{out}}
Line 4,962:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Fmt
Line 4,994:
[23, 123, 1234, 12345].each { |i|
Fmt.print("$5s: $s", i, cumu.call(i)[-1])
}</
{{out}}
Line 5,034:
=={{header|Yabasic}}==
{{trans|VBA}}
<
Sub nine_billion_names(rows)
Line 5,054:
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 5,075:
}
}
}</
<
p[0].set(1);
Line 5,082:
(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}}
|