Someone recently posted a puzzle involving geometric series. It goes like this:
From the set of integers in range [1..4000,000,000], in how many ways that we can pick 6 different integers from the set, and those 6 numbers form a geometric progression?
From the big range of the set, we can see that brute force won’t cut it. However, after some analysis, a smarter approach can be applied here. The following is the step-by-step approach I took when I pondered this puzzle.
Consider the following facts:
* In a geometric series, the 6th term of a series which starts with a as its 1st term is: a r^5 where r is obviously the constant ratio between successive terms.
* We can visualize r as a fraction n / d, where both n and d are integers. We can safely consider only n and d pairs with n > d (which means we’ll just get the strictly ascending series). So, visualizing ratios as n / d, we see the 6th term as a n^5 / d^5.
Then I started thinking about the simplest series with ratio 2 / 1. The smallest valid progression is:
1 2 4 8 16 32
We immediately see that an integer multiple k of the above progression is also valid as long as 32 x k does not exceed 4,000,000,000 which is the maximum integer in the set. We can see that the largest possible k is floor(4,000,000,000 / 32) = 125,000,000. More generally, the number of valid integer multiples can be obtained by doing an integer division of the maximum number in the set by the highest term of the 6 numbers in the smallest valid progression of this ratio.
Let’s move on with another example with ratio 4 / 1. The smallest valid progression is:
1 4 16 64 256 1024
And we’ll have floor(4,000,000,000 / 1024) = 3,906,250 valid progressions from the set.
Now it is obvious that we’ll start with the integer ratios like 2 or 4. However, the trick to this puzzle is also to see that the ratio might not be an integer as the puzzle only seeks to pick 6 integers which forms geometric progression.
To find out more about this, I started looking at n / d and for each n, I walked up the d part from 1 up to n-1, as those will be the ratios to look at. I skipped 4 / 2 (same as 2 / 1) because this is not a simple fraction, and thus would already be taken care of when dealing with ratios with n = 2.
Next value of d is 3, which is interesting to look at. We can see that for a ratio of 4 / 3, the first term of the series has to be a multiple of 3^5. Otherwise, we won’t be having integer terms because to get each successive term, we’d have to divide by 3. So, the smallest valid progression for ratio 4 / 3 is:
243 324 432 576 768 1024
The a-ha moment came when I saw that the smallest progressions of both ratio 4 / 1 and 4 / 3 shares the same high number (6th term), which is 1024, or 4^5, or even more generally n^5. This would mean that it would also have the same number of valid integer multiples, which is 3,906,250. That is, for a particular simple fraction ratio n / d, the number of valid progressions is floor(MAX / n^5).
I got excited. We can then ponder how many valid d‘s, each of which is less than n, and the pair n, d is relatively prime to each other to avoid non-simple fractions. This is none other than the well-known Euler’s Totient function. Combine this with the number of valid integer multiples of a progression, we know that for a particular numerator n, the number of ways to pick 6 integers which forms a geometric progression is:
f(n) = phi(n) x floor(MAX / (n^5)),
where phi is the Euler’s Totient function, and MAX is the maximum integer value in the set (in this case, 4,000,000,000).
Now, we just need to find the sum of all f(n) for n values of 2, 3, 4, … all the way until f(n) yields 0.
Take a look at the Python code for this puzzle.
