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$
11
  • 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, 2019 at 1:05
  • 1
    $\begingroup$ $1\times1649=17\times97$ $\endgroup$
    – J. W. Tanner
    Jul 17, 2019 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, 2019 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, 2019 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, 2019 at 2:39

2 Answers 2

Reset to default
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$
4
  • $\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, 2019 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, 2019 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, 2019 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, 2019 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .