9 billion names of God the integer: Difference between revisions

{{task}}

This task is a variation of the [[wp:The Nine Billion Names of God#Plot_summary|short story by Arthur C. Clarke]].

 

If your environment is able, plot &nbsp; <math>P(n)</math> &nbsp; against &nbsp; <math>n</math> &nbsp; for &nbsp; <math>n=1\ldots 999</math>.

<br><br>

 

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

var r = [0]

}

}

return cache[n]

}

func row(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>

=={{header|FreeBASIC}}==

{{libheader|GMP}}

' compile with: fbc -s console

 

' ------=< MAIN >=------

 

Dim As ULongInt p(max, max) ' to big for a 64bit unsigned integer

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 1

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>

</pre>

 

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:

 

=={{header|JavaScript}}==

{{trans|Python}}

(function () {

var cache = [

}

 

var s = cumu(a);

console.log(a, s[s.length - 1]);

});

})()

 

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

1234: 156978797223733228787865722354959930

12345: (ran long, timed out)</pre>

 

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

{{out}}

<pre>

{{trans|C}}

{{libheader|Phix/mpfr}}

{{Out}}

<pre>

=== Third and last, a simple plot ===

{{libheader|Phix/pGUI}}

 

=={{header|PicoLisp}}==

{{trans|Python}}

(let C '((1))

(do N

(println (sumr I)) ) )

 

 

{{out}}

69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

0.626 sec</pre>

 

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

1234: 156978797223733228787865722354959930

12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736</pre>

 

=={{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 +@todo .. $n -> $l {

my $r = [];

for reverse ^$l -> $x {

 

say "rows:";

 

 

say "\nsums:";

for 23, 123, 1234, 12345 {

{{out}}

<pre>rows:

 

sums:

1234 156978797223733228787865722354959930

12345 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736</pre>

 

=={{header|REXX}}==

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

}

 

 

'''Output'''

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

<small>(I killed the run when it started to take a significant proportion of my system's memory.)</small>

 

=={{header|VBA}}==

Dim p(25, 25) As Long

p(1, 1) = 1

Debug.Print

Next i

<pre> 1

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

 

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

100000: 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519

</pre>