For each positive integer \(n\), consider the poset of divisors of \(n\) ordered by divisibility. Let \(f(n)\) be the maximum possible size of an antichain in that poset. The implementations in this repository compute
$$S(N)=\sum_{n=1}^{N} f(n)$$
for \(N=10^8\). The key simplification is that \(f(n)\) can be read from the middle rank of the divisor lattice, and those middle-rank divisors can be counted by grouping integers according to \(\Omega(n)\), the total number of prime factors with multiplicity.
Write the prime factorization of \(n\) as
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$$
Every divisor of \(n\) has the form
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$$
If we rank divisors by the sum of their exponents, then the rank of \(d\) is exactly
$$\operatorname{rank}(d)=a_1+\cdots+a_r=\Omega(d).$$
Therefore the number of divisors of rank \(m\) is the coefficient of \(x^m\) in the generating polynomial
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i}).$$
Each factor \(1+x+\cdots+x^{e_i}\) is symmetric and unimodal, and the product of symmetric unimodal polynomials is again symmetric and unimodal. So the coefficient sequence of \(P_n(x)\) increases up to the middle and then decreases symmetrically.
The divisor lattice is a product of chains, so a classical Sperner-type result implies that its width equals the size of its largest rank. If \(t=\Omega(n)\), then the largest coefficient of \(P_n(x)\) occurs at the middle rank:
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$$
When \(t\) is odd, the ranks \((t-1)/2\) and \((t+1)/2\) have the same size by symmetry, so either middle rank can be used.
Fix a divisor \(d\mid n\) from the middle rank and write \(b=n/d\). Since exponents add,
$$\Omega(d)+\Omega(b)=\Omega(n).$$
If \(\Omega(n)=2k\), then every middle-rank divisor satisfies \(\Omega(d)=k\), hence also \(\Omega(b)=k\). Thus \(f(n)\) equals the number of ordered factorizations
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k.$$
If \(\Omega(n)=2k+1\), choose the lower middle rank. Then
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$$
Summing over all \(n\le N\) gives a global counting identity:
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
This is exactly what the code counts.
Define
$$G_k=\{m\le N:\Omega(m)=k\}.$$
The smallest-prime-factor sieve provides the recurrence
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$$
Because the programs process integers in increasing order, every list \(G_k\) is already sorted. The formula above then becomes two kinds of pair counts for each \(k\): pairs inside \(G_k\), and pairs between \(G_k\) and \(G_{k+1}\).
For two sorted lists \(A\) and \(B\), we must count pairs \((a,b)\in A\times B\) satisfying \(ab\le N\). If we scan \(a\) from left to right, the largest valid index in \(B\) can only move left, never right. So one monotone two-pointer pass counts all valid pairs in \(O(|A|+|B|)\) time.
The implementations perform this scan once for \((G_k,G_k)\) and once for \((G_k,G_{k+1})\). Summing over all \(k\) produces \(S(N)\).
For \(n=36=2^2\cdot 3^2\),
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$$
The largest coefficient is \(3\), so \(f(36)=3\). The middle-rank divisors are \(4,6,9\), giving the ordered factorizations
$$(4,9),\qquad (6,6),\qquad (9,4).$$
All three have \(\Omega=2\) on both sides, matching the even case.
For \(n=12=2^2\cdot 3\),
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$$
Now \(f(12)=2\), coming from the lower middle rank divisors \(2\) and \(3\), which correspond to
$$(2,6),\qquad (3,4),$$
with degree pattern \((1,2)\). This is the odd case counted between consecutive groups.
The C++ and Python versions build an SPF table, compute \(\Omega(i)\) from the recurrence, and append each integer to by_degs[d]. The Java version first counts how many values fall into each degree, allocates exact arrays, and fills them in a second pass, which avoids list overhead.
All three implementations then run the same two-pointer loops. Since \(2^{26}\le 10^8<2^{27}\), the maximum possible value of \(\Omega(n)\) is \(26\), so the small fixed-size Java arrays are sufficient.
Building the SPF sieve costs \(O(N\log\log N)\) time. Computing \(\Omega(i)\) and distributing integers into degree groups costs \(O(N)\). The total cost of all two-pointer scans is linear in the total size of the groups, so the overall running time remains \(O(N\log\log N)\). The memory usage is \(O(N)\) for the sieve, the degree array, and the grouped integers.
Für jede positive ganze Zahl \(n\) betrachten wir die durch Teilbarkeit geordnete Menge aller Teiler von \(n\). Sei \(f(n)\) die maximale Größe einer Antikette in diesem Verband. Die Implementierungen in diesem Repository berechnen
$$S(N)=\sum_{n=1}^{N} f(n)$$
für \(N=10^8\). Die entscheidende Vereinfachung besteht darin, dass sich \(f(n)\) als Größe der mittleren Rangschicht des Teilergitters ausdrücken lässt und diese Rangschichten über \(\Omega(n)\), also die Anzahl der Primfaktoren mit Vielfachheit, gezählt werden können.
Schreibe die Primfaktorzerlegung von \(n\) als
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$$
Jeder Teiler von \(n\) hat die Form
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$$
Wenn wir Teiler nach der Summe ihrer Exponenten schichten, dann ist der Rang von \(d\) genau
$$\operatorname{Rang}(d)=a_1+\cdots+a_r=\Omega(d).$$
Die Anzahl der Teiler in Rang \(m\) ist also der Koeffizient von \(x^m\) im erzeugenden Polynom
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i}).$$
Jeder Faktor \(1+x+\cdots+x^{e_i}\) ist symmetrisch und unimodal; ihr Produkt ist daher wieder symmetrisch und unimodal. Die Koeffizientenfolge von \(P_n(x)\) wächst also bis zur Mitte und fällt danach symmetrisch wieder ab.
Das Teilergitter ist ein Produkt von Ketten, und ein klassisches Sperner-artiges Resultat besagt, dass seine Breite gleich der Größe der größten Rangschicht ist. Für \(t=\Omega(n)\) erhält man deshalb
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$$
Ist \(t\) ungerade, dann haben die beiden mittleren Ränge \((t-1)/2\) und \((t+1)/2\) wegen der Symmetrie dieselbe Größe.
Fixiere einen mittleren Teiler \(d\mid n\) und setze \(b=n/d\). Wegen der Additivität der Exponenten gilt
$$\Omega(d)+\Omega(b)=\Omega(n).$$
Falls \(\Omega(n)=2k\), erfüllt jeder mittlere Teiler \(\Omega(d)=k\), also auch \(\Omega(b)=k\). Damit ist \(f(n)\) gleich der Anzahl geordneter Faktorisierungen
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k.$$
Falls \(\Omega(n)=2k+1\), wählen wir den unteren mittleren Rang. Dann gilt
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$$
Summiert über alle \(n\le N\) entsteht die globale Zählformel
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
Genau diese beiden Arten von Paaren werden im Code gezählt.
Definiere
$$G_k=\{m\le N:\Omega(m)=k\}.$$
Das SPF-Sieb liefert die Rekursion
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$$
Da die Programme die Zahlen in aufsteigender Reihenfolge verarbeiten, ist jede Liste \(G_k\) bereits sortiert. Die Formel oben zerfällt somit für jedes \(k\) in zwei Paarzählungen: innerhalb von \(G_k\) und zwischen \(G_k\) und \(G_{k+1}\).
Für zwei sortierte Listen \(A\) und \(B\) müssen wir die Anzahl der Paare \((a,b)\in A\times B\) mit \(ab\le N\) bestimmen. Wenn \(a\) von links nach rechts wächst, kann der größte zulässige Index in \(B\) nur nach links wandern, niemals nach rechts. Deshalb genügt ein monotoner Zwei-Zeiger-Durchlauf mit Laufzeit \(O(|A|+|B|)\).
Die Implementierungen wenden dieses Verfahren einmal auf \((G_k,G_k)\) und einmal auf \((G_k,G_{k+1})\) an. Die Summe über alle \(k\) liefert \(S(N)\).
Für \(n=36=2^2\cdot 3^2\) gilt
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$$
Der größte Koeffizient ist \(3\), also \(f(36)=3\). Die mittleren Teiler sind \(4,6,9\), und daraus entstehen die geordneten Faktorisierungen
$$(4,9),\qquad (6,6),\qquad (9,4).$$
Alle drei gehören zum geraden Fall mit \(\Omega=2\) auf beiden Seiten.
Für \(n=12=2^2\cdot 3\) erhält man
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$$
Daher ist \(f(12)=2\). Die unteren mittleren Teiler \(2\) und \(3\) entsprechen
$$(2,6),\qquad (3,4),$$
also dem ungeraden Fall mit Gradmuster \((1,2)\).
Die C++- und Python-Versionen bauen eine SPF-Tabelle, berechnen \(\Omega(i)\) aus der Rekursion und hängen jede Zahl an by_degs[d] an. Die Java-Version zählt zuerst, wie viele Werte in jeden Grad fallen, reserviert dann exakt passende Arrays und füllt sie in einem zweiten Durchlauf, wodurch Listen-Overhead vermieden wird.
Anschließend führen alle drei Implementierungen dieselben Zwei-Zeiger-Schleifen aus. Da \(2^{26}\le 10^8<2^{27}\), ist der maximal mögliche Wert von \(\Omega(n)\) gleich \(26\); daher reichen die kleinen festen Arrays in Java sicher aus.
Das SPF-Sieb benötigt \(O(N\log\log N)\) Zeit. Die Berechnung von \(\Omega(i)\) und das Einsortieren in die Gradgruppen kosten \(O(N)\). Die gesamte Arbeit aller Zwei-Zeiger-Durchläufe ist linear in der Gesamtgröße der Gruppen, also bleibt die Gesamtlaufzeit \(O(N\log\log N)\). Der Speicherverbrauch ist \(O(N)\) für Sieb, Gradfeld und gruppierte Zahlen.
Her pozitif tam sayi \(n\) icin, \(n\)'in bolenlerini bolunebilme iliskisine gore siralanmis bir kume olarak dusunelim. \(f(n)\), bu posetteki en buyuk antizincirin boyu olsun. Bu depodaki cozumler
$$S(N)=\sum_{n=1}^{N} f(n)$$
toplamini \(N=10^8\) icin hesaplar. Temel sadeleştirme, \(f(n)\)'in bolen kafesinin orta rankindan okunabilmesi ve bu orta ranktaki bolenlerin \(\Omega(n)\), yani asal carpan sayisi (tekrarla birlikte), kullanilarak sayilabilmesidir.
\(n\)'in asal carpanlara ayrilisini
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r$$
seklinde yazalim. Her bolen
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i$$
biçimindedir. Bolenleri uslerin toplamina gore katmanlarsak, \(d\)'nin ranki tam olarak
$$\operatorname{rank}(d)=a_1+\cdots+a_r=\Omega(d)$$
olur. Dolayisiyla ranki \(m\) olan bolen sayisi,
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i})$$
ureten polinomunda \(x^m\)'in katsayisidir.
Her \(1+x+\cdots+x^{e_i}\) carpani hem simetrik hem de unimodaldir; bu nedenle carpim da simetrik ve unimodal kalir. Yani \(P_n(x)\)'in katsayilari ortaya kadar buyur, sonra simetrik bicimde azalir.
Bolen kafesi bir zincir carpimidir ve klasik Sperner tipi bir sonuc, genisligin en buyuk rankin boyuna esit oldugunu soyler. \(t=\Omega(n)\) icin bu nedenle
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}$$
elde edilir. \(t\) tek ise \((t-1)/2\) ve \((t+1)/2\) ranklari simetri nedeniyle ayni buyukluge sahiptir.
Orta ranktan bir \(d\mid n\) boleni secip \(b=n/d\) yazalim. Usler toplandigi icin
$$\Omega(d)+\Omega(b)=\Omega(n)$$
olur. Eger \(\Omega(n)=2k\) ise orta ranktaki her bolen icin \(\Omega(d)=k\) ve dolayisiyla \(\Omega(b)=k\) olur. Bu durumda \(f(n)\),
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k$$
kosulunu saglayan sirali carpanlasmalarin sayisidir.
Eger \(\Omega(n)=2k+1\) ise alt orta ranki seceriz ve
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1$$
elde edilir. Tum \(n\le N\) icin toplayinca su global sayim kimligi ortaya cikar:
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
Kodun yaptigi sayim tam olarak budur.
Su kümeyi tanimlayalim:
$$G_k=\{m\le N:\Omega(m)=k\}.$$
En kucuk asal bolen suzgeci bize
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1$$
bağıntisini verir. Programlar sayilari artan sirayla isledigi icin her \(G_k\) listesi zaten siralidir. Böylece yukaridaki formül her \(k\) icin iki parca olur: \(G_k\) icindeki ciftler ve \(G_k\) ile \(G_{k+1}\) arasindaki ciftler.
Sirali iki liste \(A\) ve \(B\) icin, \(ab\le N\) kosulunu saglayan \((a,b)\in A\times B\) ciftlerini saymamiz gerekir. \(a\) soldan saga ilerlerken, \(B\) icindeki en buyuk gecerli indeks yalnizca sola kayabilir; saga gidemez. Bu nedenle tek bir monoton iki-isaretci gecisi tum gecerli ciftleri \(O(|A|+|B|)\) zamanda sayar.
Uygulamalar bu taramayi bir kez \((G_k,G_k)\), bir kez de \((G_k,G_{k+1})\) icin yapar. Tum \(k\) degerleri toplandiginda \(S(N)\) elde edilir.
\(n=36=2^2\cdot 3^2\) icin
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4$$
olur. En buyuk katsayi \(3\) oldugu icin \(f(36)=3\). Orta rank bolenleri \(4,6,9\)'dur ve bunlar
$$(4,9),\qquad (6,6),\qquad (9,4)$$
sirali carpanlasmalarini verir. Ucun de cift tarafta da \(\Omega=2\) oldugundan bu cift derece durumudur.
\(n=12=2^2\cdot 3\) icin ise
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3$$
elde edilir. Buradan \(f(12)=2\) gelir. Alt orta ranktaki \(2\) ve \(3\) bolenleri
$$(2,6),\qquad (3,4)$$
ciftlerine karsilik gelir; bu da \((1,2)\) derece desenidir.
C++ ve Python surumleri SPF tablosunu kurar, \(\Omega(i)\)'yi yinelemeli bagintidan hesaplar ve her sayiyi by_degs[d] listesine ekler. Java surumu ise once her derecede kac sayi oldugunu sayar, sonra tam boyutlu diziler ayirip ikinci geciste bunlari doldurur; boylece liste nesnesi maliyeti azalir.
Ardindan uc surum de ayni iki-isaretci dongulerini calistirir. \(2^{26}\le 10^8<2^{27}\) oldugundan \(\Omega(n)\)'in alabilecegi en buyuk deger \(26\)'dir; bu nedenle Java'daki kucuk sabit diziler guvenlidir.
SPF suzgecinin maliyeti \(O(N\log\log N)\) zamandir. \(\Omega(i)\)'yi hesaplamak ve sayilari derece gruplarina dagitmak \(O(N)\) tutar. Tum iki-isaretci gecislerinin toplam maliyeti gruplarin toplam boyunda lineerdir; dolayisiyla genel calisma suresi \(O(N\log\log N)\) olarak kalir. Bellek kullanimi suzgec, derece dizisi ve gruplanmis sayilar icin \(O(N)\)'dir.
Para cada entero positivo \(n\), consideramos el poset de sus divisores ordenado por divisibilidad. Sea \(f(n)\) la maxima longitud de una anticadena en ese poset. Las implementaciones de este repositorio calculan
$$S(N)=\sum_{n=1}^{N} f(n)$$
para \(N=10^8\). La idea central es que \(f(n)\) coincide con el tamano de la capa central del reticulo de divisores, y esas capas centrales se pueden contar agrupando los enteros segun \(\Omega(n)\), el numero total de factores primos contando multiplicidades.
Escribamos la factorizacion prima de \(n\) como
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$$
Cada divisor de \(n\) tiene la forma
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$$
Si clasificamos los divisores por la suma de sus exponentes, el rango de \(d\) es exactamente
$$\operatorname{rango}(d)=a_1+\cdots+a_r=\Omega(d).$$
Por tanto, el numero de divisores de rango \(m\) es el coeficiente de \(x^m\) en el polinomio generador
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i}).$$
Cada factor \(1+x+\cdots+x^{e_i}\) es simetrico y unimodal, y el producto de polinomios simetricos y unimodales vuelve a ser simetrico y unimodal. Por eso la sucesion de coeficientes de \(P_n(x)\) crece hasta el centro y luego decrece de forma simetrica.
El reticulo de divisores es un producto de cadenas, y un resultado clasico de tipo Sperner afirma que su anchura es igual al tamano del rango mas grande. Si \(t=\Omega(n)\), entonces
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$$
Cuando \(t\) es impar, los rangos \((t-1)/2\) y \((t+1)/2\) tienen el mismo tamano por simetria, de modo que cualquiera de los dos sirve.
Tomemos un divisor central \(d\mid n\) y definamos \(b=n/d\). Como los exponentes se suman, se cumple
$$\Omega(d)+\Omega(b)=\Omega(n).$$
Si \(\Omega(n)=2k\), entonces todo divisor central satisface \(\Omega(d)=k\), y por lo tanto \(\Omega(b)=k\). Asi, \(f(n)\) es el numero de factorizaciones ordenadas
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k.$$
Si \(\Omega(n)=2k+1\), elegimos el rango central inferior y obtenemos
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$$
Al sumar sobre todos los \(n\le N\) aparece la identidad global
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
Eso es exactamente lo que cuenta el programa.
Definimos
$$G_k=\{m\le N:\Omega(m)=k\}.$$
La criba de menor factor primo proporciona la recurrencia
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$$
Como los programas recorren los enteros en orden creciente, cada lista \(G_k\) ya queda ordenada. Entonces la formula anterior se convierte, para cada \(k\), en dos conteos de pares: dentro de \(G_k\) y entre \(G_k\) y \(G_{k+1}\).
Dados dos arreglos ordenados \(A\) y \(B\), queremos contar los pares \((a,b)\in A\times B\) tales que \(ab\le N\). Si avanzamos \(a\) de izquierda a derecha, el mayor indice valido en \(B\) solo puede desplazarse hacia la izquierda. Por eso un unico barrido monotono con dos punteros cuenta todos los pares validos en \(O(|A|+|B|)\).
Las implementaciones hacen este recorrido una vez para \((G_k,G_k)\) y otra vez para \((G_k,G_{k+1})\). La suma sobre todos los \(k\) produce \(S(N)\).
Para \(n=36=2^2\cdot 3^2\),
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$$
El coeficiente maximo es \(3\), asi que \(f(36)=3\). Los divisores del rango central son \(4,6,9\), y corresponden a las factorizaciones ordenadas
$$(4,9),\qquad (6,6),\qquad (9,4).$$
Las tres pertenecen al caso par, con \(\Omega=2\) en ambos lados.
Para \(n=12=2^2\cdot 3\),
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$$
Ahora \(f(12)=2\), proveniente de los divisores centrales inferiores \(2\) y \(3\), que producen
$$(2,6),\qquad (3,4),$$
con patron de grados \((1,2)\). Este es el caso impar entre grupos consecutivos.
Las versiones en C++ y Python construyen la tabla SPF, calculan \(\Omega(i)\) mediante la recurrencia y anaden cada entero a by_degs[d]. La version Java primero cuenta cuantos valores caen en cada grado, reserva arreglos del tamano exacto y los rellena en una segunda pasada, reduciendo el coste de estructuras dinamicas.
Despues, las tres versiones ejecutan los mismos bucles con dos punteros. Como \(2^{26}\le 10^8<2^{27}\), el valor maximo posible de \(\Omega(n)\) es \(26\), asi que los arreglos pequenos y fijos de Java son suficientes.
La criba SPF cuesta \(O(N\log\log N)\) tiempo. Calcular \(\Omega(i)\) y distribuir los enteros por grupos cuesta \(O(N)\). La suma del trabajo de todos los barridos con dos punteros es lineal en el tamano total de los grupos, asi que el algoritmo completo sigue siendo \(O(N\log\log N)\). El uso de memoria es \(O(N)\) por la criba, el arreglo de grados y los enteros agrupados.
对每个正整数 \(n\)，考虑其所有约数按整除关系形成的偏序集。设 \(f(n)\) 为该偏序集中最大反链的长度。仓库中的实现要计算
$$S(N)=\sum_{n=1}^{N} f(n)$$
其中 \(N=10^8\)。关键化简在于，\(f(n)\) 等于约数格中间层的大小，而这些中间层可以通过 \(\Omega(n)\) 来计数。这里 \(\Omega(n)\) 表示质因子总数，重数也计算在内。
把 \(n\) 的素因子分解写成
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$$
\(n\) 的任意约数都可写为
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$$
如果按指数和来定义层数，那么 \(d\) 的秩正好是
$$\operatorname{rank}(d)=a_1+\cdots+a_r=\Omega(d).$$
因此，秩为 \(m\) 的约数个数，就是生成函数
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i})$$
中 \(x^m\) 的系数。
每个因子 \(1+x+\cdots+x^{e_i}\) 都是对称且单峰的，因此它们的乘积仍然对称且单峰。于是 \(P_n(x)\) 的系数序列会一直增大到中间，然后再对称地减小。
约数格本质上是若干链的直积，经典的 Sperner 型结果说明，其宽度等于最大层的大小。若记 \(t=\Omega(n)\)，则
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$$
当 \(t\) 为奇数时，由于对称性，\((t-1)/2\) 与 \((t+1)/2\) 两个中间层大小相同。
固定一个中间层约数 \(d\mid n\)，再令 \(b=n/d\)。因为指数相加，所以
$$\Omega(d)+\Omega(b)=\Omega(n).$$
若 \(\Omega(n)=2k\)，那么中间层约数满足 \(\Omega(d)=k\)，同时也有 \(\Omega(b)=k\)。因此 \(f(n)\) 等于满足
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k$$
的有序分解个数。
若 \(\Omega(n)=2k+1\)，取较低的中间层，则有
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$$
对所有 \(n\le N\) 求和后，得到全局恒等式
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
这正是代码中实际执行的计数。
定义
$$G_k=\{m\le N:\Omega(m)=k\}.$$
最小质因子筛给出递推式
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$$
程序按从小到大的顺序处理整数，所以每个 \(G_k\) 天然已经有序。于是上面的公式对每个 \(k\) 都变成两类配对计数：\(G_k\) 内部，以及 \(G_k\) 与 \(G_{k+1}\) 之间。
对于两个有序数组 \(A\) 与 \(B\)，我们需要统计满足 \(ab\le N\) 的 \((a,b)\in A\times B\)。当 \(a\) 从左向右增大时，\(B\) 中最大的可行下标只会向左移动，不会回退向右。因此一次单调双指针扫描就能在 \(O(|A|+|B|)\) 时间内完成计数。
实现中对 \((G_k,G_k)\) 扫描一次，再对 \((G_k,G_{k+1})\) 扫描一次，最后把所有 \(k\) 的结果相加得到 \(S(N)\)。
对 \(n=36=2^2\cdot 3^2\)，有
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$$
最大系数是 \(3\)，所以 \(f(36)=3\)。中间层约数为 \(4,6,9\)，对应的有序分解是
$$(4,9),\qquad (6,6),\qquad (9,4).$$
三者都属于偶数情形，两边的 \(\Omega\) 都等于 \(2\)。
对 \(n=12=2^2\cdot 3\)，
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$$
因此 \(f(12)=2\)。较低中间层的约数 \(2\) 与 \(3\) 对应
$$(2,6),\qquad (3,4),$$
它们的度数模式是 \((1,2)\)，这正是相邻两组之间的情况。
C++ 与 Python 版本先建立 SPF 表，再由递推式计算 \(\Omega(i)\)，并把每个整数加入 by_degs[d]。Java 版本先统计每个度数里有多少个数，随后分配精确大小的数组，再第二遍填充，从而减少动态列表开销。
之后三种实现都执行相同的双指针循环。因为 \(2^{26}\le 10^8<2^{27}\)，所以 \(\Omega(n)\) 的最大可能值是 \(26\)，Java 里使用的小型定长数组是安全的。
构建 SPF 筛需要 \(O(N\log\log N)\) 时间。计算 \(\Omega(i)\) 并把整数分配到各组需要 \(O(N)\)。所有双指针扫描的总代价与各组总长度线性相关，因此总时间复杂度仍为 \(O(N\log\log N)\)。内存复杂度为 \(O(N)\)，用于筛表、度数数组以及分组后的整数。
Для каждого положительного целого \(n\) рассматривается частично упорядоченное множество его делителей по отношению делимости. Пусть \(f(n)\) обозначает максимальную длину антицепи в этом poset. Реализации в репозитории вычисляют
$$S(N)=\sum_{n=1}^{N} f(n)$$
для \(N=10^8\). Ключевое упрощение состоит в том, что \(f(n)\) равно размеру среднего ранга решетки делителей, а такие ранги удобно считать через функцию \(\Omega(n)\), то есть через число простых множителей с учетом кратностей.
Запишем разложение \(n\) на простые множители в виде
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$$
Любой делитель числа \(n\) имеет вид
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$$
Если ранжировать делители по сумме показателей, то ранг делителя \(d\) равен
$$\operatorname{rank}(d)=a_1+\cdots+a_r=\Omega(d).$$
Следовательно, число делителей ранга \(m\) равно коэффициенту при \(x^m\) в производящем многочлене
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i}).$$
Каждый множитель \(1+x+\cdots+x^{e_i}\) симметричен и унимодален, поэтому и их произведение остается симметричным и унимодальным. Значит, коэффициенты \(P_n(x)\) растут до середины, а затем симметрично убывают.
Решетка делителей является произведением цепей, и классический результат типа теоремы Шпернера утверждает, что ее ширина равна размеру наибольшего ранга. Если \(t=\Omega(n)\), то
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$$
Когда \(t\) нечетно, ранги \((t-1)/2\) и \((t+1)/2\) имеют одинаковый размер по симметрии.
Зафиксируем делитель среднего ранга \(d\mid n\) и положим \(b=n/d\). Тогда из аддитивности показателей следует
$$\Omega(d)+\Omega(b)=\Omega(n).$$
Если \(\Omega(n)=2k\), то для среднего ранга \(\Omega(d)=k\), а значит и \(\Omega(b)=k\). Следовательно, \(f(n)\) равно числу упорядоченных разложений
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k.$$
Если \(\Omega(n)=2k+1\), берем нижний средний ранг и получаем
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$$
После суммирования по всем \(n\le N\) выходит глобальная формула
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
Именно эти две категории пар и считает программа.
Определим
$$G_k=\{m\le N:\Omega(m)=k\}.$$
Решето наименьшего простого делителя дает рекурсию
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$$
Поскольку программы перебирают числа в возрастающем порядке, каждая группа \(G_k\) уже отсортирована. Тогда исходная формула распадается, для каждого \(k\), на подсчет пар внутри \(G_k\) и между \(G_k\) и \(G_{k+1}\).
Для двух отсортированных списков \(A\) и \(B\) нужно посчитать пары \((a,b)\in A\times B\), удовлетворяющие \(ab\le N\). Если двигать \(a\) слева направо, то максимальный допустимый индекс в \(B\) может сдвигаться только влево. Поэтому одного монотонного прохода двумя указателями достаточно, чтобы получить все пары за \(O(|A|+|B|)\).
Реализации выполняют такой проход один раз для \((G_k,G_k)\) и один раз для \((G_k,G_{k+1})\). Сумма по всем \(k\) дает \(S(N)\).
Для \(n=36=2^2\cdot 3^2\)
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$$
Наибольший коэффициент равен \(3\), значит \(f(36)=3\). Делители среднего ранга: \(4,6,9\), им соответствуют упорядоченные разложения
$$(4,9),\qquad (6,6),\qquad (9,4).$$
Все они относятся к четному случаю, когда по обе стороны \(\Omega=2\).
Для \(n=12=2^2\cdot 3\)
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$$
Поэтому \(f(12)=2\). Нижний средний ранг состоит из делителей \(2\) и \(3\), что дает пары
$$(2,6),\qquad (3,4),$$
то есть шаблон степеней \((1,2)\). Это именно нечетный случай между соседними группами.
Версии на C++ и Python строят таблицу SPF, затем по рекурсии вычисляют \(\Omega(i)\) и добавляют каждое число в by_degs[d]. Версия на Java сначала считает, сколько чисел попадает в каждый уровень, затем выделяет массивы точного размера и заполняет их вторым проходом, уменьшая накладные расходы динамических структур.
После этого все три реализации выполняют одинаковые циклы с двумя указателями. Так как \(2^{26}\le 10^8<2^{27}\), максимальное возможное значение \(\Omega(n)\) равно \(26\), поэтому небольшие фиксированные массивы в Java полностью достаточны.
Построение SPF-решета требует \(O(N\log\log N)\) времени. Вычисление \(\Omega(i)\) и распределение чисел по группам требует \(O(N)\). Суммарная стоимость всех проходов двумя указателями линейна по общему размеру групп, поэтому итоговая асимптотика остается \(O(N\log\log N)\). Память составляет \(O(N)\) для решета, массива степеней и сгруппированных чисел.
لكل عدد صحيح موجب \(n\)، ننظر الى مجموعة قواسمه المرتبة بعلاقة القسمة. ولتكن \(f(n)\) هي اكبر قيمة ممكنة لطول anti-chain في هذا الترتيب. البرامج الموجودة في هذا المستودع تحسب
$$S(N)=\sum_{n=1}^{N} f(n)$$
عندما يكون \(N=10^8\). الفكرة الاساسية هي ان \(f(n)\) يساوي حجم الطبقة الوسطى في شبكة القواسم، ويمكن عد هذه الطبقات الوسطى عبر \(\Omega(n)\)، اي عدد العوامل الاولية مع احتساب التكرار.
نكتب التحليل الاولي للعدد \(n\) بالشكل
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$$
وكل قاسم لـ \(n\) يكتب على الصورة
$$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$$
اذا رتبنا القواسم بحسب مجموع الاسس، فان رتبة \(d\) هي بالضبط
$$\operatorname{rank}(d)=a_1+\cdots+a_r=\Omega(d).$$
ولذلك فان عدد القواسم في الرتبة \(m\) يساوي معامل \(x^m\) في كثير الحدود المولد
$$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i}).$$
كل عامل من الشكل \(1+x+\cdots+x^{e_i}\) متناظر و unimodal، وبالتالي يبقى حاصل الضرب متناظرا و unimodal ايضا. لذلك تزداد معاملات \(P_n(x)\) حتى المنتصف ثم تتناقص بصورة متناظرة.
شبكة القواسم هي حاصل ضرب سلاسل، وتقول نتيجة كلاسيكية من نوع مبرهنة Sperner ان العرض يساوي حجم اكبر رتبة. اذا وضعنا \(t=\Omega(n)\)، نحصل على
$$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$$
وعندما يكون \(t\) فرديا، فان الرتبتين \((t-1)/2\) و \((t+1)/2\) لهما الحجم نفسه بسبب التناظر.
لنثبت قاسما وسطيا \(d\mid n\) ونضع \(b=n/d\). بما ان الاسس تتجمع، فلدينا
$$\Omega(d)+\Omega(b)=\Omega(n).$$
اذا كان \(\Omega(n)=2k\)، فان كل قاسم من الطبقة الوسطى يحقق \(\Omega(d)=k\)، وبالتالي \(\Omega(b)=k\) ايضا. عندها يصبح \(f(n)\) مساويا لعدد التحليلات المرتبة
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k.$$
اما اذا كان \(\Omega(n)=2k+1\)، فنختار الطبقة الوسطى الدنيا فنحصل على
$$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$$
وبجمع ذلك على جميع \(n\le N\) نحصل على الهوية الشاملة
$$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$$
وهذا هو بالضبط ما تعده الشيفرة.
نعرف
$$G_k=\{m\le N:\Omega(m)=k\}.$$
ومن غربال اصغر قاسم اولي نحصل على العلاقة
$$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$$
وبما ان البرامج تمر على الاعداد تصاعديا، فان كل قائمة \(G_k\) تكون مرتبة مسبقا. وهكذا تتحول الصيغة السابقة، لكل \(k\)، الى نوعين من العد: ازواج داخل \(G_k\)، وازواج بين \(G_k\) و \(G_{k+1}\).
اذا كان لدينا قائمتان مرتبتان \(A\) و \(B\)، فنحن نريد عدد الازواج \((a,b)\in A\times B\) التي تحقق \(ab\le N\). عندما نزيد \(a\) من اليسار الى اليمين، فان اكبر فهرس صالح في \(B\) لا يمكنه الا ان يتحرك الى اليسار. لذلك تكفي عملية مرور monotone واحدة بمؤشرين لحساب كل الازواج الصالحة بزمن \(O(|A|+|B|)\).
التنفيذ يطبق هذا المسح مرة على \((G_k,G_k)\) ومرة على \((G_k,G_{k+1})\). وبعد جمع النتائج على كل \(k\) نحصل على \(S(N)\).
بالنسبة الى \(n=36=2^2\cdot 3^2\)، لدينا
$$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$$
اكبر معامل يساوي \(3\)، ولذلك \(f(36)=3\). قواسم الطبقة الوسطى هي \(4,6,9\)، وهي تعطي التحليلات المرتبة
$$(4,9),\qquad (6,6),\qquad (9,4).$$
وهذه كلها من الحالة الزوجية حيث \(\Omega=2\) على الجهتين.
اما بالنسبة الى \(n=12=2^2\cdot 3\)، فنحصل على
$$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$$
ومن ثم \(f(12)=2\). القاسمان في الطبقة الوسطى الدنيا هما \(2\) و \(3\)، ويقابلهما الزوجان
$$(2,6),\qquad (3,4),$$
اي بنمط درجات \((1,2)\). وهذه هي الحالة الفردية بين مجموعتين متتاليتين.
نسختا C++ و Python تبنيان جدول SPF ثم تحسبان \(\Omega(i)\) من العلاقة السابقة وتضيفان كل عدد الى by_degs[d]. اما نسخة Java فتعرف اولا عدد العناصر في كل درجة، ثم تخصص مصفوفات بالحجم الدقيق وتملؤها في مرور ثان، مما يقلل كلفة البنى الديناميكية.
بعد ذلك تنفذ النسخ الثلاث الحلقات نفسها ذات المؤشرين. وبما ان \(2^{26}\le 10^8<2^{27}\)، فان اكبر قيمة ممكنة لـ \(\Omega(n)\) هي \(26\)، ولذلك فان المصفوفات الصغيرة الثابتة في Java كافية تماما.
بناء غربال SPF يكلف \(O(N\log\log N)\) زمنا. وحساب \(\Omega(i)\) وتوزيع الاعداد على المجموعات يكلف \(O(N)\). اما مجموع كل عمليات المسح بالمؤشرين فهو خطي في الحجم الكلي للمجموعات، لذلك يبقى التعقيد الزمني الكلي \(O(N\log\log N)\). ويكون استهلاك الذاكرة \(O(N)\) من اجل الغربال ومصفوفة الدرجات والاعداد المجمعة.