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