Arithmetic Progressions

October 24, 2017

Here is our solution:

(define (arith-progs xs)
  (define (signum x) (if (< x 0) -1 (if (< 0 x) 1 0)))
  (define (x i) (vector-ref xs i))
  (define len (vector-length xs))
  (do ((j 1 (+ j 1))) ((= j (- len 1)))
    (let loop ((i (- j 1)) (k (+ j 1)))
      (when (and (<= 0 i) (< k len))
        (case (signum (+ (x i) (x k) (* (x j) -2)))
        ((-1) (loop i (+ k 1)))
        ((1)  (loop (- i 1) k))
        (else (display (list (x i) (x j) (x k))) (newline)
              (loop (- i 1) (+ k 1))))))))

Three array elements Xi, Xj and Xk form an arithmetic progression if and only if Xi + Xk = 2 × Xj. We loop over all possible j, testing for arithmetic progressions at each combination of i and k, decrementing i or incrementing k as appropriate. Here are some examples:

> (arith-progs '#(1 2 3 4 6 7 9))
(1 2 3)
(2 3 4)
(2 4 6)
(1 4 7)
(3 6 9)
> (arith-progs '#(1 3 4 6 7 8 9))
(1 4 7)
(4 6 8)
(3 6 9)
(6 7 8)
(7 8 9)

Our program to find geometric progressions is similar:

(define (geo-progs xs)
  (define (signum x) (if (< x 0) -1 (if (< 0 x) 1 0)))
  (define (x i) (vector-ref xs i))
  (define len (vector-length xs))
  (do ((j 1 (+ j 1))) ((= j (- len 1)))
    (let loop ((i (- j 1)) (k (+ j 1)))
      (when (and (<= 0 i) (< k len))
        (case (signum (- (/ (x j) (x i)) (/ (x k) (x j))))
        ((-1) (loop (- i 1) k))
        ((1)  (loop i (+ k 1)))
        (else (display (list (x i) (x j) (x k))) (newline)
              (loop (- i 1) (+ k 1))))))))

And here are our examples:

> (geo-progs '#(1 2 3 4 6 7 9))
(1 2 4)
(1 3 9)
(4 6 9)
> (geo-progs '#(1 3 4 6 7 8 9))
(1 3 9)
(4 6 9)

Both solutions take time O(n2). You can run the program at https://ideone.com/it0Gl6.

Advertisements

Pages: 1 2

11 Responses to “Arithmetic Progressions”

  1. It’s an interesting problem indeed.
    It makes me wonder – can one formulate a program to find harmonic progressions of a similarly created array?

  2. Daniel said

    Here’s a solution in C++11.

    /* arithmetic_progressions.cpp */
    
    #include <array>
    #include <stdio.h>
    #include <vector>
    
    using std::array;
    using std::vector;
    
    typedef unsigned int uint;
    
    void arithmetic_progressions(
            const vector<uint>& v, vector<vector<uint>>* output) {
        for (size_t j = 1; j < v.size() - 1; ++j) {
            uint val_j = v[j];
            size_t i = j - 1;
            size_t k = j + 1;
            while (true) {
                if (i < 0 || k >= v.size()) break;
                uint val_i = v[i];
                uint val_k = v[k];
                uint i_diff = val_j - val_i;
                uint k_diff = val_k - val_j;
                if (i_diff == k_diff) {
                    output->push_back({val_i, val_j, val_k});
                }
                if (k_diff > i_diff) {
                    --i;
                } else {
                    ++k;
                }
            }
        }
    }
    
    int main() {
        vector<uint> v = {1, 2, 3, 4, 6, 7, 9};
        vector<vector<uint>> output;
        arithmetic_progressions(v, &output);
        for (const auto& p : output) {
            printf("[%d,%d,%d]\n", p[0], p[1], p[2]);
        }
    }
    

    Build/Run:

    $ g++ -std=c++11 -o arithmetic_progressions arithmetic_progressions.cpp
    $ ./arithmetic_progressions 
    

    Output:

    [1,2,3]
    [0,2,4]
    [2,3,4]
    [0,3,6]
    [2,4,6]
    [1,4,7]
    [3,6,9]
    
  3. Daniel said

    Here’s my updated, code, fixing a bug in my last post. My bug arises from checking if unsigned int i is less than 0. I changed size_t to int for that variable.

    I originally used ints and my program worked. I changed to size_t and didn’t check if the output was still correct, which led to the bug in my earlier post.

    /* arithmetic_progressions.cpp */
    
    #include <array>
    #include <stdio.h>
    #include <vector>
    
    using std::array;
    using std::vector;
    
    typedef unsigned int uint;
    
    void arithmetic_progressions(
            const vector<uint>& v, vector<vector<uint>>* output) {
        for (size_t j = 1; j < v.size() - 1; ++j) {
            uint val_j = v[j];
            int i = j - 1;
            size_t k = j + 1;
            while (true) {
                if (i < 0 || k >= v.size()) break;
                uint val_i = v[i];
                uint val_k = v[k];
                uint i_diff = val_j - val_i;
                uint k_diff = val_k - val_j;
                if (i_diff == k_diff) {
                    output->push_back({val_i, val_j, val_k});
                }
                if (k_diff > i_diff) {
                    --i;
                } else {
                    ++k;
                }
            }
        }
    }
    
    int main() {
        vector<uint> v = {1, 2, 3, 4, 6, 7, 9};
        vector<vector<uint>> output;
        arithmetic_progressions(v, &output);
        for (const auto& p : output) {
            printf("[%d,%d,%d]\n", p[0], p[1], p[2]);
        }
    }
    

    Build/Run:

    $ g++ -std=c++11 -o arithmetic_progressions arithmetic_progressions.cpp
    $ ./arithmetic_progressions 
    

    Output:

    [1,2,3]
    [2,3,4]
    [2,4,6]
    [1,4,7]
    [3,6,9]
    
  4. David Liu said

    Great puzzle! My solution in Python:

    def array_threes(arr1):
        # Takes a larger array and returns all the permutations smaller arrays of size 3.
    
        for i in arr1[:-2]:
            for j in arr1[i:-1]:
                for k in arr1[j:]:
                    yield([i,j,k])
    
    def array_diff(arr1):
        # Takes the difference between successive numbers in an array
        diff = []
        arr2 = arr1[1:]
        
        for a2, a1 in zip(arr2, arr1):
            diff.append(a2 - a1)
    
        return(diff)
    
          
    def arith_prog(arr1):
        # Finds size-3 arithmetic progressions in an any sized array
        threes = []
        
        for threes in array_threes(arr1):
            diff = array_diff(threes)
            if diff[0]==diff[1]:
                yield(threes)
    
    array_test = [1, 2, 3, 4, 6, 7 ,9]
    
    for y in arith_prog(array_test):
        print(y)
    
  5. programmingpraxis said

    @DavidLiu: Your solution takes cubic time to find the triples, the suggested solution takes linear time.

  6. Daniel said

    “…the suggested solution takes linear time.”

    @programmingpraxis, quadratic time, as you mention in the solution.

  7. programmingpraxis said

    @Daniel. You are correct. I correctly stated the time complexity of the suggested solution as quadratic in the text of the exercise, but incorrectly stated that it is linear in my comment.

    My comment about the time complexity of David Liu’s solution stands: the triply-nested loops

    for i ... for j ... for k ...

    in array_threes take cubic time.

  8. Paul said

    In Python.

    def prog(arr):
        n = len(arr)
        for j, aj in enumerate(arr):
            i, k, target = 0, n-1, 2*aj
            while i < j < k:
                test = arr[i] + arr[k]
                if test == target:
                    yield arr[i], aj, arr[k]
                    i, k = i+1, k-1
                elif test > target:
                    k -= 1
                else:
                    i += 1
    
  9. Jan Van lent said

    Another Python solution. Using set is convenient. Bisection on x[j+1:] would also work.

    def ap3(x):
        # x assumed sorted
        n = len(x)
        s = set(x[2:])
        for i in range(n-2):
            for j in range(i+1, n-1):
                xk = x[j] + (x[j] - x[i])
                if xk in s:
                    yield (x[i], x[j], xk)
    
    x = [1, 2, 3, 4, 6, 7, 9]
    print(list(ap3(x)))
    
  10. Paul said

    Another version. This is faster (in Python) than doing the scan.

    def prog(arr):
        S = set(arr)
        for a, b in combinations(arr, 2):
            if 2*b - a in S:
                yield a, b, 2*b - a
    
  11. Zack said

    That’s a nifty little problem. Here is my take on it, using Julia…

    IsArithmetic{T <: Real}(x::Array{T, 1}) = (2x[2] == x[1] + x[3])
    IsGeometric{T <: Real}(x::Array{T, 1}) = (x[2]^2 == x[1] * x[3])
    IsHarmonic{T <: Real}(x::Array{T, 1}) = (x[2] == (2
    x[1]*x[3] / (x[1] + x[3])))

    function main{T <: Real}(x::Array{T, 1}, pt::AbstractString = “a”)
    pt = lowercase(pt)
    n = length(x)

    if pt == "a"
        println("Searching for Arithmetic progressions...\n")
        check = IsArithmetic
    elseif pt == "g"
        println("Searching for Geometric progressions...\n")
        check = IsGeometric
    elseif pt == "h"
        println("Searching for Harmonic progressions...\n")
        check = IsHarmonic
    else
        println("Progression parameter should be one of the following: a, g, or h")
        return
    end
    
    for i = 1:(n-2)
        for j = (i+1):(n-1)
            for k = (j+1):n
                z = [x[i], x[j], x[k]]
                if check(z); println(z); end
            end     
        end
    end
    
    return
    

    end

    BTW, I figured it would be nice to include the Harmonic progression option, since that’s an interesting series to consider…

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: