Detailed mathematical approach

Problem Summary

The problem asks for the largest total number of integers in \(1,\dots,N\) that can be arranged into pairwise non-overlapping local \(123\)-blocks. Every positive integer has a unique representation

$n=m\,2^a3^b,\qquad \gcd(m,6)=1,$

so the search splits into independent components indexed by the part \(m\) that is coprime to \(6\). Inside one component, only \(2^a3^b\)-smooth multipliers matter, and the final answer is the sum of the optimal local contributions.

Mathematical Approach

Write \(A(N)\) for the required optimum. The fast solution has two layers: first solve one component exactly, then sum those component values over all possible \(m\).

Step 1: Split by the part coprime to 6

Fix \(m\) with \(\gcd(m,6)=1\) and let

$L=\left\lfloor\frac{N}{m}\right\rfloor.$

Every integer in \(1,\dots,N\) whose \(6\)-free part is \(m\) can be written uniquely as \(m s\) with

$\mathcal{S}(L)=\{2^a3^b\le L: a,b\ge 0\}.$

Different values of \(m\) never mix, so the global optimum is a sum of independent component optima:

$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}} G\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right),$

where \(G(L)\) denotes the best contribution of one component with smooth bound \(L\).

Step 2: Turn one component into a weighted graph

For a smooth base \(s\in \mathcal{S}(L)\), the local block is

$B_L(s)=\{s,2s,3s\}\cap [1,L].$

After multiplying by \(m\), this becomes \(\{ms,2ms,3ms\}\cap [1,N]\). Its size is

$|B_L(s)|=1+\mathbf{1}_{2s\le L}+\mathbf{1}_{3s\le L}.$

So inside one component we want a collection of smooth bases whose blocks do not overlap, maximizing the total weight contributed by those block sizes.

Step 3: Why only six local conflicts matter

Two local blocks \(B_L(s)\) and \(B_L(t)\) overlap exactly when

$i s=j t\quad \text{for some } i,j\in\{1,2,3\}.$

For distinct \(s\) and \(t\), this is equivalent to

$\frac{t}{s}\in \left\{2,3,\frac{3}{2},\frac{1}{2},\frac{1}{3},\frac{2}{3}\right\}.$

If we write \(s=2^a3^b\), these six ratios become the six neighbor moves

$ (a,b)\leftrightarrow(a\pm 1,b),\qquad (a,b)\leftrightarrow(a,b\pm 1),\qquad (a,b)\leftrightarrow(a+1,b-1),\qquad (a,b)\leftrightarrow(a-1,b+1). $

Thus \(G(L)\) is a maximum-weight independent-set value on the triangular lattice formed by the exponent pairs \((a,b)\) with \(2^a3^b\le L\).

Step 4: Closed form for the component value

The key structural fact used by the implementations is that this graph optimization has a simple exact value:

$G(L)=|\mathcal{S}(L)|-|\mathcal{E}\cap [1,L]|,$

where the exceptional smooth numbers are

$\mathcal{E}=\{6,24,54\}\cup \{384\cdot 8^t:t\ge 0\}\cup \{243\cdot 27^t:t\ge 0\}.$

So every \(2^a3^b\)-smooth number normally contributes one unit to the optimum, and only the explicit exceptional values subtract one unit. All three implementations are based on this identity.

Step 5: Reassemble the global answer

Substituting the component formula into the outer sum gives

$A(N)=\sum_{\substack{1\le m\le N\\ \gcd(m,6)=1}}\left(|\mathcal{S}(\lfloor N/m\rfloor)|-|\mathcal{E}\cap [1,\lfloor N/m\rfloor]|\right).$

This already removes the hard combinatorial search. The remaining work is purely arithmetic: count smooth numbers, count exceptional smooth numbers, and aggregate them over the quotient values \(\lfloor N/m\rfloor\).

Step 6: Group equal quotients into intervals

List the smooth numbers in increasing order. Between two consecutive smooth breakpoints, neither \(|\mathcal{S}(L)|\) nor \(|\mathcal{E}\cap [1,L]|\) changes, because every exceptional number is itself smooth. Hence \(G(L)\) is constant on each interval \([L,R]\), where \(L\) is a smooth number and \(R\) is the next smooth number minus \(1\), or \(R=N\) for the final interval.

For such an interval, the condition

$L\le \left\lfloor\frac{N}{m}\right\rfloor\le R$

is equivalent to

$m_{\mathrm{low}}=\left\lfloor\frac{N}{R+1}\right\rfloor+1,\qquad m_{\mathrm{high}}=\left\lfloor\frac{N}{L}\right\rfloor.$

The count of integers up to \(x\) that are coprime to \(6\) is

$C(x)=x-\left\lfloor\frac{x}{2}\right\rfloor-\left\lfloor\frac{x}{3}\right\rfloor+\left\lfloor\frac{x}{6}\right\rfloor.$

Therefore one quotient interval contributes

$G(L)\left(C(m_{\mathrm{high}})-C(m_{\mathrm{low}}-1)\right).$

Worked Example: \(N=20\)

The integers up to \(20\) that are \(2^a3^b\)-smooth are

$1,2,3,4,6,8,9,12,16,18,$

so \(|\mathcal{S}(20)|=10\). At this scale the only exceptional value is \(6\), so

$G(20)=10-1=9.$

The integers \(m\le 20\) with \(\gcd(m,6)=1\) are

$1,5,7,11,13,17,19.$

The corresponding quotient values are

$\left\lfloor\frac{20}{1}\right\rfloor=20,\quad \left\lfloor\frac{20}{5}\right\rfloor=4,\quad \left\lfloor\frac{20}{7}\right\rfloor=2,\quad \left\lfloor\frac{20}{11}\right\rfloor=\left\lfloor\frac{20}{13}\right\rfloor=\left\lfloor\frac{20}{17}\right\rfloor=\left\lfloor\frac{20}{19}\right\rfloor=1.$

Since \(G(4)=4\), \(G(2)=2\), and \(G(1)=1\), we get

$A(20)=9+4+2+1+1+1+1=19,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations never build the conflict graph explicitly. Instead they first generate all \(2^a3^b\)-smooth numbers up to \(N\), sort them, and remove duplicates. They also generate the exceptional subset up to the same limit.

Next, they scan the smooth list once in increasing order. At each smooth breakpoint they update the current component value \(G(L)\): ordinary smooth numbers increase it by one, while exceptional smooth numbers leave it unchanged because they represent the one-unit loss encoded by the closed form.

Finally, the implementation walks through consecutive breakpoint intervals \([L,R]\), converts each interval into the matching range of \(m\)-values, counts how many of those \(m\) are coprime to \(6\) with the inclusion-exclusion formula for \(C(x)\), and adds the resulting block contribution. Python gets arbitrary-precision arithmetic automatically, while the compiled implementations use a wider accumulator for the final sum.

Complexity Analysis

Let \(S(N)=|\mathcal{S}(N)|\). Since \(2^a3^b\le N\) implies \(0\le a\le \lfloor \log_2 N\rfloor\) and \(0\le b\le \lfloor \log_3 N\rfloor\), we have \(S(N)=O((\log N)^2)\). Generating and sorting the smooth list costs \(O(S(N)\log S(N))\), the exceptional list has only \(O(\log N)\) terms, and the final sweep over the breakpoint intervals is \(O(S(N))\). Memory usage is \(O(S(N))=O((\log N)^2)\).

Footnotes and References

1. Problem page: Project Euler 821
2. Smooth numbers: Wikipedia — Smooth number
3. Independent sets in graphs: Wikipedia — Independent set
4. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
5. Floor function: Wikipedia — Floor and ceiling functions