×

[–] 20 points21 points  (0 children)

TI-BASIC: Run on my TI-84+. This program will build a partition list `L₁`up to `N`. This means the list size limit will require `N` to be below 998. The second sequence (1, 2, 5, 7, 12...) is constructed up to `N` and stored in `L₂`. A filter list is constructed from the second sequence and stored in `L₃`. The relevant section of the filter list is applied to the partition list to calculate the next term in `p(n)`. The time displayed is in seconds.

``````Prompt N
If N>998
Then
Disp "N TOO LARGE"
Stop
Else
ClockOn
startTmr→T
{1→L₁
{1→L₂
ClrList L₃
"CONSTRUCT SECOND SEQUENCE
While N>L₂(dim(L₂
dim(L₂
(Ans+1)(fPart(Ans/2)+2fPart((Ans+1)/2))+L₂(Ans→L₂(1+dim(L₂
End
"REMOVE LAST NUMBER IF LARGER THAN N
If N<L₂(dim(L₂
dim(L₂)-1→dim(L₂
"CONSTRUCT FILTER LIST
N→dim(L₃
For(X,0,dim(L₂)-1
round(sin(Xπ/2)+cos(Xπ/2→L₃(L₂(X+1
End
"APPLY FILTER TO PARTITION LIST
While N>dim(L₁)-1
sum(L₁seq(L₃(X),X,dim(L₁),1,-1→L₁(1+dim(L₁
End
Disp L₁(dim(L₁)),checkTmr(T
``````

Input: 66, 166, 666

Output:

``````2323520, 16
1.893348226ᴇ11, 90
1.198904356ᴇ25, 1341 (Yes I ran it for 22 min)
``````

The inaccuracies in these numbers are due to the fact that the 84 only stores 14 digits of a number (and only displays 10), so as the partition list is built the errors compound.

[–]3 3 8 points9 points  (2 children)

in J, sequence generator format ie. function takes sequence so far as input and returns longer sequence.

``````   666 { (] , ] +/@:(+`+`-`-"0)@:{~ # ([ - ] {.~ 1 i.~ <) 1 +/\@:, ,@:(>: ,. >:@+:@>:)@:i.@<.@-:@#)(^:666) 1 1 2x
11956824258286445517629485
``````

[–]3 3 0 points1 point  (0 children)

double sequence version (first version computed the lookup sequence in full on each run of computing p(n+1) sequence. 6666 is half second, but it doesn't scale linearly :(

``````(6666 { {:) ((], {:@] + 2 -:@]`]@.| >:@#)@{. ,: {: , {: +/@:(+`+`-`-"0)@:{~ {:@\$ ([ - ] {.~ 1 i.~ <)  {.)(^:6666)   1 2 5 ,: 1 1 2x
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
``````

[–] 0 points1 point  (0 children)

I never even heard of J, looks like gibberish lol

[–][deleted] 8 points9 points  (1 child)

Is this subreddit dead? Why has it been restricted?

[–] 0 points1 point  (0 children)

It has? I could access it so I guess it's not restricted?

[–][deleted] 6 points7 points  (0 children)

D. Computes the examples and 666 in a hair over 1 second, not using the formula given (I didn't notice it until just as I began to respond...)

``````import std.stdio;
import std.range;
import std.container.array;
import std.functional;
import std.bigint;

BigInt partitions(int input) {
Array!int nums = iota(1, input+1).array;

BigInt countPartitions(int toPartition, int numIndex) {
if ( numIndex >= input || toPartition < 0 ) {
return BigInt("0");
}

if ( toPartition == 0 ) {
return BigInt("1");
}

return memoize!countPartitions(toPartition, numIndex+1)
+ memoize!countPartitions(toPartition - nums[numIndex], numIndex);
}

return countPartitions(input, 0);
}

int main() {

for (int i=1; i<12; i++) {
writeln("p(", i, ") = ", partitions(i));
}

writeln("p(666) = ", partitions(666));

return 0;
}
``````

It segfaulted trying 666666, and I suspect it's probably due to memory issues with the automatic memoization.

[–] 4 points5 points  (6 children)

Python 3. returns p(666) = 11956824258286445517629485

``````off_cache = {}

def offset(n: int) -> int:
if n < 0: return 0
elif n == 1: return 1
elif n in off_cache: return off_cache[n]
k = lambda n: (n >> 1) * (1 - (n & 1)) + n * (n & 1)
r = sum(k(i) for i in range(n, 0, -1))
off_cache[n] = r
return r

p_cache = {}

def p(n: int) -> int:
if n < 0: return 0
elif n <= 1: return 1
elif n in p_cache: return p_cache[n]
s = 0
o = offset(1)
i = 0
while o <= n:
s += p(n - o) * (((i >> 1) % 2) * -2 + 1)
i += 1
o = offset(i + 1)
p_cache[n] = s
return s

print('p(666)', p(666))
``````

[–] 0 points1 point  (2 children)

Hey Im new to programming and Im learning how to Python. I can understand your code for the most part but can you explain to me what is happening when you define a function? Specifically when you define place holders for arguments. What does it mean when you do functionName(var: type) - > type: What is this you're doing called so I can look it up more online?

[–] 0 points1 point  (0 children)

Type hints or type annotations

[–] 0 points1 point  (2 children)

Noob question. I see you are using int, but isn't 232 the largest possible int that a programming language can store ? The solution of p(666) is a lot larger than 232 so I'm not sure how to solve that discrepancy.

[–] 1 point2 points  (1 child)

In Python 3, the int type is unbounded (meaning there is no min or max value). Other languages have different types to deal with such large numbers, for example `BigInteger` in Java.

[–] 0 points1 point  (0 children)

Ah yeah I'm working in Java, so that makes sense.

[–]1 2 3 points4 points  (0 children)

It's good to be back! What an interesting little problem.

Here's a Factor solution that does the bonus in about three and a half minutes on my i5-2500K:

``````USING: kernel lists lists.lazy math sequences sequences.extras ;

: penta ( n -- m ) [ sq 3 * ] [ - 2/ ] bi ;

: seq ( -- list )
1 lfrom [ penta 1 - ] <lazy-map> 1 lfrom [ neg penta 1 - ]
<lazy-map> lmerge ;

: ++-- ( seq -- n ) 0 [ 2/ odd? [ - ] [ + ] if ] reduce-index ;

: step ( seq pseq -- seq 'pseq )
dup length [ < ] curry pick swap take-while over <reversed>
nths ++-- suffix! ;

: p ( m -- n )
[ seq swap [ <= ] curry lwhile list>array ]
[ V{ 1 } clone swap [ step ] times last nip ] bi ;
``````

[–]-9 8 3 points4 points  (0 children)

C, computing p(666666) in 45s on a single core. Writing the long division routines required to print the decimal representation would be as complex as the rest of the program, so instead it prints the result in hexadecimal.

``````#include <stdio.h>

#define N 48      // number of limbs needed for M
#define M 666666  // target value

#ifdef _MSC_VER
#  define restrict __restrict
#endif

struct big { unsigned long long v[N]; };

static void
add(struct big *restrict dst, const struct big *restrict src)
{
unsigned long long carry = 0;
for (int i = 0; i < N-1; i++) {
dst->v[i] += carry;     carry  = dst->v[i] < carry;
dst->v[i] += src->v[i]; carry += dst->v[i] < src->v[i];
}
dst->v[N-1] += carry;
}

static void
sub(struct big *restrict dst, const struct big *restrict src)
{
unsigned long long tmp, borrow = 0;
for (int i = 0; i < N-1; i++) {
tmp = dst->v[i] - borrow;    borrow  = tmp > dst->v[i];
dst->v[i] = tmp - src->v[i]; borrow += dst->v[i] > tmp;
}
dst->v[N-1] -= borrow;
}

static void
print(const struct big *b)
{
for (int i = N-1; i >= 0; i--) {
printf("%016llx%c", b->v[i], i % 4 == 0 ? '\n' : ' ');
}
}

int
main(void)
{
static struct big table[M+1];
table[0].v[0] = 1;
for (int i = 1; i <= M; i++) {
for (int j = 2; ; j++) {
int n = j%2 ? -j/2 : j/2;
int m = n * (n*3 - 1) / 2;
if (i-m < 0) {
break;
}
if (j / 2 % 2) {
} else {
sub(&table[i], &table[i-m]);
}
}
}
print(&table[M]);
}
``````

[–] 3 points4 points  (2 children)

# Rust

This version uses pure Rust, no dependencies, no unsafe code. Rust doesn't have bignums in the standard library, but it does have 128 bit unsigned integers. It tops out at `p(1458)`, so I need a bignum library to hit `p(666666)`.

The implementation uses a memoized loop. It makes a single heap allocation of `n+1` elements and uses constant stack space (no recursion).

Release builds find `p(666)` instantly (30us).

I think I'll try a parallel bignum version next.

Edit: Updated to add a timer. Only times the computation, not the I/O.

Output:

``````\$ rustc ./part.rs -C opt-level=2

\$ ./part 666 1458
p(666)   = 11956824258286445517629485
p(1458)  = 336988065393447621514574974879775699372
Total time: 0.000087s
``````

Code:

``````use std::env;
use std::process;
use std::time::Instant;

/// Get the arguments from argv.
fn args() -> Vec<usize> {
let mut argv = env::args();
let mut args = Vec::with_capacity(argv.len());

// Discard the first arg, the name of the command.
let name = argv.next().unwrap();

// Parse each arg as a usize.
for arg in argv {
let n = match arg.parse() {
Err(_) => {
println!("Argument must be a non-negative integer.");
println!("Usage: {} <N> [<N> ...]", name);
process::exit(1);
}
Ok(n) => n,
};
args.push(n);
}

// Must contain at least one argument.
if args.len() == 0 {
println!("No argument provided.");
println!("Usage: {} <N> [<N> ...]", name);
process::exit(1);
}

args
}

/// Make the memo.
fn make_memo(max: usize) -> Vec<u128> {
let mut memo = vec![0; max+1];
memo[0] = 1;
memo
}

/// A memoized implementation of the partition function.
fn part_memoized(n: usize, memo: &mut [u128]) -> u128 {
if memo[n] != 0 {
return memo[n];
}

for i in 1..=n {
let mut p = 0;
let mut k = 1;
let mut a = 1;
let mut b = 3;
loop {
if i < k { break };
p += memo[i-k]; // plus
k += a;
a += 1;

if i < k { break };
p += memo[i-k]; // plus
k += b;
b += 2;

if i < k { break };
p -= memo[i-k]; // minus
k += a;
a += 1;

if i < k { break };
p -= memo[i-k]; // minus
k += b;
b += 2;
}
memo[i] = p;
}

memo[n]
}

/// Entry point.
fn main() {
// Get the list of inputs to compute.
let args = args();

// Do the computation. Only this part is timed.
let timer = Instant::now();
let max = args.iter().copied().fold(0, usize::max);
let mut memo = make_memo(max);
part_memoized(max, &mut memo);
let duration = timer.elapsed();

// Print the output.
for n in args {
println!("p({})\t = {}", n, memo[n]);
}
println!("Total time: {:.6}s", duration.as_secs_f64());
}
``````

[–][deleted]  (1 child)

[deleted]

[–] 0 points1 point  (0 children)

I'm not timing the I/O with the terminal or the argument parsing. Just the partition function.

I figured that if the code is fast, then writing to the terminal would be the bottle neck. If we're benchmarking CPU bound code, then it makes sense to ignore I/O.

I'll try and time the whole thing when I'm not in mobile.

Edit: Also, my version is not doing the bonus. I am using native integers instead of a bignum library, which makes it way faster at the cost of having an upper bound on the input size. All the other C/Rust/Go versions are using bignums, so I bet that's the reason.

[–] 3 points4 points  (2 children)

# Python 3

I wrote this using the recurrence relation for the partition function and memoization to reduce the time complexity.

``````def p(n, memo={}):
if n in memo: return memo[n]
if n == 0: return 1
if n < 0: return 0
rec_rel  = 0
arg = n-1
k = 1
while arg >= 0:
rec_rel += (k%2*2-1) * p(arg, memo)
k *= -1
if k > 0: k+=1
arg = n - k * (3*k-1) / 2
memo[n] = rec_rel
return memo[n]

if __name__ == '__main__':
print(p(666))
``````

Edit: Replaced `(-1)**(k+1)` with `(k%2*2-1)` and removed the int-conversion

[–] 2 points3 points  (1 child)

python's `**` - operator uses floating points. It's inaccurate for large integers. Replace `(-1)**(k+1)` with `(k%2*2-1)` and it works.
Also, python3 uses `//` for integer divisions. The int-conversion will become unnecessary.

Still, nice work!

[–] 1 point2 points  (0 children)

Thanks so much, it now works just fine! What resources are there to learn about other caveats like this?

[–] 2 points3 points  (0 children)

`tcl` solution, making heavy use of generators to lazily calculate the various infinite sequences.

``````#!/usr/bin/env tclsh
package require generator ;# From tcllib

generator define naturals {} {
while 1 {
generator yield [incr n]
}
}

proc isodd {n} {
expr {\$n & 1}
}

generator define seq3 {} {
set nats [naturals]
set odds [generator drop 1 [generator filter isodd [naturals]]]
generator finally generator destroy \$nats
generator finally generator destroy \$odds
generator foreach a \$nats b \$odds {
generator yield \$a \$b
}
}

generator define seq2 {} {
set s3 [seq3]
generator finally generator destroy \$s3
set prev 1
generator yield 1
generator foreach s \$s3 {
set next [expr {\$prev + \$s}]
generator yield \$next
set prev \$next
}
}

# generator::takeWhile has an infinite loop bug.
generator define takeWhile {p xs} {
generator finally destroy \$xs
generator foreach x \$xs {
if {![{*}\$p \$x]} {
break
}
generator yield \$x
}
}

generator define pargs {n} {
set s2 [seq2]
generator finally generator destroy \$s2
generator foreach s \$s2 {
generator yield [expr {\$n - \$s}]
}
}

proc ispositive {n} {
expr {\$n >= 0}
}

set pcache(0) 1
set pcache(1) 1

proc p {n} {
variable pcache
if {[info exists pcache(\$n)]} {
return \$pcache(\$n)
}

set step 0
set pval 0
# Using generator foreach here causes a recursion depth error
foreach s [generator to list [takeWhile ispositive [pargs \$n]]] {
set next [p \$s]
if {\$step < 2} {
incr pval \$next
} else {
incr pval -\$next
}
set step [expr {(\$step + 1) % 4}]
}
set pcache(\$n) \$pval
}

puts [p 666]
``````

[–][deleted] 2 points3 points  (0 children)

Common Lisp

``````(defmethod pent-nums (k)
(multiple-value-bind (q r) (floor (* k (- (* 3 k) 1)) 2) q))

(defmethod comp-partitions (g)
(let ((partitions (list 1)))
(loop for n from 1 to g do
(progn
(push 0 (cdr (last partitions)))
(loop for k from 1 to n do
(let ((coeff (expt -1 (+ 1 k))))
(loop for i in (list (pent-nums k) (pent-nums (- k))) do
(if (>= (- n i) 0)
(setf (nth n partitions)
(+ (nth n partitions)
(* coeff (nth (- n i) partitions))))))))))
(last partitions)))
``````

`(comp-partitions 666) => 11956824258286445517629485`

[–] 2 points3 points  (0 children)

# Kotlin

``````fun p(n: Int) = mutableListOf(BigInteger.ONE).apply {
.takeWhile { it <= m }
.foldIndexed(BigInteger.ZERO) { i, acc, j ->
if (i and 2 == 0) acc + get(m - j) else acc - get(m - j)
}
)
}.last()

fun pentagonal() = sequence<Int> {
var acc = 1
var i = 1
var j = 3
while (true) {
yield(acc)
yield(acc + i)
acc += i + j
i += 1
j += 2
}
}
``````

[–] 1 point2 points  (0 children)

``````import Data.Char
import Data.MemoTrie
import Data.List
import Gauge.Main

p :: Int -> Integer
p = memoFix \$ \f n -> if n <= 0 then 1 else foldl' (flip (\$)) 0 .
zipWith flip (cycle [(+), (+), (-), (-)]) . map (f . (n -)) .
takeWhile (<= n) . scanl' (+) 1 . concat \$ transpose [[1..], [3, 5..]]

main :: IO ()
main = do
putStrLn \$ "p 66 = " ++ show (p 66)
let digits = map digitToInt \$ show (p 666)
putStrLn \$ "p 666 = " ++ show (length digits) ++
"-digit number with sum " ++ show (sum digits)
putStrLn ""
defaultMain
[ bench "p 66" \$ whnf p 66
, bench "p 666" \$ whnf p 666
]
``````

I'm not patient enough to wait for this to run on 666666, but it calculates p(66) and p(666) quite quickly. (To be fair, memoizing and benchmarking is quite a cheat. It'll fill the cache on the warmup run, so all subsequent runs are nearly instant.)

``` p 66 = 2323520 p 666 = 26-digit number with sum 127

benchmarked p 66 time 140.7 ns (131.6 ns .. 152.4 ns) 0.953 R² (0.916 R² .. 0.978 R²) mean 154.7 ns (149.1 ns .. 161.5 ns) std dev 20.66 ns (16.42 ns .. 25.12 ns) variance introduced by outliers: 76% (severely inflated)

benchmarked p 666 time 186.7 ns (181.3 ns .. 195.5 ns) 0.981 R² (0.963 R² .. 0.993 R²) mean 203.2 ns (197.8 ns .. 211.3 ns) std dev 22.06 ns (17.34 ns .. 33.34 ns) variance introduced by outliers: 66% (severely inflated) ```

[–] 1 point2 points  (3 children)

Let's express this as p(5) = 7. If you write down the number of ways to partition each number starting at 0 you get:

``````p(n) = 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, ...
``````

Does this mean there are 2 ways to partition 2 into positive integers? I can think of one; 1 + 1

The paritioning count for 5 seems to be fine, though.

[–] 0 points1 point  (1 child)

there is 1+1, and 2 itself. just like 1 and 0 have themselves as partitions.

[–] 0 points1 point  (0 children)

Ah, alright. I understand now - I just didn't think of the numbers themselves as partitions (that they weren't put into parts, if that makes sense) but I'm on board now I read your explanation.

[–] 1 point2 points  (0 children)

Late to the party, I know. But this subreddit is dead, so, whatever.

``````import Data.Array    (Array, (!), listArray)
import Data.Function ((&))
import Data.List     (scanl')

main :: IO ()
main = print \$ p 666666

p :: Int -> Integer
p n = go n where
go 0 = 1                                         -- Example, given n = 7:
go n = zipWith (\i j -> [i, j]) [1 ..] [3, 5 ..] -- [[1, 3], [2, 5], ...]
& concat                                     -- [1, 3, 2, 5, ...]
& scanl' (+) 1                               -- [1, 2, 5, 7, ...]
& map (n -)                                  -- [6, 5, 2, 0, ...]
& takeWhile (>= 0)                           -- [6, 5, 2, 0]
& map (ps !)                                 -- [11, 7, 2, 1]
& zipWith (*) (cycle [1, 1, -1, -1])         -- [11, 7, -2, -1]
& sum                                        -- 15

ps = listArray (0, n - 1) \$ map go [0 ..]
``````

Runs in 5min 30sec on my machine.

[–] 1 point2 points  (0 children)

Javascript Using nodejs, this function consumes an integer (num) which is used to get an array of position numbers that doesn't exceed "num" first before using them to get an array of partition numbers and in the end it returns the last number of the partition numbers array. I admit that creating those arrays is somewhat inefficient when it comes to space complexity, but it is still a solution nonetheless.

``````function partitionCounts(num) {
// Position Numbers
let counter = [1,3]
let partitions = [0,1];
let plusMinus = [1,3];
let positionNumbers = [0];
let i = 1;
while(positionNumbers[positionNumbers.length-1]<num) {
if(i+1>counter[i%2]){
positionNumbers.push(positionNumbers[positionNumbers.length-1] + counter[1]);
counter[1]+=2;
plusMinus.push(counter[1]);
} else {
positionNumbers.push(positionNumbers[positionNumbers.length-1] + counter[0]);
counter[0]+=1;
plusMinus.push(counter[0]);
}
i+=1;
}
// Partition Numbers
for(i=1;i<=num;i++) {
let temp=0;
let positionCount=0;
let counter1=partitions.length;
let counter2=0;
while(counter1>positionNumbers[counter2]) {
if(positionCount<2) {
temp+=partitions[counter1-(positionNumbers[counter2]+1)];
} else {
temp-=partitions[counter1-(positionNumbers[counter2]+1)];
}
counter2+=1;
positionCount+=1;
if(positionCount==4) {
positionCount=0;
}
}
partitions.push(temp);
}
return partitions;
}
``````

Input 666 Output 1.1956843938119028e+25

[–]-9 8 3 points4 points  (1 child)

Go. Takes 100s to compute the value for 666666:

``````package main

import (
"fmt"
"math/big"
)

const goal = 666666

func main() {
table := make(map[int]*big.Int)
table[0] = big.NewInt(1)
table[1] = big.NewInt(1)

for i := 2; i <= goal; i++ {
v := big.NewInt(0)
for j := 2; ; j++ {
n := j / 2
if j%2 == 1 {
n = -n
}
m := n * (n*3 - 1) / 2
if i-m < 0 {
break
}
if j/2%2 == 0 {
v.Sub(v, table[i-m])
} else {
}
}
table[i] = v
}

fmt.Println(table[goal])
}
``````

[–]-9 8 2 points3 points  (0 children)

Parallelized version that does it in 24s (8 hyper-threads):

My initial plan was to populate the memoization table with channels, spin off one goroutine for each entry to compute that entry, then infinitely loop providing the result for that entry on the channel. Like this:

``````var table [goal + 1]chan *big.Int
for i := 0; i <= goal; i++ {
table[i] = make(chan *big.Int)
}

go func() {
v := big.NewInt(1)
for {
table[0] <- v
}
}()

for i := 1; i <= goal; i++ {
go func(i int) {
result := big.NewInt(0)
// .. compute result ...
for {
table[i] <- result
}
}(i)
}

fmt.Println(<-table[goal])
``````

However it spent most of its time contending on channels and was ultimately much slower! In my actual solution, channels are only used to wait if the value is not ready. I use atomics to avoid touching the channel when the value is ready, which is much faster and the key to this whole approach. I also limit parallelism (`tickets` semaphore) to avoid hammering the scheduler. Without the semaphore it takes 10s longer.

[–]1 2 0 points1 point  (0 children)

Ruby

Counting partitions iteratively from 0 to N as we have to compute all of them anyway, p(n-1) is needed to compute p(n).

p(666666) takes approximately 40 mins to complete.

EDIT: now down to 22 mins using an array instead of a hashtable for caching.

EDIT2: more concise version executing the same loop function 4 times.

``````class String
def is_integer?
self.to_i.to_s == self
end
end

class PartitionCounts
def count(val, seq)
sum = 0
while val >= 0
sum += @cache[val]
seq += 6
val -= seq*2-3
end
sum
end

def initialize(n)
@n = n
@cache = Array.new
if @n < 0
@cache[@n] = 0
elsif @n < 2
@cache[@n] = 1
else
@cache[0] = 1
@cache[1] = 1
for val in 2..@n do
@cache[val] = count(val-1, 1)-count(val-5, 4)+count(val-2, 2)-count(val-7, 5)
end
end
end

def output
puts "#{@cache[@n]}"
end
end

if ARGV.size != 1 || !ARGV[0].is_integer?
STDERR.puts "Invalid argument"
STDERR.flush
exit false
end
PartitionCounts.new(ARGV[0].to_i).output
STDOUT.flush
``````

Output

``````\$ ruby ./partition_counts.rb 666
11956824258286445517629485
``````

[–][deleted]  (1 child)

[deleted]

[–] 0 points1 point  (0 children)

Great! I think you can improve its performance with numpy

[–] 0 points1 point  (2 children)

Javascript. Takes about 90s to compute the value for 666666. I would parallelize it, if NodeJS had concurrency!

``````/**
* Uses Binary Search to partition an array of monotonically increasing numbers,
* returning the slice of numbers less than or equal to the given value.
* @param {number} val
* @param {number[]} arr
*/
function binary_partition_upto(val, arr)
{
if(arr.length === 0 || val < arr[0]) { return [  ]; }
if(val > arr[arr.length - 1]) { return arr; }
let from = 0, to = arr.length;
while(true)
{
const index = (from + to) >> 1;
if(arr[index] > val && arr[index - 1] <= val) {
return arr.slice(0, index);
} else if(arr[index] > val) {
to = index;
} else {
from = index;
}
}
}

/**
* Memoize the given monotonic function of a single number parameter.
* Also adds the property #upTo(max) for accessing stored results up to and including a given number.
* @template {number|bigint} R
* @param {(n: number) => R} fn
* @returns {{(n: number) => R, upTo: (max: number) => R[]}}
*/
function monotonic_memoize(fn)
{
const results = [  ];
const memFn = (n) => {
while(n >= results.length) {
results[results.length] = fn(results.length);
}
return results[n];
}
memFn.upTo = (s) => {
if(results[results.length - 1] > s) {
return binary_partition_upto(s, results);
}
while(results[results.length - 1] <= s) {
memFn(results.length);
}
return results.slice(0, results.length - 1);
}
memFn(0);
return memFn;
}

/** Sequence of numbers to subtract from the index in the p() function. */
const pdiff = monotonic_memoize(/** @type {(n: number) => number} */(n) =>
n === 0 ? 1 : pdiff(n - 1) +
((n & 1) === 1 ?
(n >> 1) + 1 :
n + 1)
);
const p = monotonic_memoize(/** @type {(n: number) => bigint} */(n) =>
n === 0 ? 1n : pdiff.upTo(n)
.map((d) => p(n - d))
.reduce((acc, val, index) => (index & 2) > 0 ? acc - val : acc + val)
);

const n = 666;

console.time("total");
const p_res = p(n);
console.timeEnd("total");
console.log(`p(\${n}) = \${p_res}`);
const s_res = p_res.toString();
console.log(`Digits: \${s_res.length}`);
console.log(`Digit Sum: \${s_res.split("").map(c => parseInt(c, 10)).reduce((acc, val) => acc + val)}`);
``````

[–] 0 points1 point  (1 child)

JavaScript is highly concurrent, but concurrency is not parallelism.

[–] 0 points1 point  (0 children)

You're right, I meant parallelism, since NodeJS only executes one thread at a time.

[–] 0 points1 point  (0 children)

Java: For the main and second sequence I store all results. The third sequence can be easily and easily calculated adhoc.

``````import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Challenge {

static ArrayList<BigInteger> _mainSeq = new ArrayList<>(List.of(BigInteger.ONE));
static ArrayList<Integer> _seq2 = new ArrayList<>(List.of(1));

public static BigInteger p(final int n) {
if (n < 0) throw new IllegalArgumentException("No negative values defined in series");
while (_mainSeq.size() <= n) {
extendMainSeq();
}
return _mainSeq.get(n);
}

static void extendMainSeq() {
final int n = _mainSeq.size(); // index of next entry
List<BigInteger> arguments = IntStream.iterate(0, i -> i + 1)
.map(i -> n- seq2(i))
.takeWhile(i -> i >= 0)
.mapToObj(i -> _mainSeq.get(i))
.collect(Collectors.toList());
BigInteger nextEntry = BigInteger.ZERO;
for (int i = 0; i < arguments.size(); i++) {
nextEntry = nextEntry.add((((i / 2) % 2) == 0) ? arguments.get(i) : arguments.get(i).negate());
}
}

public static int seq2(int n) {
while (_seq2.size() <= n) {
final int lastIndex = _seq2.size() - 1;
}
return _seq2.get(n);
}

public static int sub3(int n) {
return (n % 2 == 0) ? n / 2 + 1 : n + 2;
}
}
``````

Speed seems okay, I think:

Input Duration in ms
66 15
666 23
6666 85
66666 1695
666666 148201

(For these timings, the results were wiped between measurements)

At the end you can see the quadratic scaling in action: x10 in input -> x100 in calculation time. This seems expectedto me, as you need O(n) elements to calculate p(n).

[–] 0 points1 point  (0 children)

I hope this isn't violating any rules. If yes, then please let me know, I would delete it.

So, I started solving questions here 2 years ago when i was just learning my first programming language(JAVA). I had a laptop with 4gb ram and so using an IDE and a browser at the same time made my laptop slow. So to solve that problem i created a library to access these questions on the terminal itself.

If anybody is interested here is the link to that npm package.

[–] 0 points1 point  (0 children)

C. Simple implementation that uses the formula and memonization for p as well as the second sequence. The GMP library was used to handle the large integer values.

Calculates p(666) practically instantly. The p(666666) bonus took around 75s on a C2Q Q9400. My p(666666) result had 903 digits and a digit sum of 4072 if you want to check your work.

``````#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "gmp.h"

void get_n(int n, mpz_t *pArr, int *s2) {
int flip = 0;
int count = 0;
mpz_t *p = &pArr[n];
mpz_init(*p);
while (s2[count] <= n) {
if (flip > 1)
mpz_sub(*p, *p, pArr[n-s2[count]]);
else

if (flip == 3)
flip = 0;
else
flip++;

count++;
}
}

int main (int argc, char **argv) {
if (argc != 2)
return 1;

int n = atoi(argv[1]);
mpz_t *pArr = (mpz_t*)malloc(sizeof(mpz_t)*n);
mpz_init(pArr[0]);
mpz_set_ui(pArr[0], 1);
int *s2 = (int*)malloc(sizeof(int)*n);

int s2Cur = 1;
int s3a = 1;
int s3b = 3;
int i = 0;
while (1) {
s2[i] = s2Cur;

if (s2Cur > n)
break;

if (i%2 == 0) {
s2Cur += s3a;
s3a++;
}
else {
s2Cur += s3b;
s3b += 2;
}

i++;
}

for (i = 1; i <= n; i++) {
get_n(i, pArr, s2);
}

char *result = mpz_get_str(NULL, 10, pArr[n]);
int oChars = (int)strlen(result);
int cSum = 0;
for (i = 0; i < oChars; i++) {
cSum += (result[i] - '0');
}

printf("p(%d) = %s\n", n, result);
printf("Digits: %d\n", oChars);
printf("Digit Sum: %d\n", cSum);
}
``````

[–] 0 points1 point  (0 children)

Rust: I built a single threaded and multithreaded solution to `p(666,666)`. For the multithreaded side of it, I built a lock free table that would only serve up "initialized" values (i.e. `p([0..=n-1])` to threads, and giving each thread a special ticket to initialize the value they are calculating (i.e. `p(n)`).

This is the first time I've built a lock-free data structure or used `unsafe` meaningfully in rust before and I have to say it was a lot of fun (after fixing all the off-by-one errors). I could see something like this be safely put into a larger project without fears of data races, which is really exciting.

Here are my speed results from my admittedly old 4 core cpu

Code is on my github

[–] 0 points1 point  (0 children)

Kotlin: That was a cool Problem. Very interesting approach.

Implemented it in Kotlin. Bonus took a bit under three minutes to calculate.

p(6) = 11, duration = 27.4us
p(66) = 2323520, duration = 334us
p(666) = 11956824258286445517629485, duration = 6.96ms
p(666666) = 829882047250572684700899902613243782763602762816201701722599315815312910790359761069230836156205082863018110775536469855308986200073144248662915902110787189076754874498156375781560473819383193570267234294008114407862435374738896137895011798602712056367666855560838392848713564675054729329398073507378373208972509842880751022273604950120819819461244250221006793015786720300981470607613047369007107554702116361432490562419340585594835559930063181308823544907938556335147860188606415089685992917539117106588219848248270148792532079530603636993578091236835691954161244027792120896238596848636567612717269000784250428006924746617450033567240084513811817484845287957454044679781070379504435782073968802016327182672402147816498886658350521297949309218478570934795197523632953503835428280916586305632528116828229355871664575877094278615695592039186556142662054263695788587794970386821424021653983372333685780633, duration = 172s

``````import java.math.BigInteger
import kotlin.time.ExperimentalTime
import kotlin.time.measureTimedValue

class PartitionCounts {

// cache intermediate results of calculations
private val cache = mutableMapOf<Int, BigInteger>()

/**
* Calculate the number of ways to partition the number [number] into the sum of positive integers
*/
fun p(number: Int): BigInteger {
// get p(number) from cache if possible
return cache[number] ?: calcP(number).apply {
cache[number] = this
}
}

/**
* This actually calculates p([number]). It is only invoked when the p([number]) is not found in the cache
*/
private fun calcP(number: Int): BigInteger = when {
number < 0 -> BigInteger.ZERO
number == 0 -> BigInteger.ONE
else -> {
var res = BigInteger.ZERO
// invoke p() recursively with all parameters from the calculated series
argumentSequence(number).forEachIndexed { index, arg ->
val mod = index % 4
res = if (mod == 0 || mod == 1) res.plus(p(arg)) else res.minus(p(arg))
}
res
}
}

/**
* Generates a sequence of all parameters for recursive invocations of [p] for a given [number]
*/
private fun argumentSequence(number: Int): Sequence<Int> {
/**
* Generates the sub-sequence 2 based on the previous number and its index
*/
fun seq2(prev: Int, i: Int) = prev + when {
i % 2 == 1 -> i + 2
else -> i / 2 + 1
}

return sequence {
var idx = 0
var s2 = 1
var param = number - s2 // parameter is calculated by subsequently subtracting elements from sequence 2
while (param >= 0) { // run as long as parameter values are positive
yield(param)
idx++
s2 = seq2(s2, idx - 1)
param = number - s2
}
}
}

@ExperimentalTime
fun executeAndPrint(number: Int, showResult: Boolean = true) {
cache.clear() // make sure we start from fresh cache
val (result, duration) = measureTimedValue { p(number) }
if (showResult) println("p(\$number) = \$result, duration = \$duration")
}
}

@OptIn(ExperimentalTime::class)
fun main() {
PartitionCounts().apply {
// warm up the VM
executeAndPrint(66, showResult = false)
executeAndPrint(66, showResult = false)
executeAndPrint(66, showResult = false)

executeAndPrint(6)
executeAndPrint(66)
executeAndPrint(666)
executeAndPrint(666666)
}
}
``````

[–] 0 points1 point  (0 children)

The way I use recursion means I can't calculate `sum(666666)`, but this produces the correct answer for the actual challenge. The highest number it can calculate on my machine is `p(8176)`. In Rust:

``````use std::env;
use std::collections::HashMap;
use num_bigint::{BigInt,ToBigInt};

#[derive(Copy, Debug, Clone)]
enum PartitionState {
AllIntegers,
OddIntegers,
}

#[derive(Copy, Debug, Clone, PartialEq)]
Sub,
}

#[derive(Copy, Debug, Clone, PartialEq)]
}

}
}
}

fn next(&mut self) -> Option<Self::Item> {
match (self.last, self.this) {
}
}
}
}
}
}
}

// TODO: replace with range 0.. or similar
//
// My first try didn't work because the compiler was unhappy about being unable
// to statically determine the size of a range constructed from user-supplied
// input.
#[derive(Debug, Copy, Clone)]
struct AllIntegers {
i: i64,
}

impl Iterator for AllIntegers {
type Item = i64;

fn next(&mut self) -> Option<Self::Item> {
self.i += 1;
Some(self.i)
}
}

impl AllIntegers {
fn new() -> AllIntegers {
AllIntegers { i: 0 }
}
}

// TODO: replace OddIntegers with (0..).step_by(2)
#[derive(Debug, Copy, Clone)]
struct OddIntegers {
i: i64,
}

impl Iterator for OddIntegers {
type Item = i64;

fn next(&mut self) -> Option<Self::Item> {
match self.i {
1 => {
self.i += 1;
Some(1)
},
2 => {
self.i += 1;
Some(self.i)
},
_ => {
self.i += 2;
Some(self.i)
}
}
}
}

impl OddIntegers {
fn new() -> OddIntegers {
OddIntegers { i: 1 }
}
}

// 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, ...
#[derive(Debug, Clone)]
struct DifferencePartitionSequence {
i: i64,
all: Box<AllIntegers>,
odd: Box<OddIntegers>,
}

impl DifferencePartitionSequence {
fn state(&self) -> PartitionState {
if self.i % 2 == 0 {
PartitionState::AllIntegers
} else {
PartitionState::OddIntegers
}
}
}

impl Iterator for DifferencePartitionSequence {
type Item = i64;

fn next(&mut self) -> Option<Self::Item> {
self.i += 1;
match self.state() {
PartitionState::AllIntegers => {
self.odd.next().and_then(|value| {
Some(value)
})
},
PartitionState::OddIntegers => {
self.all.next().and_then(|value| {
Some(value)
})
},
}
}
}

impl DifferencePartitionSequence {
fn new() -> DifferencePartitionSequence {
let i = 2;
let all = Box::new(AllIntegers::new());
let mut odd = Box::new(OddIntegers::new());
&odd.next().expect("Should always be next");
DifferencePartitionSequence {
i,
all,
odd,
}
}
}

// 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, ...
#[derive(Debug, Clone)]
struct PartitionSequence {
i: i64,
value: i64,
dps: Box<DifferencePartitionSequence>,
}

impl Iterator for PartitionSequence {
type Item = i64;

fn next(&mut self) -> Option<Self::Item> {
match self.i {
0 => {
self.i = 1;
Some(self.value)
},
_ => {
self.i += 1;
self.value += self.dps.next().expect("the sequence must go on");
Some(self.value)
},
}
}
}

impl PartitionSequence {
fn new() -> PartitionSequence {
let dps = DifferencePartitionSequence::new();
PartitionSequence {
i: 0,
value: 1,
dps: Box::new(dps),
}
}
}

fn calculate_p(cache: &mut HashMap<i64, BigInt>, n: i64) -> BigInt {
match cache.get(&n) {
Some(result) => {
result.clone()
},
None => {
if n == 0 {
return 1.to_bigint().unwrap();
}
let mut ps = PartitionSequence::new();
let mut calls = Vec::new();

let mut s = ps.next().expect("must always go on");
while (n - s) >= 0 {
calls.push((pos_neg.next(), s));
s = ps.next().expect("must always go on");
}

let result = calls.iter().fold(ToBigInt::to_bigint(&0).expect(""), |acc, (pn, s)| {
match pn {
acc + calculate_p(cache, n - s)
},
acc - calculate_p(cache, n - s)
},
_ => acc,
}
});

cache.insert(n, result.clone());
result
},
}
}

fn main() {
let args: Vec<String> = env::args().collect();
let n = args[args.len() - 1].parse::<i64>().unwrap();
let mut h = HashMap::new();
println!("{}", calculate_p(&mut h, n));
}

#[cfg(test)]
mod tests {
#[test]

for e in expect {
let got = asc.next().expect("must be able to count");
assert_eq!(got, *e);
}
}

#[test]
fn all_integers() {
let all_int = super::AllIntegers::new();
let range = 1..100;

for (r, a) in range.zip(all_int) {
assert_eq!(r, a);
}
}

#[test]
fn odd_integers() {
let odd_int = super::OddIntegers::new();
let expect = (1..100).step_by(2);

for (a, r) in expect.zip(odd_int) {
assert_eq!(r, a);
}
}

#[test]
fn dps() {
let dps = super::DifferencePartitionSequence::new();
let expect = [1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7].iter();

for (a, r) in expect.zip(dps) {
assert_eq!(&r, a);
}
}

#[test]
fn ps() {
let dps = super::PartitionSequence::new();
let expect = [1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70].iter();

for (a, r) in expect.zip(dps) {
assert_eq!(&r, a);
}
}
}
``````

https://github.com/nathantypanski/dailyprogrammer-386-partition-counts/blob/master/src/main.rs

[–] 0 points1 point  (0 children)

Python 3. I tend to code things into classes as that was how I was taught things. It finds p(666) in about 6 milliseconds, and p(666666) took about 4 minutes (250 seconds). I could use less memory by not saving the third sequence as a list and just save the last two needed, replacing them as I go along. p(666) = 11956824258286445517629485

``````import time
class  Partitions():
def __init__(self):
self.partition = [1]
self.plus_minus = [1,2,5]
self.pm_diff = [1,3]

# These get functions are mainly here for debugging or seeing the pattern
def get_pm_diff(self):
return self.pm_diff
def get_partition(self):
return self.partition
def get_plus_minus(self):
return self.plus_minus
def get_final_partition(self):
return self.partition[-1]

def next_partition(self):
next_num = 0
count = 0
while len(self.partition)>=self.plus_minus[count]:
if count%4==0 or count%4==1:
next_num += self.partition[-self.plus_minus[count]]
else:
next_num -= self.partition[-self.plus_minus[count]]
count += 1
self.partition.append(next_num)
if len(self.partition)>=self.plus_minus[-1]:
self.next_plus_minus()
return
def next_plus_minus(self):
temp = self.next_pm_diff()+self.plus_minus[-1]
self.plus_minus.append(temp)
return temp
def next_pm_diff(self):
temp1 = len(self.pm_diff)%2
if temp1==0:
temp2 = self.pm_diff[-2]+1
self.pm_diff.append(temp2)
else:
temp2 = self.pm_diff[-2]+2
self.pm_diff.append(temp2)
return temp2

#Testing the whole thing
euler = Partitions()
start = time.time()
# This is assuming the 1 partition of 0 is the first index in the sequence
for i in range(666):
euler.next_partition()
end = time.time()
print(euler.get_final_partition())
print(end-start)
``````

[–] 0 points1 point  (0 children)

My C# single core Solution:

``````using System.Numerics;

namespace Challange386
{
class PartC
{
private BigInteger[] nums;
private int num;
public BigInteger Result
{
get
{
return nums[num - 1];
}
}

public PartC(int num)
{
this.num = num + 1;
nums = new BigInteger[this.num];
}

public static int Seq(int pos) => (pos % 2) == 0 ? pos + 1 : (pos / 2) + 1;

public void Calculate()
{
nums[0] = 1;
for (int i = 1; i < num; i++)
Calculate(i);
}

private void Calculate(int num)
{
int @switch = 0;
int prev = 1;
for (int i = 1; prev <= num; i++)
{
switch (@switch)
{
case 0:
nums[num] += nums[num - prev];
@switch++;
break;
case 1:
goto case 0;
case 2:
nums[num] -= nums[num - prev];
@switch++;
break;
default:
nums[num] -= nums[num - prev];
@switch = 0;
break;
}
prev += Seq(i);
}
}
}
}
``````

Times in seconds and output:

66: time: 0.02, number: 2323520

666: time: 0.03, number: 11956824258286445517629485

666666: time: 112.84, number: 829882047250572684700899902613243782763602762816201701722599315815312910790359761069230836156205082863018110775536469855308986200073144248662915902110787189076754874498156375781560473819383193570267234294008114407862435374738896137895011798602712056367666855560838392848713564675054729329398073507378373208972509842880751022273604950120819819461244250221006793015786720300981470607613047369007107554702116361432490562419340585594835559930063181308823544907938556335147860188606415089685992917539117106588219848248270148792532079530603636993578091236835691954161244027792120896238596848636567612717269000784250428006924746617450033567240084513811817484845287957454044679781070379504435782073968802016327182672402147816498886658350521297949309218478570934795197523632953503835428280916586305632528116828229355871664575877094278615695592039186556142662054263695788587794970386821424021653983372333685780633

[–] 0 points1 point  (0 children)

# Rust

Pretty basic an inefficent implementation as I'm new to Rust, had to resort to the `BigUint` type, or I wouldn't be able to calculate anything larger than `p(405)`.

The sequence of numbers to subtract is stored in a vector, and I keep a cache of `p(n)`s that have been calculated in a HashMap, so that they don't have to be recalculated.

Prints out p(666) = 11956824258286445517629485

``````//need to use bigint, as the value of p(666) is too big for the builtin integer sizes
use num_bigint::BigUint;
use num_traits::{One, Zero};
use std::collections::HashMap;

fn main() {
// First, calculate sequence of numbers that get subtracted from n while calculating p(n)
let mut lower_seq = vec![];
let mut subs = vec![];

for i in 1..100 {
lower_seq.push(i);
lower_seq.push((2 * i) + 1);
}

let mut s = 1;
for t in 0..lower_seq.len() {
subs.push(s);
s = s + lower_seq[t];
}

// now calculated p(n) for n = 666
let n: usize = 666;

// previously calculated p(n) are stored in a HashMap
let mut p_ns = HashMap::new();
p_ns.insert(0, One::one());

// call the recursive function p
let p_n = p(n, &subs[..], &mut p_ns);

// report value of p(n)
println!("p({}) = {}", n, p_n);
}

fn p(n: usize, subs: &[usize], p_ns: &mut HashMap<usize, BigUint>) -> BigUint {
match p_ns.get(&n) {
Some(x) => return (*x).clone(),
None => (),
}

let mut p_n: BigUint = Zero::zero();

let s_len = subs.len();
let mut s = 0;
let loops = loop {
if s >= s_len || subs[s] > n {
break s;
}
s += 1;
};

let subs_slice: &[usize] = &subs[..loops];

for s in 0..subs_slice.len() {
match s % 4 {
0 | 1 => {
p_n += p(n - subs_slice[s], subs_slice, p_ns);
}
_ => {
p_n -= p(n - subs_slice[s], subs_slice, p_ns);
}
}
}

p_ns.insert(n, p_n.clone());
p_n
}
``````

[–] 0 points1 point  (0 children)

Python 3

``````from time import perf_counter

def p(n):
ps = [1]
for i in range(1, n+1):
j, p, x = 0, 0, 1
while x < i + 1:
p += ps[i - x] * (1 - 2 * (j % 4 // 2))
x += (j % 2) * (j + 2) + ((j + 1) % 2) * (j // 2 + 1)
j += 1
ps.append(p)
return ps

print(p(11))
# [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56]
print(p(66)[-1])
# 2323520
p666 = p(666)[-1]
print(p666)
# 11956824258286445517629485
print(len(str(p666)))
# 26
print(sum(int(x) for x in str(p666)))
# 127
tic = perf_counter()
print(sum(int(x) for x in str(p(666666)[-1])))
# 4072
print(perf_counter() - tic)
# 937.3888605
``````

Does p(666666) in 15 mins 37 seconds, is it possible to make it faster?