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

{{trans|Python}}

 

F cumu(n)

L(l) :cache.len .. n

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

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program integerName64.s */

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

 

with Ada.Numerics.Big_Numbers.Big_Integers;

 

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

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program integerName.s */

 

=={{header|AutoHotkey}}==

 

InputBox, Enter_value, Enter the no. of lines sought

 

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>

 

(this requires a System.Numerics registry reference)

 

using System.Collections.Generic;

using System.Linq;

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

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

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

The following will display OTT(25).

int main(){

N = 25;

===Values of Integer Partition Function===

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

#include <iostream>

int main(){

 

=={{header|Clojure}}==

(cond (<= row 0) 0

(<= column 0) 0

 

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

(cond ((<= row 0) 0)

((<= column 0) 0)

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

===Producing rows===

{{trans|Python}}

 

auto cumu(in uint n) {

===Only partition functions===

{{trans|C}}

 

struct Names {

{{trans|Python}}

 

 

List<BigInt> partitions(int n) {

 

In main:

 

main(List<String> arguments) {

=={{header|Dyalect}}==

 

func namesOfGod(n) {

{{trans|Ruby}}

Naive Solution

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

def g(n,g) do

 

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

=={{header|Factor}}==

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

sequences ;

 

=={{header|FreeBASIC}}==

{{libheader|GMP}}

' compile with: fbc -s console

 

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

{

=={{header|GAP}}==

The partition function is built-in.

 

[ [ 1 ],

 

=={{header|Go}}==

 

import (

 

=={{header|Groovy}}==

def partitions(c)

{

 

=={{header|Haskell}}==

 

cumu :: [[Integer]]

{{trans|Python}}

 

n := integer(!A) | 10

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

=={{header|J}}==

Recursive calculation of a row element:

Calculation of the triangle:

'''Show triangle''':

1

1 1

 

Calculate row sums:

z=. (y+1){. 1x

for_ks. <\1+i.y do.

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;

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

G(12345) = 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736

</pre>

 

=={{header|Julia}}==

using Combinatorics, StatsBase

 

=={{header|Kotlin}}==

{{trans|Swift}}

import java.math.BigInteger

import java.util.ArrayList

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

 

=={{header|Lua}}==

local tri = {{1}}

for r = 2, n do

 

=={{header|Maple}}==

Triangle := proc(m)

local i;

 

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

Faster version:

{{trans|C}}

 

var p = @[1.initBigInt]

 

=={{header|OCaml}}==

let get, sum_unto =

let cache = ref [||]

 

=={{header|Ol}}==

(define (nine-billion-names row column)

(cond

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

 

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

show(25)

=={{header|Perl}}==

{{libheader|ntheory}}

 

sub triangle_row {

 

{{trans|Raku}}

use strict;

use warnings;

 

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

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

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

=={{header|Phixmonti}}==

{{trans|Yabasic}}

by Galileo, 05/2022 #/

 

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

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

 

main =>

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

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

=={{header|PicoLisp}}==

{{trans|Python}}

(let C '((1))

(do N

{{trans|Python}}

 

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

 

 

=={{header|PureBasic}}==

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

Dim pfx.s(1)

 

=={{header|Python}}==

def cumu(n):

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

</pre>

To calculate partition functions only:

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

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

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)

 

1234: 156978797223733228787865722354959930

12345: 69420357953926116819562977205209384460667673094671463620270321700806074195845953959951425306140971942519870679768681736</pre>

 

=={{header|Racket}}==

 

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

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

 

=={{header|Red}}==

Red []

 

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

=={{header|Ruby}}==

===Naive Solution===

# Generate IPF triangle

# Nigel_Galloway: May 1st., 2013.

 

===Full Solution===

# Find large values of IPF

# Nigel_Galloway: May 1st., 2013.

=={{header|Rust}}==

{{trans|Python}}

 

use std::cmp;

=={{header|Scala}}==

===Naive Solution===

object Main {

 

 

===Full Solution===

cache(0) = 1

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

 

=={{header|scheme}}==

(define (sigma g x y)

(define (sum i)

 

=={{header|Sidef}}==

 

func cumu (n) {

 

=={{header|SPL}}==

> n, 1..25

k = 50-n*2

 

=={{header|Stata}}==

function part(n) {

a = J(n,n,.)

=={{header|Swift}}==

{{trans|Python}}

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

for l in cache.count...n {

=={{header|Tcl}}==

{{trans|Python}}

proc cumu {n} {

global cache

{{trans|VBA}}

Since uBasic/4tH features a single array of 256 elements, level "15" is the best that can be achieved.

End

 

0 OK, 0:30 </pre>

=={{header|VBA}}==

Dim p(25, 25) As Long

p(1, 1) = 1

1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1</pre>

 

{{trans|Go}}

 

fn int_min(a int, b int) int {

{{libheader|Wren-big}}

{{libheader|Wren-fmt}}

 

var cache = [[BigInt.one]]

=={{header|Yabasic}}==

{{trans|VBA}}

 

Sub nine_billion_names(rows)

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

}

}</syntaxhighlight>

p[0].set(1);

 

100000: 27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519

</pre>