Sum of partition numbers

Question

The partition function:

In number theory, the partition function p(n) represents the number of possible partitions of a positive integer n into positive integers

For instance, p(4) = 5 because the integer 4 has five possible partitions:

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 3
• 2 + 2
• 4

Your task:

• Accept an input (let's call it n). It will be a positive integer.
• Find the sum of the partitions of the numbers from 1 to n and output it.

Example:

Given the input 5:

• p(1) = 1
• p(2) = 2
• p(3) = 3
• p(4) = 5
• p(5) = 7

Sum = 18

As this is code-golf, the shortest answer in bytes wins.

I'll add my attempt as an answer, but it can probably be golfed down a bit.

Answer 1

Prolog (SWI), 56 bytes

N+I+R:-I>N,R=0;N-I+I+Q,N+(I+1)+W,R is Q+W+1.
X+R:-X+1+R.

Try it online!

Using Arnauld's formula again.

-1 thanks to Jo King

Answer 2

JavaScript (ES6), 35 bytes

f=(n,i=1)=>i<=n&&f(n-i,i)-~f(n,i+1)

Try it online!

Recursive formula

The sum of the partitions of the numbers from \$1\$ to \$n\$ is given by \$f(n,1)\$ where:

$$f(n,i)=\begin{cases} 0&\text{if }i>n\\ f(n-i,i)+f(n,i+1)+1&\text{if }i\le n \end{cases}$$

Answer 3

Desmos, 75 bytes

f(N)=N+∑_{n=1}^N∑_{k=1}^{n^n}0^{(n-∑_{j=1}^njmod(floor(nk/n^j),n))^2}

It's times like this when I really wish Desmos supported recursion... a majority of the other answers are just using some super golfy recursive formula...

Try It On Desmos!

Try It On Desmos! - Prettified

---

Me when no Desmos Recursion 😔

Answer 4

Wolfram Language (Mathematica), 22 bytes

Tr@*PartitionsP@*Range

Try it online!

Answer 5

Python,  58 48  42 bytes

-6 thanks to Steffan!

f=lambda n,b=1:b<=n and f(n-b,b)-~f(n,b+1)

Try it online!

Answer 6

Python, ⁹⁷ 88 bytes

lambda n:sum(map(f,range(1,n+1)))
f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n//2+1))

(-9 thanks to 97.100.91.109)

Try it online!

Answer 7

Charcoal, 43 42 41 40 39 20 bytes

Ｆ⊕Ｎ⊞υＥ⮌υ⊕↨¹✂κλι¹ＩΣ⊟υ

Try it online! Link is to verbose version of code. Explanation: Vaguely based on @Arnauld's formula, but there's not much of it left.

Ｆ⊕Ｎ

Loop from 0 to n. (This part of the algorithm actually works for n=0, but it costs 1 byte to output the final result correctly.)

⊞υＥ⮌υ⊕↨¹✂κλι¹

Calculate the incremented sums of the upper right triangle of the reversed matrix so far and add that as the next row.

ＩΣ⊟υ

Output the sum of the last row.

Example:

For n=0 we don't have any thing so far so we just create an empty row. The final matrix conceptually looks like this:

 0 ...

For n=1 there is only one empty row so far so its sum is zero. This results in a row of [1], with the matrix now like this:

 0 0 ...
 1 0 ...

For n=2 there are two rows. For the second row we take the sum of all of the elements but for the first row we omit the first element. Incrementing results in [2, 1], with the matrix now like this:

 0 0 0 ...
 1 0 0 ...
 2 1 0 ...

For n=3 the triangle's rows are [2, 1, 0], [0, 0] and [0], giving incremented sums of [4, 1, 1], with the matrix now like this:

 0 0 0 0 ...
 1 0 0 0 ...
 2 1 0 0 ...
 4 1 1 0 ...

For n=4 the triangle's rows are [4, 1, 1, 0], [1, 0, 0], [0, 0] and [0], giving incremented sums of [7, 2, 1, 1], with the matrix now like this:

 0 0 0 0 0 ...
 1 0 0 0 0 ...
 2 1 0 0 0 ...
 4 1 1 0 0 ...
 7 2 1 1 0 ...

For n=5 the triangle's rows are [7, 2, 1, 1, 0], [1, 1, 0, 0], [0, 0, 0], [0, 0] and [0] with incremented sums of [12, 3, 1, 1, 1], with the matrix now like this:

 0 0 0 0 0 0 ...
 1 0 0 0 0 0 ...
 2 1 0 0 0 0 ...
 4 1 1 0 0 0 ...
 7 2 1 1 0 0 ...
12 3 1 1 1 0 ...

For n=6 the triangle's rows are [12, 3, 1, 1, 1, 0], [2, 1, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0], [0, 0] and [0] with incremented sums of [19, 5, 2, 1, 1, 1], with the matrix now like this:

 0 0 0 0 0 0 0 ...
 1 0 0 0 0 0 0 ...
 2 1 0 0 0 0 0 ...
 4 1 1 0 0 0 0 ...
 7 2 1 1 0 0 0 ...
12 3 1 1 1 0 0 ...
19 5 2 1 1 1 0 ...

The full row sums are the partition sums are desired. The first column is also A000070.

Answer 8

Haskell, 31 30 bytes

n!i|i>n=0|z<-n-i=1+z!i+n!(i+1)

Try it online!

Thanks to Arnauld for the formula from their answer.

-1 thanks to xnor.

Answer 9

Vyxal l, 4 bytes

vṄÞf

Try it Online!

Partitions of each number in the range 1...input, flatten one layer, l flag takes length of that.

Alternatively,

5 bytes

ƛṄL;∑

Try it Online!

3 bytes with s flag

Explained

ƛṄL;∑
ƛ  ;   # Over each number in the range [1, input]:
 ṄL    #   Get the number of partitions of that number
    ∑  # Take the sum of that list.

Answer 10

PARI/GP, 25 bytes

n->sum(i=1,n,numbpart(i))

Attempt This Online!

Answer 11

Jelly, 5 bytes

ŒṗL)S

Try it online!

---

Or

Œṗ€ẎL

Answer 12

C (gcc), ^{49 48} 35 bytes

i;f(n){n=i<n?i++,f(n)-~f(n-i--):0;}

Try it online!

Uses Arnauld's formula from his JavaScript answer.
Saved a byte thanks to Steffan!!!
Saved a whopping 13 bytes thanks to tsh!!!

Inputs positive integer \$n\$.
Returns the sum of partitions \$\displaystyle\sum\limits_{i=1}^n p(i)\$.

Answer 13

Regex 🐇 (RME / Perl / PCRE2 _^v10.35+ / Raku^:P5), _¹⁶ 11 bytes

(\1x*|^x+)+

Try it on replit.com - RegexMathEngine
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Attempt This Online! - PCRE2 v10.40+
Try it online! - Raku

Takes its input in unary, as the length of a string of xs. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

This simply enumerates all the partitions that add up to less than or equal to the input number. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary positive-sized partition on the first iteration, and adding an arbitrary nonnegative integer to the partition size on each iteration.

This differs conceptually from How many partitions do I have? in that the first iteration is forced to have positive size (to prevent p(0)=1 from being added to the total) and that there is no ending $ anchor.

                # tail = N = input number; no need to anchor, because the
                # following loop is forced to do at least one iteration,
                # and its first iteration has an anchor.
(               # \1 = the following:
    \1x*        # Previous value of \1, plus any arbitrary nonnegative integer,
                # if this is not the first iteration.
|           # or
    ^x+         # Any arbitrary positive integer, if this is the first iteration.
)+              # Iterate the above any positive number of times.

A more natural way for this function to work would be to sum p(0)...p(n), rather than p(1)...p(n). This would result in the 11 byte regex ((\1|^)x*)+, which returns a number 1 greater than the function asked for by this challenge.

Regex 🐇 (_{^{RME / Perl /}} PCRE), 20 bytes

((?=(\3|^x))(\2x*))+

Try it on replit.com - RegexMathEngine
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+

PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied between \2 and \3 using only forward-declared backreferences.

This would also make the regex compatible with Python^regex and Ruby, but they have no way of doing 🐇 output without source code modifications.

                      # tail = N = input number; no need to anchor, because the
                      # following loop is forced to do at least one iteration,
                      # and its first iteration has an anchor.
(
    (?=
        (             # \2 = the following:
            \3        # Previous value of \3, if \3 is set
        |         # or
            ^x        # 1, if on the first iteration
        )
    )
    (                 # \3 = the following, which is also subtracted from tail:
        \2x*          # \2 plus any arbitrary nonnegative integer
    )
)+                    # Iterate the above as many times as possible, minimum 1

Perl, _⁴¹ 36 bytes _{^{(full program)}}

1x<>~~/(\1.*|^.+)+(??{-++$i})/;say$i

Try it online!

Unlike all of my other Perl answers of this type so far, the regex in this one is not $-anchored at the end, so (??{++$i)) so no longer guaranteed not to match. It can in fact match if the regex hasn't reached the end of the string and $i is 1, 11, or any other number whose digits are all 1 in decimal. So a negative sign is added to the return value to guarantee that this "postponed" regular subexpression embedded code block will not match.

Alternative 36 bytes:

1x<>~~/(\1.*|^.+)+(??{-++$\})/;print

Try it online!

Perl -p, _³⁷ 32 bytes _{^{(full program)}}

1x$_~~/(\1.*|^.+)+(??{-++$\})/}{

Try it online!

Can only take one input (followed by EOF) per run. See Fibonacci function or sequence for an explanation.

Raku, 27 bytes^{SBCS _{(anonymous function)}}

{+m:ex:P5/(\1.*|^.+)+/}o¹x*

Try it online!

Answer 14

Scala, 58 bytes

Use the recursive formula proposed in @Arnauld's answer.

---

Try it online!

def f(n:Int,i:Int=1):Int=if(i>n)0 else f(n-i,i)+f(n,i+1)+1

Answer 15

PowerShell Core, 61 bytes

filter f{param($i=1)if($i-le$_){($_-$i|f $i)+($_|f($i+1))+1}}

Try it online!

A recursive filter, this is an implementation of Arnauld's javascript answer

Answer 16

05AB1E, 6 bytes

LÅœ€gO

Try it online.

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
 Ŝ     # Map each to a list of list of positive integers that sum to that value
   €g   # Get the length of each inner list
     O  # Sum those together
        # (after which the result is output implicitly)

Answer 17

Pyt, 3 bytes

řᵱƩ

Try it online!

ř           implicit input; řangify
 ᵱ          ᵱartition number of each element in the array
  Ʃ         Ʃum; implicit print

Answer 18

x86-64 machine code, 24 bytes

31 C0 89 F9 51 57 29 CF 76 06 E8 F5 FF FF FF F8 83 D8 FF 5F 59 E2 ED C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes n in EDI and returns a value in EAX.

In assembly:

f:
    xor eax, eax    # Set EAX to 0.
    mov ecx, edi    # Set ECX to n.
recursion:
            # Starting here will add to EAX the number of partitions of 1,...,n,
            #  but with the numbers within the partitions limited to ECX.
    push rcx        # Save RCX and RDI (the 64-bit registers containing ECX and EDI)
    push rdi        #  onto the stack.
    sub edi, ecx    # Subtract the limit value from n,
                    #  to try including that value in a partition.
    jbe skip        # Jump if the result is 0 or negative.
    call recursion  # Make a recursive call (if it is positive).
    clc             # Set CF to 0.
skip:
    sbb eax, -1     # Subtract -1+CF from EAX. This increases it by 1 if CF=0:
                    #  if the result of the earlier 'sub' was not negative,
                    #  which means the limit value on its own is a valid partition.
    pop rdi         # Restore RCX and RDI
    pop rcx         #  from the stack.
    loop recursion  # Subtract 1 from ECX, and jump back to repeat if it's nonzero.
    ret             # Return.