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.
It’s an interesting problem indeed.
It makes me wonder – can one formulate a program to find harmonic progressions of a similarly created array?
Here’s a solution in C++11.
Build/Run:
Output:
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.
Build/Run:
Output:
Great puzzle! My solution in Python:
@DavidLiu: Your solution takes cubic time to find the triples, the suggested solution takes linear time.
@programmingpraxis, quadratic time, as you mention in the solution.
@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
in
array_threes
take cubic time.In Python.
Another Python solution. Using set is convenient. Bisection on x[j+1:] would also work.
Another version. This is faster (in Python) than doing the scan.
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] == (2x[1]*x[3] / (x[1] + x[3])))
function main{T <: Real}(x::Array{T, 1}, pt::AbstractString = “a”)
pt = lowercase(pt)
n = length(x)
end
BTW, I figured it would be nice to include the Harmonic progression option, since that’s an interesting series to consider…