The sum of consecutive odd numbers

Question

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 code-golf, so the shortest answer in each language wins.

Answer 1

Haskell, 67 65 63 62 58 bytes

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

Answer 2

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!

Answer 3

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?

ẆḤ’S_¥Ðḟ⁸Ṫ - Link: number, n
Ẇ          - 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:
     ¥     -   last two links as a dyad:
   S       -     sum
    _      -     subtract the right from the left = sum - n
         Ṫ - tail (last and hence longest such run)

Answer 4

JavaScript (ES7), 87 86 85 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

Answer 5

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!

Answer 6

Haskell, 61 60 bytes

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.

Answer 7

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.

Answer 8

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>

Answer 9

Python 2.7, 109 108 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.

Answer 10

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

Answer 11

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)

Answer 12

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.

Answer 13

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

Answer 14

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!

Answer 15

Pyth, 11 bytes

efqsTQ.:%2S

Try it here.

Answer 16

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!

Answer 17

Python 2, 122 121 119 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!

Answer 18

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.

Answer 19

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.

Answer 20

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.

Answer 21

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.

Answer 22

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.

Answer 23

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:

1. Start with [1]
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

Answer 24

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

Answer 25

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;
            }

        }
    }
}

Answer 26

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