# 11 = (1+2+3+4+5) - (1+2+3) + (6) - (4)

Given a positive integer N, your task is to return the number of steps required by the following algorithm to reach N:

1. Find the smallest triangular number Ti such that Ti ≥ N. Build the corresponding list L = [ 1, 2, ..., i ].

2. While the sum of the terms of L is greater than N, remove the first term from the list.

3. If the sum of the terms of L is now less than N, increment i and append it to the list. Go on with step #2.

We stop as soon as N is reached. Only the first step is systematically executed. Steps #2 and #3 may not be processed at all.

### Examples

Below is an example for N = 11:

So the expected output for N = 11 is 4.

Other examples:

• N = 5 - We start with T3 = 1 + 2 + 3 = 6, followed by 2 + 3 = 5. Expected output: 2.
• N = 10 - Only the first step is required because 10 is a triangular number: T4 = 1 + 2 + 3 + 4 = 10. Expected output: 1.

### First 100 values

Below are the results for 1 ≤ N ≤ 100:

  1,  2,  1,  4,  2,  1,  2, 10,  2,  1,  4,  2,  6,  2,  1, 22,  8,  2, 10,  2,
1,  2, 12,  6,  2,  4,  2,  1, 16,  2, 18, 50,  2,  6,  2,  1, 22,  6,  2,  4,
26,  2, 28,  2,  1,  8, 30, 16,  2,  6,  4,  2, 36,  2,  1,  2,  4, 12, 40,  2,
42, 14,  2,108,  2,  1, 46,  2,  6,  4, 50,  2, 52, 18,  2,  4,  2,  1, 56, 12,
2, 20, 60,  4,  2, 22, 10,  2, 66,  2,  1,  4, 10, 24,  2, 40, 72,  8,  2,  6


### Rules

• You may write either a full program or a function, that either prints or returns the result.
• You're required to process any N ≤ 65536 in less than one minute on mid-range hardware.
• Given enough time, your program/function should theoretically work for any value of N that is natively supported by your language. If it doesn't, please explain why in your answer.
• This is code golf, so the shortest answer in bytes wins!
• Related. (I suspect you already know about this one, but just posting it for posterity) May 13, 2017 at 22:37
• What is the maximum value of N we need to handle?
– Luke
May 13, 2017 at 22:52
• @Luke Please see the updated rules. May 13, 2017 at 23:05
• Do you accept unary output? Nov 27, 2020 at 14:47
• @Titus This is a bit disputed, but I'll stick to the current consensus on that one. Nov 27, 2020 at 15:33

## Mathematica, 79 bytes

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&


### Explanation

I couldn't be bothered to implement the algorithm in the challenge, so I wanted to look for a shortcut to the solution. While I found one, unfortunately it doesn't beat the Mathematica answer that does implement the algorithm. That said, I'm sure this isn't optimally golfed yet, and there might be other languages who can benefit from this approach or some of the insights gained in the process.

So I claim that the sequence we're supposed to compute is:

f(n) = 2*(A212652(n) - A002024(n)) + 1 + A023532(n-1)

Alternatively, it's f(n) = 1 if n is a triangular number and f(n) = 2*(A212652(n) - A002024(n) + 1) otherwise.

In the first expression, A023532 simply encodes these two different cases. The other two sequences (plus 1) are the difference between the the largest integer k in the longest decomposition of n into consecutive integers (k-i+1) + (k-i+2) + ... + k = n and the largest integer j so that 1 + 2 + ... + j < n.

In somewhat simpler words, here is how we find the answer for non-triangular numbers: first, find the largest triangular number Tj which is less than n. Then j is the penultimate integer that gets added during step 1 (because after adding j+1 we will have exceeded n). Then decompose n into as many (or as small) consecutive integers as possible and call the maximum among these numbers k. The result is simply 2*(k-j). The intuitive reason for this is that the maximum in the decomposition grows by 1 every other step and we stop when we reach k.

We need to show four things to prove that this works:

1. f(n) = 1 for triangular numbers. This is trivially the case, because the first step simply iterates through all triangular numbers. If we hit n exactly during this process we're done and there was only one step to compute.
2. For all other numbers, we always end after a deletion step, never after an insertion step. That means all other f(n) are even.
3. In each insertion step after the first, we only add a single number. This guarantees that we'll reach a decomposition including k after k-j pairs of steps.
4. The final decomposition of n that we obtain is always the longest possible decomposition of n into consecutive integers, or in other words, it's always the decomposition of n with the lowest maximum among the summed numbers. In other words, the last number we add to the sum is always A212652(n).

We've already shown why (1) is true. Next, we prove that we can't end on an insertion step except the initial one (which doesn't happen for non-triangular numbers).

Suppose we ended on an insertion step, reaching n after adding a value p to the sum. That means that before this insertion step, the value was n-p (or less if we added multiple values at once). But this insertion step was preceded by a deletion step (since we couldn't have hit n during step 1). The last value q we removed during this deletion step was necessarily less than p due to the way the algorithm works. But that means before we removed q we had n-p+q (or less) which is less than n. But that's a contradiction, because we would have had to stop removing integers when we hit n-p+q instead of removing another q. This proves point (2) above. So now we know that we always end on a deletion step and that therefore all non-triangular numbers have even outputs.

Next we prove (3), that each insertion step can only insert one value. This is essentially a corollary of (2). We have shown that after adding one value we cannot hit n exactly and since the prove was using an inequality, we also cannot end up below n (since then n-p+q would still be less than n and we shouldn't have removed that many values in the first place). So whenever we add a single value, we're guaranteed to exceed n because we went below n by removing a smaller value. Hence, we know that the upper end of the sum grows by 1 every other step. We know the initial value of this upper end (it's the smallest m such that Tm > n). Now we just need to figure out this upper end once we've reached the final sum. Then the number of steps is simply twice the difference (plus 1).

To do this, we prove (4), that the final sum is always the decomposition of n into as many integers as possible, or the decomposition where the maximum in that decomposition is minimal (i.e. it's the earliest possible decomposition). We'll again do this by contradiction (the wording in this part could be a bit more rigorous, but I've already spent way too much time on this...).

Say the earliest/longest possible decomposition of n is some a + (a+1) + ... (b-1) + b, a ≤ b, and say the algorithm skips it. That means at the time that b gets added, a must no longer be part of the sum. If a was part of the sum s, then we'd have n ≤ s at that moment. So either the sum only contains the values from a to b, which equals n and we stop (hence we didn't skip this decomposition), or there is at least one value less than a in the sum, win which case n < s and that value would get removed until we hit the exact sum (again, the decomposition wasn't skipped). So we'd have to get rid of a before adding b. But that means we'd have to reach a situation in which a is the smallest component of the sum, and the largest isn't b yet. However, at that point we can't remove a, because the sum is clearly less than n (since b is missing), so we're required to add values first until we add b and hit n exactly. This proves (4).

So taking these things together: we know that the first pair of steps gives us a maximum value of A002024(n). We know that the maximum value of the final decomposition is A212652(n). And we know that this maximum is incremented once in every pair of steps. Hence, the final expression is 2*(A212652(n) - A002024(n) + 1). This formula almost works for triangular numbers, except that for those we only need 1 step instead of 2, which is why we correct the result with the indicator function of the triangular numbers (or its inverse, whichever is more convenient).

Finally, as for the implementation. For the former sequence, I'm using the formula MIN(odd d|n; n/d + (d-1)/2) from OEIS. It turns out to save a few bytes if we take the factor of 2 into this expression to get MIN(odd d|n; 2n/d + d-1), because that -1 then cancels with the +1 in my first version of f(n) which directly encodes the two cases for triangular and non-triangular numbers. In the code, this is:

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]


For the latter sequence (1, 2, 2, 3, 3, 3, ...), we can use a simple closed form:

⌊(2#)^.5+.5⌋


And finally, the inverse indicator function of the triangular numbers is 0 whenever 8n+1 is a perfect square. This can be expressed in Mathematica as

⌈Sqrt[8#+1]~Mod~1⌉


There are a lot of ways to express these last two sequences and to shift some constant offset between them, so I'm sure this is not an optimal implementation yet, but I hope this might give others a starting point to look into new approaches in their own languages.

Since I went to all this trouble, here is a plot of the sequence up to n = 1000 (I could also compute 100k in a couple of seconds, but it doesn't really show any additional insights):

It might be interesting to look into the variations about those very straight lines, but I'll leave that to someone else...

• I finally took the time to read your answer thoroughly. This is brilliant. Note that (3) was already assumed in the algorithm (step #3 is a if, not a while), but the proof is -- of course -- much welcomed. May 16, 2017 at 10:20
• @Arnauld Thank you. :) I must have overlooked/misunderstood the if/while part. Good thing it doesn't make a difference then. May 16, 2017 at 10:55

# Jelly, 29 31 28 bytes

-3 thanks to caird coinheringaahing (save a $, use the newer Ä, and use the newer Ƒ) ÆDµ’H+ṚḞƑƇṂ >TḢ_@Ç}‘Ḥ RÄðċȯç  A monadic link that returns the result (N=65536 takes less than two seconds). Try it online! ### How? For a thorough explanation of the algorithm see the fantastic post by Martin Ender. ÆDµ’H+ṚḞƑƇṂ - Link 1, smallest natural number, M, that satisfies the below*, N - * N = T(M) - T(i) for some non-negative integer i <= M ÆD - divisors of N µ - monadic chain separation, call that d ’ - increment d (vectorises) H - halve (vectorises Ṛ - reverse d + - add (vectorises) Ƈ - filter keep if: Ƒ - is invariant under: Ḟ - floor (i.e. those which are the result of even divisors) Ṃ - minimum >TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N > - T(i) > N T - truthy indexes Ḣ - head (yields the first i for which T(i) > N) Ç} - call last link (1) as a monad converted to a dyad using the right argument _@ - subtract with reverse @rguments ‘ - increment Ḥ - double RÄðċȯç - Main link: N R - range -> [1,2,...,N] Ä - reduce with addition -> [1,3,6,10,...T(N)] ð - dyadic chain separation, call that t ċ - count occurrences of N in t (1 if N is triangular else 0) ç - call last link (2) as a dyad(t, N) ȯ - or  The 29 byte full-program implementation I created of the algorithm described takes 4 min 30 for N=65536 on my laptop, so I suppose it does not count. Ṁ‘ṭµS<³µ¿ ḊµS>³µ¿ 0®Ḃ‘©¤ĿÐĿL’  • 29 bytes Nov 16, 2020 at 11:33 • Nice save of $, thanks! Nov 16, 2020 at 17:30
• 28 bytes Nov 17, 2020 at 18:52
• @cairdcoinheringaahing Thanks. Nov 18, 2020 at 17:37

# Mathematica, 72 bytes

(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&


Pure function taking an integer argument.

## How it works

For[ ... ]


A For loop.

l=u=c=k=0


Initialization; set l (lower), u (upper), c (counter), and k (sum) to 0.

k!=#


Condition; repeat while k is not equal to the input.

c++


Increment; increment the counter c.

If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]


Body

If[#>k, ... ]


If the input is greater than k:

While[#>k,k+=++u]


While the input is greater than k, increment u and increment k by u.

If the input is not greater than k:

While[#<k,k-=l++]


While the input is less than k, decrement k by l and increment l.

( ... ;c)


Return c after the loop.

• For[,...] beats While[...]. May 15, 2017 at 9:57

# Python 2, 104 bytes

N=input();i=s=0;l=()
while N!=sum(l):exec'while sum(l)'+['<N:i+=1;l+=i,','>N:l=l[1:]'][s%2];s+=1
print s


Try it online!

Alternates between adding terms to the end of the list, and removing terms from the beginning.

# PHP>=7.0, 74 Bytes

while($i=$r<=>$argn)for($s++;($r<=>$argn)==$i;)$r+=$i+1?-++$y:++$x;echo$s;


use the spaceship operator

Try it online!

Expanded

while($i=$r<=>$argn) # if input is not equal sum of array for($s++;  # raise count steps
($r<=>$argn)==$i;) # so long as value compare to input has not change to lower/higher to higher/lower or equal$r+=$i+1 ?-++$y # if $i was higher remove the first integer :++$x;} # if $i was lower add the next highest integer echo$s; # Output steps

echo$x; # print step counter  uses the spaceship operator <=> (introduced in PHP 7.0) and variable variables (introduced in PHP/FI). Thanks @Jörg for reminding me of the spaceship. Without the parentheses around the spaceship in the post condition, PHP wouldn not know what comparison to evaluate first (and throw a syntax error). ## PHP 7 (unary output), 53 bytes for(;$d=$argn<=>$s;print$d!=($argn<=>$s))$s+=d+=$d;  # 05AB1E, 28 27 bytes ÅTθÊiÑÂ<;+ʒ.ï}ßI·t2z+ï->·ë1  Port of @JonathanAllan's Jelly answer, which is using @MartinEnder's Mathematica formula, so make sure to upvote both of them! Try it online or verify the first 100 test cases. (NOTE: The .ï has been replaced with DïQ in the TIOs, because this .ï bug on floating values, which was fixed on October 23rd, hasn't been pushed to TIO yet.) Explanation: ÅT # Push a list of triangular numbers smaller than or equal to the # (implicit) input-integer θ # Pop and only leave the last value in this list Êi # If it's NOT equal to the (implicit) input, so the input isn't a # triangular number: Ñ # Get all divisors of the (implicit) input Â # Bifurcate this list (short for Duplicate & Reverse copy) < # Decrease each by 1 in the reversed list ; # Then halve each + # And add the values at the same positions in the lists together ʒ # Filter it by: .ï # Where the decimal value is an integer }ß # After the filter: pop and leave the minimum I· # Push the input again and double it t # Take the square-root of this 2z+ # Add 1/2 to it ï # Floor it to an integer - # Subtract it from the earlier minimum > # Increase it by 1 · # Double it ë # Else (the input is a triangular number): 1 # Simply push a 1 # (after which the top of the stack is output implicitly as result)  # Perl 6, 114 bytes {((0,0,1),->(\a,\b,\c){b,(a..*).first(->\d{(d,b).minmax.sum*c>=$_*c}),-c}...->(\a,\b,\c){(a,b).minmax.sum==$_})-1}  (inspired by an earlier Haskell implementation) Try it It runs with an input of 65536 in under 45 seconds on my computer, but I have been unable to get it to run in under 60 seconds with TIO.run. I have Rakudo v2017.04+ , where it has v2017.01. Rakudo/NQP/MoarVM gets optimizations almost daily, so there could be any number of them from the interim that are needed to get it in under time. ## Expanded { ( # generate a sequence (0,0,1), # initial value -> (\a,\b,\c) { b, # swap the first two values (a..*) .first( # find the first number that brings us to or past the input -> \d { (d,b).minmax # get a Range object regardless of which is larger .sum * c # sum it, and negate it every other time >= # is it equal to or greater than$_ * c       # negate the original input every other time
}

),

-c               # invert for next round
}

...                # keep doing that until

-> (\a,\b,\c) {
(a,b).minmax.sum == \$_ # it finally reaches the input
}

) - 1 # count the number of elements in the sequence
# and subtract one for the initializer
}


Note that Rakudo has an optimization for Range.sum so that it doesn't have to iterate through all of the values.

# Husk, 32 bytes

→L↑o≠⁰Σ¡?oḟo≤⁰ΣṫS:o→→o>⁰Σḟo>⁰ΣḣN


Try it online!

Not that this will not run in 1 minute for n-65536, hence it cannot compete.

However, it can theoretically calculate for any given n.

# Jelly, 26 bytes

S>³
RÄ<i0RḊÇ¿Ṃ;‘ƊÇ?S⁻³ƊÐ¿L


Try it online!

Full program only, because ¿ handles dyads in an... interesting way.

Directly implements the given algorithm.

S>³                       Monadic helper link:
S                         the sum of the argument,
>                        is it greater than
³                       the input (to the entire program)?

Ä                        cumulative sums of
R                         [1 .. input],
i0                     first index of 0 in
<                       whether or not each sum is less than the input,
R                    starting with [1 .. that index]:
¿     while
S⁻³Ɗ       the sum is not equal to the input,
?           if
Ç            (helper link) the sum is greater than the input,
Ḋ                   then remove the first element
Ç¿                 while the sum is greater than the input,
;   ?           else concatenate
Ṃ                the smallest element to
‘Ɗ             the list incremented.
Ð¿L    Output the number of iterations this took.


I haven't finished verifying execution times, but specifically for N = 65536 TIO takes 9 seconds while my computer takes 15.

EDIT: My machine seems to have taken more than a minute for N = 32924, 32933, and 32941. TIO computes each result in less than 5 seconds, however, so I suspect this may be because the lid of my laptop was closed for eight hours.

N = 45596 also just now took a minute and 9 seconds, but this also coincided with my laptop going to sleep, and TIO takes less than 2 seconds for it.