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.

Advertisements

Pages: 1 2

15 Responses to “Consecutive Sums”

  1. Zack said

    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

    for i = 1:n
        for j = (i+1):n1
            if sum(i:j) == x
                c += 1
                S[c] = collect(i:j)
                break
            end
        end
    end
    
    return S[1:c]
    

    end

    Cheers!

  2. Ernie said

    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.

  3. matthew said

    @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).

  4. matthew said

    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 -= 1
    

    And 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:

    1 [(1, 1)]
    3 [(1, 2), (3, 3)]
    9 [(2, 4), (4, 5), (9, 9)]
    15 [(1, 5), (4, 6), (7, 8), (15, 15)]
    45 [(1, 9), (5, 10), (7, 11), (14, 16), (22, 23), (45, 45)]
    105 [(1, 14), (6, 15), (12, 18), (15, 20), (19, 23), (34, 36), (52, 53), (105, 105)]
    
  5. Globules said

    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]
    
  6. Smith said
    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)
    
     [1]
     [1, 2]
     [1, 2, 3]
     [1, 2, 3, 4]
    * [1, 2, 3, 4, 5]
     [2, 3, 4, 5]
     [2, 3, 4, 5, 6]
     [3, 4, 5, 6]
    * [4, 5, 6]
     [5, 6]
     [5, 6, 7]
     [6, 7]
     [6, 7, 8]
    * [7, 8]
     [8]
     [8, 9]
    
  7. Carl Vereen said

    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;
        }
    
    }
    
    
    
  8. Steve said

    Can’t seem to post my entry

  9. Jim said
    
    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
    xxx
    

    yyy

  10. Richard A. O'Keefe said
    /* 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;
    }
  11. Richard A. O'Keefe said

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

  12. matthew said

    ie. do something like this:

    [code lang="c"]
    int main() {
        return 0;
    }
    [/code]
    
  13. programmingpraxis said

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

  14. Daniel said

    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:

    $ ./a.out 3
    3
    1+2
    
    $ ./a.out 10
    10
    1+2+3+4
    
    $ ./a.out 15
    15
    7+8
    4+5+6
    1+2+3+4+5
    
    $ ./a.out 20
    20
    2+3+4+5+6
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: