August 2023 - Solution
August 2023 Solution:
The numerical solutions are 66 for googol and 653124034718489245484923772216924660058607596119243405888292084074025349410485980501955062384795 7752
for googolplex.
Since this is a very well-known problem, it can be solved by a quick journey to Wikipedia:
Of course, it can be argued that part of the fun is finding a formula independently without resorting to known results.
For googol, a formula is enough; for googolplex some manipluation of the formula is required, which results in a complex floating-point computation. A "*" was given for any good approximation resulting from this computation; a "**" was given to those who obtained an exact solution. The most common way to do this is by using an arbitrary precision floating point library such as `mpmath`:
One possible way of solving the problem with general prior knowledge in number theory but not specific for square- triangular numbers is by using the method for solving **Pell's equation** after a suitable reduction of the problem to it (the exact derivation is given in Wikipedia).
Another simple solution requiring only elementary tools in combinatorics is looking in the first few elements on the sequence:
1, 6, 35, 204, 1189, 6930, 40391, 235416, \dotsAnd the first and second difference seqeunces:
1, 5, 29, 169, 985, 5741, 33461, 195025,\dots
4, 24, 140, 816, 4756, 27720, 161564, \dots
It can be seen that the second difference sequence is the original sequence multiplied by 4; with little algebra this gives the recurrence relation
a_n = 6a_{n-1} - a_{n-2}
which can be solved to obtain
a_n = \frac{\alpha^n-\beta^n}{4\sqrt{2}}
\alpha = 3+2\sqrt{2}
\beta = 3-2\sqrt{2}
For googolplex it gives us
n = \left\lfloor \frac{10^{100}+\log_{10}{4\sqrt{2}}}{\alpha}\right\rfloor
We end up with a problem in high-precision floating point arithmetic. A common solution many solvers used was to turn to a suitable library, e.g. Python's mpmath.