# 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,

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

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

That is,

Then,

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