# The sum of consecutive odd numbers

Although related challenges have been asked, this one is different to warrant its own question.

# Challenge

Given a positive integer, return the longest sequence of consecutive positive odd integers whose sum is the given integer. If no such sequence exists, you may report an error in whatever way makes sense for your language, including returning a falsy value or throwing an exception.

# Test Cases

1 -> [1]
2 -> []
3 -> [3]
4 -> [1, 3]
5 -> [5]
6 -> []
9 -> [1, 3, 5] (note that [9] is not a valid answer)
15 -> [3, 5, 7]
104 -> [23, 25, 27, 29] (note that [51, 53] is not a valid answer)

# Scoring

This is , so the shortest answer in each language wins.

• Can my program just run forever if there's no solution? – Dennis Jul 6 '17 at 21:35
• Very related. The fact that some even numbers cannot be represented in this one might save it from being a dupe though. – ETHproductions Jul 6 '17 at 22:26
• Can't 15 give [-1, 1, 3, 5, 7]? If only positive values are allowed, you should say so. – xnor Jul 7 '17 at 1:10
• @ЕвгенийНовиков you skipped 17 – kalsowerus Jul 7 '17 at 6:09
• @kalsowerus yes. I misunderstand word "consecutive" – Евгений Новиков Jul 7 '17 at 6:11

Saved 4 bytes thanks to Julian Wolf

f x=[[2*n+1,2*n+3..2*m]|n<-[0..x],m<-[n..x],m^2-n^2==x]!!0

Try it online!

I check if the number can be expressed as he difference of two squares: m^2-n^2. I can then construct the list of consecutive odd numbers: [2n+1,2n+3...2m-1]. Note that because the minimum n is chosen, the longest list will be output

• Down-voter: It would be both friendlier and more constructive to add a comment giving your reason, especially when down-voting a new user. – Jonathan Allan Jul 6 '17 at 20:25
• Unless I'm missing something, you can save 4 bytes by only going up to x for both n and m – Julian Wolf Jul 6 '17 at 21:23
• Just so you know, the downvote was cast automatically by the Community user when you edited your answer. I consider this a bug. (CC @JonathanAllan) – Dennis Jul 7 '17 at 3:09
• Ahh, it was one of those. – Jonathan Allan Jul 7 '17 at 11:41

# Python 2, 66 62 bytes

f=lambda n,k=0,*r:n-sum(r)and f(n,k+1,*range(k%n|1,k/n,2))or r

Exits with a RuntimeError (maximum recursion depth exceeded) if there's no solution.

Try it online!

• If the input values are high enough, but there is a solution, will this result in a RuntimeError? – Okx Jul 7 '17 at 10:38
• If the recursion limit isn't high enough and/or the stack isn't big enough, yes. However, it's common to ignore physical limitations (e.g., a C answer only has to work for 32-bit ints), and the OP explicitly said that running forever is acceptable if there's no solution. – Dennis Jul 7 '17 at 14:07

# Jelly,  11  10 bytes

-1 byte thanks to Dennis (use the implicit range building of - replace Rm2Ẇ with ẆḤ’)

ẆḤ’S_¥Ðḟ⁸Ṫ

A monadic link returning a list of the summands if possible, or 0 if not.

Try it online!

### How?

Ẇ          - all sublists (implicit range of input) note: ordered by increasing length
-                i.e. [[1], [2], [3], ..., [1,2], [2,3], ..., [1,2,3], ...]]
Ḥ         - double              [[2], [4], [6], ..., [2,4], [4,6], ..., [2,4,6], ...]]
’        - decrement           [[1], [3], [5], ..., [1,3], [3,5], ..., [1,2,5], ...]]
⁸  - link's left argument, n
Ðḟ   - filter out items for which the following yields a truthy value:
S       -     sum
_      -     subtract the right from the left = sum - n
Ṫ - tail (last and hence longest such run)
• ẆḤ’ saves a byte. – Dennis Jul 7 '17 at 14:04

## JavaScript (ES7), 878685 81 bytes

Returns a comma-delimited list of integers, or 0 if no solution exists.

n=>(g=(s,k,x=n+s)=>(x**.5|0)**2-x?k>n?0:g(s+k,k+2):(n-=k)?k+','+g(-n,k+2):k)(0,1)

### How?

We first look for the smallest perfect square s such that x = n + s is another perfect square.

If s exists, n is the difference x - s of 2 perfect squares, which can be written as the difference of 2 sequences of consecutive odd numbers. We then build the resulting list.

Example:

For n = 104:

We find s = 11² = 121 which satisfies x = n + s = 225 = 15²

Then:

15² = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 + 27 + 29
11² = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21
104 = 15² - 11² = 23 + 25 + 27 + 29

let f =

n=>(g=(s,k,x=n+s)=>(x**.5|0)**2-x?k>n?0:g(s+k,k+2):(n-=k)?k+','+g(-n,k+2):k)(0,1)

console.log(f(1))   // -> 1
console.log(f(2))   // -> 0
console.log(f(3))   // -> 3
console.log(f(4))   // -> 1,3
console.log(f(5))   // -> 5
console.log(f(6))   // -> 0
console.log(f(9))   // -> 1,3,5
console.log(f(15))  // -> 3,5,7
console.log(f(104)) // -> 23,25,27,29

# 05AB1E, 9 8 bytes

-1 byte thanks to Emigna

ÅÉŒʒOQ}н

Explanation:

ÅÉ           Generate a list of odd numbers up to, and including, the input
Œ          Substrings
ʒ         Only keep values
O          where the sum
Q         equals the input
}     End
For 9, the result would look like this:
[[1, 3, 5], [9]]
н    Get the first value

On invalid input, outputs nothing.

Try it online!

• ʒOQ} instead of DO¹QÏ saves a byte. – Emigna Jul 6 '17 at 21:25
• @JonathanAllan Docs say "uneven" so that might've been confused... – Erik the Outgolfer Jul 7 '17 at 10:11
• @JonathanAllan Small mistake. Fixed. – Okx Jul 7 '17 at 10:37

Thanks to @maple_shaft for shaving off 1 byte

f n=[k|r<-[1,3..],s<-[r,r+2..n],k<-[[r,r+2..s]],sum k==n]!!0

Try it online!

Uses the fact that the longest run will always be the run that starts with the lowest number.

I wanted to do something with arithmetic in stead of brute-forcing k, but fromInteger seems to kill it.

• You can save yourself one byte by changing [1,3..n] to [1,3..] – maple_shaft Jul 6 '17 at 20:31
• You can save 7 bytes with a helper function r?n=[r,r+2..n]. Try it online! – Ørjan Johansen Jan 13 '18 at 0:11

# Python, 67 bytes

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

Try it online!

I copied my answer from the previous consecutive sum challenge and changed the +1 to +2. Who knew that golfed code could be so modular?

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

• If the sum is too small, shift the right endpoint of the interval up 2 by appending the next number 2 above it.
• 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. If no possible interval can be found, terminates with IndexError.

# JavaScript (ES6), 65 64 bytes

f=(a,i=1)=>a>i?(c=f(a-i,i+=2))[0]==i?[i-2,...c]:f(a,i):a<i?0:[i]

Returns an array if there's a solution, or 0 for no solution.

This is a highly inefficient yet golfy solution to the problem.

It searches for the first solution using a-i and i=1, even if it doesn't work up the recursive stack. If that solution doesn't begin with i+2, then we recursively search for the first solution using a and i+2.

Ungolfed

f=(a,i=1)=>
a > i ?
(c = f(a - i, i += 2))[0] == i ?
[i-2, ...c] :
f(a, i) :
a < i ?
0 :
[i]

Test cases:

f=(a,i=1)=>a>i?(c=f(a-i,i+=2))[0]==i?[i-2,...c]:f(a,i):a<i?0:[i]

console.log(JSON.stringify(f(1)));   //[1]
console.log(JSON.stringify(f(3)));   //[3]
console.log(JSON.stringify(f(4)));   //[1, 3]
console.log(JSON.stringify(f(5)));   //[5]
console.log(JSON.stringify(f(6)));   //[0]
console.log(JSON.stringify(f(9)));   //[1, 3, 5]
console.log(JSON.stringify(f(15)));  //[3, 5, 7]
console.log(JSON.stringify(f(104))); //[23, 25, 27, 29]

For an idea of how inefficient this is, the solution to f(104) requires 69,535 recursive calls. The stack is never more than 51 levels deep, so no problem with stack overflow.

The solution to f(200) requires 8.6 million recursive calls, with a stack 99 levels deep. (Its solution is [11,13,15,17,19,21,23,25,27,29].)

Here's a visual representation of the program running:

r=0;
output=o=>setTimeout(_=>O.textContent += o + '\n', r++ * 20);

f=(a,i=1,s='',o = s + 'a=' + a + '; i=' + i + ';')=>
(
output(o),
a > i ?
(c = f(a - i, i += 2, s + '  '))[0] == i ? (
output(o + ' a > i; [i-2, ...c] = [' + [i-2, ...c] + '];'),
[i-2, ...c]
) : (
output(o + ' a > i; c=[' + c + ']; ' + 'c[0]+2 != i ... dead end\n' + s + 'trying a, i+2:'),
f(a, i, s)
) :
a < i ? (
output(o + ' a < i ... dead end'),
0
) : (
output(o + ' a == i;'),
[i]
)
)

f(21);  //[5, 7, 9]
<pre id=O></pre>

# Python 2.7, 109108 97 bytes

11 bytes down, Thanks to Erik the Outgolfer.

This is my first code golf!

def f(N):
for n in range(N):
x=(n*n+N)**.5-n
if x%1==0:return[2*(k+n)+1for k in range(int(x))]

## How it works

I used the well known identity that 1 + 3 + 5 + ... + (2n - 1) = n²

Take the case of 15

15 = 3 + 5 + 7 = (1 + 2) + (3 + 2) + (5 + 2) = (1 + 3 + 5) + 3×2 = 3² + 3×2

In general, if there are x terms starting from 2n + 1, like

(2n + 1) + (2n + 3) + (2n + 5) ... (2n + (2x-1))

It is equal to 2nx + x²

If N is the input integer, the problem reduces to finding maximum x such that

x² + 2nx - N = 0

It is a quadratic equation with solution

x = sqrt(n² + N) - n

The longest sequence is one with largest x. The program iterates n from 0 to N and when it find that x is an integer, it creates a list of (2n + 1) + (2n + 3) + (2n + 5) ... (2n + (2x-1)) and returns it.

# Python 3, 190 81 Bytes

def c(q,l,i):
if sum(l)0:
l.append(i)
return c(q,l,i+2)
elif sum(l)>q:
l.pop(0)
return c(q,l,i)
else:
print(l)
c(q,[1],1)

c=lambda q,l=[1]:c(q,l+[l[-1]+2])if(sum(l)<q)*l else c(q,l[1:])if sum(l)>q else l

Thanks to @ovs and @musicman523

• You can get this down to 122 bytes just by removing some indentation. If you want to shorten your code further, have a look at Tips for golfing in Python. – ovs Jul 6 '17 at 21:20
• This doesn't run in Python 3, because the call to print is missing parentheses – musicman523 Jul 7 '17 at 4:04
• You can remove l.append(i) by simply using l+[i] in the recursive call. You can remove l.pop(0) by using l[1:] in the recursive call. You can remove the call to c at the very bottom by using keyword arguments instead. You can remove >0 on line 2. Finally, you can change your if and else statements into expressions, using the ternary form, which gets you down to 92 bytes as a lambda expression. Try it online! – musicman523 Jul 7 '17 at 4:10
• Based on @musicman523 suggestions we can still shorten the conditions and drop i to get to a total of 81 bytes. – ovs Jul 7 '17 at 6:06
• I think you could change sum(l)>q else to q<sum(l)else to save 1 byte. – Adalynn Jul 9 '17 at 15:18

# QBIC, 47 bytes

{_Cg=q┘q=q+2~g>:|_Xp\?g,[q,a,2|?b,┘g=g+b~g=a|_X

This tries to count all the odd numbers from one until its sum is n. If it passes n, reset the loop, increase 1 to 3 and try again. Quit, printing 0, if at the start of the loop our number > n.

## Explanation

{       Do infinitely
_C      Clear the screen (we basically print every run of odd numbers, but clear out everything that doesn't sum up to n)
g=q     Set g to the first num of this cycle (q starts as 1 in QBIC)
┘       (Syntatcic linebreak)
q=q+2   Raise q to the next odd number, this sets up both the next outer loop as well as a coming FOR loop
~g>:|   If we start out with a number > n (read as 'a' from the cmd line)
_Xp     THEN quit, printing 0 (the value of the number var 'p')
\       ELSE
[q,a,2| FOR b = q, b <= n, b+=2
?b,┘    PRINT b followed by a tab
g=g+b   Add 'b' to running total 'g'
~g=a|   and if that lands us on 'n'
_X      QUIT (printing nothing: everything is already printed)

# R, 90 bytes

f=function(x,y=1)'if'(length(w<-which(cumsum(r<-y:x*2-1)==x)),r[1:w],'if'(y>x,0,f(x,y+1)))

Try it online!

Uses a recursive function that test sequence cumulative sum of y:x converted to an odd number sequence. y is incremented on each recursion until it exceeds x. The first sequence which sums to the target will be returned.

# Python 2, 89 bytes

lambda n,r=range:[v for v in[r(1,n+1,2)[i:j]for i in r(n)for j in r(n+1)]if sum(v)==n][0]

An unnamed function taking a positive integer, n, and returning the result if it exists and raising an IndexError otherwise.

Try it online!

Creates a list of all the relevant odd numbers with r(1,n+1,2) which is range(start=1, stop=n+1, step=2); creates all the relevant sub-slices (plus some empty ones) by slicing that from i inclusive to j exclusive with [i:j] across i in [0,n) using r(n) and j in [0,n] using r(n+1) (the empty ones when i>=j or i is out of bounds); filters for those with the correct sum with if sum(v)==n; returns the first (and hence longest) such slice using [0].

# Python 2, 91 90 bytes

-1 byte thanks to @CMcAvoy

lambda n,r=range:[r(i,j+1,2)for i in r(1,n+1,2)for j in r(i,n+1,2)if(i+j)*(2+j-i)==4*n][0]

Try it online!

efqsTQ.:%2S

Try it here.

# PHP, 73 bytes

no solution is a infinite loop

for($e=-1;$s-$i=$argn;)$s+=$s<$i?$n[]=$e+=2:-array_shift($n);print_r($n); Try it online! # PHP, 83 bytes prints nothing for no solution every input mod 4 == 2 has no solution for($e=-1;($i=$argn)%4-2&&$s-$i;)$s+=$s<$i?$n[]=$e+=2:-array_shift($n);print_r($n); Try it online! • fails to detect unsolvable input – Titus Jul 7 '17 at 12:46 • @Titus fixed... – Jörg Hülsermann Jul 7 '17 at 13:08 # Python 2, 122121119 115 bytes -1 byte thanks to musicman523. -4 bytes thanks to Step Hen. haha def f(n,R=range):r=R(1,n,2);print[i for w in R(1,len(r)+1)for i in[r[j:j+w]for j in R(len(r)-w+1)]if sum(i)==n][-1] Try it online! • This is one byte shorter as a function. Try it online! – musicman523 Jul 6 '17 at 20:07 • Save bytes if you redefine range, Try it online! – Stephen Jul 6 '17 at 20:14 • This fails for 1. – Dennis Jul 6 '17 at 23:08 # Python 3, 93 bytes lambda n,r=range:[[*r(s,e+1,2)]for s in r(1,n+1,2)for e in r(s,n+1,2)if(s+e)*(2+e-s)==4*n][0] Try it online! Only thing special I did was noting that (s+e)*(2+e-s)==4*n is equivalent to sum(range(s,e+1,2))==n, and though they're the same size when r=range, the former can be placed closer to the if statement. # Python 3, 185 bytes def f(s): d={k:v for k,v in{a:(1-a+((a-1)**2+4*s)**(.5))/2 for a in range(1,s,2)}.items()if int(v)==v};m=max(d.keys(), key=(lambda k: d[k]));return list(range(int(m),int(m+2*d[m]),2)) Try it online! As for how this works, I tried to go for a bit more elegant solution than a simple brute force search. I rearranged the formula for the sum of an arithmetic sequence and applied the quadratic formula to get the expression (1-a+((a-1)**2+4*s)**(.5))/2, which appears in the code. What the expression calculates is, given a desired sum s and a first term for of arithmetic sequence a, the length of the sequence. These lengths are stored in a dictionary as values to the first terms as keys. Next, all non-integer values are removed from the dictionary, as those represent invalid sequences. From there, the largest value is identified with max(d.keys(), key=(lambda k: d[k])) and the sequence of odd numbers at that position and at that length is made with list(range(int(m),int(m+2*d[m]),2)). I'm looking for help golfing this if you see anything. I was more interested in seeing how well I could do with a non-trivial algorithm; my answer is nearly twice as long as the best Python solution. • Would this work? repl.it/JTt7 (177 bytes) – Adalynn Jul 9 '17 at 15:25 # Mathematica, 56 bytes Last@Cases[Subsequences@Table[n,{n,1,#,2}],x_/;Tr@x==#]& Function with first argument #. Table[n,{n,1,#,2}] computes the list of positive odd numbers less than or equal to #. Subsequences returns all subsequences of that list ordered by increasing length. We then take the Cases which match x_/;Tr@x==#, that is, sequences x such that their sum Tr@x is equal to the input #. We then take the Last such sequence. ## JavaScript (ES6), 72 bytes n=>(g=s=>s?s>0?g(s-(u+=2)):g(s+l,l+=2):u-l?l+' '+g(s,l+=2):u)(n-1,l=u=1) Returns a space-separated string of odd numbers or throws on invalid input. 84 byte version that returns an (empty when appropriate) array: n=>n%4-2?(g=s=>s?s>0?g(s-(u+=2)):g(s+l,l+=2):u-l?[l,...g(s,l+=2)]:[u])(n-1,l=u=1):[] Explanation: Loosely based on @Cabbie407's awk solution to Sums of Consecutive Integers except I was able to save some bytes by using recursion. # PHP, 78 bytes for($b=-1;$s-$argn;)for($n=[$s=$x=$b+=2];$s<$argn;)$s+=$n[]=$x+=2;print_r($n);

infinite loop if no solution. insert ?$b>$argn+2?$n=[]:1:0 after$s-\$argn to print empty array instead.

Run with -nR or try it online.

# C# (.NET Core), 129 bytes

(i)=>{int s,j,b=1,e=3;for(;;){var o="";s=0;for(j=b;j<e;j+=2){s+=j;o+=j+" ";}if(s==i)return o;s=s<i?e+=2:b+=2;if(b==e)return"";}};

Outputs numbers in a string, space delimited (any other character would just require changing the " "). Input with no solution returns an empty string (though if running forever without error is a valid way to indicate no solution then 17 bytes could be saved by removing if(b==e)return"";).

Algorithm is:

2. If the sum is equal to the target, return the list
3. If the sum is less than the target, add the next odd number
4. If the sum is greater than the target, remove the first item
5. If the list is empty, return it
6. Repeat from 2
• You can write (i)=> as i=> – aloisdg Nov 26 '17 at 10:31

## C++, 157 -> 147 Bytes

-10 Bytes thanks to DJMcMayhem

will return 0 if there's no answer, 1 otherwise

the last line it prints is the answer

int f(int n){for(int i=1;;i+=2){int v=0;for(int k=i;;k+=2){v+=k;std::cout<<k<<" ";if(v==n)return 1;if(v>n)break;}if(i>n)return 0;std::cout<<"\n";}}

ungolfed:

int f(int n)
{
for (int i = 1;; i += 2)
{
int v = 0;
for (int k = i;; k += 2)
{
v += k;
std::cout << k << " ";
if (v == n)
return 1;
if (v > n)
break;

}
if (i > n)
return 0;
std::cout << "\n";
}
}

this is my first code golf ^^

• You could save some bytes if you made it an int function and returned 0 or 1. Also, you could do int v=0; instead of int v;....v=0; and if you made your output Newline delimited, you could do std::cout<<k<<"\n"; and then remove the second Newline altogether – James Jul 8 '17 at 16:24
• the if i did the last recomendation then it would print a new line on every single number but i want to seperate number groups, but thanks anyways for -10 Bytes – SeeSoftware Jul 8 '17 at 16:43

# Kotlin, 152 bytes

fun f(a:Double){var n=Math.sqrt(a).toInt()+1;var x=0;while(n-->0){if(((a/n)-n)%2==0.0){x=((a/n)-n).toInt()+1;while(n-->0){println(x.toString());x+=2}}}}

Try it online (Wait 4-5 seconds, compiler is slow)

Ungolfed

fun f(a: Double){
var n=Math.sqrt(a).toInt()+1;
var x=0;

while(n-->0){
if(((a/n)-n)%2==0.0){
x=((a/n)-n).toInt()+1;

while(n-->0){
println(x.toString());
x+=2;
}

}
}
}

# Excel VBA, 139 Bytes

Subroutine that takes input n of expected type integer and reports the longest sequence of consecutive odd numbers to cell [A1]

Sub a(n)
For i=1To n Step 2
s=0
For j=i To n Step 2
s=s+j
If s=n Then:For k=i To j-1 Step 2:r=r &k &"+":Next:[A1]=r &j:End
Next j,i
End Sub