20
\$\begingroup\$

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!

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Can it be 0-indexed? \$\endgroup\$
    – totallyhuman
    Jan 5, 2018 at 0:05
  • 1
    \$\begingroup\$ @totallyhuman "it" being the answers? Because this isn't about a list... \$\endgroup\$
    – Addison Crump
    Jan 5, 2018 at 0:12
  • 3
    \$\begingroup\$ @totallyhuman No. This is about the distinct partitions of specific numbers. \$\endgroup\$
    – Addison Crump
    Jan 5, 2018 at 0:14
  • 5
    \$\begingroup\$ This is OEIS A003056. \$\endgroup\$
    – Jeppe Stig Nielsen
    Jan 5, 2018 at 10:33
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – KalleMP
    Jan 6, 2018 at 21:25

37 Answers 37

Reset to default
1
2
9
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
8
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ In the explanation, you surely mean "how many numbers are smaller than or equal to n" \$\endgroup\$
    – Luis Mendo
    Jan 5, 2018 at 0:10
  • \$\begingroup\$ @LuisMendo See the new explanation. \$\endgroup\$
    – DJMcMayhem
    Jan 5, 2018 at 0:12
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • 3
    \$\begingroup\$ I can't help but ask what "succ" is \$\endgroup\$
    – Addison Crump
    Jan 5, 2018 at 0:13
  • \$\begingroup\$ Yeah, I know lol. succ stands for successor. \$\endgroup\$
    – totallyhuman
    Jan 5, 2018 at 0:14
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Pari/GP, 19 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Brain-Flak, 82 bytes

Whitespace added for "Readability"

(())

{
    {}

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

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

}{}{}{}

([]<>)

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Competition as always \$\endgroup\$
    – Wheat Wizard ♦
    Jan 5, 2018 at 18:40
  • 1
    \$\begingroup\$ Who'd've thought that combining two unreadable languages, Whitespace and Brain-Flak, could be considered "readable"! \$\endgroup\$
    – caird coinheringaahin g ♦
    Apr 2, 2018 at 2:02
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog), 8 bytes

+/+\∘⍳<⊢

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

TI-Basic, 12 bytes

int(√(2Ans+1/4)-.5
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 18 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Is this always correct? I'm not certain floor((sqrt(8x+4)-1)/2) (your formula) and floor((sqrt(8x+1)-1)/2) (correct formula) give the same result for every x. \$\endgroup\$
    – ETHproductions
    Jan 6, 2018 at 1:10
  • \$\begingroup\$ @ETHproductions I could bluff and say "yes", but I think the more honest answer is that you should try to develop your own hypothesis and figure out if / why it mirrors the same formula. I didn't come up with this approach by myself (I learned it from a different site) but I played around with it a bit. It's a very interesting approach and I don't want to dissect the frog so early. \$\endgroup\$
    – Unihedron
    Jan 6, 2018 at 13:32
  • \$\begingroup\$ Hmm. I'm not sure how to prove it directly, but I wrote a brute-forcer that does not find any failures under 100 million. \$\endgroup\$
    – ETHproductions
    Jan 7, 2018 at 2:24
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Befunge, 32 20 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
2
\$\begingroup\$

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 = a1 + a2 + ... + an and B = b1 + b2 + ... + bm 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.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 28 bytes "Because your code was really not well golfed" ;p \$\endgroup\$
    – Kevin Cruijssen
    May 24, 2019 at 6:50
  • \$\begingroup\$ @KevinCruijssen Well, now it is! :o \$\endgroup\$
    – Olivier Grégoire
    May 24, 2019 at 7:29
1
\$\begingroup\$

Jelly, 7 bytes

ŒPfŒṗṪL

Runs roughly in O(2n) 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.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Can you include an explanation? I haven't done Javascript in a while \$\endgroup\$
    – qqq
    Jan 5, 2018 at 1:45
  • \$\begingroup\$ How bout n=>(8*n+1)**.5-1>>1 to save 3 bytes? (haven't tested) \$\endgroup\$
    – ETHproductions
    Jan 5, 2018 at 2:56
  • \$\begingroup\$ I outgolfed this in JS: codegolf.stackexchange.com/a/152558/21830 \$\endgroup\$
    – Unihedron
    Jan 5, 2018 at 5:28
  • \$\begingroup\$ @ETHproductions - looks like that works, thanks. \$\endgroup\$
    – Shaggy
    Jan 5, 2018 at 9:59
  • \$\begingroup\$ @tfbninja, I'd have thought t fairly self-explanatory but explanation added. \$\endgroup\$
    – Shaggy
    Jan 5, 2018 at 9:59
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to PPCG! Does this need from math import sqrt to work? If so, it should be included in the bytecount. (In that case lambda n:int((math.sqrt(1+8*n)-1)//2) import math is a little shorter.) \$\endgroup\$
    – Steadybox
    Jan 5, 2018 at 11:15
  • \$\begingroup\$ 29 bytes \$\endgroup\$
    – FlipTack
    Jan 5, 2018 at 17:27
  • \$\begingroup\$ Yes, it needs the import to work, so that should be included in the byte count. \$\endgroup\$
    – mbomb007
    Jan 5, 2018 at 19:30
1
\$\begingroup\$

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]
Improve this answer
\$\endgroup\$
2
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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÷
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 11 bytes

2&!inv<.@-*

Try it online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I like that trick with * to produce 1 \$\endgroup\$
    – Jonah
    Jun 2, 2019 at 0:51
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -p, 19(++) bytes

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

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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