Project Euler

Permutation of 3-smooth Numbers

A 3-smooth number is an integer whose only prime factors are 2 and 3. For an integer N, let S(N) be the set of 3-smooth numbers <= N. Define F(N) as the number of permutations of S(N) in which each...

Source sync Apr 19, 2026

Problem #0462

Level Level 26

Solved By 395

Languages C++, Python

Answer 5.5350769703e1512

Length 357 words

combinatoricslinear_algebrasearch

A $3$-smooth number is an integer which has no prime factor larger than $3$. For an integer $N$, we define $S(N)$ as the set of <span style="white-space:nowrap;">$3$-smooth</span> numbers less than or equal to $N$. For example, $S(20) = \{ 1, 2, 3, 4, 6, 8, 9, 12, 16, 18 \}$.

We define $F(N)$ as the number of permutations of $S(N)$ in which each element comes after all of its proper divisors.

This is one of the possible permutations for $N = 20$. \[1, 2, 4, 3, 9, 8, 16, 6, 18, 12.\] This is not a valid permutation because $12$ comes before its divisor $6$. \[1, 2, 4, 3, 9, 8, \boldsymbol {12}, 16, \boldsymbol 6, 18\]

We can verify that $F(6) = 5$, $F(8) = 9$, $F(20) = 450$ and $F(1000) \approx 8.8521816557\mathrm e21$.

Find $F(10^{18})$. Give as your answer its scientific notation rounded to ten digits after the decimal point.

When giving your answer, use a lowercase e to separate mantissa and exponent. E.g. if the answer is $112\,233\,445\,566\,778\,899$ then the answer format would be $1.1223344557e17$.

Problem 462: Permutation of 3-smooth Numbers

Mathematical Foundation

Theorem 1 (Poset isomorphism). The set of 3-smooth numbers under divisibility is isomorphic as a poset to the lattice $\{(a, b) \in \mathbb{Z}_{\ge 0}^2\}$ under componentwise $\le$ , via the map $2^a \cdot 3^b \mapsto (a, b)$ .

Proof. The map is a bijection between 3-smooth numbers and pairs $(a, b)$ of non-negative integers. For divisibility: $2^{a_1} 3^{b_1} \mid 2^{a_2} 3^{b_2}$ if and only if $a_1 \le a_2$ and $b_1 \le b_2$ , which is precisely the componentwise order. $\square$

Lemma 1 (Young diagram structure). The set $\{(a, b) : 2^a \cdot 3^b \le N\}$ forms a Young diagram $\lambda = (\lambda_0, \lambda_1, \ldots, \lambda_m)$ where $\lambda_i = \lfloor \log_2(N / 3^i) \rfloor + 1$ for $0 \le i \le m = \lfloor \log_3 N \rfloor$ , and the row lengths are non-increasing.

Proof. For row $i$ (corresponding to $b = i$ ), the constraint $2^a \cdot 3^i \le N$ gives $a \le \lfloor \log_2(N/3^i) \rfloor$ , so the row has $\lambda_i = \lfloor \log_2(N/3^i) \rfloor + 1$ cells (for $a = 0, 1, \ldots$ ). Since $3^{i+1} > 3^i$ , we have $N/3^{i+1} < N/3^i$ , so $\lambda_{i+1} \le \lambda_i$ . Thus the row lengths are non-increasing, forming a valid Young diagram. $\square$

Theorem 2 (Frame—Robinson—Thrall hook-length formula). The number of linear extensions of the poset $\lambda$ (equivalently, the number of standard Young tableaux of shape $\lambda$ ) is:

f^\lambda = \frac{n!}{\displaystyle\prod_{(i,j) \in \lambda} h(i,j)}

where $n = |\lambda|$ is the total number of cells, and $h(i,j) = (\lambda_i - j) + (\lambda'_j - i) - 1$ is the hook length at cell $(i,j)$ , with $\lambda'$ the conjugate partition.

Proof. This is the classical Frame—Robinson—Thrall theorem (1954). The proof proceeds by induction on $n$ : removing a corner cell $(i_0, j_0)$ from $\lambda$ yields a Young diagram $\mu$ , and one shows

f^\lambda = \sum_{\text{corners } (i_0,j_0)} f^\mu

and verifies the hook-length product satisfies the same recurrence. See Frame, Robinson, and Thrall, Canadian J. Math. 6 (1954), 316—324. $\square$

Lemma 2 (Logarithmic computation). For large $n$ , $F(N)$ is computed in floating-point logarithmic form:

\log_{10} F(N) = \sum_{k=1}^{n} \log_{10} k - \sum_{(i,j) \in \lambda} \log_{10} h(i,j)

from which the mantissa and exponent are extracted.

Proof. This follows directly from taking $\log_{10}$ of the hook-length formula. The mantissa $m$ and exponent $e$ satisfy $\log_{10} F = e + m$ with $0 \le m < 1$ , giving $F = 10^m \times 10^e$ . $\square$

Editorial

We build the Young diagram. We then compute conjugate partition. Finally, compute log10(F) via hook-length formula. We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

Build the Young diagram
Compute conjugate partition
Compute log10(F) via hook-length formula
Extract mantissa and exponent

Complexity Analysis

Time: $O(n)$ to enumerate all cells and compute hook lengths, where $n = |S(N)| \sim \frac{(\ln N)^2}{2 \ln 2 \cdot \ln 3}$ . For $N = 10^{18}$ , $n \approx 1107$ .
Space: $O(n)$ for storing the partition and its conjugate.

Answer

\boxed{5.5350769703e1512}

C++ project_euler/problem_462/solution.cpp

/*
 * Project Euler Problem 462: Permutation of 3-smooth Numbers
 *
 * 3-smooth numbers: 2^a * 3^b.
 * S(N) = set of 3-smooth numbers <= N.
 * F(N) = number of linear extensions of S(N) under divisibility.
 *
 * Known: F(6)=5, F(8)=9, F(20)=450, F(1000)~8.8521816557e21
 * Find: F(10^18) ~ 5.5350769703e1512
 *
 * Approach: Hook-length formula on Young diagram.
 * The divisibility poset of 3-smooth numbers forms a staircase Young diagram.
 *
 * Compile: g++ -O2 -o solution solution.cpp -lm
 */

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cassert>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

vector<int> get_staircase(ull N) {
    vector<int> rows;
    ull pow3 = 1;
    while (pow3 <= N) {
        // max a such that 2^a * pow3 <= N
        ull remaining = N / pow3;
        int max_a = 0;
        while ((1ULL << (max_a + 1)) <= remaining) max_a++;
        rows.push_back(max_a + 1);
        if (pow3 > N / 3) break;
        pow3 *= 3;
    }
    return rows;
}

// Exact F(N) for small N using hook-length formula
ll F_exact(ull N) {
    auto rows = get_staircase(N);
    int n = 0;
    for (int r : rows) n += r;

    if (n == 0) return 1;

    int num_rows = rows.size();
    int max_col = rows[0];

    // Column lengths
    vector<int> cols(max_col, 0);
    for (int r : rows) {
        for (int j = 0; j < r; j++) {
            cols[j]++;
        }
    }

    // Compute n! / product of hooks
    // Use double for now (exact for small n)
    ll numerator = 1;
    for (int k = 1; k <= n; k++) numerator *= k;

    ll denominator = 1;
    for (int i = 0; i < num_rows; i++) {
        for (int j = 0; j < rows[i]; j++) {
            int arm = rows[i] - j - 1;
            int leg = cols[j] - i - 1;
            int h = arm + leg + 1;
            denominator *= h;
        }
    }

    return numerator / denominator;
}

// log10(F(N)) for large N
double F_log10(ull N) {
    auto rows = get_staircase(N);
    int n = 0;
    for (int r : rows) n += r;

    if (n == 0) return 0;

    int num_rows = rows.size();
    int max_col = rows[0];

    vector<int> cols(max_col, 0);
    for (int r : rows) {
        for (int j = 0; j < r; j++) {
            cols[j]++;
        }
    }

    // log10(n!)
    double log_nfact = 0;
    for (int k = 1; k <= n; k++) {
        log_nfact += log10((double)k);
    }

    // log10(product of hooks)
    double log_hooks = 0;
    for (int i = 0; i < num_rows; i++) {
        for (int j = 0; j < rows[i]; j++) {
            int arm = rows[i] - j - 1;
            int leg = cols[j] - i - 1;
            int h = arm + leg + 1;
            log_hooks += log10((double)h);
        }
    }

    return log_nfact - log_hooks;
}

int main() {
    cout << "Problem 462: Permutation of 3-smooth Numbers" << endl;
    cout << string(50, '=') << endl;

    // Verify small cases
    cout << "\nExact verification:" << endl;
    for (ull N : {6ULL, 8ULL, 20ULL, 1000ULL}) {
        auto rows = get_staircase(N);
        int n = 0;
        for (int r : rows) n += r;

        cout << "  N=" << N << ": rows=[";
        for (int i = 0; i < (int)rows.size(); i++) {
            if (i) cout << ",";
            cout << rows[i];
        }
        cout << "], n=" << n;

        if (n <= 20) {
            ll f = F_exact(N);
            cout << ", F=" << f << endl;
        } else {
            double log_f = F_log10(N);
            int exp = (int)log_f;
            double mant = pow(10.0, log_f - exp);
            cout << fixed << setprecision(10);
            cout << ", F~" << mant << "e" << exp << endl;
        }
    }

    // Solve for 10^18
    cout << "\nSolving for N = 10^18:" << endl;
    ull N_big = 1000000000000000000ULL;
    auto rows = get_staircase(N_big);
    int n = 0;
    for (int r : rows) n += r;

    cout << "  Staircase: " << rows.size() << " rows, " << n << " elements" << endl;
    cout << "  First 10 rows: ";
    for (int i = 0; i < min((int)rows.size(), 10); i++) {
        cout << rows[i] << " ";
    }
    cout << endl;

    double log_f = F_log10(N_big);
    int exp = (int)log_f;
    double mant = pow(10.0, log_f - exp);

    cout << fixed << setprecision(10);
    cout << "  log10(F) = " << log_f << endl;
    cout << "  F(10^18) ~ " << mant << "e" << exp << endl;

    cout << "\nKnown answer: 5.5350769703e1512" << endl;

    return 0;
}

Python project_euler/problem_462/solution.py

#!/usr/bin/env python3
"""
Project Euler Problem 462: Permutation of 3-smooth Numbers

A 3-smooth number has the form 2^a * 3^b.
S(N) = set of 3-smooth numbers <= N.
F(N) = number of permutations of S(N) where each element comes after
       all its proper divisors (= linear extensions of divisibility poset).

Known: F(6)=5, F(8)=9, F(20)=450, F(1000)~8.8521816557e21
Find: F(10^18) in scientific notation with 10 decimal digits.

Answer: 5.5350769703e1512

Approach: The 3-smooth numbers form a Young-diagram-like poset.
Use the hook-length formula for counting linear extensions.
"""

import math
import sys
from decimal import Decimal, getcontext

# Set high precision for large number computation
getcontext().prec = 2000

def get_3smooth_up_to(N):
    """Generate all 3-smooth numbers <= N, sorted."""
    result = []
    b = 0
    pow3 = 1
    while pow3 <= N:
        a = 0
        val = pow3
        while val <= N:
            result.append(val)
            a += 1
            val = pow3 * (1 << a)
        b += 1
        pow3 *= 3
    result.sort()
    return result

def get_staircase(N):
    """
    Get the staircase shape for 3-smooth numbers <= N.
    Returns list of row lengths: row_lengths[b] = max_a + 1
    where 2^a * 3^b <= N.
    """
    rows = []
    b = 0
    pow3 = 1
    while pow3 <= N:
        # Find max a such that 2^a * 3^b <= N
        max_a = int(math.log2(N / pow3)) if pow3 <= N else -1
        if max_a >= 0:
            rows.append(max_a + 1)  # number of elements in this row
        b += 1
        pow3 *= 3
    return rows

def F_bruteforce(N):
    """Brute force: count linear extensions by generating all valid permutations."""
    smooth = get_3smooth_up_to(N)
    n = len(smooth)

    # Build divisor relation
    # For each element, find its proper divisors in the set
    idx = {v: i for i, v in enumerate(smooth)}
    predecessors = [set() for _ in range(n)]
    for i, v in enumerate(smooth):
        for j, u in enumerate(smooth):
            if u != v and v % u == 0:
                predecessors[i].add(j)

    # Count linear extensions via recursive enumeration
    count = 0
    placed = [False] * n

    def backtrack(pos):
        nonlocal count
        if pos == n:
            count += 1
            return
        for i in range(n):
            if placed[i]:
                continue
            # Check all predecessors are placed
            if all(placed[j] for j in predecessors[i]):
                placed[i] = True
                backtrack(pos + 1)
                placed[i] = False

    backtrack(0)
    return count

def hook_length(rows):
    """
    Compute number of linear extensions using hook-length formula
    for a Young diagram with given row lengths.

    rows must be non-increasing (standard Young diagram).

    F = n! / prod of hook lengths
    """
    n = sum(rows)
    if n == 0:
        return 1

    num_rows = len(rows)

    # Compute column lengths from row lengths
    max_col = rows[0] if rows else 0
    cols = [0] * max_col
    for r in rows:
        for j in range(r):
            cols[j] += 1

    # Compute hook lengths for each cell
    # hook(i, j) = (rows[i] - j) + (cols[j] - i) - 1
    #            = arm_length + leg_length + 1
    hook_product_log = 0.0
    for i in range(num_rows):
        for j in range(rows[i]):
            arm = rows[i] - j - 1
            leg = cols[j] - i - 1
            h = arm + leg + 1
            hook_product_log += math.log10(h)

    # F = n! / product of hooks
    # log10(F) = log10(n!) - sum(log10(hooks))
    log_n_fact = sum(math.log10(k) for k in range(1, n + 1))
    log_F = log_n_fact - hook_product_log

    return log_F

def hook_length_exact(rows):
    """Exact computation using Python arbitrary precision."""
    n = sum(rows)
    if n == 0:
        return 1

    num_rows = len(rows)
    max_col = rows[0] if rows else 0
    cols = [0] * max_col
    for r in rows:
        for j in range(r):
            cols[j] += 1

    # Compute n! / product of hooks
    numerator = math.factorial(n)
    denominator = 1
    for i in range(num_rows):
        for j in range(rows[i]):
            arm = rows[i] - j - 1
            leg = cols[j] - i - 1
            h = arm + leg + 1
            denominator *= h

    return numerator // denominator

def solve(N):
    """
    Solve F(N) for 3-smooth numbers.

    The poset of 3-smooth numbers under divisibility corresponds to
    lattice points (a, b) with 2^a * 3^b <= N, ordered componentwise.

    The staircase shape is a Young diagram (row lengths are non-increasing
    since increasing b means smaller max_a).

    Number of linear extensions = n! / product of hook lengths.
    """
    rows = get_staircase(N)

    # Verify rows are non-increasing (valid Young diagram)
    for i in range(1, len(rows)):
        assert rows[i] <= rows[i-1], f"Not a valid Young diagram: {rows}"

    n = sum(rows)
    print(f"  N = {N}")
    print(f"  Number of 3-smooth numbers: {n}")
    print(f"  Staircase rows: {rows}")

    if N <= 10000:
        # Use exact computation
        F = hook_length_exact(rows)
        print(f"  F({N}) = {F}")
        return F
    else:
        # Use logarithmic computation
        log_F = hook_length(rows)
        exponent = int(log_F)
        mantissa = 10 ** (log_F - exponent)
        print(f"  log10(F({N})) = {log_F:.6f}")
        print(f"  F({N}) ~ {mantissa:.10f}e{exponent}")
        return log_F

def solve_large(N):
    """Solve for very large N using Stirling and high-precision log."""
    rows = get_staircase(N)
    n = sum(rows)

    print(f"  N = {N:.2e}")
    print(f"  Number of 3-smooth numbers: {n}")
    print(f"  Number of rows: {len(rows)}")
    print(f"  Row lengths: {rows[:10]}... (first 10)")

    # Compute log10(F) = log10(n!) - sum(log10(hook_lengths))
    # Use Stirling for n!: log10(n!) = n*log10(n) - n*log10(e) + 0.5*log10(2*pi*n)

    # For precision, compute with Decimal
    D = Decimal

    log10 = lambda x: D(x).ln() / D(10).ln()

    # log10(n!)
    log_n_fact = D(0)
    for k in range(1, n + 1):
        log_n_fact += log10(k)

    # Hook lengths
    max_col = rows[0]
    cols = [0] * max_col
    for r in rows:
        for j in range(r):
            cols[j] += 1

    log_hooks = D(0)
    for i in range(len(rows)):
        for j in range(rows[i]):
            arm = rows[i] - j - 1
            leg = cols[j] - i - 1
            h = arm + leg + 1
            log_hooks += log10(h)

    log_F = log_n_fact - log_hooks

    exponent = int(log_F)
    mantissa_log = log_F - exponent
    mantissa = D(10) ** mantissa_log

    print(f"  log10(F) = {log_F}")
    print(f"  F({N:.2e}) ~ {mantissa:.10f}e{exponent}")

    return float(log_F), float(mantissa), exponent

def create_visualization():
    """Create visualization for the 3-smooth numbers problem."""