Solution to "Geometric Subsets (Big Number Challenge)"


There are 1973093124882606298882104993483387674675038805 17-element subsets of \{1, 2, 3, \dots, 33^{33}\} that form a geometric sequence. My solution follows.

Since we're dealing with such huge numbers, it may be better to think about things in a more generalized manner. That is, let's see how to find the number of k-element subsets of the set A=\{1, 2, 3, \dots, n\} that form a geometric sequence. Any such subset will have the form \{ar^0, ar^1, ar^2, \dots, ar^{k-1}\}, where a and r are natural numbers and r\ge 2. Notice that we will have a different geometric sequence for different values of a. So for any given r we will have a k-element subset for each natural number a given that the largest term ar^{k-1} does not exceed n. Then for any r, ar^{k-1}\le n. That is,

a_{\text{max}}=\left\lfloor\frac{n}{r^{k-1}}\right\rfloor.

This also means that for any given r we have a_{\text{max}} k-element subsets of A that form a geometric sequence with that particular ratio r. Now we just sum those up over all possible r. But notice that when r^{k-1} exceeds n (that is, we no longer are dealing with subsets of A), then the value of a_{\text{max}} will equal zero. Thus we can simply sum each a_{\text{max}} for r=2 to infinity.

In other words, let f(n,k) be a function which describes the number of k-element subsets of the set \{1, 2, 3, \dots, n\} that form a geometric sequence. Then

f(n,k)=\sum_{r=2}^{\infty}\left\lfloor\frac{n}{r^{k-1}}\right\rfloor.

The problem with this is that the question asks for a final answer. Obviously we can't tell a computer to sum to infinity. So there are two ways to do it. We can either find a max value for r or we can check each time to see if \left\lfloor\frac{n}{r^{k-1}}\right\rfloor=0. When it does we can stop summing.

To find a max for r, we want to know when r^{k-1} exceeds n. Then we have

r^{k-1}\le n,\text{ or}

r\le n^{1/(k-1)}.

That is,

r_{\text{max}}=\left\lfloor n^{1/(k-1)}\right\rfloor.

Then,

f(n,k)=\sum_{r=2}^{\left\lfloor n^{1/(k-1)}\right\rfloor}\left\lfloor\frac{n}{r^{k-1}}\right\rfloor.

Now we can use a program which can handle huge numbers to quickly find the solution. I used the wonderful, free PARI/GP. (Follow link to download or if using Linux check your distro's package manager for it.) Other programs/languages which handle huge numbers are Maple and Mathematica. Here is the code I used to obtain the solution in PARI/GP:

? f(n,k)=sum(r=2,floor(n^(1/(k-1))),floor(n/r^(k-1)));
? f(33^33,17)
%2 = 1973093124882606298882104993483387674675038805