18
\$\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!

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

37 Answers 37

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.

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

\$\endgroup\$
  • 3
    \$\begingroup\$ I can't help but ask what "succ" is \$\endgroup\$ – Addison Crump Jan 5 '18 at 0:13
  • \$\begingroup\$ Yeah, I know lol. succ stands for successor. \$\endgroup\$ – totallyhuman Jan 5 '18 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.

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

Pari/GP, 19 bytes

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

Try it online!

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

Brain-Flak, 82 bytes

Whitespace added for "Readability"

(())

{
    {}

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

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

}{}{}{}

([]<>)

Try it online!

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

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

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

APL (Dyalog), 8 bytes

+/+\∘⍳<⊢

Try it online!

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

TI-Basic, 12 bytes

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

JavaScript (Node.js), 18 bytes

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

Try it online!

\$\endgroup\$
  • \$\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 '18 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 '18 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 '18 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).

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

Befunge, 32 20 bytes

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

Try it online!

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

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

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

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 28 bytes "Because your code was really not well golfed" ;p \$\endgroup\$ – Kevin Cruijssen May 24 at 6:50
  • \$\begingroup\$ @KevinCruijssen Well, now it is! :o \$\endgroup\$ – Olivier Grégoire May 24 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.
\$\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.

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

\$\endgroup\$
  • 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 '18 at 11:15
  • \$\begingroup\$ 29 bytes \$\endgroup\$ – FlipTack Jan 5 '18 at 17:27
  • \$\begingroup\$ Yes, it needs the import to work, so that should be included in the byte count. \$\endgroup\$ – mbomb007 Jan 5 '18 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]
\$\endgroup\$
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
\$\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÷
\$\endgroup\$
1
\$\begingroup\$

J, 11 bytes

2&!inv<.@-*

Try it online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
\$\endgroup\$
  • \$\begingroup\$ I like that trick with * to produce 1 \$\endgroup\$ – Jonah Jun 2 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
\$\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.

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

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

Perl 5 -p, 19(++) bytes

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

Try it online!

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

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