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.
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\).
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\).
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\).
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.
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.
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.
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.
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.
Eine 3-glatte Zahl ist eine positive ganze Zahl der Form \(2^a3^b\) mit \(a,b\ge 0\). Für ein gegebenes \(n\) sei
$$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}.$$
Gesucht ist die Anzahl der Permutationen von \(\mathcal{S}(n)\) mit der Bedingung, dass bei \(x\mid y\) die Zahl \(x\) früher als \(y\) erscheinen muss. Bezeichnen wir diese Anzahl mit \(F(n)\), so verwenden die Implementierungen die Kontrollwerte
$$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}.$$
Die entscheidende Vereinfachung besteht darin, dass Teilbarkeit zwischen Zahlen \(2^a3^b\) genau der koordinatenweisen Ordnung der Exponentenpaare \((a,b)\) entspricht. Damit wird die Aufgabe zu einem Zählproblem für lineare Erweiterungen eines Ferrers-förmigen Posets.
Wir stellen jedes Element von \(\mathcal{S}(n)\) durch sein Exponentenpaar dar. Dann gilt
$$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d.$$
Also sind die zulässigen Permutationen genau die linearen Erweiterungen der Gitterpunkte \((a,b)\) mit \(2^a3^b\le n\).
Fixiere einen Wert \(b\). Zulässig sind genau die \(a\)-Werte mit \(2^a\le n/3^b\). Daher ist die Zeilenlänge
$$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor,$$
für jedes \(b\) mit \(3^b\le n\). Da \(n/3^b\) mit wachsendem \(b\) abnimmt, sind diese Zeilenlängen nichtzunehmend. Sie bilden also eine Partition
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor.$$
Geometrisch steht die Zelle in Zeile \(b+1\) und Spalte \(a+1\) für die Zahl \(2^a3^b\).
Jeder Zelle wird ihre Position in der Permutation zugewiesen. Die Teilbarkeitsbedingung sagt: Liegt eine Zelle schwach nordwestlich von einer anderen, dann muss ihre Marke kleiner sein. Deshalb entspricht eine gültige Permutation genau einer Füllung des Ferrers-Diagramms mit \(1,2,\dots,N\), die nach rechts und nach unten streng wächst, wobei
$$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r.$$
Genau das ist ein Standard-Young-Tableau der Form \(\lambda\).
Die Anzahl der Standard-Young-Tableaux der Form \(\lambda\) ist
$$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}.$$
Bezeichnet \(\lambda'_c\) die Höhe der Spalte \(c\), dann lautet die Hakenlänge der Zelle \((r,c)\)
$$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1.$$
Der Haken zählt also die Zelle selbst, alle Zellen rechts davon in derselben Zeile und alle Zellen darunter in derselben Spalte.
Die Exponentenpaare bilden ein linksbündiges Diagramm. Ein Schritt nach rechts entspricht der Multiplikation mit \(2\), ein Schritt nach unten der Multiplikation mit \(3\). Beide Schritte vergrößern die Zahl und daher auch den zulässigen Permutationsrang. Die partielle Ordnung ist somit genau die übliche Zeilen-Spalten-Ordnung eines Ferrers-Diagramms. Darum kann die Hakenlängenformel unmittelbar verwendet werden, ohne Permutationen explizit zu durchsuchen.
Die 3-glatten Zahlen bis \(8\) sind
$$1,\ 2,\ 3,\ 4,\ 6,\ 8.$$
Das zugehörige Ferrers-Diagramm hat die Form
$$\lambda=(4,2),$$
denn die Zeile für \(b=0\) enthält \(1,2,4,8\), und die Zeile für \(b=1\) enthält \(3,6\). Die Hakenlängen sind
$$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$$
also
$$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9.$$
Das stimmt mit dem Kontrollwert überein und zeigt die gesamte Methode an einem kleinen Beispiel.
Die Implementierungen in C++, Python und Java benutzen dieselbe Verarbeitungskette. Zuerst erzeugen sie die Zeilen, indem sie die Potenzen von \(3\) durchlaufen. Für jede Zeile bestimmen sie den größten zulässigen Exponenten von \(2\) mit reiner Ganzzahlarithmetik; dadurch entstehen die Zeilenlängen ohne Rundungsfehler aus Fließkommaarithmetik.
Danach werden alle Zeilenlängen zu \(N\) addiert. Anschließend wird für jede Spalte ihre Höhe berechnet, also wie viele Zeilen diese Spalte noch enthalten. Mit diesen beiden Strukturen besucht die Implementierung jede Zelle genau einmal, berechnet ihre Hakenlänge und multipliziert alle Haken zu einem exakten Nenner.
Danach wird \(N!\) als Zahl beliebiger Präzision aufgebaut und durch das Hakenprodukt geteilt, um \(F(n)\) zu erhalten. Die C++-Implementierung enthält vor der letzten Division zusätzlich eine explizite Ganzzahligkeitsprüfung; das ist ein nützlicher Sicherheitscheck, obwohl die Theorie die Ganzzahligkeit bereits garantiert. Am Ende wird der exakte Wert mit 10 Nachkommastellen in wissenschaftlicher Schreibweise formatiert, wobei die Rundung auf Dezimalstrings und nicht auf Gleitkommazahlen basiert.
Sei \(R=1+\lfloor \log_3 n\rfloor\) die Zeilenzahl und \(W=1+\lfloor \log_2 n\rfloor\) die Breite der ersten Zeile. Das Erzeugen der Zeilenlängen kostet \(O(R)\). Das Berechnen der Spaltenhöhen durch Scannen der Zeilenlängen kostet \(O(RW)\). Das Multiplizieren aller Hakenlängen besucht jede Zelle einmal, also \(O(N)\) mit
$$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n).$$
Damit ist der kombinatorische Teil des Verfahrens \(O(RW)=O(\log^2 n)\). Der zusätzliche Arrayspeicher beträgt \(O(R+W)\); die dominierende Rechenlast entsteht durch Multiplikation und Division von Ganzzahlen beliebiger Präzision, deren Größe von der Ausgabezahl abhängt.
3-smooth sayı, \(a,b\ge 0\) olmak üzere \(2^a3^b\) biçimindeki pozitif tamsayıdır. Verilen bir \(n\) için
$$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}$$
kümesini tanımlayalım. Amaç, \(\mathcal{S}(n)\) kümesinin şu kurala uyan permütasyonlarını saymaktır: \(x\mid y\) ise \(x\), \(y\)'den önce gelmelidir. Bu sayıya \(F(n)\) dersek, implementasyonların kullandığı kontrol değerleri şunlardır:
$$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}.$$
Temel sadeleştirme şudur: \(2^a3^b\) biçimindeki sayılarda bölünebilme, üs çiftleri \((a,b)\) üzerinde koordinat bazlı sıralamaya eşittir. Böylece problem, sonlu bir Ferrers şeklinin lineer uzantılarını sayma problemine dönüşür.
Her elemanı üs çiftiyle gösterelim. O zaman
$$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d.$$
Dolayısıyla uygun permütasyonlar, \(2^a3^b\le n\) koşulunu sağlayan kafes noktalarının lineer uzantılarıdır.
Sabit bir \(b\) değeri alalım. Uygun \(a\) değerleri \(2^a\le n/3^b\) koşulunu sağlar. Bu yüzden satır uzunluğu
$$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor$$
olur; burada \(3^b\le n\) olmalıdır. \(b\) arttıkça \(n/3^b\) azaldığı için satır uzunlukları artmaz. Böylece
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor$$
şeklinde bir bölüşüm elde ederiz. Geometrik olarak \(b+1\). satır, \(a+1\). sütundaki hücre \(2^a3^b\) sayısını temsil eder.
Her hücreye, temsil ettiği sayının permütasyondaki konumunu yazalım. Bölünebilme kuralı, kuzeybatıda kalan bir hücrenin etiketinin daha küçük olması gerektiğini söyler. Bu nedenle geçerli bir permütasyon, Ferrers diyagramının \(1,2,\dots,N\) sayılarıyla soldan sağa ve yukarıdan aşağıya artacak şekilde doldurulmasına denktir; burada
$$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r.$$
Bu da tam olarak \(\lambda\) şekilli bir standart Young tablosudur.
\(\lambda\) şekilli standart Young tablolarının sayısı
$$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}$$
ile verilir. Eğer \(\lambda'_c\), \(c\). sütunun yüksekliği ise \((r,c)\) hücresinin kanca uzunluğu
$$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1$$
olur. Yani hücrenin kendisi, sağındaki aynı satır hücreleri ve altındaki aynı sütun hücreleri birlikte sayılır.
Üs çiftleri sola yaslı bir şekil oluşturur. Sağa bir adım gitmek sayıyı \(2\) ile, aşağı bir adım gitmek ise \(3\) ile çarpmaktır. Her iki hareket de sayıyı büyüttüğü için permütasyondaki konum da büyümelidir. Böylece kısmi sıralama, Ferrers diyagramının klasik satır-sütun sıralamasıyla aynıdır. Bu yüzden hook-length kuramı doğrudan uygulanır; olası tüm permütasyonları denemeye gerek kalmaz.
\(8\)'e kadar olan 3-smooth sayılar
$$1,\ 2,\ 3,\ 4,\ 6,\ 8$$
şeklindedir. Buna karşılık gelen Ferrers şekli
$$\lambda=(4,2)$$
olur; çünkü \(b=0\) satırında \(1,2,4,8\), \(b=1\) satırında ise \(3,6\) vardır. Kanca uzunlukları
$$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$$
olduğundan
$$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9$$
elde edilir. Bu değer kontrol sonucu ile aynıdır ve yöntemin tamamını küçük bir örnekte gösterir.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(3\)'ün kuvvetleri üzerinden giderek satırları üretirler. Her satır için uygun en büyük \(2\) üssü tamamen tamsayı işlemleriyle bulunur; böylece satır uzunluğu kayan nokta yuvarlama hatası olmadan hesaplanır.
Sonra tüm satır uzunlukları toplanarak \(N\) elde edilir. Ardından her sütunun yüksekliği, o sütuna kadar uzanan satırların sayısı sayılarak bulunur. Bu iki bilgiyle implementasyon her hücreyi bir kez ziyaret eder, kanca uzunluğunu hesaplar ve tüm kancaları tek bir tam paydaya çarpar.
Bundan sonra \(N!\) çok büyük tamsayı olarak oluşturulur ve kanca çarpımına bölünerek \(F(n)\) elde edilir. C++ implementasyonu son bölmeden önce bölünebilirliği ayrıca kontrol eder; teorem zaten tam sayı çıktısını garanti etse de bu iyi bir iç tutarlılık denetimidir. Son aşamada kesin sonuç, kayan nokta kullanmadan, ondalık dizge üzerinde yuvarlanarak virgülden sonra 10 basamaklı bilimsel gösterime çevrilir.
\(R=1+\lfloor \log_3 n\rfloor\) satır sayısı, \(W=1+\lfloor \log_2 n\rfloor\) ise ilk satır genişliği olsun. Satır uzunluklarını oluşturmak \(O(R)\) zaman alır. Sütun yüksekliklerini satırları tarayarak bulmak \(O(RW)\) maliyetlidir. Tüm kancaları çarpmak her hücreyi bir kez ziyaret eder; bu da
$$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n)$$
olmak üzere \(O(N)\)'dir. Böylece kombinatoryal kısım \(O(RW)=O(\log^2 n)\) karmaşıklığındadır. Ek dizi belleği \(O(R+W)\) kadardır; asıl ağır maliyet, büyüklüğü sonuca bağlı olan çok hassas tamsayı çarpma ve bölme işlemleridir.
Un número 3-smooth es un entero positivo de la forma \(2^a3^b\) con \(a,b\ge 0\). Para un \(n\) dado definimos
$$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}.$$
Hay que contar las permutaciones de \(\mathcal{S}(n)\) que respetan la regla de divisibilidad: si \(x\mid y\), entonces \(x\) debe aparecer antes que \(y\). Si llamamos \(F(n)\) a ese número, los valores de comprobación usados por las implementaciones son
$$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}.$$
La simplificación central es que la divisibilidad entre números \(2^a3^b\) coincide exactamente con el orden coordenado sobre el par de exponentes \((a,b)\). Por eso el problema se convierte en contar extensiones lineales de un poset con forma de diagrama de Ferrers.
Representemos cada elemento de \(\mathcal{S}(n)\) por su par de exponentes. Entonces
$$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d.$$
Así, las permutaciones válidas son exactamente las extensiones lineales del conjunto de puntos \((a,b)\) que satisfacen \(2^a3^b\le n\).
Fijemos un valor de \(b\). Los valores admisibles de \(a\) son los que cumplen \(2^a\le n/3^b\). Por tanto, la longitud de la fila es
$$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor,$$
para cada \(b\) con \(3^b\le n\). Como \(n/3^b\) decrece cuando \(b\) aumenta, estas longitudes de fila son no crecientes y forman una partición
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor.$$
Geométricamente, la celda de la fila \(b+1\) y la columna \(a+1\) representa el número \(2^a3^b\).
Asignamos a cada celda la posición de su número en la permutación final. La regla de divisibilidad implica que una celda situada al noroeste de otra debe recibir una etiqueta menor. Por lo tanto, una permutación válida equivale a rellenar el diagrama de Ferrers con \(1,2,\dots,N\) de forma creciente hacia la derecha y hacia abajo, donde
$$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r.$$
Esa es exactamente la definición de un tableau estándar de Young de forma \(\lambda\).
El número de tableaux estándar de Young de forma \(\lambda\) es
$$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}.$$
Si \(\lambda'_c\) denota la altura de la columna \(c\), entonces la longitud del gancho de la celda \((r,c)\) es
$$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1.$$
Es decir, cuenta la propia celda, todas las celdas a su derecha en la misma fila y todas las celdas por debajo en la misma columna.
Los pares de exponentes forman un diagrama alineado a la izquierda. Moverse una casilla a la derecha multiplica por \(2\), y moverse una casilla hacia abajo multiplica por \(3\). Ambos movimientos aumentan el número y, por tanto, también deben aumentar la posición en la permutación. Así, el orden parcial es precisamente el orden habitual por filas y columnas de un diagrama de Ferrers. La teoría de ganchos se aplica directamente y evita explorar permutaciones una a una.
Los números 3-smooth hasta \(8\) son
$$1,\ 2,\ 3,\ 4,\ 6,\ 8.$$
La forma de Ferrers correspondiente es
$$\lambda=(4,2),$$
porque la fila con \(b=0\) contiene \(1,2,4,8\), mientras que la fila con \(b=1\) contiene \(3,6\). Las longitudes de gancho son
$$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$$
y por tanto
$$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9.$$
Este valor coincide con el punto de control y muestra el método completo en un caso pequeño.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero enumeran las filas recorriendo las potencias de \(3\). Para cada fila determinan el mayor exponente admisible de \(2\) usando aritmética entera, de modo que la longitud de fila se obtiene exactamente, sin errores de redondeo de coma flotante.
Después suman todas las longitudes de fila para obtener \(N\). A continuación calculan la altura de cada columna contando cuántas filas alcanzan esa columna. Con esas dos estructuras, la implementación visita cada celda una vez, evalúa su gancho y multiplica todos los ganchos en un único denominador exacto.
Luego forma \(N!\) como entero de precisión arbitraria y divide por el producto de ganchos para obtener \(F(n)\). La implementación en C++ añade además una comprobación explícita de divisibilidad exacta antes de la división final; es una buena verificación interna aunque el teorema ya garantice que el cociente es entero. Finalmente, el entero exacto se convierte a notación científica con 10 cifras decimales mediante redondeo sobre cadenas decimales, sin recurrir a aritmética de punto flotante.
Sea \(R=1+\lfloor \log_3 n\rfloor\) el número de filas y \(W=1+\lfloor \log_2 n\rfloor\) la anchura de la primera fila. Construir las longitudes de fila cuesta \(O(R)\). Calcular las alturas de columna recorriendo las filas cuesta \(O(RW)\). Multiplicar todas las longitudes de gancho visita cada celda una sola vez, es decir, \(O(N)\), con
$$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n).$$
Así, la parte combinatoria del algoritmo es \(O(RW)=O(\log^2 n)\). El almacenamiento adicional en arreglos es \(O(R+W)\), mientras que el coste dominante de aritmética proviene de multiplicar y dividir enteros de precisión arbitraria cuyo tamaño crece con la respuesta final.
3-smooth 数是指形如 \(2^a3^b\) 的正整数，其中 \(a,b\ge 0\)。对给定的 \(n\)，定义
$$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}$$
题目要求计算 \(\mathcal{S}(n)\) 的排列个数，并满足如下约束：只要 \(x\mid y\)，元素 \(x\) 就必须排在 \(y\) 前面。把这个数量记为 \(F(n)\)，那么实现中使用的校验值为
$$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}$$
核心观察是：对所有 \(2^a3^b\) 而言，整除关系完全等价于指数对 \((a,b)\) 的坐标比较。因此这不是“枚举排列”的问题，而是“计算一个有限偏序集的线性扩张数”的问题，而且这个偏序集恰好具有 Ferrers 图形的结构。
把集合中的每个数都写成指数点 \((a,b)\)。于是有
$$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d$$
所以，所有合法排列恰好对应于满足 \(2^a3^b\le n\) 的格点集合的线性扩张。
固定某个 \(b\)。可取的 \(a\) 必须满足 \(2^a\le n/3^b\)，因此这一行的长度为
$$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor,$$
其中 \(3^b\le n\)。随着 \(b\) 增大，\(n/3^b\) 单调减小，所以这些行长不会增大，从而形成一个分拆
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor$$
从几何上看，第 \(b+1\) 行、第 \(a+1\) 列的那个格子，正好代表数 \(2^a3^b\)。
给每个格子写上它在最终排列中的位置。如果某个格子位于另一个格子的左上方向，那么对应的数一定整除后者，所以它的标号必须更小。于是，一个合法排列等价于：把 \(1,2,\dots,N\) 填进这个 Ferrers 图形，使得每一行从左到右递增、每一列从上到下递增，其中
$$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r$$
这正是形状为 \(\lambda\) 的标准 Young tableau 的定义。
形状 \(\lambda\) 的标准 Young tableaux 数量满足
$$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}$$
如果 \(\lambda'_c\) 表示第 \(c\) 列的高度，那么格子 \((r,c)\) 的 hook 长度为
$$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1$$
它等于该格子本身，加上同一行中它右边的所有格子，再加上同一列中它下方的所有格子。
指数点构成的是一个左对齐图形。向右走一步相当于再乘一个 \(2\)，向下走一步相当于再乘一个 \(3\)。这两个操作都会使数变大，所以在合法排列里，标号也必须相应变大。换句话说，这个偏序正是 Ferrers 图中“行列同时递增”的标准偏序，因此可以直接套用 hook-length 理论，而不必对所有排列进行回溯或动态搜索。
当 \(n=8\) 时，不超过 \(8\) 的 3-smooth 数为
$$1,\ 2,\ 3,\ 4,\ 6,\ 8$$
对应的 Ferrers 形状是
$$\lambda=(4,2)$$
因为 \(b=0\) 这一行有 \(1,2,4,8\)，而 \(b=1\) 这一行有 \(3,6\)。它的 hook 长度表为
$$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$$
因此
$$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9$$
这与程序中的校验值完全一致，也清楚展示了整个数学过程。
C++、Python 和 Java 实现采用同一条计算流程。首先，它们按 \(3\) 的幂次逐行生成图形。对每一行，程序用纯整数运算找出允许的最大 \(2\) 的指数，因此行长是精确得到的，不依赖浮点对数，也不会引入舍入误差。
随后，程序把所有行长相加得到总格子数 \(N\)。接着，再统计每一列被多少行覆盖，从而得到列高数组。有了行长和列高之后，程序只需逐格扫描一次，就能算出每个格子的 hook 长度，并把它们全部乘成一个精确分母。
接下来，程序以大整数形式构造 \(N!\)，再除以 hook 乘积，得到精确的 \(F(n)\)。C++ 实现还会在最后除法之前额外检查一次是否整除；虽然理论上 hook-length 公式已经保证结果一定是整数，但这个检查有助于及时发现实现错误。最后，精确整数被转换成科学计数法，保留小数点后 10 位，并且采用十进制字符串舍入，而不是浮点舍入，因此不会产生精度漂移。
设 \(R=1+\lfloor \log_3 n\rfloor\) 是行数，\(W=1+\lfloor \log_2 n\rfloor\) 是首行宽度。构造所有行长需要 \(O(R)\) 时间。通过扫描所有行来求每一列的高度需要 \(O(RW)\) 时间。把所有 hook 长度相乘时，每个格子恰好访问一次，也就是 \(O(N)\)，其中
$$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n)$$
因此，组合结构本身的处理代价是 \(O(RW)=O(\log^2 n)\)。除大整数本身以外，额外数组空间只有 \(O(R+W)\)。真正占主导的是任意精度整数的乘法和除法，而它们的位数由最终答案的规模决定。
3-гладкое число имеет вид \(2^a3^b\), где \(a,b\ge 0\). Для заданного \(n\) определим множество
$$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}.$$
Нужно подсчитать число перестановок элементов \(\mathcal{S}(n)\), удовлетворяющих правилу делимости: если \(x\mid y\), то элемент \(x\) обязан стоять раньше элемента \(y\). Обозначим это количество через \(F(n)\). Контрольные значения, используемые в реализациях, таковы:
$$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}.$$
Главное упрощение состоит в том, что для чисел вида \(2^a3^b\) отношение делимости полностью совпадает с покоординатным порядком на паре показателей \((a,b)\). Поэтому задача сводится не к перебору перестановок, а к подсчёту линейных расширений конечного частично упорядоченного множества формы Феррерса.
Представим каждый элемент множества \(\mathcal{S}(n)\) как пару показателей. Тогда
$$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d.$$
Следовательно, допустимые перестановки в точности совпадают с линейными расширениями множества точек \((a,b)\), для которых выполнено \(2^a3^b\le n\).
Зафиксируем значение \(b\). Тогда допустимы те \(a\), для которых \(2^a\le n/3^b\). Значит, длина строки равна
$$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor,$$
при всех \(b\), удовлетворяющих \(3^b\le n\). Поскольку при росте \(b\) величина \(n/3^b\) уменьшается, длины строк не возрастают. Следовательно, они образуют разбиение
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor.$$
Геометрически клетка в строке \(b+1\) и столбце \(a+1\) представляет число \(2^a3^b\).
Запишем в каждую клетку позицию соответствующего числа в итоговой перестановке. Правило делимости означает, что клетка, лежащая северо-западнее другой, обязана получить меньшую метку. Поэтому допустимая перестановка эквивалентна заполнению диаграммы Феррерса числами \(1,2,\dots,N\), возрастающими слева направо и сверху вниз, где
$$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r.$$
Это и есть стандартная таблица Юнга формы \(\lambda\).
Число стандартных таблиц Юнга формы \(\lambda\) равно
$$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}.$$
Если \(\lambda'_c\) обозначает высоту столбца \(c\), то длина крюка клетки \((r,c)\) равна
$$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1.$$
Иными словами, крюк включает саму клетку, все клетки справа от неё в той же строке и все клетки ниже неё в том же столбце.
Пары показателей образуют левосторонне выровненную диаграмму. Шаг вправо означает умножение на \(2\), шаг вниз означает умножение на \(3\). Оба движения увеличивают число, а значит, увеличивают и допустимый номер в перестановке. Следовательно, частичный порядок здесь совпадает со стандартным порядком по строкам и столбцам в диаграмме Феррерса. Поэтому формула крюков применяется напрямую и полностью заменяет перебор перестановок.
3-гладкие числа, не превосходящие \(8\), таковы:
$$1,\ 2,\ 3,\ 4,\ 6,\ 8.$$
Соответствующая форма Феррерса имеет вид
$$\lambda=(4,2),$$
потому что строка с \(b=0\) содержит \(1,2,4,8\), а строка с \(b=1\) содержит \(3,6\). Длины крюков равны
$$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$$
откуда
$$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9.$$
Это совпадает с контрольным значением и на маленьком примере показывает весь метод целиком.
Реализации на C++, Python и Java выполняют одну и ту же последовательность шагов. Сначала они перечисляют строки, проходя по степеням \(3\). Для каждой строки максимальный допустимый показатель степени двойки находится целочисленными операциями, поэтому длина строки вычисляется точно, без использования плавающей арифметики.
Затем все длины строк суммируются, что даёт \(N\). После этого для каждого столбца считается его высота, то есть количество строк, которые доходят до данного столбца. Имея массив длин строк и массив высот столбцов, реализация один раз проходит по всем клеткам, вычисляет длину каждого крюка и перемножает эти значения в один точный знаменатель.
Далее строится \(N!\) как целое число произвольной точности, и результат делится на произведение крюков, что даёт точное значение \(F(n)\). В реализации на C++ перед последним делением дополнительно выполняется проверка точной делимости; хотя теорема уже гарантирует целочисленность, такая проверка полезна как внутренняя защита от ошибок. В конце точный результат переводится в научную запись с 10 знаками после запятой, причём округление выполняется по десятичной строке, а не через типы с плавающей точкой.
Пусть \(R=1+\lfloor \log_3 n\rfloor\) — число строк, а \(W=1+\lfloor \log_2 n\rfloor\) — ширина первой строки. Построение длин строк занимает \(O(R)\). Вычисление высот столбцов сканированием строк стоит \(O(RW)\). Перемножение всех крюков посещает каждую клетку ровно один раз, то есть требует \(O(N)\), где
$$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n).$$
Следовательно, комбинаторная часть алгоритма работает за \(O(RW)=O(\log^2 n)\). Дополнительная память под массивы равна \(O(R+W)\), а основная арифметическая стоимость определяется умножением и делением целых чисел произвольной точности, размер которых растёт вместе с конечным ответом.
العدد 3-smooth هو كل عدد صحيح موجب من الصورة \(2^a3^b\) حيث \(a,b\ge 0\). ولعدد معطى \(n\) نعرّف المجموعة
$$\mathcal{S}(n)=\{2^a3^b \le n : a,b \in \mathbb{Z}_{\ge 0}\}.$$
المطلوب هو عدّ جميع ترتيبات عناصر \(\mathcal{S}(n)\) التي تحترم قاعدة القسمة: إذا كان \(x\mid y\)، فيجب أن يظهر \(x\) قبل \(y\) في الترتيب. إذا رمزنا إلى هذا العدد بـ \(F(n)\)، فإن نقاط التحقق المستخدمة في التنفيذات هي
$$F(6)=5,\qquad F(8)=9,\qquad F(20)=450,\qquad F(1000)=8.8521816557\times 10^{21}.$$
الفكرة الحاسمة هي أن علاقة القسمة بين الأعداد من الشكل \(2^a3^b\) تتحول تمامًا إلى ترتيب إحداثي على الزوج \((a,b)\). وبذلك لا تعود المسألة مسألة تعداد مباشر للترتيبات، بل تصبح مسألة حساب عدد الامتدادات الخطية لـ poset محدود له شكل Ferrers.
نمثل كل عنصر من \(\mathcal{S}(n)\) بزوج أسس. عندئذٍ
$$2^a3^b \mid 2^c3^d \iff a\le c,\ b\le d.$$
لذلك فإن جميع الترتيبات الصحيحة هي بالضبط الامتدادات الخطية لمجموعة النقاط \((a,b)\) التي تحقق \(2^a3^b\le n\).
لنثبت قيمة \(b\). القيم المسموح بها لـ \(a\) هي تلك التي تحقق \(2^a\le n/3^b\). إذن طول الصف يساوي
$$\lambda_{b+1}=1+\left\lfloor \log_2\left(\frac{n}{3^b}\right)\right\rfloor,$$
لكل \(b\) يحقق \(3^b\le n\). وبما أن \(n/3^b\) يتناقص عندما يزداد \(b\)، فإن أطوال الصفوف غير متزايدة، وبالتالي نحصل على تقسيم
$$\lambda=(\lambda_1,\lambda_2,\dots,\lambda_R),\qquad R=1+\left\lfloor \log_3 n\right\rfloor.$$
ومن الناحية الهندسية فإن الخلية في الصف \(b+1\) والعمود \(a+1\) تمثل العدد \(2^a3^b\).
نضع في كل خلية موضع العدد الموافق لها داخل الترتيب النهائي. قاعدة القسمة تعني أن الخلية الواقعة شمال غرب خلية أخرى يجب أن تحمل رقمًا أصغر. لذلك فإن الترتيب الصحيح يكافئ ملء شكل Ferrers بالأعداد \(1,2,\dots,N\) بحيث تزداد الأعداد من اليسار إلى اليمين ومن الأعلى إلى الأسفل، حيث
$$N=|\mathcal{S}(n)|=\sum_{r=1}^{R}\lambda_r.$$
وهذا هو بالضبط تعريف جدول Young القياسي ذي الشكل \(\lambda\).
عدد الجداول القياسية للشكل \(\lambda\) يعطى بالعلاقة
$$F(n)=\frac{N!}{\prod_{(r,c)\in\lambda} h_{r,c}}.$$
إذا رمزنا إلى ارتفاع العمود \(c\) بـ \(\lambda'_c\)، فإن طول الخطاف للخلية \((r,c)\) هو
$$h_{r,c}=(\lambda_r-c)+(\lambda'_c-r)+1=\lambda_r+\lambda'_c-r-c+1.$$
أي أنه يساوي الخلية نفسها مع جميع الخلايا الواقعة على يمينها في الصف نفسه، وجميع الخلايا الواقعة تحتها في العمود نفسه.
أزواج الأسس تشكل شكلًا مصطفًا إلى اليسار. التحرك خطوة إلى اليمين يعني الضرب في \(2\)، والتحرك خطوة إلى الأسفل يعني الضرب في \(3\). كلتا الحركتين تكبران العدد، وبالتالي يجب أن تكبران موضعه في الترتيب الصحيح. لذلك فإن الترتيب الجزئي هنا هو نفسه ترتيب الصفوف والأعمدة المعتاد في شكل Ferrers، ومن ثم تنطبق نظرية الخطافات مباشرة من دون أي تعداد صريح للترتيبات.
الأعداد 3-smooth التي لا تتجاوز \(8\) هي
$$1,\ 2,\ 3,\ 4,\ 6,\ 8.$$
والشكل الموافق لها هو
$$\lambda=(4,2),$$
لأن صف \(b=0\) يحتوي على \(1,2,4,8\)، بينما صف \(b=1\) يحتوي على \(3,6\). أما أطوال الخطافات فهي
$$\begin{array}{cccc} 5 & 4 & 2 & 1\\ 2 & 1 \end{array}$$
ومن ثم نحصل على
$$F(8)=\frac{6!}{5\cdot 4\cdot 2\cdot 1\cdot 2\cdot 1}=\frac{720}{80}=9.$$
وهذه النتيجة تطابق قيمة التحقق وتعرض الفكرة كاملة على مثال صغير وواضح.
تتبع تنفيذات C++ وPython وJava المسار نفسه. أولًا تُبنى الصفوف عبر المرور على قوى العدد \(3\). وفي كل صف يُحسب أكبر أس للعدد \(2\) ما زال مسموحًا به باستخدام عمليات صحيحة فقط، وبذلك يُستخرج طول الصف بدقة كاملة من دون الاعتماد على لوغاريتمات عائمة.
بعد ذلك تُجمع أطوال الصفوف كلها للحصول على \(N\). ثم يُحسب ارتفاع كل عمود من خلال عدّ الصفوف التي تصل إلى ذلك العمود. وبوجود أطوال الصفوف وارتفاعات الأعمدة، تمر الشيفرة على كل خلية مرة واحدة، وتحسب طول خطافها، ثم تضرب جميع هذه القيم في مقام صحيح واحد.
بعدها تُبنى القيمة \(N!\) كعدد صحيح كبير، ثم تُقسم على حاصل ضرب الخطافات للحصول على \(F(n)\) بدقة تامة. تنفيذ C++ يضيف أيضًا فحصًا صريحًا لقابلية القسمة قبل القسمة النهائية؛ ورغم أن النظرية تضمن أن الناتج عدد صحيح، فإن هذا الفحص مفيد كاختبار سلامة داخلي. وفي النهاية يُحوَّل العدد الصحيح الدقيق إلى صيغة علمية مع 10 أرقام بعد الفاصلة، ويُجرى التقريب على سلسلة عشرية لا على أعداد عائمة، لذلك لا يوجد انجراف في الدقة.
لنفرض أن \(R=1+\lfloor \log_3 n\rfloor\) هو عدد الصفوف، وأن \(W=1+\lfloor \log_2 n\rfloor\) هو عرض الصف الأول. بناء أطوال الصفوف يكلف \(O(R)\). وحساب ارتفاعات الأعمدة بمسح الصفوف يكلف \(O(RW)\). أما ضرب جميع أطوال الخطافات فيزور كل خلية مرة واحدة فقط، أي \(O(N)\)، حيث
$$N=\sum_{r=1}^{R}\lambda_r=\Theta(\log^2 n).$$
ومن ثم فإن الجزء التوافقي من الخوارزمية يعمل بزمن \(O(RW)=O(\log^2 n)\). الذاكرة الإضافية للمصفوفات هي \(O(R+W)\)، بينما تأتي الكلفة الحسابية المسيطرة من عمليات ضرب وقسمة الأعداد الصحيحة كبيرة الدقة، التي يعتمد حجمها على حجم الجواب النهائي.