Partition function P: Difference between revisions

 

 

 

 

The successive numbers in the above equation have the differences:   1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8 ...

 

 

In Wolfram Language, this function has been implemented as PartitionsP.

{{trans|Python: Alternative}}

 

V p = [BigInt(1)] [+] [BigInt(0)] * n

L(i) 1 .. n

V start = time:perf_counter()

print(partitions(6666))

 

{{out}}

=={{header|C}}==

{{libheader|GMP}}

#include <stdlib.h>

#include <stdio.h>

(double)(clock() - start) / (double)CLOCKS_PER_SEC);

return 0;

 

{{out}}

=={{header|C#|CSharp}}==

This can also be done using BigIntegers, but will take around five times longer. Since only adding and subtracting are required, some simple routines can be created to handle the tabulations. Also note that detecting odd and even numbers on each loop iteration is avoided by coding four increments per loop.

 

class Program {

Console.Write("{0} {1} ms", fmt(res), sw.Elapsed.TotalMilliseconds);

}

{{out}}

<pre>193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 12.9365 ms</pre>

===GMP version===

{{libheader|GMP}}

#include <iostream>

#include <vector>

std::cout << result << '\n';

std::cout << "elapsed time: " << ms.count() << " milliseconds\n";

 

{{out}}

===Non GMP version===

{{trans|C#}}

#include <iostream>

 

duration<double, milli> ms(end - start);

cout << fmt(result) << " " << ms.count() << " ms";

{{out}}

Timing from Tio.run, but execution time can't be directly compared to the GMP version, as GMP isn't accessible at Tio.run.

{{libheader| System.Diagnostics}}

{{Trans|Go}}

program Partition_function_P;

 

writeln('Took ', stopwatch.ElapsedMilliseconds, 'ms');

Readln;

{{out}}

<pre>p[6666] = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

=={{header|Elixir}}==

Loosely based on the Erlang version.

use Bitwise, skip_operators: true

 

Partition.init

IO.puts Partition.p 6666

{{Out}}

<pre>

 

=={{header|Erlang}}==

-mode(compile).

 

true -> gpentagonals(M + 1, Max, [GP|Ps])

end.

{{Out}}

<pre>

=={{header|F_Sharp|F#}}==

An implementation of the formula in the task description. P(123456) is included for comparison with the largest value in the related task.

// PartionP: Nigel Galloway. April 12th., 2021

let pP g=let rec fN i g e l=seq{yield(l,e+i);yield(-l,e+i+g);yield! fN(i+1)(g+2)(e+i+g)(-l)}

seq{2..g}|>Seq.iter(fun p->N.[p]<-G|>List.takeWhile(fun(_,n)->n<=p)|>Seq.fold(fun Σ (n,g)->Σ+n*N.[p-g]) 0I); N.[g]

printfn "666->%A\n\n6666->%A\n\n123456->%A" (pP 666) (pP 6666) (pP 123456)

{{out}}

<pre>

=={{header|Factor}}==

{{works with|Factor|0.99 2020-08-14}}

 

! Compute the nth pentagonal number.

: partitions ( m -- n )

[ seq swap [ <= ] curry lwhile list>array ]

{{out}}

<pre>

===Unsiged 64bit version===

{{trans|Python}}

' if n > 416, the result becomes to large for a unsigned 64bit integer

Dim As ULongInt p(n)

 

Print !"\n\ndone"

{{out}}

<pre>PartitionsP: 1 1 2 3 5 7 11 15 22 30 42 56 77</pre>

{{libheader|GMP}}

[https://rosettacode.org/wiki/9_billion_names_of_God_the_integer#FreeBASIC From the 9_billion_names_of_God_the_integer entry]

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>PartitionsP(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

=={{header|Frink}}==

Frink has a built-in function for counting partitions that uses Euler's pentagonal method. It works for arbitrarily-large integers and caches results.

{{out}}

<pre>

{{trans|Julia}}

I also tried using Euler's generating function but it was about 20 times slower than this version.

 

import (

fmt.Printf("p[%d)] = %d\n", N, p[N])

fmt.Printf("Took %s\n", time.Since(start))

 

{{out}}

 

=={{header|Java}}==

 

public class PartitionFunction {

return p[n];

}

 

{{out}}

=={{header|JavaScript}}==

 

function p(n){

var a = new Array(n+1)

console.log("p(6666) = " + p(6666))

console.log("Computation time in ms: ", Date.now() - t)

 

{{out}}

=={{header|Haskell}}==

 

 

------------------------------------------------------------

 

main :: IO ()

 

<pre>*Main> partitionP <$> [1..10]

Solution stolen [https://code.jsoftware.com/wiki/Essays/Partitions#The_Number_of_Partitions verbatim from the J Wiki]. Note the use of memoization (M.) for efficiency:

 

 

{{out}}

Translation of: Python:Alternative

 

def div2: (. - (.%2)) / 2;

reduce range(1; $n + 1) as $i ( {p: ([1] + [range(0;$n)|0])};

| .p[$n] ;

 

{{out}}

<pre>[1,2,3,5,7,11,15,22,30,42,56,77,101,135]</pre>

 

with a trivially-modified version of the ''partitions'' implementation above. That is, after

modifying the lines that refer to "p" (or ".p"), we see that ''partitions(6666)'' yields:

"193655306161707661080005073394486091998480950338405932486880600467114423441282418165863"

 

 

{{trans|Julia}} with memoization

if ($n % 2) == 1 then ($n+1) / 2 else $n+1 end;

 

# Stretch goal:

6666 | partitionsP

Using gojq, the above program takes 41.35 seconds (u+s) on a 3GHz Mac Mini to produce:<pre>

193655306161707661080005073394486091998480950338405932486880600467114423441282418165863</pre>

=={{header|Julia}}==

===Recursive===

 

function partDiffDiff(n::Int)::Int

 

n=6666

{{out}}

<pre>p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

=={{header|Lingo}}==

Lingo natively only supports 32 bit integers, so P(6666) would be way too big.

on partitions(n, res_table)

if n < 2 then return 1

res_table[n] = res

return res

{{out}}

<pre>

 

=={{header|Maple}}==

option remember;

local k,s:=0,m;

 

combinat[numbpart](1000);

 

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

PartitionsP[666]

{{out}}

<pre>{1,2,3,5,7,11,15,22,30,42,56,77,101,135,176}

{{trans|C++}}

{{libheader|bignum}}

import bignum

 

let t0 = cpuTime()

echo partitions(6666)

 

{{out}}

 

=={{header|Perl}}==

use warnings;

no warnings qw(recursion);

 

print partitionsP($_) . ' ' for 0..25; print "\n";

{{out}}

<pre>1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958

{{libheader|Phix/mpfr}}

Not exactly super-fast, but this sort of stuff is not really what Phix does best.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">partDiffDiff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">6666</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"p(%d) = %s (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">partitionsP</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>

{{out}}

<pre>

 

=={{header|Picat}}==

/* Picat 3.0#5 */

/* Author: Hakan Kjellerstrand */

 

CPU time 0.206 seconds.

 

=={{header|PicoLisp}}==

Based on the Erlang implementation.

(de gpentagonals (Max)

(make

(setq Sgn (& 3 (inc Sgn))))

Sum))))

{{Out}}

<pre>

 

=={{header|Prolog}}==

/* SWI-Prolog 8.3.21 */

/* Author: Jan Burse */

X = 1936553061617076610800050733944860919984809503384

05932486880600467114423441282418165863.

 

=={{header|Python}}==

This follows the algorithm from the Mathloger video closely

 

 

def posd():

print(" pos_gen:", list(islice(pos_gen(), 10)))

print(" plus_minus:", list(islice(plus_minus(), 15)))

 

{{out}}

====Python: Mathloger video prime generator====

Add the following code after that above

"Prime number generator from the partition machine"

p = [1]

yield p

 

 

{{Out}}

===Python: Alternative===

{{trans|C++}}

 

 

 

if __name__ == '__main__':

 

{{out}}

In [4]: %timeit partitions(6666)

215 ms ± 1.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

</pre>

 

Backwards range was used to get responsive feedback for progress.

 

 

(require math/number-theory)

(p 666)

(p 1000)

 

{{out}}

{{works with|Rakudo|2020.09}}

Not the fastest, but it gets the job done.

 

put @P[^26];

{{out}}

<pre>1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958

These three REXX versions are recursive.

=== version 1 ===

numeric digits 1000 /*able to handle some ginormous numbers*/

parse arg lo hi . /*obtain optional arguments from the CL*/

else #= # - (x + y) /*Even? " subtract " " " */

end /*k*/

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 6666 </tt>}}

<pre>

 

The biggest part of the improvement was using the expression &nbsp; &nbsp; '''k+k+k''' &nbsp; &nbsp; instead of &nbsp; &nbsp; '''k*3'''.

numeric digits 1000 /*able to handle some ginormous numbers*/

parse arg lo hi . /*obtain optional arguments from the CL*/

else #= # - (x + y) /*Even? " subtract " " " */

end /*k*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}}

 

 

The biggest part of the improvement was using memoization of the expressions &nbsp; &nbsp; ('''k+k+k - 1) * k % 2''' &nbsp; &nbsp; for all values of (positive) &nbsp; '''k''' &nbsp; up to &nbsp; '''hi'''.

numeric digits 1000 /*able to handle some ginormous numbers*/

parse arg lo hi . /*obtain optional arguments from the CL*/

else #= # - (x + y) /*Even? " subtract " " " */

end /*k*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br><br>

 

=={{header|Rust}}==

// rug = "1.11"

 

println!("P({}) = {}", n, result);

println!("elapsed time: {} microseconds", time.as_micros());

 

{{out}}

 

Built-in:

 

User-defined:

func (n) is cached {

 

say partitionsP(6666)

 

 

{{out}}

Using AttaSwift's BigInt library.

 

 

func partitions(n: Int) -> BigInt {

}

 

 

{{out}}

{{libheader|Wren-big}}

Although it may not look like it, this is actually a decent time for Wren which is interpreted and the above module is written entirely in Wren itself.

 

var p = []

for (n in 2..N) partitionsP.call(n)

System.print("p[%(N)] = %(p[N])")

 

{{out}}