For each integer \(n \ge 2\), let \(\operatorname{fsf}(n)\) denote the number of unordered factorizations of \(n\) into squarefree factors greater than 1. Repeated factors are allowed as long as each factor itself is squarefree. The Project Euler quantity is
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
As a small example, \(12=2^2\cdot 3\) has exactly two valid factorizations:
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
so \(\operatorname{fsf}(12)=2\). A direct scan up to \(10^{10}\) is impossible, so the implementation groups integers by their exponent pattern and counts entire families at once.
Write the prime factorization of \(n\) as
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$$
The multiset of exponents \((e_1,\dots,e_r)\) is the only part that matters for the squarefree-factor count.
Every squarefree factor of \(n\) is obtained by choosing a nonempty subset \(J\subseteq\{1,\dots,r\}\) and taking
$$f_J=\prod_{i\in J} p_i.$$
Because the factorization is unordered, all we need is the multiplicity \(x_J\in\mathbb{Z}_{\ge 0}\) of each subset type. Prime \(p_i\) must appear exactly \(e_i\) times across all chosen factors, hence
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
So \(\operatorname{fsf}(n)\) is precisely the number of nonnegative integer solutions of this linear system. In particular, it depends only on the exponent signature, not on the actual prime values. If \(\sigma=(e_1,\dots,e_r)\), we may therefore write \(F(\sigma)\) for this common value.
The C++ and Java implementations build all nonempty bitmasks \(J\), sort them by decreasing size, and recurse on a vector of remaining exponents. At one mask \(J\), the multiplicity \(x_J\) can be any value from \(0\) up to
$$\min_{i\in J} \operatorname{remaining}_i.$$
For each choice, the code subtracts that amount from every coordinate in \(J\) and continues with the next mask. The base case returns 1 if all remaining exponents are zero and 0 otherwise. Memoization uses the pair
$$\bigl(\text{mask position},\text{remaining exponent vector}\bigr)$$
as the state key. This is exactly what fsf_from_signature and its DFS helper implement.
For \(12=2^2\cdot 3\), the signature is \((2,1)\). There are three subset types: \(\{1\}\), \(\{2\}\), and \(\{1,2\}\). Writing their multiplicities as \(x_1,x_2,x_{12}\), the constraints become
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$$
The two solutions are
$$ (x_1,x_2,x_{12})=(2,1,0)\quad\text{and}\quad (1,0,1), $$
corresponding to \(2\cdot 2\cdot 3\) and \(2\cdot 6\). Hence \(F(2,1)=2\). Every integer with exponent multiset \(\{2,1\}\) has the same squarefree-factor count.
To sum over all \(n\le N\), the program does not iterate over integers. Instead it enumerates exponent signatures \(\sigma=(e_1,\dots,e_r)\) in nonincreasing order
$$e_1\ge e_2\ge \dots\ge e_r\ge 1.$$
For such a signature, the smallest integer realizing it is obtained by pairing the largest exponent with the smallest prime:
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
If \(m_{\min}(\sigma)>N\), then no integer up to \(N\) can have that signature. If \(m_{\min}(\sigma)\le N\), then the signature is feasible. This is exactly why generate_signatures_dfs grows signatures along the seed primes \(2,3,5,\dots\) while forcing exponents to stay nonincreasing.
A signature is an unordered multiset of exponents, but actual integers assign those exponents to increasing primes. For one ordered tuple \(a=(a_1,\dots,a_r)\), define
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$$
The recursion in OrderedPrimeTupleCounter chooses the primes left to right. If
$$T_k=a_k+a_{k+1}+\dots+a_r$$
is the remaining exponent sum at depth \(k\), then the current prime must satisfy
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$$
where \(R\) is the remaining limit after previous prime choices. This bound is sharp because every later prime is at least \(q_k\). On the last position there is no deeper recursion; the number of valid choices is obtained directly from the prime-counting function:
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
If some exponents repeat, the same ordered tuple would arise many times, so the code generates only unique permutations of the signature.
The signature \((2,1)\) illustrates the split between \(F(\sigma)\) and \(C(a,N)\). We already know \(F(2,1)=2\). For \(N=100\), the ordered tuple \((2,1)\) counts integers of the form \(p^2q\) with \(p\lt q\), while \((1,2)\) counts integers of the form \(pq^2\).
For \((2,1)\): \(2^2q\le 100\) gives 8 possibilities for \(q\), and \(3^2q\le 100\) gives 3 more, so
$$C((2,1),100)=11.$$
For \((1,2)\): \(2q^2\le 100\) gives 3 possibilities and \(3q^2\le 100\) gives 1 more, so
$$C((1,2),100)=4.$$
Therefore this entire signature family contributes
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30$$
to \(S(100)\). This is exactly the logic used for every signature.
The last remaining ingredient is a fast \(\pi(x)\). The implementation builds a sieve up to \(\sqrt{N}\), stores the prime list and the small values of \(\pi(x)\), and for larger arguments uses a Lehmer-style prime counter with cached
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
This makes the many root-bound queries inside the tuple recursion fast enough. If \(\Sigma(N)\) is the set of feasible signatures and \(\mathcal{U}(\sigma)\) is the set of unique permutations of \(\sigma\), then the program computes
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
The C++ file contains the full optimized solver. PrimeTable builds the sieve and small \(\pi(x)\) table, PrimeCounter provides the Lehmer-style prime-counting routine, fsf_from_signature counts squarefree factorizations for one signature, generate_signatures enumerates feasible exponent patterns, generate_unique_permutations expands repeated exponents into distinct orderings, and OrderedPrimeTupleCounter::count_for_exponents counts the prime tuples for one ordered exponent vector.
The Java solution mirrors the same mathematics and almost the same function decomposition in a single-threaded implementation. The Python file is intentionally thin: it recompiles and runs the C++ source when necessary, then parses the final numeric output. In other words, the mathematical source of truth is the shared C++/Java algorithm, while Python is just a bridge.
The C++ program also validates the logic with internal checkpoints: it verifies the known value \(S(100)=193\), compares fast and brute-force computations on a small limit, and checks that single-threaded and multi-threaded runs agree.
The sieve and small prime table up to \(\sqrt{N}\) cost \(O(\sqrt{N}\log\log \sqrt{N})\) time and \(O(\sqrt{N})\) memory. For \(N=10^{10}\), that preprocessing size is only \(10^5\).
The rest of the runtime is dominated by the signature tasks. There is no simple single closed form, because the DFS state counts depend on the exponent pattern and on the distribution of root-bound prime queries. However, the key compression is dramatic: the algorithm works on signatures, permutations, and memoized prime-tuple states rather than on all integers up to \(N\).
In this problem, the number of distinct prime factors is automatically small: the product of the first ten primes is \(6469693230\), while including the eleventh prime already exceeds \(10^{10}\). Hence every signature has length at most 10, which keeps the subset DFS, the permutation generation, and the tuple recursion practical. Memory is dominated by the memo tables for the factorization DFS and the prime-counting cache.
Für jede ganze Zahl \(n \ge 2\) sei \(\operatorname{fsf}(n)\) die Anzahl ungeordneter Zerlegungen von \(n\) in quadratfreie Faktoren größer als 1. Gleiche Faktoren dürfen mehrfach vorkommen, solange jeder einzelne Faktor quadratfrei ist. Gesucht ist
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
Als kleines Beispiel gilt für \(12=2^2\cdot 3\):
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
also \(\operatorname{fsf}(12)=2\). Ein direkter Durchlauf bis \(10^{10}\) ist unmöglich; daher gruppiert die Implementierung Zahlen nach ihrer Exponenten-Signatur und zählt ganze Familien auf einmal.
Schreibe die Primfaktorzerlegung von \(n\) als
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$$
Für die Anzahl der quadratfreien Faktorzerlegungen ist nur das Exponentenmuster \((e_1,\dots,e_r)\) relevant.
Jeder quadratfreie Faktor von \(n\) entsteht durch die Wahl einer nichtleeren Teilmenge \(J\subseteq\{1,\dots,r\}\) und hat den Wert
$$f_J=\prod_{i\in J} p_i.$$
Da die Zerlegung ungeordnet ist, reicht die Multiplizität \(x_J\in\mathbb{Z}_{\ge 0}\) jedes Teilmengentyps. Die Primzahl \(p_i\) muss insgesamt genau \(e_i\)-mal über alle gewählten Faktoren verteilt sein. Also gilt
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
Damit ist \(\operatorname{fsf}(n)\) genau die Anzahl nichtnegativer ganzzahliger Lösungen dieses linearen Systems. Insbesondere hängt der Wert nur von der Signatur ab, nicht von den konkreten Primzahlen. Für eine Signatur \(\sigma=(e_1,\dots,e_r)\) schreiben wir daher \(F(\sigma)\).
Die C++- und Java-Implementierungen erzeugen alle nichtleeren Bitmasken \(J\), sortieren sie nach absteigender Größe und rekursieren über einen Vektor verbleibender Exponenten. Für eine Maske \(J\) kann die Multiplizität \(x_J\) jeden Wert zwischen \(0\) und
$$\min_{i\in J} \operatorname{remaining}_i$$
annehmen. Für jede Wahl zieht der Code diesen Wert bei allen Koordinaten in \(J\) ab und geht zur nächsten Maske weiter. Im Endzustand liefert die Rekursion genau dann 1, wenn alle Restexponenten Null sind, sonst 0. Memoisiert wird der Zustand
$$\bigl(\text{Maskenposition},\text{Restvektor}\bigr).$$
Genau das implementieren fsf_from_signature und die zugehörige DFS-Hilfsfunktion.
Für \(12=2^2\cdot 3\) ist die Signatur \((2,1)\). Es gibt drei Teilmengentypen: \(\{1\}\), \(\{2\}\) und \(\{1,2\}\). Mit Multiplizitäten \(x_1,x_2,x_{12}\) lauten die Bedingungen
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$$
Die beiden Lösungen sind
$$ (x_1,x_2,x_{12})=(2,1,0)\quad\text{und}\quad (1,0,1), $$
also \(2\cdot 2\cdot 3\) und \(2\cdot 6\). Folglich ist \(F(2,1)=2\). Jede Zahl mit Exponentenmultimenge \(\{2,1\}\) hat denselben Wert.
Für die Summe über alle \(n\le N\) iteriert das Programm nicht über die Zahlen selbst, sondern über Signaturen \(\sigma=(e_1,\dots,e_r)\) in nichtzunehmender Reihenfolge
$$e_1\ge e_2\ge \dots\ge e_r\ge 1.$$
Die kleinste Zahl mit dieser Signatur entsteht, wenn der größte Exponent mit der kleinsten Primzahl gepaart wird:
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
Ist \(m_{\min}(\sigma)>N\), dann kann keine Zahl bis \(N\) diese Signatur besitzen. Ist \(m_{\min}(\sigma)\le N\), dann ist die Signatur zulässig. Genau deshalb wächst generate_signatures_dfs entlang der Startprimzahlen \(2,3,5,\dots\) und erzwingt nichtzunehmende Exponenten.
Eine Signatur ist eine ungeordnete Multimenge von Exponenten. Konkrete Zahlen ordnen diese Exponenten aber wachsenden Primzahlen zu. Für ein geordnetes Tupel \(a=(a_1,\dots,a_r)\) definieren wir
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$$
Die Rekursion in OrderedPrimeTupleCounter wählt die Primzahlen von links nach rechts. Ist
$$T_k=a_k+a_{k+1}+\dots+a_r$$
die verbleibende Exponentensumme an Tiefe \(k\), dann muss die aktuelle Primzahl die Schranke
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor$$
erfüllen, wobei \(R\) die nach den bisherigen Entscheidungen verbleibende Obergrenze ist. Diese Schranke ist scharf, weil jede spätere Primzahl mindestens so groß ist wie \(q_k\). Im letzten Schritt ersetzt der Code die Rekursion durch eine direkte Primzahlzählung:
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
Bei wiederholten Exponenten erzeugt die Implementierung nur unterschiedliche Permutationen der Signatur.
Die Signatur \((2,1)\) zeigt die Trennung zwischen \(F(\sigma)\) und \(C(a,N)\). Wir wissen bereits \(F(2,1)=2\). Für \(N=100\) zählt das geordnete Tupel \((2,1)\) Zahlen der Form \(p^2q\) mit \(p\lt q\), während \((1,2)\) Zahlen der Form \(pq^2\) zählt.
Für \((2,1)\) liefern \(2^2q\le 100\) genau 8 Möglichkeiten und \(3^2q\le 100\) weitere 3, also
$$C((2,1),100)=11.$$
Für \((1,2)\) ergeben \(2q^2\le 100\) drei Möglichkeiten und \(3q^2\le 100\) noch eine, also
$$C((1,2),100)=4.$$
Damit trägt diese Signaturfamilie insgesamt
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30$$
zu \(S(100)\) bei. Genauso verfährt das Programm mit jeder Signatur.
Als letzte Zutat benötigt man eine schnelle \(\pi(x)\). Die Implementierung baut ein Sieb bis \(\sqrt{N}\), speichert die Primzahlliste und kleine Werte von \(\pi(x)\), und verwendet für größere Argumente einen Lehmer-artigen Primzahlzähler mit gecachter Funktion
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
Damit werden die vielen Wurzelabfragen in der Tupelrekursion schnell genug. Bezeichnet \(\Sigma(N)\) die Menge aller zulässigen Signaturen und \(\mathcal{U}(\sigma)\) die Menge ihrer unterschiedlichen Permutationen, dann berechnet das Programm
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
Die C++-Datei enthält den vollständigen optimierten Löser. PrimeTable baut Sieb und kleine \(\pi(x)\)-Tabelle auf, PrimeCounter liefert die Lehmer-artige Primzahlzählung, fsf_from_signature zählt die quadratfreien Zerlegungen einer Signatur, generate_signatures erzeugt alle zulässigen Exponentenmuster, generate_unique_permutations expandiert Wiederholungen zu verschiedenen Reihenfolgen, und OrderedPrimeTupleCounter::count_for_exponents zählt die Primtupel für einen geordneten Exponentenvektor.
Die Java-Lösung spiegelt dieselbe Mathematik und fast dieselbe Funktionszerlegung in einer einsträngigen Implementierung. Die Python-Datei ist bewusst dünn: Sie kompiliert bei Bedarf die C++-Quelle, führt sie aus und extrahiert die Ausgabe. Inhaltlich liegt die mathematische Logik also in C++ und Java; Python ist nur eine Brücke.
Zusätzlich prüft das C++-Programm seine Logik über interne Kontrollwerte: Es verifiziert den bekannten Wert \(S(100)=193\), vergleicht schnelle und brute-force Berechnung für eine kleine Schranke und prüft die Konsistenz zwischen Single-Thread- und Multi-Thread-Lauf.
Das Sieb und die kleine Primzahltafel bis \(\sqrt{N}\) kosten \(O(\sqrt{N}\log\log \sqrt{N})\) Zeit und \(O(\sqrt{N})\) Speicher. Für \(N=10^{10}\) beträgt diese Vorverarbeitung nur \(10^5\).
Die restliche Laufzeit wird von den Signatur-Aufgaben dominiert. Es gibt keine einfache geschlossene Asymptotik, weil die Zahl der DFS-Zustände von der Exponentensignatur und von der Verteilung der Primzahlzähl-Abfragen abhängt. Der entscheidende Gewinn ist aber, dass die Methode auf Signaturen, Permutationen und memoisierten Primtupel-Zuständen arbeitet statt auf allen Zahlen bis \(N\).
In dieser Aufgabe bleibt die Zahl verschiedener Primfaktoren automatisch klein: Das Produkt der ersten zehn Primzahlen ist \(6469693230\), mit der elften Primzahl liegt man bereits über \(10^{10}\). Daher hat jede Signatur Länge höchstens 10, was Teilmengen-DFS, Permutationserzeugung und Tupelrekursion praktikabel hält. Der Speicherverbrauch wird von den Memo-Tabellen für die Faktorisierungs-DFS und dem Primzahlzähl-Cache dominiert.
Her \(n \ge 2\) için \(\operatorname{fsf}(n)\), \(n\)'in 1'den büyük kare-serbest çarpanlara ayrılma sayısı olsun; çarpanların sırası önemli değildir. Aynı çarpan birden fazla kez kullanılabilir, yeter ki her bir çarpanın kendisi kare-serbest olsun. Aranan toplam
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
Küçük bir örnek olarak \(12=2^2\cdot 3\) için
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
olduğundan \(\operatorname{fsf}(12)=2\). \(10^{10}\)'a kadar tek tek tarama yapılamayacağı için kod, sayıları üs imzalarına göre gruplayıp tüm aileleri birlikte sayar.
\(n\)'in asal çarpanlara ayrılışı
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1$$
olsun. Kare-serbest çarpan sayısı açısından önemli olan şey, asalların kendisi değil üs kalıbıdır.
\(n\)'in her kare-serbest çarpanı, \(\{1,\dots,r\}\) kümesinin boş olmayan bir alt kümesi \(J\) seçilerek elde edilir:
$$f_J=\prod_{i\in J} p_i.$$
Çarpanlara ayırma sırasız olduğundan, yalnızca her alt küme tipinin kaç kez kullanıldığını bilmek yeterlidir. Buna \(x_J\in\mathbb{Z}_{\ge 0}\) diyelim. Asal \(p_i\), seçilen tüm çarpanlar boyunca tam olarak \(e_i\) kez görünmelidir; dolayısıyla
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
Böylece \(\operatorname{fsf}(n)\), bu lineer sistemin negatif olmayan tamsayı çözümlerinin sayısına eşittir. Demek ki değer, asal sayılardan değil yalnızca üs imzasından etkilenir. \(\sigma=(e_1,\dots,e_r)\) için bu ortak değeri \(F(\sigma)\) ile gösterebiliriz.
C++ ve Java çözümleri tüm boş olmayan bit maskelerini \(J\) üretir, bunları bit sayısı büyükten küçüğe sıralar ve kalan üs vektörü üzerinde özyinelemeli dolaşır. Bir maske \(J\) için \(x_J\) değeri, \(0\) ile
$$\min_{i\in J} \operatorname{remaining}_i$$
arasında herhangi bir sayı olabilir. Her seçimde kod, bu değeri \(J\) içindeki tüm koordinatlardan düşer ve bir sonraki maskeye geçer. Taban durumda tüm kalan üsler sıfırsa 1, aksi halde 0 döner. Memo anahtarı
$$\bigl(\operatorname{maskPos},\operatorname{remaining}\bigr)$$
çiftidir. fsf_from_signature fonksiyonu tam olarak bunu uygular.
\(12=2^2\cdot 3\) için imza \((2,1)\)'dir. Üç alt küme tipi vardır: \(\{1\}\), \(\{2\}\) ve \(\{1,2\}\). Bunların kullanım sayıları \(x_1,x_2,x_{12}\) olsun. Koşullar
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0$$
şeklindedir. İki çözüm vardır:
$$ (x_1,x_2,x_{12})=(2,1,0)\quad\text{ve}\quad (1,0,1). $$
Bunlar \(2\cdot 2\cdot 3\) ve \(2\cdot 6\) ayrışımlarına karşılık gelir. Sonuç olarak \(F(2,1)=2\). Üs çokluğu \(\{2,1\}\) olan her sayı aynı değere sahiptir.
Tüm \(n\le N\) toplamı için program sayıları tek tek dolaşmaz; bunun yerine üs imzalarını
$$e_1\ge e_2\ge \dots\ge e_r\ge 1$$
biçiminde, azalmayan değil azalan sırada üretir. Böyle bir imzayı gerçekleştiren en küçük sayı, büyük üslerin küçük asallarla eşleştirilmesiyle elde edilir:
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
Eğer \(m_{\min}(\sigma)>N\) ise, \(N\)'e kadar hiçbir sayı bu imzaya sahip olamaz. Eğer \(m_{\min}(\sigma)\le N\) ise imza mümkündür. generate_signatures_dfs fonksiyonunun \(2,3,5,\dots\) asalları boyunca ilerleyip üsleri azalmayan değil azalan biçimde kısıtlamasının nedeni tam olarak budur.
İmza, üslerin sırasız bir çoklu kümesidir; gerçek sayılar ise bu üsleri artan asallara belli bir sırayla yerleştirir. Bir sıralı dizi \(a=(a_1,\dots,a_r)\) için
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|$$
tanımını yapalım. OrderedPrimeTupleCounter içindeki özyineleme asalları soldan sağa seçer. Eğer derinlik \(k\)'da kalan üs toplamı
$$T_k=a_k+a_{k+1}+\dots+a_r$$
ise, o anda seçilen asal şu sınırı sağlamak zorundadır:
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$$
burada \(R\), önceki seçimlerden sonra kalan limittir. Bu sınır keskindir; çünkü daha sonraki tüm asallar en az \(q_k\) kadar büyüktür. Son basamakta özyineleme yerine doğrudan asal sayım kullanılır:
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
Bazı üsler tekrarlanıyorsa, aynı düzen birkaç kez sayılmasın diye kod yalnızca benzersiz permütasyonları üretir.
\((2,1)\) imzası, \(F(\sigma)\) ile \(C(a,N)\) ayrımını net gösterir. Daha önce \(F(2,1)=2\) bulduk. \(N=100\) için sıralı dizi \((2,1)\), \(p\lt q\) koşuluyla \(p^2q\) biçimindeki sayıları; \((1,2)\) ise \(pq^2\) biçimindekileri sayar.
\((2,1)\) için \(2^2q\le 100\) den 8 seçenek, \(3^2q\le 100\) den 3 seçenek gelir; yani
$$C((2,1),100)=11.$$
\((1,2)\) için \(2q^2\le 100\) üç seçenek, \(3q^2\le 100\) ise bir seçenek verir; dolayısıyla
$$C((1,2),100)=4.$$
Bu durumda bu imza ailesinin toplam katkısı
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30$$
olur. Program her imza için aynı mantığı uygular.
Son eksik parça hızlı bir \(\pi(x)\) hesabıdır. Uygulama \(\sqrt{N}\)'e kadar bir asal tablosu kurar, küçük \(\pi(x)\) değerlerini saklar ve daha büyük argümanlar için önbellekli Lehmer tipi bir sayaç kullanır:
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
Böylece tuple özyinelemesi içindeki çok sayıdaki kök-sınır sorgusu hızlı çalışır. \(\Sigma(N)\), mümkün imzalar kümesi; \(\mathcal{U}(\sigma)\) ise \(\sigma\)'nın benzersiz permütasyonları olsun. Programın hesapladığı toplam
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
C++ dosyası tam optimize çözümü içerir. PrimeTable süzgeç ve küçük \(\pi(x)\) tablosunu kurar, PrimeCounter Lehmer tipi asal sayımı sağlar, fsf_from_signature bir imza için kare-serbest ayrışım sayısını hesaplar, generate_signatures mümkün üs kalıplarını üretir, generate_unique_permutations tekrar eden üsleri benzersiz sıralara açar ve OrderedPrimeTupleCounter::count_for_exponents tek bir sıralı üs vektörü için asal tuple sayısını bulur.
Java çözümü aynı matematiği ve neredeyse aynı fonksiyon ayrımını tek iş parçacıklı biçimde yansıtır. Python dosyası ise bilerek incedir: gerektiğinde C++ kaynağını derler, çalıştırır ve sonucu ayrıştırır. Yani matematiksel asıl çözüm C++ ve Java tarafındadır; Python yalnızca bir köprüdür.
C++ programı ayrıca iç doğrulamalar da yapar: bilinen \(S(100)=193\) değerini test eder, küçük bir sınırda hızlı çözümü kaba kuvvetle karşılaştırır ve tek iş parçacıklı sonuçla çok iş parçacıklı sonucun aynı olduğunu denetler.
\(\sqrt{N}\)'e kadar olan süzgeç ve küçük asal tablosu \(O(\sqrt{N}\log\log \sqrt{N})\) zaman ve \(O(\sqrt{N})\) bellek kullanır. \(N=10^{10}\) için bu ön işlem boyutu yalnızca \(10^5\)'tir.
Kalan çalışma süresi imza görevlerinde toplanır. Tek ve temiz bir kapalı asimptotik ifade yoktur; çünkü DFS durum sayısı, üs desenine ve kök sınırıyla yapılan asal sayım sorgularının dağılımına bağlıdır. Asıl kazanç, yönteminin tüm sayıları taramak yerine imzalar, permütasyonlar ve memoized asal-tuple durumları üzerinde çalışmasıdır.
Bu problemde farklı asal çarpan sayısı zaten küçüktür: ilk on asalın çarpımı \(6469693230\), on birinci asalı dahil edince değer \(10^{10}\)'u aşar. Bu yüzden her imzanın uzunluğu en fazla 10'dur. Böylece alt küme DFS'i, permütasyon üretimi ve tuple özyinelemesi pratik kalır. Bellek kullanımını esas olarak faktorizasyon DFS'inin ve asal sayım önbelleğinin memo tabloları belirler.
Para cada entero \(n \ge 2\), sea \(\operatorname{fsf}(n)\) el número de factorizaciones no ordenadas de \(n\) en factores libres de cuadrados mayores que 1. Se permiten repeticiones, siempre que cada factor individual siga siendo libre de cuadrados. La cantidad pedida es
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
Por ejemplo, \(12=2^2\cdot 3\) tiene exactamente dos descomposiciones válidas:
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
así que \(\operatorname{fsf}(12)=2\). Un barrido directo hasta \(10^{10}\) es inviable, por lo que la implementación agrupa enteros por su firma de exponentes y cuenta familias enteras de una sola vez.
Escribimos la factorización prima de \(n\) como
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$$
Para contar las factorizaciones en factores libres de cuadrados, lo importante no son los valores concretos de los primos, sino solo el patrón de exponentes.
Cada factor libre de cuadrados de \(n\) se obtiene eligiendo un subconjunto no vacío \(J\subseteq\{1,\dots,r\}\) y tomando
$$f_J=\prod_{i\in J} p_i.$$
Como el orden no importa, basta conocer la multiplicidad \(x_J\in\mathbb{Z}_{\ge 0}\) de cada tipo de subconjunto. El primo \(p_i\) debe aparecer exactamente \(e_i\) veces a lo largo de todos los factores elegidos, así que
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
Por tanto, \(\operatorname{fsf}(n)\) es exactamente el número de soluciones enteras no negativas de este sistema lineal. En particular, depende solo de la firma de exponentes y no de qué primos concretos aparezcan. Si \(\sigma=(e_1,\dots,e_r)\), denotamos por \(F(\sigma)\) ese valor común.
Las implementaciones en C++ y Java construyen todas las máscaras no vacías \(J\), las ordenan por tamaño decreciente y hacen una recursión sobre un vector de exponentes restantes. Para una máscara \(J\), la multiplicidad \(x_J\) puede tomar cualquier valor entre \(0\) y
$$\min_{i\in J} \operatorname{remaining}_i.$$
Para cada elección, el código resta esa cantidad de todas las coordenadas incluidas en \(J\) y continúa con la siguiente máscara. El caso base devuelve 1 si todos los exponentes restantes son cero y 0 en caso contrario. La memoización usa como estado
$$\bigl(\operatorname{maskPos},\operatorname{remaining}\bigr).$$
Eso es exactamente lo que implementa fsf_from_signature.
Para \(12=2^2\cdot 3\), la firma es \((2,1)\). Hay tres tipos de subconjunto: \(\{1\}\), \(\{2\}\) y \(\{1,2\}\). Si sus multiplicidades son \(x_1,x_2,x_{12}\), entonces las restricciones son
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$$
Las dos soluciones son
$$ (x_1,x_2,x_{12})=(2,1,0)\quad\text{y}\quad (1,0,1), $$
que corresponden a \(2\cdot 2\cdot 3\) y \(2\cdot 6\). Así, \(F(2,1)=2\). Cualquier entero con multiconjunto de exponentes \(\{2,1\}\) tendrá el mismo valor.
Para sumar sobre todos los \(n\le N\), el programa no recorre enteros uno por uno. En su lugar, enumera firmas \(\sigma=(e_1,\dots,e_r)\) en orden no creciente:
$$e_1\ge e_2\ge \dots\ge e_r\ge 1.$$
El entero más pequeño que realiza esa firma se obtiene emparejando el mayor exponente con el menor primo:
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
Si \(m_{\min}(\sigma)>N\), entonces ningún entero hasta \(N\) puede tener esa firma. Si \(m_{\min}(\sigma)\le N\), la firma sí es viable. Por eso generate_signatures_dfs avanza sobre los primos semilla \(2,3,5,\dots\) imponiendo que los exponentes no crezcan.
Una firma es un multiconjunto no ordenado, pero un entero concreto asigna esos exponentes a primos crecientes en un orden determinado. Para una tupla ordenada \(a=(a_1,\dots,a_r)\), definimos
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$$
La recursión de OrderedPrimeTupleCounter elige los primos de izquierda a derecha. Si
$$T_k=a_k+a_{k+1}+\dots+a_r$$
es la suma de exponentes restante en la profundidad \(k\), entonces el primo actual debe satisfacer
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$$
donde \(R\) es el límite restante tras las decisiones anteriores. Esta cota es exacta porque todo primo posterior es al menos tan grande como \(q_k\). En la última posición, el código sustituye la recursión por un conteo directo de primos:
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
Si algunos exponentes se repiten, la implementación genera solo las permutaciones distintas.
La firma \((2,1)\) muestra claramente la separación entre \(F(\sigma)\) y \(C(a,N)\). Ya sabemos que \(F(2,1)=2\). Para \(N=100\), la tupla ordenada \((2,1)\) cuenta enteros de la forma \(p^2q\) con \(p\lt q\), mientras que \((1,2)\) cuenta enteros de la forma \(pq^2\).
Para \((2,1)\), las desigualdades \(2^2q\le 100\) y \(3^2q\le 100\) dan \(8+3\) posibilidades, así que
$$C((2,1),100)=11.$$
Para \((1,2)\), las condiciones \(2q^2\le 100\) y \(3q^2\le 100\) dan \(3+1\) posibilidades, por lo que
$$C((1,2),100)=4.$$
La contribución total de esta familia de firma es entonces
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30.$$
El programa aplica exactamente esta lógica a cada firma posible.
La última pieza es una \(\pi(x)\) rápida. La implementación construye una criba hasta \(\sqrt{N}\), almacena la lista de primos y los valores pequeños de \(\pi(x)\), y para argumentos grandes usa un contador de primos de estilo Lehmer con caché de
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
Eso acelera las numerosas consultas con raíces que aparecen en la recursión de tuplas. Si \(\Sigma(N)\) es el conjunto de firmas viables y \(\mathcal{U}(\sigma)\) el conjunto de permutaciones distintas de \(\sigma\), entonces el programa calcula
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
El archivo C++ contiene el solucionador optimizado completo. PrimeTable construye la criba y la tabla pequeña de \(\pi(x)\), PrimeCounter implementa el contador de primos tipo Lehmer, fsf_from_signature cuenta las factorizaciones libres de cuadrados para una firma dada, generate_signatures enumera las firmas viables, generate_unique_permutations expande exponentes repetidos en órdenes distintos y OrderedPrimeTupleCounter::count_for_exponents cuenta las tuplas de primos para un vector ordenado de exponentes.
La versión Java reproduce la misma matemática y prácticamente la misma descomposición funcional en una implementación monohilo. El archivo Python es deliberadamente ligero: recompila y ejecuta la fuente C++ cuando hace falta y luego extrae la salida final. Es decir, la lógica matemática real vive en C++ y Java, mientras que Python actúa como puente.
El programa en C++ también incluye comprobaciones internas: verifica el valor conocido \(S(100)=193\), compara el método rápido con fuerza bruta en un límite pequeño y comprueba que las ejecuciones en uno y varios hilos produzcan el mismo resultado.
La criba y la tabla de primos pequeños hasta \(\sqrt{N}\) cuestan \(O(\sqrt{N}\log\log \sqrt{N})\) tiempo y \(O(\sqrt{N})\) memoria. Para \(N=10^{10}\), ese preprocesamiento solo llega a \(10^5\).
El resto del tiempo está dominado por las tareas sobre firmas. No hay una única fórmula cerrada sencilla, porque el número de estados DFS depende del patrón de exponentes y de la distribución de consultas al contador de primos. La compresión esencial es que el algoritmo trabaja con firmas, permutaciones y estados memoizados de tuplas de primos, no con todos los enteros hasta \(N\).
Además, el número de factores primos distintos es pequeño por fuerza: el producto de los diez primeros primos es \(6469693230\), mientras que al incluir el undécimo ya se supera \(10^{10}\). Así, toda firma tiene longitud a lo sumo 10, lo que mantiene manejables la DFS sobre subconjuntos, la generación de permutaciones y la recursión de tuplas. La memoria está dominada por las tablas de memoización y la caché del contador de primos.
对每个整数 \(n \ge 2\)，记 \(\operatorname{fsf}(n)\) 为把 \(n\) 分解成若干个大于 1 的平方自由因子时，不计顺序的分解方案数。因子允许重复，但每个因子本身都必须是平方自由数。题目要求计算
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
例如 \(12=2^2\cdot 3\) 有且只有两种合法分解：
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
因此 \(\operatorname{fsf}(12)=2\)。显然不可能把 \(2\) 到 \(10^{10}\) 的所有整数逐个处理，所以程序改为按“指数签名”把整数分组，并一次统计整类数字。
把 \(n\) 的素因子分解写成
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$$
对平方自由因子分解的计数来说，真正重要的不是素数本身，而是指数模式 \((e_1,\dots,e_r)\)。
\(n\) 的每个平方自由因子都对应于一个非空子集 \(J\subseteq\{1,\dots,r\}\)，其值为
$$f_J=\prod_{i\in J} p_i.$$
由于分解不计顺序，我们只需要知道每种子集类型出现了多少次。记其重数为 \(x_J\in\mathbb{Z}_{\ge 0}\)。素数 \(p_i\) 在所有选出因子中总共必须出现恰好 \(e_i\) 次，因此有
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
所以 \(\operatorname{fsf}(n)\) 就等于这个线性系统的非负整数解个数。特别地，它只取决于指数签名，而与具体是哪几个素数无关。若 \(\sigma=(e_1,\dots,e_r)\)，就记这个共同的值为 \(F(\sigma)\)。
C++ 和 Java 实现先生成所有非空 bitmask \(J\)，按集合大小从大到小排序，然后在“剩余指数向量”上做递归。对某个掩码 \(J\)，其重数 \(x_J\) 可以取 \(0\) 到
$$\min_{i\in J} \operatorname{remaining}_i$$
之间的任意值。每取一次，就从 \(J\) 中所有坐标减去同样的数量，再递归到下一掩码。所有掩码处理完以后，如果剩余向量全为 0，则返回 1，否则返回 0。记忆化状态就是
$$\bigl(\operatorname{maskPos},\operatorname{remaining}\bigr).$$
这正是 fsf_from_signature 所实现的数学过程。
对 \(12=2^2\cdot 3\)，签名是 \((2,1)\)。共有三种子集类型：\(\{1\}\)、\(\{2\}\)、\(\{1,2\}\)。若其重数分别为 \(x_1,x_2,x_{12}\)，则满足
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$$
它有两组解：
$$ (x_1,x_2,x_{12})=(2,1,0),\qquad (x_1,x_2,x_{12})=(1,0,1). $$
对应的分解就是 \(2\cdot 2\cdot 3\) 与 \(2\cdot 6\)。因此 \(F(2,1)=2\)。任何指数多重集为 \(\{2,1\}\) 的整数都有同样的平方自由分解数。
为了求和所有 \(n\le N\)，程序不会按整数枚举，而是按非增序的签名
$$e_1\ge e_2\ge \dots\ge e_r\ge 1$$
来枚举。对这样一个签名，实现它的最小整数来自“最大指数配最小素数”的安排：
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
如果 \(m_{\min}(\sigma)>N\)，那么不可能有任何不超过 \(N\) 的整数具有该签名；如果 \(m_{\min}(\sigma)\le N\)，该签名就是可行的。这正是 generate_signatures_dfs 沿着 \(2,3,5,\dots\) 这些种子素数递归并强制指数不增的原因。
签名本身是无序的指数多重集，但具体整数会把这些指数按某种顺序分配给递增的素数。对一个有序向量 \(a=(a_1,\dots,a_r)\)，定义
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$$
OrderedPrimeTupleCounter 中的递归按从左到右的顺序选择素数。如果在第 \(k\) 层时，剩余指数和为
$$T_k=a_k+a_{k+1}+\dots+a_r,$$
那么当前素数必须满足
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$$
其中 \(R\) 是前面已经选定部分之后的剩余上界。这个界是精确的，因为后续素数都不会小于当前素数。到最后一层时，不再递归，而是直接调用素数计数函数：
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
若签名中有重复指数，代码只生成不同的排列，以避免重复计数。
签名 \((2,1)\) 很适合说明 \(F(\sigma)\) 与 \(C(a,N)\) 的分工。我们已经知道 \(F(2,1)=2\)。当 \(N=100\) 时，有序向量 \((2,1)\) 统计的是 \(p^2q\) 这种形式，且 \(p\lt q\)；而 \((1,2)\) 统计的是 \(pq^2\)。
对 \((2,1)\)，由 \(2^2q\le 100\) 得到 8 个可选 \(q\)，由 \(3^2q\le 100\) 再得到 3 个，所以
$$C((2,1),100)=11.$$
对 \((1,2)\)，由 \(2q^2\le 100\) 得到 3 个，\(3q^2\le 100\) 再得到 1 个，因此
$$C((1,2),100)=4.$$
于是这一整类签名对 \(S(100)\) 的贡献为
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30.$$
程序对每一个可行签名都进行同样的处理。
最后一块拼图是快速计算 \(\pi(x)\)。实现先建立到 \(\sqrt{N}\) 为止的筛表，保存素数列表和小范围的 \(\pi(x)\)，然后对更大的参数使用带缓存的 Lehmer 型素数计数，其中会反复用到
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
这样，递归里大量出现的根号上界查询就可以高效完成。若 \(\Sigma(N)\) 表示所有可行签名的集合，\(\mathcal{U}(\sigma)\) 表示签名 \(\sigma\) 的不同排列集合，那么程序计算的是
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
C++ 文件包含完整的优化版求解器。PrimeTable 建立筛法和小范围 \(\pi(x)\) 表，PrimeCounter 提供 Lehmer 型素数计数，fsf_from_signature 负责一个签名的平方自由分解计数，generate_signatures 枚举所有可行指数签名，generate_unique_permutations 处理重复指数的不同顺序，而 OrderedPrimeTupleCounter::count_for_exponents 则计算某个有序指数向量对应的素数元组数量。
Java 版本复现了同样的数学思路和几乎相同的函数结构，只是采用单线程实现。Python 文件则是一个很薄的桥接层：如果需要，它会重新编译 C++ 源码并运行，然后解析最终输出。也就是说，真正的数学实现以 C++ 和 Java 为准，Python 只是调用入口。
C++ 程序还带有内部校验：它验证已知值 \(S(100)=193\)，在较小上界上比较快速算法与暴力算法，并检查单线程与多线程结果的一致性。
建立到 \(\sqrt{N}\) 的筛表和小素数表需要 \(O(\sqrt{N}\log\log \sqrt{N})\) 时间与 \(O(\sqrt{N})\) 空间。对 \(N=10^{10}\) 而言，这个预处理规模只有 \(10^5\)。
其余运行时间主要由签名任务决定。这里没有一个简单的单一闭式，因为 DFS 状态数量依赖于具体指数模式，也依赖于素数计数查询的分布。真正的压缩在于，算法处理的是签名、排列和记忆化后的素数元组状态，而不是遍历所有 \(n\le N\)。
此外，不同素因子的个数天然很小：前十个素数的乘积是 \(6469693230\)，再乘上第十一个素数就已经超过 \(10^{10}\)。因此每个签名的长度最多只有 10，这使得子集 DFS、排列生成和元组递归都保持在可处理范围内。内存主要消耗在各类 memo 表和素数计数缓存上。
Для каждого целого \(n \ge 2\) обозначим через \(\operatorname{fsf}(n)\) число неупорядоченных разложений \(n\) на квадратсвободные множители, большие 1. Одинаковые множители разрешены, если каждый отдельный множитель сам квадратсвободен. Требуется вычислить
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
Например, для \(12=2^2\cdot 3\) существуют ровно два допустимых разложения:
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
поэтому \(\operatorname{fsf}(12)=2\). Очевидно, полный перебор до \(10^{10}\) невозможен, и программа вместо отдельных чисел работает с целыми семействами, задаваемыми сигнатурой показателей.
Запишем разложение \(n\) на простые множители в виде
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$$
Для числа квадратсвободных факторизаций важны не сами простые числа, а только шаблон показателей \((e_1,\dots,e_r)\).
Каждый квадратсвободный множитель \(n\) получается выбором непустого подмножества \(J\subseteq\{1,\dots,r\}\):
$$f_J=\prod_{i\in J} p_i.$$
Поскольку порядок множителей не важен, достаточно знать кратность \(x_J\in\mathbb{Z}_{\ge 0}\) каждого типа подмножества. Простой множитель \(p_i\) должен встретиться ровно \(e_i\) раз во всех выбранных факторах, значит
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
Следовательно, \(\operatorname{fsf}(n)\) равна числу неотрицательных целочисленных решений этой линейной системы. Поэтому она зависит только от сигнатуры показателей, а не от конкретных простых чисел. Для сигнатуры \(\sigma=(e_1,\dots,e_r)\) будем обозначать это общее значение через \(F(\sigma)\).
Реализации на C++ и Java строят все непустые битовые маски \(J\), сортируют их по убыванию размера и запускают рекурсию по вектору оставшихся показателей. Для одной маски \(J\) величина \(x_J\) может принимать любое значение от \(0\) до
$$\min_{i\in J} \operatorname{remaining}_i.$$
Для каждого выбора код вычитает это значение из всех координат, входящих в \(J\), и переходит к следующей маске. В конце рекурсия возвращает 1, если все остаточные показатели занулены, и 0 иначе. Состояние для memo имеет вид
$$\bigl(\operatorname{maskPos},\operatorname{remaining}\bigr).$$
Именно это делает функция fsf_from_signature.
Для \(12=2^2\cdot 3\) сигнатура равна \((2,1)\). Есть три типа подмножеств: \(\{1\}\), \(\{2\}\) и \(\{1,2\}\). Обозначим их кратности через \(x_1,x_2,x_{12}\). Тогда имеем
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$$
Существует две допустимые тройки:
$$ (x_1,x_2,x_{12})=(2,1,0),\qquad (x_1,x_2,x_{12})=(1,0,1). $$
Им соответствуют разложения \(2\cdot 2\cdot 3\) и \(2\cdot 6\). Следовательно, \(F(2,1)=2\). Любое число с мультисетом показателей \(\{2,1\}\) имеет то же значение \(\operatorname{fsf}\).
Чтобы просуммировать по всем \(n\le N\), программа не идет по числам по одному, а перебирает сигнатуры \(\sigma=(e_1,\dots,e_r)\) в невозрастающем порядке
$$e_1\ge e_2\ge \dots\ge e_r\ge 1.$$
Наименьшее число с такой сигнатурой получается, если наибольший показатель поставить к наименьшему простому:
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
Если \(m_{\min}(\sigma)>N\), то ни одно число до \(N\) не может иметь такую сигнатуру. Если \(m_{\min}(\sigma)\le N\), сигнатура допустима. Именно поэтому generate_signatures_dfs растит сигнатуры вдоль простых \(2,3,5,\dots\), одновременно заставляя показатели не возрастать.
Сигнатура является неупорядоченным мультисетом, но конкретное число распределяет показатели по возрастающим простым в определенном порядке. Для одного упорядоченного вектора \(a=(a_1,\dots,a_r)\) определим
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$$
Рекурсия в OrderedPrimeTupleCounter выбирает простые слева направо. Если на глубине \(k\) сумма оставшихся показателей равна
$$T_k=a_k+a_{k+1}+\dots+a_r,$$
то текущий простой должен удовлетворять ограничению
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$$
где \(R\) — оставшийся лимит после предыдущих выборов. Эта граница точна, потому что каждый следующий простой не меньше текущего. На последнем шаге рекурсия заменяется прямым обращением к функции подсчета простых:
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
Если некоторые показатели повторяются, код генерирует только различные перестановки.
Сигнатура \((2,1)\) наглядно показывает разделение между \(F(\sigma)\) и \(C(a,N)\). Мы уже знаем, что \(F(2,1)=2\). При \(N=100\) упорядоченный набор \((2,1)\) считает числа вида \(p^2q\) с \(p\lt q\), а набор \((1,2)\) считает числа вида \(pq^2\).
Для \((2,1)\) из неравенств \(2^2q\le 100\) и \(3^2q\le 100\) получаем \(8+3\) вариантов, то есть
$$C((2,1),100)=11.$$
Для \((1,2)\) из условий \(2q^2\le 100\) и \(3q^2\le 100\) получаем \(3+1\) вариант, значит
$$C((1,2),100)=4.$$
Итак, все числа этого семейства вместе дают вклад
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30$$
в сумму \(S(100)\). Ровно так же программа поступает с каждой сигнатурой.
Последний ключевой компонент — быстрая функция \(\pi(x)\). Реализация строит решето до \(\sqrt{N}\), хранит список простых и малые значения \(\pi(x)\), а для больших аргументов использует счетчик простых в стиле Lehmer с кешированием функции
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
Именно это делает многочисленные запросы с корневыми границами в рекурсии достаточно быстрыми. Если \(\Sigma(N)\) — множество всех допустимых сигнатур, а \(\mathcal{U}(\sigma)\) — множество различных перестановок сигнатуры \(\sigma\), то программа вычисляет
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
Файл C++ содержит полный оптимизированный решатель. PrimeTable строит решето и малую таблицу \(\pi(x)\), PrimeCounter реализует счетчик простых типа Lehmer, fsf_from_signature считает число квадратсвободных факторизаций одной сигнатуры, generate_signatures перечисляет все допустимые шаблоны показателей, generate_unique_permutations раскрывает повторяющиеся показатели в разные порядки, а OrderedPrimeTupleCounter::count_for_exponents считает количество простых кортежей для одного упорядоченного вектора показателей.
Версия на Java воспроизводит ту же математику и почти ту же декомпозицию функций, но в однопоточном виде. Файл Python специально очень тонкий: при необходимости он перекомпилирует C++-источник, запускает его и затем извлекает итоговое число из вывода. Иными словами, математическая сущность решения находится в C++ и Java, а Python служит только мостом.
В C++ также встроены проверки корректности: программа подтверждает известное значение \(S(100)=193\), сравнивает быстрый и brute-force подходы на малом лимите и проверяет совпадение однопоточного и многопоточного результатов.
Решето и малая таблица простых до \(\sqrt{N}\) требуют \(O(\sqrt{N}\log\log \sqrt{N})\) времени и \(O(\sqrt{N})\) памяти. Для \(N=10^{10}\) это всего лишь \(10^5\) элементов предварительной обработки.
Оставшееся время работы определяется задачами по сигнатурам. Здесь нет одной аккуратной замкнутой формулы, потому что число состояний DFS зависит от конкретного рисунка показателей и от распределения запросов к счетчику простых. Главное сжатие состоит в том, что алгоритм работает с сигнатурами, их перестановками и мемоизированными состояниями подсчета простых кортежей, а не перебирает все числа до \(N\).
Кроме того, число различных простых множителей автоматически мало: произведение первых десяти простых равно \(6469693230\), а с одиннадцатым простым уже превышает \(10^{10}\). Поэтому длина любой сигнатуры не больше 10, и DFS по подмножествам, генерация перестановок и рекурсия по кортежам остаются практичными. Память в основном расходуется на таблицы memo и кеш для \(\pi(x)\).
لكل عدد صحيح \(n \ge 2\)، نرمز بـ \(\operatorname{fsf}(n)\) إلى عدد التفكيكات غير المرتبة للعدد \(n\) إلى عوامل خالية من المربعات وأكبر من 1. يُسمح بتكرار العامل نفسه ما دام كل عامل على حدة خاليًا من المربعات. الكمية المطلوبة هي
$$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$$
على سبيل المثال، للعدد \(12=2^2\cdot 3\) تفكيكان صحيحان فقط:
$$12=2\cdot 2\cdot 3=2\cdot 6,$$
ومن ثم \(\operatorname{fsf}(12)=2\). من الواضح أن المرور على جميع الأعداد حتى \(10^{10}\) غير ممكن، لذلك تجمع الخوارزمية الأعداد بحسب بصمة الأسس وتعدّ عائلات كاملة دفعة واحدة.
لنكتب التحليل الأولي لـ \(n\) على الصورة
$$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$$
بالنسبة لعدد التفكيكات إلى عوامل خالية من المربعات، المهم ليس قيم الأوليات نفسها بل نمط الأسس \((e_1,\dots,e_r)\).
كل عامل خالٍ من المربعات لـ \(n\) ينتج من اختيار مجموعة جزئية غير فارغة \(J\subseteq\{1,\dots,r\}\) وأخذ
$$f_J=\prod_{i\in J} p_i.$$
وبما أن ترتيب العوامل غير مهم، فيكفي أن نعرف عدد مرات ظهور كل نوع من هذه المجموعات. لنرمز إلى هذه المضاعفية بـ \(x_J\in\mathbb{Z}_{\ge 0}\). يجب أن يظهر كل أولي \(p_i\) مجموع \(e_i\) مرة عبر جميع العوامل المختارة، ولذلك نحصل على
$$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$$
إذن \(\operatorname{fsf}(n)\) تساوي عدد الحلول الصحيحة غير السالبة لهذا النظام الخطي. وبالتالي فهي تعتمد فقط على بصمة الأسس، لا على قيم الأوليات نفسها. إذا كانت \(\sigma=(e_1,\dots,e_r)\)، فسنرمز إلى هذه القيمة المشتركة بـ \(F(\sigma)\).
في C++ وJava تُولَّد جميع الأقنعة غير الفارغة \(J\)، ثم تُرتَّب بحسب عدد البتات تنازليًا، ثم تُجرى عودية على متجه الأسس المتبقية. بالنسبة إلى قناع معين \(J\)، يمكن أن تأخذ المضاعفية \(x_J\) أي قيمة بين \(0\) و
$$\min_{i\in J} \operatorname{remaining}_i.$$
لكل اختيار، يطرح الكود هذه القيمة من جميع الإحداثيات الموجودة في \(J\)، ثم ينتقل إلى القناع التالي. في النهاية تعيد العودية القيمة 1 إذا أصبحت جميع الأسس المتبقية صفرًا، وتعيد 0 خلاف ذلك. حالة التخزين المؤقت هي
$$\bigl(\operatorname{maskPos},\operatorname{remaining}\bigr).$$
وهذا بالضبط ما تنفذه الدالة fsf_from_signature.
بالنسبة إلى \(12=2^2\cdot 3\)، تكون البصمة \((2,1)\). توجد ثلاثة أنواع من المجموعات الجزئية: \(\{1\}\) و\(\{2\}\) و\(\{1,2\}\). إذا سمينا مضاعفياتها \(x_1,x_2,x_{12}\)، فإن القيود تصبح
$$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$$
ولهذا النظام حلان فقط:
$$ (x_1,x_2,x_{12})=(2,1,0),\qquad (x_1,x_2,x_{12})=(1,0,1). $$
وهما يقابلان التفكيكين \(2\cdot 2\cdot 3\) و\(2\cdot 6\). لذلك \(F(2,1)=2\). وكل عدد يملك متعدد الأسس \(\{2,1\}\) سيكون له العدد نفسه من التفكيكات الخالية من المربعات.
من أجل جمع جميع \(n\le N\)، لا يمر البرنامج على الأعداد واحدًا واحدًا، بل يعدد البصمات \(\sigma=(e_1,\dots,e_r)\) بترتيب غير متزايد:
$$e_1\ge e_2\ge \dots\ge e_r\ge 1.$$
وأصغر عدد يحقق هذه البصمة ينتج من إسناد أكبر أس إلى أصغر أولي:
$$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$$
إذا كان \(m_{\min}(\sigma)>N\)، فلا يوجد أي عدد حتى \(N\) يحقق هذه البصمة. وإذا كان \(m_{\min}(\sigma)\le N\)، فالبصمة ممكنة. ولهذا تحديدًا تعمل generate_signatures_dfs على الأوليات \(2,3,5,\dots\) مع فرض أن الأسس لا تزداد.
البصمة نفسها هي متعدد أسس غير مرتب، لكن العدد الفعلي يوزع هذه الأسس على أوليات متزايدة بترتيب معين. لبنية مرتبة \(a=(a_1,\dots,a_r)\) نعرّف
$$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$$
العودية في OrderedPrimeTupleCounter تختار الأوليات من اليسار إلى اليمين. إذا كانت
$$T_k=a_k+a_{k+1}+\dots+a_r$$
هي مجموع الأسس المتبقية عند العمق \(k\)، فلا بد أن يحقق الأولي الحالي
$$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$$
حيث \(R\) هو الحد المتبقي بعد الاختيارات السابقة. هذا القيد دقيق لأن كل أولي لاحق لا يقل عن الأولي الحالي. في الموضع الأخير لا حاجة لمزيد من العودية، ويُحسب عدد الخيارات مباشرة عبر دالة عدّ الأوليات:
$$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$$
وإذا تكررت بعض الأسس، فإن الكود يولد فقط التباديل المختلفة كي لا تتكرر عملية العد.
البصمة \((2,1)\) توضح جيدًا الفصل بين \(F(\sigma)\) و\(C(a,N)\). لقد وجدنا بالفعل أن \(F(2,1)=2\). عندما \(N=100\)، فإن البنية المرتبة \((2,1)\) تعد الأعداد من الشكل \(p^2q\) مع \(p\lt q\)، بينما \((1,2)\) تعد الأعداد من الشكل \(pq^2\).
بالنسبة إلى \((2,1)\)، من الشرطين \(2^2q\le 100\) و\(3^2q\le 100\) نحصل على \(8+3\) إمكانات، أي
$$C((2,1),100)=11.$$
وبالنسبة إلى \((1,2)\)، من الشرطين \(2q^2\le 100\) و\(3q^2\le 100\) نحصل على \(3+1\) إمكانات، ومن ثم
$$C((1,2),100)=4.$$
إذن مساهمة هذه العائلة كلها في \(S(100)\) هي
$$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30.$$
وهذه هي الفكرة نفسها التي يطبقها البرنامج على كل بصمة ممكنة.
آخر مكوّن أساسي هو حساب سريع لـ \(\pi(x)\). تبني الخوارزمية غربالًا حتى \(\sqrt{N}\)، وتخزن قائمة الأوليات والقيم الصغيرة للدالة \(\pi(x)\)، ثم تستخدم عند القيم الأكبر عدّاد أوليات من نمط Lehmer مع تخزين للدالة
$$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$$
وهذا ما يجعل استعلامات الحدود الجذرية الكثيرة داخل العودية سريعة بما يكفي. إذا رمزنا إلى مجموعة البصمات الممكنة بـ \(\Sigma(N)\)، وإلى مجموعة التباديل المختلفة للبصمة \(\sigma\) بـ \(\mathcal{U}(\sigma)\)، فإن البرنامج يحسب
$$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$$
ملف C++ يحتوي على المحرك الأمثل الكامل. تبني PrimeTable الغربال وجدول \(\pi(x)\) الصغير، وتنفذ PrimeCounter عدّ الأوليات بأسلوب Lehmer، وتحسب fsf_from_signature عدد التفكيكات الخالية من المربعات لبصمة واحدة، وتولد generate_signatures جميع بصمات الأسس الممكنة، وتوسع generate_unique_permutations الأسس المكررة إلى ترتيبات مختلفة، بينما تتولى OrderedPrimeTupleCounter::count_for_exponents عدّ كتل الأوليات لبنية أسس مرتبة واحدة.
أما نسخة Java فتعكس الفكرة الرياضية نفسها وتقسيم الوظائف نفسه تقريبًا في تنفيذ أحادي الخيط. وملف Python مقصود به أن يكون طبقة خفيفة فقط: فهو يعيد ترجمة ملف C++ عند الحاجة، ثم يشغله ويستخرج الجواب النهائي من الخرج. أي إن المنطق الرياضي الحقيقي موجود في C++ وJava، بينما Python يعمل كواجهة تشغيل.
ويحتوي برنامج C++ كذلك على اختبارات داخلية: فهو يتحقق من القيمة المعروفة \(S(100)=193\)، ويقارن الحل السريع بالحل المباشر على حد صغير، ويتأكد من تطابق النتائج بين التشغيل الأحادي والمتعدد الخيوط.
إن بناء الغربال وجدول الأوليات الصغيرة حتى \(\sqrt{N}\) يحتاج إلى زمن \(O(\sqrt{N}\log\log \sqrt{N})\) وذاكرة \(O(\sqrt{N})\). وعندما \(N=10^{10}\)، يكون حجم هذه المعالجة الأولية \(10^5\) فقط.
أما بقية الزمن فتحدده مهام البصمات. لا توجد صيغة أسيمبتوطية بسيطة واحدة هنا، لأن عدد حالات DFS يعتمد على نمط الأسس نفسه وعلى توزع استعلامات عدّ الأوليات الناتجة عن حدود الجذور. لكن الاختزال الحاسم هو أن الخوارزمية تعمل على البصمات والتباديل والحالات المحفوظة لعدّ كتل الأوليات، بدلًا من المرور على جميع الأعداد حتى \(N\).
إضافة إلى ذلك، فإن عدد العوامل الأولية المختلفة صغير تلقائيًا: حاصل ضرب أول عشرة أعداد أولية يساوي \(6469693230\)، بينما إدخال الأولي الحادي عشر يتجاوز \(10^{10}\). لذلك لا يزيد طول أي بصمة على 10، وهذا يجعل DFS على المجموعات الجزئية، وتوليد التباديل، والعودية على كتل الأوليات كلها عملية. أما الذاكرة فتستهلكها أساسًا جداول memo ومخزن عدّ الأوليات.