# Find the largest number of distinct integers that sum to n

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!

• Can it be 0-indexed? Jan 5, 2018 at 0:05
• @totallyhuman "it" being the answers? Because this isn't about a list... Jan 5, 2018 at 0:12
• @totallyhuman No. This is about the distinct partitions of specific numbers. Jan 5, 2018 at 0:14
• This is OEIS A003056. Jan 5, 2018 at 10:33
• I feel insignificant most every time I stumble into the codegolf stack. The answers and the comments are much more than humbling. The questions are usually interesting too but with his comment @JeppeStigNielsen just throws in the completed blueprints when we are still contemplating the floor area. Jan 6, 2018 at 21:25

# Pyke, 6 bytes

8*h,te


Try it here!

8      - Push literal 8.
*     - Multiply by the input.
h    - Increment.
,   - Square root.
t  - Decrement.
e - Floor halve.


# Swift, 41 bytes

import Foundation
{Int(sqrt(\$0*8+1)-1)/2}


Try it online!

# Pushy, 8 bytes

8*hrt2/#


Try it online!

Uses the closed formula (sqrt(8n + 1) - 1) / 2:

8*          \ Multiply by 8
h         \ Increment
r        \ Integer root
t       \ Decrement
2/     \ Floordiv by 2
#    \ Output


I thought I recognised this formula - it's the reverse of the function for a triangle number:

f(x) = (x + 1)(x / 2)
f-1(x) = (sqrt(8x+ 1) - 1) / 2


...which makes sense as we're counting integer sums.

L,ßR¬+A€<€!s


Try it online!

Because closed form solutions are boring

# Wolfram Language (Mathematica), 22 bytes

⌊√(1+8*#)/2-.5⌋&


Try it online!

c++,61

int f(int n){for(int i=1;;i){if(n<i) return i-1; else n-=i}}

• Consider adding a short explanation of your code (see the other answers for examples). Code-only answers like this tend to get flagged automatically as low quality. May 23, 2019 at 20:08

# Cubix, 16 bytes

.(@sI1-?s.O@s)W\


Try it online!

    . (
@ s
I 1 - ? s . O @
s ) W \ . . . .
. .
. .


Watch it run

• I1 set up the stack with n and 1 (incrementer)
• -? subtract the incrementer from n and test result
• if result 0 sO@, swap result with incrementer, output and halt
• if result negative s(O, swap result with incrementer, decrement, output and via a few commands, halt
• if result positive \s)W, redirect, swap result with incrementer, increment and redirect back into the subtract/test