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.
Programming Praxis 
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:
def cosums(N): for a in range(1,N+1,2): if N%a == 0: # a is an odd divisor of N b = 2*N//a if b < a: a,b = b,a n = a-1 k = (b-a+1)//2 yield(k,k+n)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:
def cosums1(N): n,m = N,N while n > 0: t = (m-n+1)*(m+n)//2 if t < N: n -= 1 elif t > N: m -= 1 else: yield (n,m) n -= 1; m -= 1And for a test, print out the numbers where there are more solutions than any lower number:
maxlen = 0 for N in range(200): s = sorted(list(cosums(N))) s1 = sorted(list(cosums1(N))) assert(s == s1) if len(s)> maxlen: print(N,s) maxlen = len(s)Looks like we are generating https://oeis.org/A053624, Highly Composite Odd Numbers:
A quick and dirty Haskell version.
import Data.Maybe (mapMaybe) import System.Environment (getArgs) import Text.Printf (printf) import Text.Read (readMaybe) sumTo :: Integral a => a -> a -> a m `sumTo` n = (n + m) * (n - m + 1) `quot` 2 sumBounds :: Integral a => a -> [(a, a)] sumBounds n = let u = n `quot` 2 in [(i, j) | i <- [1..u], j <- [i+1..u+1], i `sumTo` j == n] consecSums :: Integral a => a -> [[a]] consecSums = map (uncurry enumFromTo) . sumBounds printConsecSums :: Int -> IO () printConsecSums n = print n >> mapM_ (printf " %s\n" . show) (consecSums n) main :: IO () main = do ns <- mapMaybe readMaybe <$> getArgs mapM_ printConsecSums ns$ ./consecsums 1 3 9 15 45 105 1 3 [1,2] 9 [2,3,4] [4,5] 15 [1,2,3,4,5] [4,5,6] [7,8] 45 [1,2,3,4,5,6,7,8,9] [5,6,7,8,9,10] [7,8,9,10,11] [14,15,16] [22,23] 105 [1,2,3,4,5,6,7,8,9,10,11,12,13,14] [6,7,8,9,10,11,12,13,14,15] [12,13,14,15,16,17,18] [15,16,17,18,19,20] [19,20,21,22,23] [34,35,36] [52,53]def solution(limit=15, verbose=False): solutions, stack = list(), [1] while True: s, l = sum(stack), len(stack) # print if verbose: print('{} {}'.format('*' if s == limit else '', stack)) # check if s == limit: solutions.append(stack.copy()) if s > limit and l <= 2: break # update if s < limit: stack.append(stack[-1] + 1) elif s >= limit: stack.pop(0) return solutions solution(limit=15, verbose=True)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
const consecutivePositiveInt = (target) => { let currentSum; let history = []; let startNum; let answerArray = []; for (let k =1; k < target; k++) { startNum = k; currentSum = k; history.push(startNum); while (currentSum < target) { currentSum = history.reduce(( accumulator, currentValue ) => accumulator + currentValue, 0); if(currentSum == target) { answerArray.push(history); history = []; } else if (currentSum > target) { history = []; } else { startNum++; history.push(startNum); } } } if(answerArray === undefined || answerArray.length === 0){ return `No Consecutive Positive numbers add to the number ${target}` }else{ return answerArray; } }Can’t seem to post my entry
Klong version 2 " Consecutive Sums" "f(x;y) returns the divisor plus the first number in the series for a given number and divisor, as f(85;2)->[2 42]. If there is no series for a divisor, it returns [0 0] as f(85;3)->[0 0]" f::{[r]; r::(x-(+/!y))%y; :[(r=((_r)%1.0))>0; y,_r; [0 0]]} "g(x) returns all pairs of divisors and series start numbers for a given number, as g(85)->[[2 42] [5 15] [10 4]]" g::{[l n]; l::[]; n::x; {t::f(n;x); ~0>(t@1)} {:[(0=t@0)|(0=t@1); t; l::l,(,t)]; x+1}:~2; l} "h(x) changes the divisor/series start number pairs from g(x) to lists of the series themselves, as h(g(85))->[[42 43] [15 16 17 18 19] [4 5 6 7 8 9 10 11 12 13]]" h::{[l l2]; l::x; l2::[]; {[m n]; m::x@0; n::x@1; n+!m}'l} "go(x) displays the number, ' --> ' and the lists of series, as in '85 --> [[42 43] [15 16 17 1819] [4 5 6 7 8 9 10 11 12 13]]'" go::{.d(x); .d(" --> "); .p(h(g(x)))} "go'2+!100 applies go to the list of numbers from 2 to 101: It is interesting to note that none of the numbers which are powers of 2 have lists, but all of the others do" go'2+!100 ./kg -l consecutive_sums.kg 2 --> [] 3 --> [[1 2]] 4 --> [] 5 --> [[2 3]] 6 --> [[1 2 3]] 7 --> [[3 4]] 8 --> [] 9 --> [[4 5] [2 3 4]] 10 --> [[1 2 3 4]] 11 --> [[5 6]] 12 --> [[3 4 5]] 13 --> [[6 7]] 14 --> [[2 3 4 5]] 15 --> [[7 8] [4 5 6] [1 2 3 4 5]] 16 --> [] 17 --> [[8 9]] 18 --> [[5 6 7] [3 4 5 6]] 19 --> [[9 10]] 20 --> [[2 3 4 5 6]] 21 --> [[10 11] [6 7 8] [1 2 3 4 5 6]] 22 --> [[4 5 6 7]] 23 --> [[11 12]] 24 --> [[7 8 9]] 25 --> [[12 13] [3 4 5 6 7]] 26 --> [[5 6 7 8]] 27 --> [[13 14] [8 9 10] [2 3 4 5 6 7]] 28 --> [[1 2 3 4 5 6 7]] 29 --> [[14 15]] 30 --> [[9 10 11] [6 7 8 9] [4 5 6 7 8]] 31 --> [[15 16]] 32 --> [] 33 --> [[16 17] [10 11 12] [3 4 5 6 7 8]] 34 --> [[7 8 9 10]] 35 --> [[17 18] [5 6 7 8 9] [2 3 4 5 6 7 8]] 36 --> [[11 12 13] [1 2 3 4 5 6 7 8]] 37 --> [[18 19]] 38 --> [[8 9 10 11]] 39 --> [[19 20] [12 13 14] [4 5 6 7 8 9]] 40 --> [[6 7 8 9 10]] 41 --> [[20 21]] 42 --> [[13 14 15] [9 10 11 12] [3 4 5 6 7 8 9]] 43 --> [[21 22]] 44 --> [[2 3 4 5 6 7 8 9]] 45 --> [[22 23] [14 15 16] [7 8 9 10 11] [5 6 7 8 9 10] [1 2 3 4 5 6 7 8 9]] 46 --> [[10 11 12 13]] 47 --> [[23 24]] 48 --> [[15 16 17]] 49 --> [[24 25] [4 5 6 7 8 9 10]] 50 --> [[11 12 13 14] [8 9 10 11 12]] 51 --> [[25 26] [16 17 18] [6 7 8 9 10 11]] 52 --> [[3 4 5 6 7 8 9 10]] 53 --> [[26 27]] 54 --> [[17 18 19] [12 13 14 15] [2 3 4 5 6 7 8 9 10]] 55 --> [[27 28] [9 10 11 12 13] [1 2 3 4 5 6 7 8 9 10]] 56 --> [[5 6 7 8 9 10 11]] 57 --> [[28 29] [18 19 20] [7 8 9 10 11 12]] 58 --> [[13 14 15 16]] 59 --> [[29 30]] 60 --> [[19 20 21] [10 11 12 13 14] [4 5 6 7 8 9 10 11]] 61 --> [[30 31]] 62 --> [[14 15 16 17]] 63 --> [[31 32] [20 21 22] [8 9 10 11 12 13] [6 7 8 9 10 11 12] [3 4 5 6 7 8 9 10 11]] 64 --> [] 65 --> [[32 33] [11 12 13 14 15] [2 3 4 5 6 7 8 9 10 11]] 66 --> [[21 22 23] [15 16 17 18] [1 2 3 4 5 6 7 8 9 10 11]] 67 --> [[33 34]] 68 --> [[5 6 7 8 9 10 11 12]] 69 --> [[34 35] [22 23 24] [9 10 11 12 13 14]] 70 --> [[16 17 18 19] [12 13 14 15 16] [7 8 9 10 11 12 13]] 71 --> [[35 36]] 72 --> [[23 24 25] [4 5 6 7 8 9 10 11 12]] 73 --> [[36 37]] 74 --> [[17 18 19 20]] 75 --> [[37 38] [24 25 26] [13 14 15 16 17] [10 11 12 13 14 15] [3 4 5 6 7 8 9 10 11 12]] 76 --> [[6 7 8 9 10 11 12 13]] 77 --> [[38 39] [8 9 10 11 12 13 14] [2 3 4 5 6 7 8 9 10 11 12]] 78 --> [[25 26 27] [18 19 20 21] [1 2 3 4 5 6 7 8 9 10 11 12]] 79 --> [[39 40]] 80 --> [[14 15 16 17 18]] 81 --> [[40 41] [26 27 28] [11 12 13 14 15 16] [5 6 7 8 9 10 11 12 13]] 82 --> [[19 20 21 22]] 83 --> [[41 42]] 84 --> [[27 28 29] [9 10 11 12 13 14 15] [7 8 9 10 11 12 13 14]] 85 --> [[42 43] [15 16 17 18 19] [4 5 6 7 8 9 10 11 12 13]] 86 --> [[20 21 22 23]] 87 --> [[43 44] [28 29 30] [12 13 14 15 16 17]] 88 --> [[3 4 5 6 7 8 9 10 11 12 13]] 89 --> [[44 45]] 90 --> [[29 30 31] [21 22 23 24] [16 17 18 19 20] [6 7 8 9 10 11 12 13 14] [2 3 4 5 6 7 8 9 10 11 12 13]] 91 --> [[45 46] [10 11 12 13 14 15 16] [1 2 3 4 5 6 7 8 9 10 11 12 13]] 92 --> [[8 9 10 11 12 13 14 15]] 93 --> [[46 47] [30 31 32] [13 14 15 16 17 18]] 94 --> [[22 23 24 25]] 95 --> [[47 48] [17 18 19 20 21] [5 6 7 8 9 10 11 12 13 14]] 96 --> [[31 32 33]] 97 --> [[48 49]] 98 --> [[23 24 25 26] [11 12 13 14 15 16 17]] 99 --> [[49 50] [32 33 34] [14 15 16 17 18 19] [7 8 9 10 11 12 13 14 15] [4 5 6 7 8 9 10 11 12 13 14]] 100 --> [[18 19 20 21 22] [9 10 11 12 13 14 15 16]] 101 --> [[50 51]] Klong 20190209 xxxyyy
/* In fact there are FOUR ways to take consecutive integers summing to 15: is another solution. Suppose the w numbers starting at p (p, ..., p-1+w) add up to n. This is wp + w(w-1)/2. So w(2p+w-1) = 2n. We must have w divides 2n and 2p+w-1 = 2n/w, so for w = 1, 2, ... while w*w < 2n if w divides 2n then t := 2n/w - w + 1 if t is even then (t/2,w) is a solution */ #include <stdio.h> #include <stdlib.h> static void consecs(int n) { int w, q, r, t; printf("%d:\n", n); n += n; w = 0; while (w++, w*w < n) { if (n % w == 0) { t = n / w - w + 1; if ((t&1) == 0) printf(" %d@%d\n", w, t>>1); } } printf("\n"); } int main(int argc, char **argv) { if (argc < 2) { consecs(15); } else for (int i = 1; i < argc; i++) { consecs(atoi(argv[i])); } return 0; }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:
[code lang="c"] int main() { return 0; } [/code]@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.
#include <stdio.h> #include <stdlib.h> int main(int argc, char* argv[]) { if (argc != 2) return EXIT_FAILURE; int x = atoi(argv[1]); for (int i = 1;; ++i) { int y = x / i; int z = y - i / 2 + !(i % 2); if (z < 1) break; int sum = i * y; if (i % 2 == 0) sum += i / 2; if (sum == x) { for (int j = z; j < i + z; ++j) { if (j > z) printf("+"); printf("%d", j); } printf("\n"); } } return EXIT_SUCCESS; }Example Usage: