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

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 2

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 3

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 4

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.