9 billion names of God the integer: Difference between revisions

{{trans|Python}}

F cumu(n)

L(l) :cache.len .. n

V p = partitions(i)

I i C ns

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program integerName64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{out}}

<pre>

{{libheader|Ada.Numerics.Big_Numbers.Big_Integers}}

with Ada.Numerics.Big_Numbers.Big_Integers;

Triangle.Print;

Row_Summer.Put_Sums;

{{out}}

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program integerName.s */

/***************************************************/

.include "../affichage.inc"

{{out}}

<pre>

=={{header|AutoHotkey}}==

InputBox, Enter_value, Enter the no. of lines sought

}

{{out}}

If user inputs 25, the result shall be:

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>

at++;

}

{{out}}

<pre>

(this requires a System.Numerics registry reference)

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre> 1

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

void G_hyp(const int n){for(int i=0;i<N-2*n-1;i++) n==1?hyp[n-1+i]=1+G(i+n+1,n+1):hyp[n-1+i]+=G(i+n+1,n+1);}

}

===The Alpha and Omega, Beauty===

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

#include <iostream>

#include <iomanip>

}

}

{{out}}

<pre>

===The One True Triangle, OTT===

The following will display OTT(25).

int main(){

N = 25;

std::cout << "1 1" << std::endl;

}

{{out}}

<pre>

===Values of Integer Partition Function===

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

#include <iostream>

int main(){

std::cout << "G(123456) = " << r << std::endl;

}

{{out}}

<pre>

=={{header|Clojure}}==

(cond (<= row 0) 0

(<= column 0) 0

(print-row x)))

=={{header|Common Lisp}}==

(cond ((<= row 0) 0)

((<= column 0) 0)

(9-billion-names-triangle 25)

=={{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

{{out}}

<pre>

===Producing rows===

{{trans|Python}}

auto cumu(in uint n) {

foreach (x; [23, 123, 1234])

writeln(x, " ", x.cumu.back);

{{out}}

<pre>Rows:

===Only partition functions===

{{trans|C}}

struct Names {

writefln("%6d: %s", i, p);

}

{{out}}

<pre> 23: 1255

{{trans|Python}}

List<BigInt> partitions(int n) {

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

=={{header|Dyalect}}==

func namesOfGod(n) {

for x in 1..25 {

print("\(x): \(row(x))")

Output:

{{trans|Ruby}}

Naive Solution

def g(n,g) when g == 1 or n < g, do: 1

def g(n,g) do

Enum.each(1..25, fn n ->

IO.puts Enum.map(1..n, fn g -> "#{God.g(n,g)} " end)

{{out}}

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

formula(A1,B1)->

formula(A1-1,B1-1)+formula(A1-B1,B1).

{{out}}

=={{header|Factor}}==

{{works with|Factor|0.99 2020-01-23}}

sequences ;

25 .triangle nl

{{out}}

<pre>

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

{

testRow[1234]

testRow[12345]

<pre>

=={{header|GAP}}==

The partition function is built-in.

[ [ 1 ],

[ 1255, 2552338241, 156978797223733228787865722354959930,

=={{header|Go}}==

import (

fmt.Printf("%d %v\n", num, r[len(r)-1].Text(10))

}

{{out}}

<pre>

=={{header|Groovy}}==

def partitions(c)

{

{partitions(i);}

}

{{out}}

<pre>

=={{header|Haskell}}==

cumu :: [[Integer]]

main = do

mapM_ print $ take 10 rows

{{out}}

<pre>

{{trans|Python}}

n := integer(!A) | 10

every r := 2 to (n+1) do write(right(r-1,2),": ",showList(row(r)))

every (s := "[") ||:= (!A||", ")

return s[1:-2]||"]"

{{out}} (terminated without waiting for output of cumu(12345)):

=={{header|J}}==

Recursive calculation of a row element:

Calculation of the triangle:

'''Show triangle''':

1

1 1

1 4 5 5 3 2 1 1

1 4 7 6 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.

z=. a n}z

end.

{{out}}

<pre> ({ [: rowSums >./) 3 23 123 1234

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;

}

}

<pre>Rows:

===Solution 1===

{{trans|Python}}

(function () {

var cache = [

});

})()

===Solution 2===

Clean and straightforward solution

function genTriangle(n){ // O(n^3) time and O(n^2) space

var a = new Array(n)

console.log("G(" + x + ") = " + G(x))

}

{{out}}

<pre>

=={{header|Julia}}==

using Combinatorics, StatsBase

end

[1]

[1, 1]

=={{header|Kotlin}}==

{{trans|Swift}}

import java.math.BigInteger

import java.util.ArrayList

System.out.printf("%s %s%n", it, c[c.size - 1])

}

<pre>

=={{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)

cumu(#x+1)->last

'\r'

{{out}}

=={{header|Lua}}==

local tri = {{1}}

for r = 2, n do

end

print("G(23) = " .. G(23))

{{out}}

<pre>1: 1

=={{header|Maple}}==

Triangle := proc(m)

local i;

end do

end proc:

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

{{out}}

<pre>1

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]

Using the built-in function to calculate <math>P(n)</math>:

{{out}}

<pre>(%o1) [1255, 2552338241, 156978797223733228787865722354959930, 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736]</pre>

=={{header|Nim}}==

{{trans|Python}}

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

for x in [23, 123, 1234, 12345]:

let c = cumu(x)

{{out}}

<pre>@[1]

Faster version:

{{trans|C}}

var p = @[1.initBigInt]

let p = partitions(i)

if i in ns:

{{out}}

<pre>23: 1255

=={{header|OCaml}}==

let get, sum_unto =

let cache = ref [||]

end

[23;123;1234;12345;123456]

{{out}}

<pre>

=={{header|Ol}}==

(define (nine-billion-names row column)

(cond

(print-triangle 25)

{{Out}}

<pre>

=={{header|PARI/GP}}==

show(n)=for(k=1,n,print(row(k)));

show(25)

apply(numbpart, [23,123,1234,12345])

{{out}}

<pre>[1]

=={{header|Perl}}==

{{libheader|ntheory}}

sub triangle_row {

printf "%2d: %s\n", $_, join(" ",triangle_row($_)) for 1..25;

print "\n";

{{out}}

[rows are the same as below]

{{trans|Raku}}

use strict;

use warnings;

print $i, "\n";

}

{{out}}

<pre>

=={{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>

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

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

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

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

<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 #/

enddef

{{out}}

<pre> 1

===The triangle, using constraint modelling===

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

main =>

foreach(I in L)

Map.put(I,Map.get(I,0)+1)

{{out}}

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

M := (K*(3*K+1)) // 2

end,

{{out}}

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

=={{header|PicoLisp}}==

{{trans|Python}}

(let C '((1))

(do N

(println (sumr I)) ) )

{{out}}

{{trans|Python}}

array(array(int)) cache = ({({1})});

}

return 0;

{{out}} Not wait for "12345" output.

<pre>rows:

=={{header|PureBasic}}==

Define nMax.i=25, n.i, k.i

Dim pfx.s(1)

PrintN(sum(12345,pfx()))

Input()

{{out}}

<pre>

=={{header|Python}}==

def cumu(n):

for l in range(len(cache), n+1):

print "\nsums:"

{{out}} (I didn't actually wait long enough to see what the sum for 12345 is)

<pre>

</pre>

To calculate partition functions only:

diffs,k,s = [],1,1

while k * (3*k-1) < 2*N:

p = partitions(12345)

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)

print "%6d: %s" % (i, p)

{{out}}

<pre> 23: 1255

=={{header|Racket}}==

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

(newline)

(map G '(23 123 1234)))

{{out}}

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

for 23, 123, 1234, 12345 {

put $_, "\t", @names-of-God[$_];

{{out}}

<pre>rows:

=={{header|Red}}==

Red []

probe names 1234

{{out}}

</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.*/

else $= $ - x - y /* " " " " " " even.*/

end /*k*/ /* [↑] Euler's recursive func.*/

{{out|output|text=&nbsp; when using the default input &nbsp; (of 25 rows):}}

<pre>

=={{header|Ruby}}==

===Naive Solution===

# Generate IPF triangle

# Nigel_Galloway: May 1st., 2013.

puts (1..n).map {|g| "%4s" % g(n,g)}.join

}

{{out}}

<pre>

===Full Solution===

# Find large values of IPF

# Nigel_Galloway: May 1st., 2013.

n = 3 + @ipn1.inject(:+) + @ipn2.inject(:+)

puts "G(12345) = #{n}"

{{out}}

<pre>

=={{header|Rust}}==

{{trans|Python}}

use std::cmp;

println!("{}: {}", x, s);

}

{{out}}

<pre>rows:

=={{header|Scala}}==

===Naive Solution===

object Main {

}

}

{{out}}

<pre>

===Full Solution===

cache(0) = 1

val cacheNaive = scala.collection.mutable.Map[Tuple2[Int, Int], BigInt]()

println(quickPartitions(123))

println(quickPartitions(1234))

{{out}}

<pre> 1

=={{header|scheme}}==

(define (sigma g x y)

(define (sum i)

(cond ((< i x) (begin (display (line i)) (display "\n") (print-loop (+ i 1)) ))))

(print-loop 1))

{{out}}

=={{header|Sidef}}==

func cumu (n) {

for i in [23, 123, 1234, 12345] {

"%2s : %4s\n".printf(i, cumu(i)[-1])

{{out}}

=={{header|SPL}}==

> n, 1..25

k = 50-n*2

<

<= p[n+1]

{{out}}

<pre>

=={{header|Stata}}==

function part(n) {

a = J(n,n,.)

return(a)

}

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

=={{header|Swift}}==

{{trans|Python}}

func namesOfGod(n:Int) -> [Int] {

for l in cache.count...n {

var numInt = array[array.count - 1]

println("\(x): \(numInt)")

{{out}}

<pre>

=={{header|Tcl}}==

{{trans|Python}}

proc cumu {n} {

global cache

foreach x {23 123 1234 12345} {

puts "${x}: [lindex [cumu $x] end]"

{{out}}

<pre>

Print

{{Out}}

<pre> 1

0 OK, 0:30 </pre>

=={{header|VBA}}==

Dim p(25, 25) As Long

p(1, 1) = 1

Debug.Print

Next i

<pre> 1

1 1

=={{header|Vlang}}==

{{trans|Go}}

fn int_min(a int, b int) int {

println("$num ${r[r.len-1]}")

}

{{out}}

{{libheader|Wren-big}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

[23, 123, 1234, 12345].each { |i|

Fmt.print("$5s: $s", i, cumu.call(i)[-1])

{{out}}

=={{header|Yabasic}}==

{{trans|VBA}}

Sub nine_billion_names(rows)

End Sub

=={{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;

}

}

p[0].set(1);

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