Sums of Consecutive Integers

Question

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]

Answer 1

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.

Answer 2

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.

Answer 3

Mathematica, 73 68 65 56 43 bytes

Cases[Range~Array~{#,#},i_/;Tr@i==#,{2},1]&

Answer 4

Haskell, 49 48 bytes

f n=[[a..b]|a<-[1..n],b<-[a..n],sum[a..b]==n]!!0

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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”+

Answer 10

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 '+'

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

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'+

Answer 15

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

Answer 16

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]

Answer 17

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.

Answer 18

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.