How to find the consecutive odd numbers that sum to a given odd number

Question

Given a non perfect square odd number, say $1649$ What is the most efficient way to find the consecutive odd positive integers that sum to that number.

No other information is provided, just the odd number to solve.

In reality the odd numbers I want to find are substantially larger than 1649 which would be trivial to find the consecutive odds that sum to it. So I am looking for an efficient generalised method to turn into an algorithm to resolve this problem for any given odd number.

EDIT: Perhaps I should have added. The numbers I am working with are too large to factor in an efficient manner. Therefore the difference of two squares is not a workable option.

I am looking for alternate approaches to solving the problem.

Answer 1

correction:

Let $m$ be the number. Find the smallest prime factor $n$ of $m$ and let $k=\frac{m}{n}$ The sequence will be $k-n+1,k-n+3,.....,k-2,k,k+2,...,k+n-3,k+n-1$.

Note: The list is of length $n$, which is the smallest possible.

Note: The method will work with any factor $\le \sqrt{m}$. My solution may be the easiest, but not necessarily.

Answer 2

Notice if you add an even number of odd numbers you get an even sum. If you add an odd number of consecutive numbers you get an odd sum. So to get an odd sum you must have an odd number of terms.

Suppose you have $2k + 1$ terms and the middle term is $m$, then you numbers are $(m-2k), (m-2k+2), (m-2k + 4),...... (m-2), m , (m+2),...... (m+k-4), (m+k-2), (m+k)$.

If you add up the first term with the last term you get $(m-2k) + (m+2k) =2m$. If add up the second and second to last term you ge $(m - 2k +2)+(m+2k -2) = 2m$. And so on.

So when you add them all up you get $2m*k + m = m(2k + 1)$

So if you factor your number into two factors and set one to $m$ and the other to $2k + 1$ (as your number is odd both factors will be odd) you can get your sum.

Example: $1649 = 1 * 1649$ so so if $m = 1649$ and $2k+1 = 1$ then we can write $1649$ as a sum of $1$ term with the middle term $1649$. I.e. $1649 = \sum_{i=1}^1 1649$.

..... Okay, that's cheating but we can write $m =1$ and $2k+1 = 1649$ so that it can be the sum of $1649$ terms with the middle term of $1$. so $-1647+(-1645) + (-1643) + ...... + 1643 + 1645 + 1647 + 1649 = 1649$.

.... Okay, that was me cheating again. But if the number is not prime we can do it.

$1649 = 17*97$. Let $m =97$ and $2k+1 =17$ so $k = 8$ then we can have a sum of $17$ terms centered at $97$.

So $81 + 83 + 85 + 87 + ..... + 109 + 111 + 113 = $

$(97-16) + (97-14) + .... + (97-2) + 97 + (97+2) + .... + (97+14)+(97+16) =$

$97 + 97 + ..... + 97 + 97 +97 +.... + 97 + 97 = 17*97 = 1649$.