Detailed mathematical approach

Problem Summary

A 3-smooth number is a positive integer of the form \(2^a3^b\) with \(a,b\ge 0\). For a given \(n\), define

$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}.$

We must count the permutations of \(\mathcal{S}(n)\) with the rule that whenever \(x\mid y\), the number \(x\) must appear earlier than \(y\). If \(F(n)\) denotes that count, the checkpoints used by the implementations are

$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}.$

The key simplification is that divisibility among numbers \(2^a3^b\) is just coordinatewise order on the exponent pair \((a,b)\). That turns the problem into counting linear extensions of a finite Ferrers-shaped poset.

Mathematical Approach

Represent each element of \(\mathcal{S}(n)\) by its exponent pair. Then

$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d.$

So the admissible permutations are exactly the linear extensions of the set of lattice points \((a,b)\) satisfying \(2^a3^b\le n\).

Step 1: Convert the exponent set into a partition

Fix a value of \(b\). The admissible values of \(a\) are those with \(2^a\le n/3^b\). Therefore the row length is

$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor,$

for every \(b\) such that \(3^b\le n\). As \(b\) increases, \(n/3^b\) decreases, so the row lengths are nonincreasing. Hence they form a partition

$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor.$

Geometrically, the cell in row \(b+1\) and column \(a+1\) corresponds to the number \(2^a3^b\).

Step 2: Interpret valid permutations as standard tableaux

Assign to every cell the position of its number inside the permutation. The divisibility rule says that if one cell is weakly north-west of another, its label must be smaller. Therefore a valid permutation is equivalent to a filling of the Ferrers diagram with \(1,2,\dots,N\) that increases from left to right and from top to bottom, where

$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r.$

That is exactly a standard Young tableau of shape \(\lambda\).

Step 3: Apply the hook-length formula

The number of standard Young tableaux of shape \(\lambda\) is

$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}.$

If \(\lambda'_c\) is the height of column \(c\), then the hook length of cell \((r,c)\) is

$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1.$

In words, the hook counts the cell itself, every cell to its right in the same row, and every cell below it in the same column.

Step 4: Why this formula matches the divisibility poset

The exponent pairs form a left-justified diagram, and moving one step right multiplies by \(2\) while moving one step down multiplies by \(3\). Both moves increase the number, so both moves must also increase the permutation label. The partial order is therefore the usual row-and-column order of a Ferrers diagram. Hook-length theory applies directly, which removes any need to enumerate permutations.

Step 5: Worked example for \(n=8\)

The 3-smooth numbers up to \(8\) are

$1,\ 2,\ 3,\ 4,\ 6,\ 8.$

The corresponding Ferrers shape is

$\lambda=(4,2),$

because the row for \(b=0\) contains \(1,2,4,8\) and the row for \(b=1\) contains \(3,6\). The hook lengths are

$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$

so

$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9.$

This matches the checkpoint and shows the full method on a small instance.

How the Code Works

The C++, Python, and Java implementations use the same pipeline. First they enumerate the rows by stepping through powers of \(3\). For each row they determine the largest admissible power of \(2\) with integer operations, so the row length is computed exactly without floating-point roundoff.

Next they sum all row lengths to obtain \(N\), then compute the height of every column by counting how many rows reach that column. With these two arrays available, the implementation visits every cell once, evaluates its hook length, and multiplies all hooks into one exact denominator.

After that the implementation forms \(N!\) as an arbitrary-precision integer and divides by the hook product to obtain \(F(n)\). The C++ implementation also includes an exact-divisibility guard before the final division, which is a useful sanity check even though the theorem guarantees that the quotient is an integer. Finally the exact integer is rendered in scientific notation with 10 digits after the decimal point, using decimal-string rounding instead of floating-point arithmetic.

Complexity Analysis

Let \(R=1+\lfloor \log_3 n\rfloor\) and \(W=1+\lfloor \log_2 n\rfloor\). Constructing the row lengths costs \(O(R)\). Computing column heights by scanning the row lengths costs \(O(RW)\). Multiplying all hook lengths touches each cell once, which is \(O(N)\) with

$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n).$

Therefore the combinatorial part of the algorithm is \(O(RW)=O(\log^2 n)\). The extra array storage is \(O(R+W)\), while the dominant arithmetic cost comes from multiplying and dividing arbitrary-precision integers whose size grows with the final answer.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=462
2. 3-smooth numbers / regular numbers: Wikipedia — Regular number
3. Ferrers and Young diagrams: Wikipedia — Young diagram
4. Hook-length formula: Wikipedia — Hook-length formula
5. Linear extension of a poset: Wikipedia — Linear extension