Find the largest number of distinct integers that sum to n

Question

The Task

Given an input positive integer n (from 1 to your language's limit, inclusively), return or output the maximum number of distinct positive integers that sum to n.

Test Cases

Let f define a valid function according to the task:

The sequence for f, starting at 1:

1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...

As a larger test case:

>>> f(1000000000) // Might not be feasible with brute-forcers
44720

Test Code

For any test cases not explicitly given, the output of your code should match the result of the following:

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
    }
}

Try it online!

Answer 1

05AB1E, 4 bytes

ÅTg<

Try it online!

Perfect tool for the job.

ÅT yields the list of Åll Triangular numbers up to and including N (unfortunately includes 0 too, otherwise it would be 3 bytes), g< gets the length and decrements it.

Answer 2

Jelly, 6 5 bytes

R+\»ċ

Try it online!

Somewhat efficient. This sequence increments at triangular numbers, so this just counts how many triangular numbers are smaller than n.

Explanation:

        # Main link
R       # Range, generate [1..n]
 +\     # Cumulative sum (returns the first n triangular numbers)
   »    # For each element, return the maximum of that element and 'n'
    ċ   # How many elements are 'n'? (implicit right argument is n)

Answer 3

Haskell, 26 bytes

-2 bytes thanks to H.PWiz.

(!!)$do x<-[0..];x<$[0..x]

Try it online!

This returns the nth element of the whole numbers where each i is replicated i + 1 times.

Answer 4

Brain-Flak, 36 bytes

<>(())({()<(({}())){<>({}[()])}>{}})

Try it online!

This uses the same structure as the standard division algorithm, except that the "divisor" is incremented every time it is read.

Answer 5

Pari/GP, 19 bytes

n->((8*n+1)^.5-1)\2

Try it online!

Answer 6

Brain-Flak, 82 bytes

Whitespace added for "Readability"

(())

{
    {}

    ((({})[[]]))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

}{}{}{}

([]<>)

Try it online!

Answer 7

Jelly, 7 bytes

×8‘½’:2

Try it online!

Jelly, 9 bytes

Ḥ+4ݤ½_.Ḟ

Try it online!

This is longer than Dennis’ and DJ’s, but this time on purpose. Very, very efficient.

Answer 8

R, 28 bytes

function(n)rep(1:n,1:n+1)[n]

Try it online!

Creates the vector of 1 repeated 2 times, 2 repeated 3 times, ..., n repeated n+1 times and takes the nth element. This will memory error either because 1:n is too large or because the repeated list with n*(n+1)/2 - 1 elements is too large.

R, 29 bytes

function(n)((8*n+1)^.5-1)%/%2

Try it online!

Computes the value directly, using the formula found in alephalpha's answer. This should run with no issues, apart from possibly numerical precision.

R, 30 bytes

function(n)sum(cumsum(1:n)<=n)

Try it online!

Counts the triangular numbers less than or equal to n. This'll possibly memory error if 1:n is large enough -- for instance, at 1e9 it throws Error: cannot allocate vector of size 3.7 Gb.

Answer 9

APL (Dyalog), 8 bytes

+/+\∘⍳<⊢

Try it online!

Answer 10

TI-Basic, 12 bytes

int(√(2Ans+1/4)-.5

Answer 11

JavaScript (Node.js), 18 bytes

x=>(x-~x)**.5-.5|0

Try it online!

Answer 12

Japt, 8 bytes

Closed formula solution.

*8Ä ¬É z

Try it

---

Explanation

Multiply by 8, add 1 (Ä), get the square root (¬), subtract 1 (É) and floor divide the result by 2 (z).

---

Alternative, 8 bytes

Port of DJMcMayhem's Jelly solution.

õ å+ è§U

Try it

Generate an array of integers (õ) from 1 to input, cumulatively reduce (å) by addition (+) and count (è) the elements that are less than or equal to (§) the input (U).

Answer 13

Befunge, 32 20 bytes

1+::1+*2/&#@0#.-`#1_

Try it online!

Answer 14

Brain-Flak, 70 56 48 bytes

{([(({}[({}())()])[()])]<>){<>({}())}{}<>{}}<>{}

Try it online!

Explanation

The main part of this is the following snippet that I've written:

([(({})[()])]<>){<>({}())}{}<>{}

This will do nothing if the TOS is positive and will switch stacks otherwise. It is super stack unclean but it works. Now the main part of the program subtracts increasingly large numbers from the input until the input is non-positive. We start the accumulator at 1 each time subtracting 1 more than the accumulator from the input.

({}[({}())()])

We can put that inside the snippet above

([(({}[({}())()])[()])]<>){<>({}())}{}<>{}

That is put in a loop so it executes until we switch stacks. Once the loop finishes we retrieve the accumulator by switching stacks and removing the junk.

Answer 15

Pyth, 7 bytes

lh{I#./

Try it online!

Filter-keep the integer partitions which are Invariant over deduplication, grab the head and obtain its length.

Validity proof

_{^{Not very rigorous nor well-worded.}}

Let A = a₁ + a₂ + ... + a_n and B = b₁ + b₂ + ... + b_m be two distinct partitions of the same integer N. We will assume that A is the longest unique partition. After we deduplicate B, that is, replace multiple occurrences of the same integer with only one of them, we know that the sum of B is less than N. But we also know that the function result is increasing (non-strictly), so we can deduce that the longest unique partition A always has at least the same amount of elements as the count of unique items in other partitions.

Answer 16

Triangularity, 49 bytes

....)....
...2)2...
..)1/)8..
.)1/)IE/.
@^)1_+/i.

Try it online!

How it works

Triangularity requires the code to have a triangular distribution of the dots. That is, the length of each row must be equal the number of rows multiplied by 2 and decremented, and each row must have (on each side) a number of dots equal to its position in the program (the bottom row is row 0, the one above it is row 1 and so forth). There are only a couple of commands, and any character other than those listed on the 'Wiki / Commands' page is treated as a no-op (extraneous dots don't make affect the program in any way, as long as the overall shape of the program stays rectangular).

Note that for two-argument commands, I've used a and b throughout the explanation. Keeping that in mind, let's see what the actual program does, after removing all the extraneous characters that make up for the padding:

)2)2)1/)8)1/)IE/@^)1_+/i | Input from STDIN and output to STDOUT.

)                        | Push a 0 onto the stack. Must precede integer literals.
 2                       | Push ToS * 10 + 2 (the literal 2, basically).
  )2                     | Again, push a 2 onto the stack. This can be replaced by D
                         | (duplicate), but then the padding would discard the saving.
    )1                   | Literal 1.
      /                  | Division. Push b / a (1 / 2).
       )8)1              | The literal 8 and the literal 1 (lots of these!).
           /             | Division. Push b / a (1 / 8).
            )IE          | Get the 0th input from STDIN and evaluate it.
               /         | Divide it by 1 / 8 (multiply by 8, but there isn't any
                         | operand for multiplication, and I'm not willing to add one).
                @        | Add 1 to the result.
                 ^       | Exponentiation. Here, it serves as a square too.
                  )1_+   | Decrement (add literal -1).
                      /  | Divide (by 2).
                       i | Cast to an integer.

An alternate solution, and shorter if padding would not be necessary:

....)....
...2)1...
../DD)I..
.E/)4)1/.
+^s_+i...

Try it online!

Answer 17

PowerShell 3.0, 45 bytes

[math]::Sqrt(2*$args[0]+.25)-.5-replace'\..*'

The math call hurt and PS's banker's rounding is the actual devil (hence needing regex to truncate to save a byte) but this seems pretty alright.

Answer 18

Java (JDK), 28 bytes

n->~-(int)Math.sqrt(8*n+1)/2

Try it online!

Because the example was really not well golfed :p

Credits

• -2 bytes thanks to Kevin Cruijssen

Answer 19

Jelly, 7 bytes

ŒPfŒṗṪL

Runs roughly in O(2ⁿ) time.

Try it online!

How it works

ŒPfŒṗṪL  Main link. Argument: n

ŒP       Powerset; yield all subarrays of [1, ..., n], sorted by length.
   Œṗ    Yield all integer partitions of n.
  f      Filter; keep subarrays that are partitions.
     Ṫ   Tail; extract the last result.
      L  Compute its length.

Answer 20

JavaScript (ES7), 22 19 bytes

n=>(8*n+1)**.5-1>>1

-3 bytes thank to ETHproductions.

---

Try it

o.innerText=(f=
n=>(8*n+1)**.5-1>>1
)(i.value=1000000000);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

---

Explanation

Multiply the input by 8 and add 1, raise that to the power of .5, giving us the square root, subtract 1 and bitshift the result right by 1.

Answer 21

Python 2/3, 32 bytes

Python implementation of the closed form formula

lambda n:int((sqrt(1+8*n)-1)//2)

The integer division //2 rounds towards zero, so no floor( ) required

Answer 22

Haskell, 28 bytes

Kinda boring, but it's quite shorter than the other Haskell solution and has a really nice pointfree expression. Unfortunately I couldn't get it any shorter without the type system getting in the way:

g x=floor$sqrt(2*x+0.25)-0.5

Try it online!

Pointfree, 33 bytes

ceiling.(-0.5+).sqrt.(0.25+).(2*)

Alternatively, 33 bytes

Same length as the pointfree version, but much more interesting.

g n=sum[1|x<-scanl1(+)[1..n],n>x]

Answer 23

Milky Way, 12 bytes

'8*1+g1-2/v!

Explanation

code         explanation       value

'            push input        n          
 8*          push 8, multiply  8n
   1+        add 1             8n+1
     g       square root       sqrt(8n+1)
      1-     subtract 1        sqrt(8n+1)-1
        2/   divide by 2       (sqrt(8n+1)-1)/2
          v  floor             floor((sqrt(8n+1)-1)/2)
           ! output

Answer 24

Pyt, 7 5 bytes

Đř△>Ʃ

Explanation:

                      Implicit input
Đř△                   Gets a list of the first N triangle numbers
   >                  Is N greater than each element in the list? (returns an array of True/False)
    Ʃ                 Sums the list (autoconverts booleans to ints)

---

Faster, but longer way

Pyt, 11 9 bytes

Đ2*√⌈ř△>Ʃ

Explanation:

Đ2*√⌈ř△           Gets a list of triangle numbers up to the ceiling(sqrt(2*N))-th
       >          Is N greater than each element of the list? (returns an array of True/False)
        Ʃ         Sums the array

---

Alternative way - port of Shaggy's answer

Pyt, 8 7 bytes

8*⁺√⁻2÷

Answer 25

J, 11 bytes

2&!inv<.@-*

Try it online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor

Answer 26

Whitespace, 111 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_integer_from_STDIN][T T   T   _Retrieve_input][S S S T    S S S N
_Push_8][T  S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][S S T   T   N
_Push_n=-1][N
S S N
_Create_Label_SQRT_LOOP][S S S T    N
_Push_1][T  S S S _Add][S N
S _Duplicate_n][S N
S _Duplicate_n][T   S S N
Multiply][S T   S S T   S N
_Copy_0-based_2nd_(the_input)][S S S T  N
_Push_1][T  S S S _Add][T   S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_SQRT_LOOP][S S S T   S N
_Push_2][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer_divide][T    N
S T _Print_integer]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs, and new-lines only).

Explanation in pseudo-code:

Uses the formula:

$$f_n = \left\lfloor\frac{\sqrt{8n + 1} - 1}{2}\right\rfloor$$

NOTE: Whitespace doesn't have a square-root builtin, so we have to do this manually.

Integer i = read STDIN as integer
i = i * 8 + 1
Integer n = -1
Start SQRT_LOOP:
  n = n + 1
  If(n*n < i+1):
    Go to next iteration of SQRT_LOOP
n = (n - 2) integer-divided by 2
Print n as integer to STDOUT

Answer 27

Vitsy, 16 bytes

2*14/+12/^12/-_N

Try it online!

Might as well add my own contribution to the mix. This is shorter than the partition iterations solution in Vitsy.

Answer 28

Oasis, 14 bytes

n8*1+1tm1%_b+0

Try it online!

How?

n8*1+           8n + 1
     1tm        sqrt
        1%_     integer?
           b+   add f(n-1)

             0  f(0) is 0

This is a recursive solution that increments the result when it encounters a triangular index, starting with 0 for the input 0.

Answer 29

Perl 5 -p, 19(++) bytes

$_=0|-.5+sqrt$_*2+1

Try it online!

Answer 30

Ruby, 27 bytes

Three for the price of one. I am disappointed that I can't go shorter.

->n{a=0;n-=a+=1while n>a;a}

->n{((8*n+1)**0.5-1).div 2}

->n{((n-~n)**0.5-0.5).to_i}

Try it online! (to select the function, add f= in front of it)