27
\$\begingroup\$

Before anyone says anything, similar and similar. But this is not a dupe.


Some positive integers can be written as the sum of at least two consecutive positive integers. For example, 9=2+3+4=4+5. Write a function that takes a positive integer as its input and prints as its output the longest sequence of increasing consecutive positive integers that sum to it (any format is acceptable, though -5 bytes if the output is the increasing sequence separated by + as shown above. If there exists no such sequence, then the number itself should be printed.

This is code golf. Standard rules apply. Shortest code in bytes wins.


Samples (note that formatting varies)

Input:   9
Output:  2,3,4

Input:   8
Output:  8

Input:   25
Output:  [3,4,5,6,7]
\$\endgroup\$
  • 2
    \$\begingroup\$ Do the numbers outputted have to be in a specific order (like increasing)? \$\endgroup\$ – xnor Dec 10 '15 at 4:13
  • 2
    \$\begingroup\$ Do the numbers have to be >0 : 6=0+1+2+3 or 6=1+2+3 \$\endgroup\$ – Damien Dec 10 '15 at 7:51
  • 5
    \$\begingroup\$ As a side note, if there are closely related challenges, saying "this is not a dupe" will do little to convince people of that if they do think it's a dupe. It would be more helpful if you explained why you think it isn't. \$\endgroup\$ – Martin Ender Dec 10 '15 at 8:01
  • 1
    \$\begingroup\$ @Damien "positive" normally means >0. If 0 was included, it would be called "non-negative". \$\endgroup\$ – Martin Ender Dec 10 '15 at 9:42
  • 3
    \$\begingroup\$ cc @Vixen ^ (also if negative numbers were allowed, the optimal solution would always be the range from -n+1 to n) \$\endgroup\$ – Martin Ender Dec 10 '15 at 9:43

18 Answers 18

11
\$\begingroup\$

Python, 67 bytes

f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+1],R[1:]][sum(R)>n])or R

An oddly straightforward strategy: search for the interval R with the right sum.

  • If the sum is too small, shift the right endpoint of the interval up one by appending the next highest number.
  • If the sum is too large, shift up the left endpoint by removing the smallest element
  • If the sum is correct, output R.

Since the bottom end of the interval only increases, longer intervals are found before shorter ones.

\$\endgroup\$
  • \$\begingroup\$ Oddly efficient as well. The recursion stack does eventually overflow, e.g. n=8192. \$\endgroup\$ – primo Dec 10 '15 at 6:34
7
\$\begingroup\$

Pyth, 12 10 bytes

j\+hfqsTQ}M^SQ2

The code is 15 bytes long and qualifies for the -5 bytes bonus. Try it online in the Pyth Compiler.

Thanks to @Jakube for golfing off 2 bytes!

How it works

j\+hfqsTQ}M^SQ2    (implicit) Store evaluated input in Q.

            S      Compute [1, ..., Q].
           ^  2    Get all pairs of elements of [1, ..., Q].
         }M        Reduce each pair by inclusive range. Maps [a, b] to [a, ..., b].
    f              Filter; for each pair T:
      sT             Add the integers in T.
     q  Q            Check if the sum equals Q.
                   Keep the pair if it does.
   h               Retrieve the first match.
                   Since the ranges [a, ..., b] are sorted by the value of a,
                   the first will be the longest, in ascending order.
j\+                Join, using '+' as separator.
\$\endgroup\$
  • 1
    \$\begingroup\$ For those of us not enlightened in the area of Pyth, could you add an explanation please? :) \$\endgroup\$ – ETHproductions Dec 10 '15 at 4:15
  • \$\begingroup\$ I've edited my answer. \$\endgroup\$ – Dennis Dec 10 '15 at 4:48
  • \$\begingroup\$ Awesome, thanks! I like your technique. \$\endgroup\$ – ETHproductions Dec 10 '15 at 5:04
  • 1
    \$\begingroup\$ Input 1000: 30 minutes and counting... \$\endgroup\$ – primo Dec 10 '15 at 5:58
3
\$\begingroup\$

Mathematica, 73 68 65 56 43 bytes

Cases[Range~Array~{#,#},i_/;Tr@i==#,{2},1]&
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 I ended up with a similar solution last night, but my internet went down. Also you can make Tuples an infix expression. \$\endgroup\$ – LegionMammal978 Dec 10 '15 at 11:23
3
\$\begingroup\$

Haskell, 49 48 bytes

f n=[[a..b]|a<-[1..n],b<-[a..n],sum[a..b]==n]!!0
\$\endgroup\$
  • 1
    \$\begingroup\$ 1 byte to save: use [...]!!0 instead of head[...]. \$\endgroup\$ – nimi Dec 10 '15 at 18:05
2
\$\begingroup\$

MATLAB, 87 79 bytes

I know there is already a MATLAB answer, but this one is significantly different in approach.

x=input('');m=1:x;n=.5-m/2+x./m;l=max(find(~mod(n(n>0),1)));disp(m(1:l)+n(l)-1)

This also works on Octave. You can try online here. I've already added the code to consecutiveSum.m in the linked workspace, so just enter consecutiveSum at the command prompt, then enter the value (e.g. 25).

I am still working on reducing it down (perhaps adjusting the equation used a bit), but basically it finds the largest value n for which m is an integer, then displays the first m numbers starting with n.

So why does this work? Well basically there is a mathematical equation governing all those numbers. If you consider that they are all consecutive, and start from some point, you can basically say:

n+(n+1)+(n+2)+(n+3)+...+(n+p)=x

Now, from this it becomes apparent that the sequence is basically just the first p triangle numbers (including the 0'th), added to p+1 lots of n. Now if we let m=p+1, we can say:

m*(n+(m-1)/2)==x

This is actually quite solvable. I am still looking for the shortest code way of doing it, I have some ideas to try and reduce the above code.


For an input of 25, the output would be:

3     4     5     6     7
\$\endgroup\$
  • 2
    \$\begingroup\$ With regards to your point about the triangle numbers, this challenge is essentially trying to find triangular numbers with a positive difference of the input such that the indices of the triangular numbers in the sequence 1,3,6,10,... is maximized. \$\endgroup\$ – Arcturus Dec 10 '15 at 15:55
1
\$\begingroup\$

Python 2, 94 bytes

n=input()
r=int((2*n)**.5)
while r:
 if~r%2*r/2==n%r:print range(n/r-~-r/2,n/r-~r/2);r=1
 r-=1

Input is taken from stdin. This solution is suitable for very large inputs.

This iterates over the possible solution lengths, r, having r ≤ √(2n), and checks for a solution explicitly. In order for a solution to exist, if r is odd, n mod r must be zero, and if r is even, n mod r must be r/2.


Sample Usage

$ echo 8192 | python sum-con-int.py
[8192]

$ echo 1000002 | python sum-con-int.py
[83328, 83329, 83330, 83331, 83332, 83333, 83334, 83335, 83336, 83337, 83338, 83339]

$ echo 1000000006 | python sum-con-int.py
[250000000, 250000001, 250000002, 250000003]

I've deliberately choosen examples with relatively small outputs.

\$\endgroup\$
1
\$\begingroup\$

Octave, 89 Bytes

This is the best I could do in Octave. The algorithm is the same as xnor's.

x=input('');k=i=1;while x;s=sum(k:i);if s<x;i++;elseif s>x;k++;else;x=0;end;end;disp(k:1)

In MATLAB this would be 95 bytes:

x=input('');k=1;i=1;while x;s=sum(k:i);if s<x;i=i+1;elseif s>x;k=k+1;else x=0;end;end;disp(k:i)

In MATLAB this runs in approx 0.1 seconds for input 2000000 and 1 second for input 1000002.

\$\endgroup\$
1
\$\begingroup\$

awk, 51 bytes

{while($0!=s+=s<$0?++j:-++i);while(++i-j)r=r i"+"}$0=r j

The code is 56 bytes, minus 5 bytes for the output format. I had to use 4 extra bytes to produce that format, so I actually saved 1 byte. Hooray! ;)

It's actually doing the hard work of summing up starting from 1 until the sum is bigger than the input. Then it begins substracting numbers starting from 1 until the number is smaller than the input. It keeps changing the start and end number this way until it found a result, which it then prints.

Usage example

echo 303 | awk '{while($0!=s+=s<$0?++j:-++i);while(++i-j)r=r i"+"}$0=r j'

Output of example

48+49+50+51+52+53

I've tried this for an input of 1e12 and it gave the correct result (464562+...+1488562) almost immediately. Though it took a while printing it of course...

\$\endgroup\$
  • \$\begingroup\$ Love the Awk approach. I'm have trouble working out the order of precedence in the bindings. Would you mind please including a version with more parentheses added to make it a bit more obvious? :) \$\endgroup\$ – Wildcard May 15 '17 at 15:58
  • 1
    \$\begingroup\$ Hope this helps: {while($0!=s)s+=(s<$0) ? (++j) : -(++i); while(++i<j)r=r i"+"}$0=r j i is always the last integer that got subtracted from the start of the chain, j is always the last integer added at the end of the chain \$\endgroup\$ – Cabbie407 May 17 '17 at 0:27
0
\$\begingroup\$

Japt, 33 bytes

This uses Dennis's Pyth technique, although it's considerably longer...

1oU à2 £W=Xg o1+Xg1¹x ¥U©W} rª ªU

Try it online! Warning: For larger inputs (<= 20), it takes a while to finish, and freezes your browser until it does.

Ungolfed and explanation

1oU à2 £    W=Xg o1+Xg1¹ x ¥ U© W} rª  ª U
1oU à2 mXYZ{W=Xg o1+Xg1) x ==U&&W} r|| ||U

          // Implicit: U = input integer
1oU à2    // Generate a range from 1 to U, and take all combinations of length 2.
mXYZ{     // Map each item X in this range to:
W=Xg o    //  Set variable W to the range of integers starting at the first item in X,
1+Xg1)    //  and ending at 1 + the second item in X.
x ==U&&W  //  If the sum of this range equals U, return W; otherwise, return false.
r||       // Reduce the result with the || operator, returning the first non-false value.
||U       // If this is still false, there are no consecutive ranges that sum to U,
          // so resort to U itself.
          // Implicit: output last expression

Bonus-earning version: (38 bytes - 5 = 33)

1oU à2 £W=Xg o1+Xg1¹x ¥U©W} rª ªU² q'+
\$\endgroup\$
0
\$\begingroup\$

Julia, 92 bytes

x->(t=filter(i->all(j->j==1,diff(sort(i))),partitions(x));collect(t)[indmax(map(length,t))])

This is an anonymous function that accepts an integer and returns an array. To call it, give it a name, e.g. f=x->....

Ungolfed:

function f(x::Integer)
    # Get all arrays of integers that sum to x
    p = partitions(x)

    # Filter these down to only consecutive runs by checking whether
    # all differences are 1
    t = filter(i -> all(j -> j == 1, diff(sort(i))), p)

    # Find the index of the longest element of t
    i = indmax(map(length, t))

    return collect(t)[i]
end
\$\endgroup\$
0
\$\begingroup\$

Ruby, 94 bytes

->n{([*1..n].permutation(2).map{|i,j|[*i..j]if(i..j).reduce(:+)==n}-[p]).max_by{|k|k.size}||n}

Ungolfed:

-> n {
  ([*1..n].permutation(2).map { |i,j|   # Finds all the possible sets of size 2
     [*i..j] if(i..j).reduce(:+) == n   # Adds a set to an array if sum of the set is n.
   }-[p]                                # Removes nil from the array
  ).max_by { |k|                        # Finds the longest sequence
    k.size
  } || n                                # Returns n if no sequence found.
}

Usage:

->n{([*1..n].permutation(2).map{|i,j|[*i..j]if(i..j).reduce(:+)==n}-[p]).max_by{|k|k.size}||n}[25]
=> [3, 4, 5, 6, 7]
\$\endgroup\$
0
\$\begingroup\$

Seriously, 53 - 5 = 48 bytes

,;;;╝`;u@n╟(D;)`n(XXk`iu@u@x;Σ╛=[])Ii`╗`ñ╜M`M;░p@X'+j

Hex Dump

2c3b3b3bbc603b75406ec728443b29606e2858586b60697540754
0783be4be3d5b5d29496960bb60a4bd4d604d3bb0704058272b6a

Try It Online!

It's the brute force approach, similar to Dennis's Pyth.

Everything up to the k just reads input n into register 1 and then creates the list [[1],[2,2],[3,3,3],[4,4,4,4],...] up to n n's.

The next bit up to is a function stored in register 0 that takes a pair, increments both elements, converts them to a range, finds the sum of the range, and checks whether that sum is the value in register 1. If it is, it returns the corresponding range, and if it's not, it returns an empty list.

The part up to the last occurrence of M maps a function over the fancy list of lists described above, doing enumerate on each list, then mapping the stored function over it. When it is done, we have a list of lists each of which is empty or a range which sums to n.

;░ removes the empty lists. p@X takes the first list which remains (0@E would also work). '+j puts + between each number as it converts the list to a string for the bonus.

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

ES6, 72 bytes

n=>{for(l=u=1;n;)n>0?n-=u++:n+=l++;return[...Array(u).keys()].slice(l);}

Straight port of @Cabbie407's awk solution, but without the formatting bonus, since it's a penalty here.

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

Python 3, 239 236 215 203 bytes

This is a little cumbersome. I'll have to golf it down later.

def x(n):
 r=[n]
 for i in range(2,n):
  t=[]
  if i%2*(n%i<1):t=[j+n//i-i//2for j in range(i)]
  elif i%2<1and n%i==i//2:t=[j+n//i-i//2+1for j in range(i)]
  if t[:1]>[0]*(sum(t)==n):r+=t,
 return r[-1]

The k is because if you check t[0] on an empty t, Python makes rude noises at you. Again, this is in need of golfing. Thanks to t[:1], no more rude noises! You just need to check against another array.

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

Jelly, 8 bytes (non-competing)

ẆS⁼¥Ðf⁸Ṫ

Try it online!

If I understand correctly, this could be an (11-5=6)-byte version:

ẆS⁼¥Ðf⁸Ṫj”+
\$\endgroup\$
  • \$\begingroup\$ For interest's sake, there are 12 similar solutions (including this one) by swapping the non-vectorizing equals for the vectorizing equals, changing left-argument to first-argument or to identity, and swapping equals with not-equals and filter-in for filter-out for both vectorizing and non-vectorizing. :O \$\endgroup\$ – HyperNeutrino May 22 '17 at 5:34
  • \$\begingroup\$ Let's say I posted the one that makes most sense, but with speed optimization. \$\endgroup\$ – Erik the Outgolfer May 22 '17 at 10:30
0
\$\begingroup\$

05AB1E, 11 - 5 = 6 bytes (non-competing)

Taking that bonus of course :)

LŒʒOQ}é¤'+ý

Try it online!

LŒʒOQ}é¤'+ý  Argument: n
LΠ          Sublists of range 1 to n
  ʒOQ}       Filter by total sum equals n
      é¤     Get longest element
        '+ý  Join on '+'
\$\endgroup\$
0
\$\begingroup\$

PHP, 70 bytes

while(fmod($q=sqrt(2*$argn+(++$p-.5)**2)-.5,1));print_r(range($p,$q));

Run as pipe with -nR or try it online.

increments p until it finds an integer solution for argument==(p+q)*(q-p+1)/2,
then prints the range from p to q.

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

Excel VBA, 119 - 5 = 114 Bytes

Subroutine that takes input n of expected type integer and outputs the longest sequence of consecutive numbers which sum to it to the cell [A1]

Sub a(n)
For i=1To n
s=0
For j=i To n
s=s+j
If s=n Then:For k=i To j-1:r=r &k &"+":Next:[A1]=r &j:End
Next
Next
End Sub
\$\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.