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

K (ngn/k), 40 32 bytes

{^/!'1+i@'*>-/i:&x=s-\:s:+\!1+x}

Try it online!

-8 bytes thanks to @ngn

Answer 4

Haskell, 49 48 bytes

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

Answer 5

Jelly (fork), 5 bytes

ẆSƘ¹Ṫ

Try it online! (or rather, don't)

For an extra 3 bytes (again, doesn't work on TIO), we can get a score of 3

How it works

ẆSƘ¹Ṫ - Main link. Takes N on the left
Ẇ     - Cast N to range and get all contiguous, non-empty sublists
  Ƙ¹  - Keep those for which the following is equal to N:
 S    -   Sum
    Ṫ - Take the last (and longest) one

Answer 6

Vyxal, 11 - 5 = 6 bytes

ɾÞS≬∑?=c\+j

Just like most of the other answers in golfing languages.

Try it Online!

Explanation:

ɾ            # Range from 1 to n
 ÞS          # All sublists
   ≬         # Three element lambda
    ∑        #   Sum
      =      #   Equals
     ?       #   The input
       c     # First truthy item under function application 
          j  # Join by:
        \+   # "+"

Answer 7

Brachylog, 8 bytes

⟦₁s.+?!∧

Try it online!

Explanation

⟦₁s.+?!∧
⟦₁         Inclusive range from 1 to the input number
  s        A consecutive sublist (trying longest sublists first)
   .       is the output
    +      Its sum
     ?     is the input
      !    Don't try any further possibilities
       ∧   Break unification with the output

Answer 8

Wolfram Language (Mathematica), 73 68 65 56 43 42 35 bytes

Range@#/.{___,x__,___}/;+x==#:>{x}&

Try it online!

Answer 9

K (ngn/k), ⁶¹ 41 bytes

h:{i{x':y}\:i:1+!x}
f:{i@*|&x=+/'i:,/h@x}

Try it online!

¯20 bytes thanks to @doug

Answer 10

K (ngn/k), 27 26 bytes

{*|(x=+/')#{y+!'x}.1+!2#x}

Try it online!

Uses doug's insight that to get a run you just need a pair of numbers.

Answer 11

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 12

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 13

Jelly, 8 bytes

ẆS⁼¥Ðf⁸Ṫ

Try it online!

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

ẆS⁼¥Ðf⁸Ṫj”+

Answer 14

Prolog (SWI), 64 62 51 bytes

-2 bytes thanks to Steffan

-11 bytes thanks to Razetime's tip

N+Z:-numlist(1,N,A),append([_,Z,_],A),sumlist(Z,N).

Try it online!

Answer 15

Pyth, 12 - 5 = 7 bytes

j\+efqQsT.:S

Test suite

The existing Pyth answer uses an older version of the language; new features have been added since.

Explanation:

j\+efqQsT.:S  | Full code
j\+efqQsT.:SQ | with implicit variables
--------------+----------------------------------------------------
           SQ | Get the range [1, ... input]
         .:   | Get all substrings, sorted by length
    f         | Filter for T such that
       sT     |  the sum of T
     qQ       |  equals the input
   e          | Get the last (longest) element of the filtered list
j\+           | Join by "+"

Answer 16

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 17

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 18

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 19

Husk, 12 - 5 = 7 bytes

J'+msḟo=¹ΣQḣ

Try it online!

Removing the first 5 bytes for joining, it still scores the same.

Explanation

J'+msḟo=¹ΣQḣ
           ḣ range from 1..n
          Q  all possible sublists
     ḟ       get the first value which satisfies:
       =¹Σ   sum = input.
   ms        convert each number to string
J'+          join on '+'

Answer 20

R, 57 bytes

for(i in (n=scan()):1)for(j in n:i)if(sum(i:j)==n)x=i:j;x

Try it online!

Answer 21

Knight, 66 bytes

;=i+=a 0P W;=r""!>=a+1=b a=c iW!>0c;=c-c=b+1b;=r+r+"+"bI?0cQ Or 0 

Try it online!

Annotated code:

;=i+ =a 0 PROMPT                        # set a to 0, i to input
WHILE ;=r "" !>(=a +1(=b a)) (=c i)     # set r to "", b to a, a to a+1, c to i, check if a less than c
  WHILE !< c 0                          # while c >= 0:
    ;=c (-c (=b +1b))                   # set b to b+1, c to c-b
    ;=r (+ r + " " b)                   # append b to r
    IF (? c 0) (QUIT OUTPUT r) 0        # if c is 0, output r and break; else, do nothing

Answer 22

05AB1E, 11 - 5 = 6 bytes

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 23

Prolog (SWI), 72 bytes

L/X/H:-between(L,H,X).
N*Z:-1/A/N,A/X/N,findall(Y,A/Y/X,Z),sumlist(Z,N).

Try it online!

-4 bytes thanks to DLosc.

Answer 24

C (gcc), 66 bytes

i,j;f(n){for(i=j=0;n;)n+=n>0?--j:++i;for(;i+j;)printf("%d ",++i);}

Inspired by xnor's sliding window solution, keeps track of the ends of the window.

Try it online!

Answer 25

05AB1E, (10-5=) 5 bytes

Åœ.Δ¥P}'+ý

Try it online or verify all test cases.

Explanation:

Ŝ        # Get all lists of positive integers that sum to the (implicit) input,
          # which is sorted from longest (all 1s) to shortest (just the number)
  .Δ      # Find the first list which is truthy for:
    ¥     #  Get the deltas/forward-differences of the list
     P    #  Take the product (only 1 is truthy in 05AB1E)
   }'+ý  '# After we've found a list: join it with "+" delimiter
          # (after which it is output implicitly as result)

Answer 26

Thunno 2, 10 - 5 = 5 bytes

RƑæS=;h'+j

Try it online!

Port of tybocopperkettle's Vyxal answer.

Explanation

RƑæS=;h'+j  '# Implicit input
RƑ           # All sublists of [1..n]
  æ  ;       # Filtered by:
   S=        #  Sum equals input
      h      # First item
       '+j  '# Joined by "+"
             # Implicit output

Answer 27

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 28

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 29

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 30

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.