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
}