4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Hint: try to write it as a difference of two squares. It's easy to write a square as a sum of consecutive odd numbers. $\endgroup$ – lulu Jul 17 at 1:05
  • 1
    $\begingroup$ $1\times1649=17\times97$ $\endgroup$ – J. W. Tanner Jul 17 at 1:08
  • 1
    $\begingroup$ Remark: Since $a^2-b^2$ is easy to factor, writing your (large) number as a difference of two squares will require you to factor it. Not completely...you just need two factors of the same parity. Of course, for large odd numbers it can be difficult to produce any factor, thereby making your problem difficult. $\endgroup$ – lulu Jul 17 at 1:15
  • 1
    $\begingroup$ @RobertShore, and J.W. Tanner Ha! Forgot you could use $1$ as a factor. Thanks for reminding me. $\endgroup$ – lulu Jul 17 at 1:33
  • 1
    $\begingroup$ You must be summing at least three consecutive odd positive integers, there is no guarantee that this is possible. There are no consecutive odd positive integers that sum to 7 or 11 $\endgroup$ – WW1 Jul 17 at 2:39
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note if $m$ is a product of two primes close together, or even consecutive, e.g., $m = 11 \times 13$, then $n$ is the smaller of the two, e.g., $11$ in my example, and $k$ would be the larger one, i.e., $13$ in my example. However, then the first number in your sequence would be, in my example, $k - 2n + 2 = 13 - 2\times 11 + 2 = 13 - 22 + 2 = -7$. Note, though, that the question asks for a sequence of consecutive odd positive integers. $\endgroup$ – John Omielan Jul 17 at 3:08
  • $\begingroup$ @John Omielan Major error - it has been corrected. In the example you cited the numbers go from $3$ to $23$. $\endgroup$ – herb steinberg Jul 17 at 3:58
  • 1
    $\begingroup$ If we assume the numbers are too large to factor efficiently are there any other techniques that can be used? $\endgroup$ – DeveloperChris Jul 17 at 4:20
  • $\begingroup$ The method works perfectly well for odd numbers which are squares, such as $9=1+3+5$. $\endgroup$ – herb steinberg Jul 17 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.