Max Geometric Sequences

Add-on: After A little discussion with Steve, I believe we are looking for the largest sum geometric sequence with integer values that is at least 3 integers long. We can generalize my previous code to check up to which prime powers n is divisible by. If any of those generate a higher sum, we take that as the new sum. Otherwise we use the old result of n-1's best sum:

ClearAll["`*"] (*max prime exponent*) maxPrimePower[n_] := Max@FactorInteger[n][[All, 2]] (*value of geometric sum*) sumValue[r_, p_] := Sum[(r)^k, {k, 0, p}] // FullSimplify // Evaluate (*max integer of the form z^k that divides n*) maxKPowerDivisor[n_, k_] := Module[{primes, pows}, {primes, pows} = Transpose@FactorInteger[n]; pows = Quotient[pows, k]; Times @@ MapThread[Power, {primes, pows}] ] (*initialize with the best geometric sum for n=4*) getMaxSumSeqAnyLength[4] = {1, 2, 4}; getMaxSumSeqAnyLength[n_ /; n >= 4] := getMaxSumSeqAnyLength[n] = Block[{$RecursionLimit = Infinity}, Module[{bestSeq, maxSumSeen, maxXSeen, maxP, bestDivisors, bestRList, sumValues, bestIndex, bestR}, bestSeq = getMaxSumSeqAnyLength[n - 1]; maxSumSeen = Total@bestSeq; maxXSeen = Last@bestSeq; maxP = maxPrimePower[n]; If[maxP > 1, bestDivisors = maxKPowerDivisor[n, #] & /@ Range[2, maxP]; bestRList = (bestDivisors - 1)/bestDivisors; sumValues = n*MapIndexed[sumValue[#1, #2[[1]] + 1] &, bestRList]; If[Max@sumValues > maxSumSeen, bestIndex = PositionLargest[sumValues, 1][[1, 1]]; bestR = bestRList[[bestIndex]]; bestSeq = n*(bestR^Range[0, bestIndex + 1]) // Reverse; ]; ]; bestSeq ] ] 

So for example:

getMaxSumSeqAnyLength[1000] (*{729, 810, 900, 1000}*) 

returns a length 4 geometric sequence.

Note for really large n, this is a little finnicky. Calling getMaxSumSeqAnyLength[10000] for example right after definition will crash the kernel, but if we preload the downvalues in steps of 1000 we can evaluate it:

Table[getMaxSumSeqAnyLength[1000 n], {n, 10}]; getMaxSumSeqAnyLength[10000] (*{6561, 7290, 8100, 9000, 10000}*) 

I feel like there's something pretty basic I'm missing about recursive functions/memoization that should allow evaluation to happen without having to preload the downvalues in small steps.

---

Your geometric sum we want to maximize will look like (I am kind of thinking about this backwards, where we start at the maximum value of the sequence, and $r<1$ so we move down to next lowest value of the sequence): $$ \begin{align} x ~ (r^2 + r^1 + 1)\\ \\ r \in \mathbb{Q} ~\land ~ r < 1 \\ \\ x \in \mathbb{Z} ~\land ~1 \leq x \leq n \end{align} $$ Where $x$ is the starting point, and $r$ is the ratio of the geometric sequence. Now expand $r$ with its integer numerator $a$ and denominator $d$: $$ r = \frac{a}{d} $$

In order for the smallest value of the sequence $$ x r^2 = x\frac{ a^2}{d^2} $$ to be an integer, $x$ must not be squarefree, and $x$ must be divisible by the square of $r$'s denominator $d^2$.

It also follows that since $d^2$ divides $x$, any integer value for the numerator $a$ will still make the sequence integer-valued. So we should pick $a$ to be as large as possible (to maximize our sum) while still having $r < 1$:

$$ a = d-1\\ r = \frac{d-1}{d} $$

Since we want $r$ to be as close to 1 as possible, we select the biggest $d$ s.t. $d^2$ divides $n$.

---

As you pointed out, the geometric sequences all with values less than $n-1$ are part of the geometric sequences for $n$, so the maximum sum can never decrease. We also know that the largest value $x(n)$ of the maximum sum sequence for $n$ is bounded by:

$$ x(n-1) \leq x(n) \leq n $$

And we know $x(n)$ is not squarefree, since it must be divisible by $d^2$. Since we know that all the previous values less than $n$ have been checked, we just need to check if $n$ is not squarefree, and then calculate if its sum

$$ n \left(\left(\frac{d-1}{d}\right)^2 + \frac{d-1}{d} + 1\right) $$ is larger than the previous best sum ending in $x(n-1)$, where $d$ is the largest integer such that $d^2$ divides $n$.

---

We can make a recursive function, where we iteravely round down the largest value in the geometric sequence $x$ to the nearest non-squarefree integer, find the largest square that is a divisor, and see if it does better than the previously best observed sequence:

ClearAll[getMaxSumSeq] (*initialize with the best geometric sum for n=4*) getMaxSumSeq[4] = {1, 2, 4}; getMaxSumSeq[n_ /; n >= 4] := getMaxSumSeq[n] = Block[{$RecursionLimit = Infinity}, Module[{bestSeq, maxSumSeen, maxXSeen, x, d, r, testSeq, testSum}, (*initialize bestSeq,maxSumSeen, maxNSeen as previous number's best sequence*) bestSeq = getMaxSumSeq[n - 1]; maxSumSeen = Total@bestSeq; maxXSeen = Last@bestSeq; (*check if n has a square factor*) If[SquareFreeQ[n] == False, (*set x to n*) x = n; (*largest square divisor*) d = Last@Select[Sqrt@Divisors[x], IntegerQ]; (*maximal geometric ratio*) r = (d - 1)/d; (*generate sequence*) testSeq = x*{r^2, r, 1}; (*and sum*) testSum = Total@testSeq; (*compare to best sum seen so far,if the sum is larger, record the sequence as the best*) If[testSum > maxSumSeen, maxSumSeen = testSum; bestSeq = testSeq; ]; ]; (*output best sequence*) bestSeq] ] 

Compare this to the brute force method:

bruteForce[n_] := MaximalBy[ Select[Subsets[Range@n, {3}], Differences@Ratios@# == {0} &], Total] // First getMaxSumSeq[100] // AbsoluteTiming bruteForce[100] // AbsoluteTiming (*{0.003176, {81, 90, 100}}*) (*{0.216285, {81, 90, 100}}*) 

And test for equality:

And @@ Table[bruteForce[n] == getMaxSumSeq[n], {n, 4, 100}] (*True*) 

---

If you are also interested in geometric sequences with lengths other than 3, we can use the same method. Suppose we want to maximize a geometric sequence of length $l$. We can write the sum as

$$ x \sum_{i=0}^{l-1} r^i = x \frac{ r^l-1}{r-1} $$

We can show like before that $d^{l-1}$ must divide $x$, and in order to maximize the sum $a = d^{l-1} -1$. We now just check if $n$ has a prime exponent greater than or equal to $l-1$, find all the maximum $d_k$ such that $d_1^2, d_2^3, ..., d_{l-2}^{l-1}$ divide $n$, and (if it's larger than the previous best sum) return the sequence that gives the largest sum.