10
\$\begingroup\$

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 , the shortest answer in bytes wins.

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

\$\endgroup\$
3

16 Answers 16

6
\$\begingroup\$

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

\$\endgroup\$
0
4
\$\begingroup\$

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}$$

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 32 bytes: f=n=>i<n&&f(n,i++)-~f(n-i--);i=0 \$\endgroup\$
    – tsh
    Sep 5 at 3:40
4
\$\begingroup\$

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 😔

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 22 bytes

Tr@*PartitionsP@*Range

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ can't you just do f=lambda n,b=1:b<=n and f(n-b,b)-~f(n,b+1)? \$\endgroup\$
    – Steffan
    Sep 3 at 16:55
3
\$\begingroup\$

Python, 97 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!

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf! Something useful to know is that the general rules allow you to create a function which takes in the input and returns the output, meaning that you can shorten your code to 88 bytes. \$\endgroup\$ Sep 3 at 19:27
3
\$\begingroup\$

Charcoal, 43 42 41 40 39 20 bytes

F⊕N⊞υE⮌υ⊕↨¹✂κλι¹IΣ⊟υ

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.

F⊕N

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

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

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

IΣ⊟υ

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
2
\$\begingroup\$

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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Port jelly for four (vṄfL) \$\endgroup\$
    – emanresu A
    Sep 4 at 9:10
2
\$\begingroup\$

PARI/GP, 25 bytes

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

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 5 bytes

ŒṗL)S

Try it online!


Or

Œṗ€ẎL
\$\endgroup\$
2
\$\begingroup\$

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)\$.

\$\endgroup\$
4
  • \$\begingroup\$ you can do g(n-i)-~g(n,i+1) instead of g(n-i)+g(n,i+1)+1 \$\endgroup\$
    – Steffan
    Sep 3 at 17:40
  • \$\begingroup\$ @Steffan Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 3 at 20:44
  • \$\begingroup\$ 35 bytes: i;f(n){n=i<n?i++,f(n)-~f(n-i--):0;} \$\endgroup\$
    – tsh
    Sep 5 at 5:55
  • \$\begingroup\$ @tsh Awesome - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 5 at 12:08
2
\$\begingroup\$

Regex 🐇 (RME / Perl / PCRE2 v10.35+ / Raku:P5), 16 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 Pythonregex 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, 41 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, 37 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 bytesSBCS (anonymous function)

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.