Geometrical progression with any number row

Question

I can have any number row which consists from 2 to 10 numbers. And from this row, I have to get geometrical progression.

For example: Given number row: 125 5 625 I have to get answer 5. Row: 128 8 512 I have to get answer 4.

Can you give me a hand? I don't ask for a program, just a hint, I want to understand it by myself and write a code by myself, but damn, I have been thinking the whole day and couldn't figure this out.

Thank you.

DON'T WRITE THE WHOLE PROGRAM!

Guys, you don't get it, I can't just simple make a division. I actually have to get geometrical progression + show all numbers. In 128 8 512 row all numbers would be: 8 32 128 512

Answer 1

Seth's answer is the right one. I'm leaving this answer here to help elaborate on why the answer to 128 8 512 is 4 because people seem to be having trouble with that.

---

A geometric progression's elements can be written in the form c*b^n where b is the number you're looking for (b is also necessarily greater than 1), c is a constant and n is some arbritrary number.

So the best bet is to start with the smallest number, factorize it and look at all possible solutions to writing it in the c*b^n form, then using that b on the remaining numbers. Return the largest result that works.

So for your examples:

125 5 625

Start with 5. 5 is prime, so it can be written in only one way: 5 = 1*5^1. So your b is 5. You can stop now, assuming you know the row is in fact geometric. If you need to determine whether it's geometric then test that b on the remaining numbers.

128 8 512

8 can be written in more than one way: 8 = 1*8^1, 8 = 2*2^2, 8 = 2*4^1, 8 = 4*2^1. So you have three possible values for b, with a few different options for c. Try the biggest first. 8 doesn't work. Try 4. It works! 128 = 2*4^3 and 512 = 2*4^4. So b is 4 and c is 2.

3 15 375

This one is a bit mean because the first number is prime but isn't b, it's c. So you'll need to make sure that if your first b-candidate doesn't work on the remaining numbers you have to look at the next smallest number and decompose it. So here you'd decompose 15: 15 = 15*?^0 (degenerate case), 15 = 3*5^1, 15 = 5*3^1, 15 = 1*15^1. The answer is 5, and 3 = 3*5^0, so it works out.

Answer 2

Edit: I think this should be correct now.

This algorithm does not rely on factoring, only on the Euclidean Algorithm, and a close variant thereof. This makes it slightly more mathematically sophisticated then a solution that uses factoring, but it will be MUCH faster. If you understand the Euclidean Algorithm and logarithms, the math should not be a problem.

(1) Sort the set of numbers. You have numbers of the form ab^{n1} < .. < ab^{nk}.

Example: (3 * 2, 3*2^5, 3*2^7, 3*2^13)

(2) Form a new list whose nth element of the (n+1)st element of the sorted list divided by the (n)th. You now have b^{n2 - n1}, b^{n3 - n2}, ..., b^{nk - n(k-1)}.

(Continued) Example: (2^4, 2^2, 2^6)

Define d_i = n_(i+1) - n_i (do not program this -- you couldn't even if you wanted to, since the n_i are unknown -- this is just to explain how the program works).

(Continued) Example: d_1 = 4, d_2 = 2, d_3 = 6

Note that in our example problem, we're free to take either (a = 3, b = 2) or (a = 3/2, b = 4). The bottom line is any power of the "real" b that divides all entries in the list from step (2) is a correct answer. It follows that we can raise b to any power that divides all the d_i (in this case any power that divides 4, 2, and 6). The problem is we know neither b nor the d_i. But if we let m = gcd(d_1, ... d_(k-1)), then we CAN find b^m, which is sufficient.

NOTE: Given b^i and b^j, we can find b^gcd(i, j) using:

log(b^i) / log(b^j) = (i log b) / (j log b) = i/j

This permits us to use a modified version of the Euclidean Algorithm to find b^gcd(i, j). The "action" is all in the exponents: addition has been replaced by multiplication, multiplication with exponentiation, and (consequently) quotients with logarithms:

import math
def power_remainder(a, b):
    q = int(math.log(a) / math.log(b))
    return a / (b ** q)        

def power_gcd(a, b):
    while b != 1:
    a, b = b, power_remainder(a, b)
    return a

(3) Since all the elements of the original set differ by powers of r = b^gcd(d_1, ..., d_(k-1)), they are all of the form cr^n, as desired. However, c may not be an integer. Let me know if this is a problem.

Answer 3

The simplest approach would be to factorize the numbers and find the greatest number they have in common. But be careful, factorization has an exponential complexity so it might stop working if you get big numbers in the row.

Answer 4

What you want is to know the Greatest Common Divisor of all numbers in a row.

One method is to check if they all can be divided by the smaller number in the row.

If not, try half the smaller number in the row.

Then keep going down until you find a number that divides them all or your divisor equals 1.

Answer 5

Seth Answer is not correct, applyin that solution does not solves 128 8 2048 row for example (2*4^x), you get: 8 128 2048 => 16 16 => GCD = 16

It is true that the solution is a factor of this result but you will need to factor it and check one by one what is the correct answer, in this case you will need to check the solutions factors in reverse order 16, 8, 4, 2 until you see 4 matches all the conditions.