Detailed mathematical approach

Problem Summary

For each integer \(k \ge 4\), let \(M(k)\) be the maximum possible sum of a geometric progression of positive integers with at least three terms, common ratio greater than \(1\), and largest term at most \(k\). The final target is the alternating total

$A(N)=\sum_{k=4}^{N}(-1)^k M(k).$

The real input is extremely large, so the solution cannot scan all geometric progressions and certainly cannot evaluate \(M(k)\) one value of \(k\) at a time. The key is to compress both the family of relevant progressions and the places where the maximum can actually change.

Mathematical Approach

The three implementations are based on the same reduction: first write every admissible integer geometric progression in a canonical form, then keep only the candidates that can ever be optimal, and finally evaluate the alternating sum block by block.

Step 1: Parametrize Every Integer Geometric Progression

Take a geometric progression with \(p+1\) terms, where \(p \ge 2\), common ratio \(a/b\) in lowest terms, and \(a > b \ge 1\). Because all terms must be integers, the progression can be written as

$q b^p,\ q a b^{p-1},\ q a^2 b^{p-2},\ \dots,\ q a^p,$

with some integer scale factor \(q \ge 1\). Its largest term is \(q a^p\), and its sum is

$q\sum_{i=0}^{p} a^i b^{p-i}=q\,\frac{a^{p+1}-b^{p+1}}{a-b}.$

So for fixed \(a\), \(b\), and \(p\), the best scale factor allowed by the bound \(k\) is

$q=\left\lfloor \frac{k}{a^p} \right\rfloor.$

Step 2: The Best Ratio Always Has Consecutive Numerator and Denominator

For fixed \(a\), \(p\), and \(q\), the sum

$q\sum_{i=0}^{p} a^i b^{p-i}$

is strictly increasing in \(b\), because every term with exponent \(p-i > 0\) grows when \(b\) grows. Since \(b\) must satisfy \(1 \le b < a\), the best admissible choice is always

$b=a-1.$

Therefore only progressions of the form

$q(a-1)^p,\ q a (a-1)^{p-1},\ \dots,\ q a^p$

need to be considered. Their largest term and one-step contribution are

$P(a,p)=a^p,\qquad \Delta(a,p)=a^{p+1}-(a-1)^{p+1}.$

For a fixed \(k\), this candidate contributes

$V_{a,p}(k)=\left\lfloor \frac{k}{P(a,p)} \right\rfloor \Delta(a,p).$

Hence

$M(k)=\max_{a \ge 2,\ p \ge 2} V_{a,p}(k).$

Step 3: Discard Dominated Candidates and Keep Only Records

If two candidates satisfy

$P_1 \le P_2,\qquad \Delta_1 \ge \Delta_2,$

then for every \(k\),

$\left\lfloor \frac{k}{P_1} \right\rfloor \Delta_1 \ge \left\lfloor \frac{k}{P_2} \right\rfloor \Delta_2,$

so the second candidate can never be optimal. The implementations therefore build only the record frontier: whenever the jump amount \(\Delta\) increases, they keep the smallest possible period \(P\) that achieves this new record. Because \(a^p \le N\), the exponent \(p\) only ranges up to \(\lfloor \log_2 N \rfloor\), and for each exponent the next record can be found by binary search on \(a\).

Step 4: Compute an Activity Bound for Each Record

Even among record candidates, many are useful only for a finite interval of \(k\). Suppose candidate \(j\) has a better asymptotic slope than candidate \(i\), meaning

$\frac{\Delta_j}{P_j} > \frac{\Delta_i}{P_i} \iff \Delta_j P_i > \Delta_i P_j.$

Then

$V_j(k)\ge \left(\frac{k}{P_j}-1\right)\Delta_j,\qquad V_i(k)\le \frac{k}{P_i}\Delta_i.$

So candidate \(j\) is guaranteed to beat candidate \(i\) whenever

$\left(\frac{k}{P_j}-1\right)\Delta_j > \frac{k}{P_i}\Delta_i,$

which simplifies to

$k > \frac{\Delta_j P_j P_i}{\Delta_j P_i-\Delta_i P_j}.$

For each record candidate, the implementations take the minimum such bound over all stronger competitors. This produces a proven upper activity limit \(R\): once \(k > R\), that candidate can never again attain the maximum.

Step 5: \(M(k)\) Can Change Only at Event Points

For one fixed candidate, the quantity \(\left\lfloor k / P \right\rfloor\) changes only when \(k\) reaches a multiple of \(P\). Therefore \(V_{a,p}(k)\) is constant between consecutive multiples of \(P\). After activity pruning, \(M(k)\) can change only at the union of all multiples of retained periods \(P\) up to \(\min(N,R)\). These integers are the event points. Once they are collected and sorted, every interval between consecutive events has a constant value of \(M(k)\).

Step 6: Evaluate the Alternating Sum by Constant Blocks

If \(M(k)=C\) for every \(k \in [L,R]\), then that whole block contributes

$C\sum_{k=L}^{R}(-1)^k.$

The inner sign sum is elementary:

$\sum_{k=L}^{R}(-1)^k= \begin{cases} 0, & R-L+1 \text{ is even},\\ 1, & R-L+1 \text{ is odd and } L \text{ is even},\\ -1, & R-L+1 \text{ is odd and } L \text{ is odd}. \end{cases}$

So the total is accumulated blockwise. Exact recomputation of the maximum is needed only at event points, not at every integer up to \(N\).

Worked Example: Small Values up to \(12\)

The first useful candidates are

$a=2,\ p=2:\quad (1,2,4),\qquad V_{2,2}(k)=7\left\lfloor \frac{k}{4} \right\rfloor,$

$a=2,\ p=3:\quad (1,2,4,8),\qquad V_{2,3}(k)=15\left\lfloor \frac{k}{8} \right\rfloor,$

$a=3,\ p=2:\quad (4,6,9),\qquad V_{3,2}(k)=19\left\lfloor \frac{k}{9} \right\rfloor.$

Up to \(12\), the event points are \(4,8,9,12\). Therefore

$\begin{aligned} 4 \le k \le 7&:&&M(k)=7,\\ 8 \le k \le 8&:&&M(k)=14,\\ 9 \le k \le 11&:&&M(k)=19,\\ 12 \le k \le 12&:&&M(k)=21. \end{aligned}$

In particular, \(M(4)=7\), \(M(10)=19\), and \(M(12)=21\). The alternating total up to \(12\) is

$A(12)=0+14-19+21=16,$

because the block \([4,7]\) has even length and contributes \(0\). This is exactly the kind of block compression the implementations exploit at the full scale.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they determine all admissible exponents \(p\) with \(2^p \le N\), and for each such exponent they use integer roots to bound the search range for \(a\). Then they repeatedly raise the current record jump amount and use binary search to find the smallest base \(a\) that beats it for each exponent. Among those contenders, the implementation keeps the one with the smallest period \(a^p\), which yields the next record candidate on the frontier.

Next, the implementations compare every pair of retained candidates and assign each one an activity limit using the inequality from Step 4. After that, they generate all event points by listing the multiples of every retained period up to the smaller of the global limit and that candidate's activity bound. The list is sorted and duplicates are removed.

Finally, they sweep from \(4\) to \(N\). Between two successive event points the maximum sum is constant, so the code adds either \(0\), the block value, or its negation according to the parity rule above. At an event point it recomputes the exact maximum over the still-relevant candidates. The C++ version uses wide integer arithmetic and multiprecision only where overflow could occur; Python relies on arbitrary-precision integers naturally; Java uses big integers where the crossover calculation needs them.

Complexity Analysis

Let \(C\) be the number of retained record candidates and \(E\) the number of distinct event points. Let \(P_{\max}=\lfloor \log_2 N \rfloor\). Building the record frontier requires scanning those exponents and performing binary searches on the admissible base range, so the preprocessing cost is driven by about \(C\) record extractions across \(P_{\max}\) exponent families. The pairwise activity-bound computation costs \(O(C^2)\). Event generation costs \(O(E)\) insertions plus \(O(E \log E)\) for sorting and deduplication. The final sweep is \(O(E \cdot C)\) in the worst case because an event-point recomputation may inspect every retained candidate, although the activity limits keep the practical active set much smaller. The memory usage is \(O(C+E)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=542
2. Geometric progression: Wikipedia — Geometric progression
3. Geometric series: Wikipedia — Geometric series
4. Floor function: Wikipedia — Floor and ceiling functions
5. Upper envelope: Wikipedia — Upper envelope