## Consecutive Sums

### February 12, 2019

There is an obvious O(*n*²) solution: consider all sums of consecutive integers, starting from 1, until the sum either equals or exceeds the target, then start again from 2, and so on:

(define (consums n) (let loop ((i 1) (j 1) (s 0) (zs (list))) ;(display i) (display " ") (display j) (display " ") ;(display s) (display " ") (display zs) (newline) (cond ((< n (+ i i 1)) (reverse zs)) ((< s n) (loop i (+ j 1) (+ s j) zs)) ((< n s) (loop (+ i 1) (+ i 1) 0 zs)) (else (loop (+ i 1) (+ i 1) 0 (cons (range i j) zs))))))

> (consums 15) ((1 2 3 4 5) (4 5 6) (7 8))

But there is a better way. If a target *n* admits a sequence of length 2, that number must be odd and the sequence consists of ⌊*n*/2⌋ and ⌈*n*/2⌈. If a target *n* admits a sequence of length 3, that number must be divisible by 3 and the sequence consists of *n*/3−1, *n*/3, and *n*/3+1. And so on. That leads to this elegant function:

(define (consums n) (let loop ((len 2) (seqs (list))) (let ((sum (/ (* len (+ len 1)) 2))) (if (< n sum) seqs (if (positive? (mod (- n sum) len)) (loop (+ len 1) seqs) (let* ((mid (quotient n len)) (start (- mid (quotient len 2) (if (even? len) -1 0))) (seq (range start (+ start len)))) (loop (+ len 1) (cons seq seqs))))))))

> (consums 15) ((1 2 3 4 5) (4 5 6) (7 8))

Here *n*(*n*+1)/2 is Gauss’s formula for the sum of the first *n* integers, and `mod`

tests divisibility, adding a new sequence only when the length of the sequence divides *n* less the sum of the first *n* positive integers.

While playing with the function, I noted this interesting pattern:

> (map (lambda (n) (length (consums n))) '(10 100 1000 10000 100000 1000000)) (1 2 3 4 5 6)

You can run the programs at https://ideone.com/omBXzJ.

Quite a nifty one, reminiscent of Euler… Here is my take on it, using Julia 1.0:

function SumOfConsecutiveNumbers(x::Int64)

n = div(x,2)

n1 = n + 1

S = Array{Array{Int64}}(undef, n)

c = 0

end

Cheers!

There is another way to solve the problem:

Let the series be k, k+1, k+2, …k+n = N

Then k(n+1) + n(n+1)/2 = N (1)

or (n+1)(n+2k) = 2N (2)

Thus we find all the divisors of 2N and solve for n and k. Some solutions do not give an integral value for k are therefore not valid.

@Ernie: nice solution. Given 2N = ab, k is integral when a and b are of different parities, so we have a (non-trivial) series for N for each odd divisor of N (and this explains Praxis’s observation on 10^n,whose odd divisors are 5^i, 1 <= i <= n).

Here’s some actual code for that solution:

Interval is [k..k+n] for n > 0, sum is k*(n+1)+ n(n+1)/2 = (n+1)(n+2k)/2

so 2N = ab with parity of a and b different. The odd one of a and b must

factor N, and any odd divisor of N will result in an interval sum:

An equivalent function to test cosums – the sum of integers between n and m (inclusive, with n <= m) is (m-n+1)(m+n)/2 decreasing n increases this product and decreasing m decreases the product:

And for a test, print out the numbers where there are more solutions than any lower number:

Looks like we are generating https://oeis.org/A053624, Highly Composite Odd Numbers:

A quick and dirty Haskell version.

Hello Everyone,

This is my first post. I am very new to programming and wanted to improve with some problem solving. Here is my solution using Javascript. I definitely did not make the output pretty. Hope this post works. Thanks

Can’t seem to post my entry

yyy

What in the name of sanity happened to my lovely indentation?

https://en.support.wordpress.com/code/posting-source-code/

ie. do something like this:

@richard: I think I got the formatting fixed properly. Let me know if I did something wrong. The easiest way to post code is just to wrap it with pre … /pre tags.

Here’s a solution in C.

Example Usage: