We seek the number of integers \(n \le N\), with \(N=9\times 10^{18}\), that can be written in the form
$$n=a^2b^3,\qquad a>1,\qquad b>1.$$
A direct scan up to \(N\) is impossible. The solution instead counts a larger class of numbers whose prime exponents are all at least \(2\), then removes the exceptional cases that still fail the conditions \(a>1\) and \(b>1\).
Define
$$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ for some } a,b>1\right\}.$$
If \(n=\prod p^{e_p}\) has the form \(a^2b^3\), then each exponent satisfies \(e_p\ge 2\). So every admissible \(n\) is a powerful number. The implementations therefore count all powerful numbers up to \(N\), and then subtract the powerful numbers that are still not valid \(a^2b^3\) values with both factors greater than \(1\).
Every powerful number has a unique representation
$$n=u^2v^3,$$
where \(v\) is squarefree. For each prime exponent \(e\ge 2\), write
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\},$$
so the parity of \(e\) decides whether that prime contributes once to \(v\). This makes the decomposition unique.
Therefore the number of powerful numbers up to \(N\) is
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$$
For each squarefree \(v\), every integer \(u\) with \(u^2v^3\le N\) contributes one powerful number.
If \(u=1\), then \(n=v^3\) with \(v\) squarefree. Every nonzero prime exponent is then exactly \(3\), and the local equation
$$3=2x+3y,\qquad x,y\ge 0$$
forces \(x=0\). So any such representation has \(a=1\), which is forbidden.
Hence we must subtract
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$$
The same squarefree sieve used for \(P(N)\) also yields this correction term.
If \(v=1\), then \(n=u^2\) is a perfect square. Such a number is not automatically admissible. The obstruction occurs exactly when \(u\) is cubefree.
If \(u\) is cubefree, every prime exponent of \(n=u^2\) is either \(2\) or \(4\). Neither exponent can contribute a positive cube part, because
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
has only solutions with \(y=0\). Therefore every representation forces \(b=1\).
Conversely, if \(u\) contains a cube factor \(p^3\), then \(n\) contains \(p^6\), and we can allocate \(p^2\) to the square part and \(p^3\) to the cube part, making both \(a\) and \(b\) greater than \(1\).
So we subtract the number of cubefree integers up to \(\lfloor\sqrt N\rfloor\):
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
By Möbius inversion,
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$$
After removing the previous two boundary families, one exceptional type remains: prime sixth powers \(p^6\).
For a single-prime exponent \(e\), the requirement that both factors be nontrivial is
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$$
This has solutions for \(e=5\) and for every \(e\ge 7\), but not for \(e=6\). Thus \(p^6\) is powerful, is not a squarefree cube, and is not a square with cubefree root, yet it still cannot be written with both \(a>1\) and \(b>1\).
If a powerful number has at least two distinct prime factors and survives Steps 2 and 3, then one prime can supply a square factor while another supplies a cube factor. So the only leftover obstruction is
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right),$$
the number of prime sixth powers up to \(N\).
The number \(1\) is included in \(P(N)\), and it is removed once by the squarefree-cube correction and once by the cubefree-square correction. Since it should be excluded only once, we add \(1\) back.
Therefore
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
This is exactly the formula implemented by the C++, Python, and Java implementations.
Here \(\lfloor N^{1/3}\rfloor=4\), and the squarefree values are \(1,2,3\). So
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
Next, \(C(100)=3\), coming from \(1^3,2^3,3^3\). Also \(\lfloor\sqrt{100}\rfloor=10\), and the cubefree integers up to \(10\) are
$$1,2,3,4,5,6,7,9,10,$$
so \(Q(10)=9\). Finally, \(\lfloor 100^{1/6}\rfloor=2\), hence \(R(100)=\pi(2)=1\).
Therefore
$$F(100)=14-3-9-1+1=2.$$
The two admissible numbers are \(64=2^2\cdot 2^3\) and \(72=3^2\cdot 2^3\).
The C++, Python, and Java implementations follow the same pipeline. First they compute exact integer square roots, cube roots, and sixth roots. Each root starts from a floating-point estimate and then uses short correction loops, which removes boundary errors near \(64\)-bit limits.
They then mark squarefree integers up to \(\lfloor N^{1/3}\rfloor\) by crossing out multiples of \(p^2\) for primes \(p\le \lfloor N^{1/6}\rfloor\). Scanning that array simultaneously gives the base sum \(P(N)\) and the correction \(C(N)\).
For the cubefree correction, the implementation computes Möbius values up to \(\lfloor N^{1/6}\rfloor\) with a sieve and evaluates
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor.$$
Finally it counts primes up to \(\lfloor N^{1/6}\rfloor\) for the sixth-power correction and combines the four terms. The same formula is checked on small values such as \(N=100\), \(20000\), and \(3000000\) before evaluating the target input.
Let \(V=\lfloor N^{1/3}\rfloor\) and \(D=\lfloor N^{1/6}\rfloor\). Marking squarefree integers up to \(V\) costs \(O(V\log\log V)\) time and \(O(V)\) memory. The Möbius sieve and the prime count up to \(D\) cost \(O(D)\) to \(O(D\log\log D)\) time and \(O(D)\) memory. Since \(V\) dominates \(D\), the overall method runs in \(O(N^{1/3}\log\log N)\) time with \(O(N^{1/3})\) memory.
Gesucht ist die Anzahl der ganzen Zahlen \(n \le N\) mit \(N=9\times 10^{18}\), die sich in der Form
$$n=a^2b^3,\qquad a>1,\qquad b>1$$
schreiben lassen. Eine direkte Suche bis \(N\) ist unmöglich, daher zählt die Lösung zunächst eine größere Klasse von Zahlen und entfernt danach genau die Fälle, die trotz dieser Vorzählung die Bedingungen \(a>1\) und \(b>1\) noch verletzen.
Wir definieren
$$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ für gewisse } a,b>1\right\}.$$
Hat \(n=\prod p^{e_p}\) die Form \(a^2b^3\), dann gilt für jeden Primexponenten \(e_p\ge 2\). Jede gesuchte Zahl ist also eine mächtige Zahl. Die Implementierungen zählen deshalb zunächst alle mächtigen Zahlen bis \(N\) und subtrahieren anschließend jene mächtigen Zahlen, die dennoch keine echte Darstellung mit beiden Faktoren größer als \(1\) besitzen.
Jede mächtige Zahl besitzt eine eindeutige Darstellung
$$n=u^2v^3,$$
wobei \(v\) quadratfrei ist. Für jeden Primexponenten \(e\ge 2\) schreiben wir
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\},$$
sodass die Parität von \(e\) festlegt, ob die entsprechende Primzahl einmal in \(v\) erscheint. Genau daraus folgt die Eindeutigkeit.
Damit ist die Anzahl aller mächtigen Zahlen bis \(N\)
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$$
Für jedes quadratfreie \(v\) trägt jedes \(u\) mit \(u^2v^3\le N\) genau eine mächtige Zahl bei.
Ist \(u=1\), so gilt \(n=v^3\) mit quadratfreiem \(v\). Dann ist jeder von Null verschiedene Primexponent gleich \(3\), und die lokale Gleichung
$$3=2x+3y,\qquad x,y\ge 0$$
erzwingt \(x=0\). Also hat jede solche Darstellung notwendigerweise \(a=1\), was verboten ist.
Daher müssen wir subtrahieren
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$$
Dasselbe Quadratfrei-Sieb, das \(P(N)\) liefert, liefert auch diesen Korrekturterm.
Ist \(v=1\), dann ist \(n=u^2\) ein perfektes Quadrat. Doch nicht jedes solche Quadrat ist zulässig. Das Hindernis tritt genau dann auf, wenn \(u\) kubusfrei ist.
Ist \(u\) kubusfrei, dann sind alle Primexponenten von \(n=u^2\) entweder \(2\) oder \(4\). Keiner dieser Exponenten kann einen positiven Kubusanteil liefern, denn
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
besitzt nur Lösungen mit \(y=0\). Damit ist in jeder Darstellung zwangsläufig \(b=1\).
Enthält \(u\) hingegen einen Kubusfaktor \(p^3\), dann enthält \(n\) einen Faktor \(p^6\). Man kann also \(p^2\) dem Quadratteil und \(p^3\) dem Kubusteil zuordnen, sodass beide Faktoren größer als \(1\) sind.
Folglich subtrahieren wir die Anzahl kubusfreier Zahlen bis \(\lfloor\sqrt N\rfloor\):
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
Mit Möbius-Inversion gilt
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$$
Nach den beiden Randkorrekturen bleibt genau ein Ausnahmetyp übrig: Primzahl-Sechstpotenzen \(p^6\).
Für einen einzelnen Primexponenten \(e\) lautet die Bedingung, dass beide Faktoren nichttrivial sein sollen,
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$$
Diese Gleichung ist für \(e=5\) und für alle \(e\ge 7\) lösbar, aber nicht für \(e=6\). Also ist \(p^6\) zwar mächtig, weder ein quadratfreier Kubus noch ein Quadrat mit kubusfreier Wurzel, aber trotzdem nicht in der geforderten Form mit \(a>1\) und \(b>1\) darstellbar.
Hat eine mächtige Zahl mindestens zwei verschiedene Primfaktoren und überlebt sie Schritt 2 und 3, dann kann eine Primzahl den Quadratteil und eine andere den Kubusteil liefern. Deshalb bleibt nur
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right)$$
als Korrekturterm übrig, also die Anzahl der Primzahl-Sechstpotenzen bis \(N\).
Die Zahl \(1\) ist in \(P(N)\) enthalten und wird sowohl durch die Korrektur für quadratfreie Kuben als auch durch die Korrektur für kubusfreie Quadrate entfernt. Da sie insgesamt nur einmal ausgeschlossen werden soll, addieren wir am Ende \(1\) zurück.
Damit erhält man
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
Genau diese Formel setzen die C++, Python- und Java-Implementierungen um.
Hier ist \(\lfloor N^{1/3}\rfloor=4\), und die quadratfreien Werte sind \(1,2,3\). Also
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
Weiter ist \(C(100)=3\), nämlich \(1^3,2^3,3^3\). Zudem gilt \(\lfloor\sqrt{100}\rfloor=10\), und die kubusfreien Zahlen bis \(10\) sind
$$1,2,3,4,5,6,7,9,10,$$
also \(Q(10)=9\). Schließlich ist \(\lfloor 100^{1/6}\rfloor=2\), also \(R(100)=\pi(2)=1\).
Daher
$$F(100)=14-3-9-1+1=2.$$
Die beiden zulässigen Zahlen sind \(64=2^2\cdot 2^3\) und \(72=3^2\cdot 2^3\).
Die C++, Python- und Java-Implementierungen verwenden dieselbe Rechenkette. Zuerst bestimmen sie exakte ganzzahlige Quadrat-, Kubik- und sechste Wurzeln. Dazu dient jeweils eine Gleitkomma-Näherung, die anschließend mit kurzen Korrekturschleifen exakt auf den richtigen ganzzahligen Wert gebracht wird.
Danach markieren sie alle quadratfreien Zahlen bis \(\lfloor N^{1/3}\rfloor\), indem Vielfache von \(p^2\) für Primzahlen \(p\le \lfloor N^{1/6}\rfloor\) gestrichen werden. Beim Durchlauf über dieses Feld entstehen gleichzeitig die Basissumme \(P(N)\) und die Korrektur \(C(N)\).
Für die kubusfreie Korrektur berechnet die Implementierung per Sieb die Möbius-Werte bis \(\lfloor N^{1/6}\rfloor\) und wertet
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor$$
aus. Zum Schluss wird die Anzahl der Primzahlen bis \(\lfloor N^{1/6}\rfloor\) für die Sechstpotenz-Korrektur bestimmt und alles zusammengesetzt. Die Formel wird zuvor noch an kleinen Testwerten wie \(N=100\), \(20000\) und \(3000000\) geprüft.
Sei \(V=\lfloor N^{1/3}\rfloor\) und \(D=\lfloor N^{1/6}\rfloor\). Das Markieren der quadratfreien Zahlen bis \(V\) kostet \(O(V\log\log V)\) Zeit und \(O(V)\) Speicher. Das Möbius-Sieb und das Primzahlzählen bis \(D\) benötigen \(O(D)\) bis \(O(D\log\log D)\) Zeit sowie \(O(D)\) Speicher. Weil \(V\) deutlich größer als \(D\) ist, ergibt sich insgesamt \(O(N^{1/3}\log\log N)\) Zeit bei \(O(N^{1/3})\) Speicher.
Aranan değer, \(N=9\times 10^{18}\) için
$$n=a^2b^3,\qquad a>1,\qquad b>1$$
şeklinde yazılabilen \(n\le N\) tamsayılarının sayısıdır. \(N\) çok büyük olduğu için doğrudan tarama yapılamaz. Bu nedenle çözüm önce daha geniş bir sayı sınıfını sayar, sonra gerçekten uygun olmayan istisna ailelerini çıkarır.
Şunu tanımlayalım:
$$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ olacak şekilde } a,b>1\right\}.$$
Eğer \(n=\prod p^{e_p}\) sayısı \(a^2b^3\) biçimindeyse her asal üs için \(e_p\ge 2\) olur. Yani aranan her sayı güçlü sayıdır. Uygulamalar önce \(N\)'e kadar olan tüm güçlü sayıları sayar, ardından güçlü olup da yine de \(a>1\) ve \(b>1\) koşullarını sağlayamayan sayıları çıkarır.
Her güçlü sayı tekil biçimde
$$n=u^2v^3$$
şeklinde yazılır; burada \(v\) karefree'dir. Gerçekten de her \(e\ge 2\) asal üssü için
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\}$$
yazılabilir. Üssün tek veya çift olması, ilgili asalın \(v\)'ye bir kez girip girmediğini belirler. Bu yüzden ayrışım tektir.
Dolayısıyla \(N\)'e kadar olan tüm güçlü sayıların sayısı
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor$$
olur. Her karefree \(v\) için, \(u^2v^3\le N\) sağlayan her \(u\) bir güçlü sayı üretir.
Eğer \(u=1\) ise \(n=v^3\) olur ve \(v\) karefree'dir. Bu durumda sıfır olmayan her asal üs tam olarak \(3\)'tür. Yerel denklem
$$3=2x+3y,\qquad x,y\ge 0$$
sadece \(x=0\) ile çözülebilir. Dolayısıyla böyle bir sayının her gösteriminde \(a=1\) olur; bu da yasaktır.
Bu yüzden
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}$$
miktarını çıkarmamız gerekir. Karefree taraması zaten yapıldığı için bu düzeltme aynı döngü içinde elde edilir.
Eğer \(v=1\) ise \(n=u^2\) tam karedir. Fakat her tam kare geçerli değildir. Sorun tam olarak \(u\) küpfree olduğunda ortaya çıkar.
\(u\) küpfree ise \(n=u^2\) sayısındaki asal üsler yalnızca \(2\) veya \(4\) olabilir. Bu üslerden hiçbiri pozitif bir küp payı veremez, çünkü
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
denklemlerinin bütün çözümlerinde \(y=0\) olur. Böylece her gösterimde zorunlu olarak \(b=1\) kalır.
Tersine, eğer \(u\) içinde bir \(p^3\) çarpanı varsa, \(n\) içinde \(p^6\) bulunur. O zaman \(p^2\) kare kısmına, \(p^3\) küp kısmına verilebilir; dolayısıyla hem \(a\) hem \(b\) \(1\)'den büyük olur.
Bu nedenle \(\lfloor\sqrt N\rfloor\)'ye kadar olan küpfree sayıların sayısını çıkarırız:
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
Möbius terslemesiyle
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor$$
elde edilir.
Önceki iki sınır ailesini çıkardıktan sonra geriye tek bir istisna tipi kalır: asal altıncı kuvvetler \(p^6\).
Tek bir asal için, her iki tarafın da önemsiz olmaması şartı
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1$$
şeklindedir. Bu denklem \(e=5\) ve tüm \(e\ge 7\) için çözülür, fakat \(e=6\) için çözülmez. Bu yüzden \(p^6\), güçlü bir sayı olmasına rağmen ne karefree bir küptür ne de küpfree köklü bir karedir; buna rağmen \(a>1\) ve \(b>1\) ile yazılamaz.
Eğer güçlü bir sayı en az iki farklı asal içeriyorsa ve Adım 2 ile Adım 3'ten sağ çıkıyorsa, bir asal kare katkısını, başka bir asal da küp katkısını verebilir. O halde geriye kalan tek engel
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right)$$
olur; yani \(N\)'e kadar olan asal altıncı kuvvetlerin sayısı.
\(1\) sayısı \(P(N)\) içinde vardır; karefree küp düzeltmesi onu bir kez, küpfree kare düzeltmesi de bir kez daha çıkarır. Oysa toplamda yalnızca bir kez dışarıda kalmalıdır. Bu yüzden sonda \(+1\) eklenir.
Böylece
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
formülüne ulaşılır. C++, Python ve Java uygulamaları tam olarak bu ifadeyi hesaplar.
Burada \(\lfloor N^{1/3}\rfloor=4\) ve karefree değerler \(1,2,3\)'tür. Dolayısıyla
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
Sonra \(C(100)=3\) gelir; bunlar \(1^3,2^3,3^3\)'tür. Ayrıca \(\lfloor\sqrt{100}\rfloor=10\) ve \(10\)'a kadar küpfree sayılar
$$1,2,3,4,5,6,7,9,10$$
olduğu için \(Q(10)=9\) olur. Son olarak \(\lfloor 100^{1/6}\rfloor=2\), dolayısıyla \(R(100)=\pi(2)=1\).
Böylece
$$F(100)=14-3-9-1+1=2.$$
Geçerli iki sayı \(64=2^2\cdot 2^3\) ve \(72=3^2\cdot 2^3\)'tür.
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce tam sayı karekök, küpkök ve altıncı kök değerleri hesaplanır. Her biri kayan noktalı bir tahminle başlar, ardından kısa düzeltme döngüleriyle sınır durumları kesin tam sayıya getirilir.
Daha sonra \(\lfloor N^{1/3}\rfloor\)'ye kadar olan karefree sayılar, \(p\le \lfloor N^{1/6}\rfloor\) asalları için \(p^2\) katları işaretlenerek bulunur. Bu dizi taranırken hem temel toplam \(P(N)\) hem de düzeltme \(C(N)\) aynı anda elde edilir.
Küpfree düzeltme için uygulama, \(\lfloor N^{1/6}\rfloor\)'ye kadar Möbius değerlerini bir sieve ile üretir ve
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor$$
toplamını hesaplar. Son olarak altıncı kuvvet düzeltmesi için \(\lfloor N^{1/6}\rfloor\)'ye kadar asallar sayılır ve dört terim birleştirilir. Aynı formül hedef girdi öncesinde \(N=100\), \(20000\) ve \(3000000\) gibi küçük kontrol değerlerinde de doğrulanır.
\(V=\lfloor N^{1/3}\rfloor\) ve \(D=\lfloor N^{1/6}\rfloor\) olsun. \(V\)'ye kadar karefree işaretleme \(O(V\log\log V)\) zaman ve \(O(V)\) bellek kullanır. Möbius sievesi ve \(D\)'ye kadar asal sayımı \(O(D)\) ile \(O(D\log\log D)\) arasında zaman ve \(O(D)\) bellek gerektirir. \(V\), \(D\)'den büyük olduğu için toplam maliyet \(O(N^{1/3}\log\log N)\) zaman ve \(O(N^{1/3})\) bellek düzeyindedir.
Se pide contar cuántos enteros \(n \le N\), con \(N=9\times 10^{18}\), pueden escribirse como
$$n=a^2b^3,\qquad a>1,\qquad b>1.$$
Recorrer todos los valores hasta \(N\) es inviable. La idea es contar primero una familia más amplia de números y luego restar exactamente los casos excepcionales que todavía no satisfacen simultáneamente \(a>1\) y \(b>1\).
Definimos
$$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ para algunos } a,b>1\right\}.$$
Si \(n=\prod p^{e_p}\) tiene la forma \(a^2b^3\), entonces cada exponente primo cumple \(e_p\ge 2\). Por tanto, todo número válido es un número poderoso. Las implementaciones cuentan primero todos los números poderosos hasta \(N\) y después restan los que, aun siendo poderosos, no admiten una representación con ambos factores estrictamente mayores que \(1\).
Todo número poderoso posee una representación única
$$n=u^2v^3,$$
donde \(v\) es libre de cuadrados. En efecto, para cada exponente primo \(e\ge 2\) escribimos
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\},$$
de modo que la paridad de \(e\) decide si ese primo aparece una vez en \(v\). Eso hace única la descomposición.
Así, el número total de números poderosos hasta \(N\) es
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$$
Para cada \(v\) libre de cuadrados, cada entero \(u\) con \(u^2v^3\le N\) aporta exactamente un número poderoso.
Si \(u=1\), entonces \(n=v^3\) con \(v\) libre de cuadrados. En ese caso, cada exponente primo no nulo vale exactamente \(3\), y la ecuación local
$$3=2x+3y,\qquad x,y\ge 0$$
obliga a \(x=0\). Por consiguiente, cualquier representación tiene \(a=1\), lo cual no está permitido.
Debemos restar entonces
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$$
El mismo tamiz de números libres de cuadrados que se usa para \(P(N)\) produce también este término de corrección.
Si \(v=1\), entonces \(n=u^2\) es un cuadrado perfecto. Pero no todo cuadrado perfecto es válido. El obstáculo aparece exactamente cuando \(u\) es libre de cubos.
Si \(u\) es libre de cubos, todos los exponentes primos de \(n=u^2\) son \(2\) o \(4\). Ninguno de esos exponentes puede aportar una parte cúbica positiva, porque
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
solo tiene soluciones con \(y=0\). Por tanto, toda representación fuerza \(b=1\).
En cambio, si \(u\) contiene un factor cúbico \(p^3\), entonces \(n\) contiene \(p^6\), y podemos asignar \(p^2\) a la parte cuadrática y \(p^3\) a la parte cúbica. Así ambos factores quedan mayores que \(1\).
Por eso restamos la cantidad de enteros libres de cubos hasta \(\lfloor\sqrt N\rfloor\):
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
Mediante inversión de Möbius,
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$$
Después de eliminar las dos familias de borde anteriores, queda una sola excepción: las sextas potencias primas \(p^6\).
Para un único exponente primo \(e\), exigir que ambos factores sean no triviales equivale a
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$$
Esto tiene solución para \(e=5\) y para todo \(e\ge 7\), pero falla en \(e=6\). Por eso \(p^6\) es poderoso, no es un cubo libre de cuadrados y tampoco es un cuadrado con raíz libre de cubos, pero aun así no se puede escribir con \(a>1\) y \(b>1\).
Si un número poderoso tiene al menos dos primos distintos y supera los Pasos 2 y 3, un primo puede aportar la parte cuadrática y otro la parte cúbica. Así, la única obstrucción restante es
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right),$$
el número de sextas potencias primas no mayores que \(N\).
El número \(1\) está incluido en \(P(N)\) y se resta una vez en la corrección de cubos libres de cuadrados y otra vez en la corrección de cuadrados con raíz libre de cubos. Como debe excluirse solo una vez, añadimos \(1\) al final.
En consecuencia,
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
Esa es exactamente la fórmula evaluada por las implementaciones en C++, Python y Java.
Aquí \(\lfloor N^{1/3}\rfloor=4\), y los valores libres de cuadrados son \(1,2,3\). Entonces
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
Luego \(C(100)=3\), procedente de \(1^3,2^3,3^3\). Además \(\lfloor\sqrt{100}\rfloor=10\), y los enteros libres de cubos hasta \(10\) son
$$1,2,3,4,5,6,7,9,10,$$
de modo que \(Q(10)=9\). Por último, \(\lfloor 100^{1/6}\rfloor=2\), así que \(R(100)=\pi(2)=1\).
Por tanto,
$$F(100)=14-3-9-1+1=2.$$
Los dos números válidos son \(64=2^2\cdot 2^3\) y \(72=3^2\cdot 2^3\).
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero calculan raíces enteras exactas de orden \(2\), \(3\) y \(6\). Cada cálculo parte de una aproximación en coma flotante y luego la corrige con pequeños bucles, evitando errores de borde cerca del límite de \(64\) bits.
Después marcan los enteros libres de cuadrados hasta \(\lfloor N^{1/3}\rfloor\) tachando los múltiplos de \(p^2\) para los primos \(p\le \lfloor N^{1/6}\rfloor\). Al recorrer ese arreglo obtienen a la vez la suma base \(P(N)\) y la corrección \(C(N)\).
Para la corrección de números libres de cubos, la implementación calcula los valores de Möbius hasta \(\lfloor N^{1/6}\rfloor\) con un tamiz y evalúa
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor.$$
Al final cuenta los primos hasta \(\lfloor N^{1/6}\rfloor\) para la corrección de sextas potencias y combina los cuatro términos. La misma fórmula se verifica antes en valores pequeños como \(N=100\), \(20000\) y \(3000000\).
Sea \(V=\lfloor N^{1/3}\rfloor\) y \(D=\lfloor N^{1/6}\rfloor\). Marcar los enteros libres de cuadrados hasta \(V\) cuesta \(O(V\log\log V)\) tiempo y \(O(V)\) memoria. El tamiz de Möbius y el conteo de primos hasta \(D\) cuestan entre \(O(D)\) y \(O(D\log\log D)\) tiempo, con \(O(D)\) memoria. Como \(V\) domina a \(D\), el método completo requiere \(O(N^{1/3}\log\log N)\) tiempo y \(O(N^{1/3})\) memoria.
题目要求统计满足 \(n\le N\) 且
$$n=a^2b^3,\qquad a>1,\qquad b>1$$
的整数个数，其中 \(N=9\times 10^{18}\)。直接枚举到 \(N\) 完全不可行，所以解法不是逐个检查整数，而是先统计一个更容易描述的超集，再把其中不合法的特殊情形精确扣掉。
记
$$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ 且 } a,b>1\right\}.$$
如果 \(n=\prod p^{e_p}\) 可以写成 \(a^2b^3\)，那么每个素因子的指数都至少是 \(2\)，因为平方部分贡献偶数指数，立方部分贡献 \(3\) 的倍数，两者相加不可能得到 \(1\)。这说明所有候选数都属于 powerful number。程序的策略正是先把所有 powerful number 统计出来，再减去那些虽然 powerful、但依然无法满足 \(a>1\) 与 \(b>1\) 的数。
每个 powerful number 都可以唯一写成
$$n=u^2v^3,$$
其中 \(v\) 是 squarefree。原因是：对任意素因子指数 \(e\ge 2\)，都可以唯一写成
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\}.$$
\(\beta\) 只取 \(0\) 或 \(1\)，恰好由指数的奇偶性决定；若 \(\beta=1\)，该素数就在 \(v\) 中出现一次，因此 \(v\) 必然是 squarefree。这就得到唯一的规范表示。
于是，不超过 \(N\) 的 powerful number 总数为
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$$
对每个 squarefree 的 \(v\)，所有满足 \(u^2v^3\le N\) 的正整数 \(u\) 都贡献一个 powerful number。
如果规范分解里 \(u=1\)，那么 \(n=v^3\)，而且 \(v\) 是 squarefree。此时所有非零素因子指数都恰好等于 \(3\)。要把它写成 \(a^2b^3\)，对应单个素数必须满足
$$3=2x+3y,\qquad x,y\ge 0.$$
这个方程唯一可能是 \(x=0,y=1\)，也就是说平方部分在每个素数上都没有贡献，于是整体上只能有 \(a=1\)。因此这类数全部不合法。
所以需要减去
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$$
实现中用于枚举 \(P(N)\) 的 squarefree 筛法，同时也顺手给出了这个修正项。
如果规范分解里 \(v=1\)，那么 \(n=u^2\) 是完全平方数。但完全平方数并不一定都能写成要求的形式。真正有问题的，恰好是 \(u\) 为 cubefree 的情形。
若 \(u\) 是 cubefree，那么 \(u\) 的每个素因子指数都小于 \(3\)，因此 \(n=u^2\) 中对应指数只能是 \(2\) 或 \(4\)。而
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
都只能在 \(y=0\) 时成立，这意味着立方部分根本不能出现，任何表示都只能让 \(b=1\)。
反过来，如果 \(u\) 含有某个立方因子 \(p^3\)，那么 \(n=u^2\) 至少含有 \(p^6\)。这时完全可以把 \(p^2\) 分配给平方部分，把 \(p^3\) 分配给立方部分，于是 \(a>1\) 且 \(b>1\) 同时成立。
因此我们要减去不超过 \(\lfloor\sqrt N\rfloor\) 的 cubefree 整数个数：
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
这个数量可以用 Möbius 反演写成
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$$
减掉前面两个边界家族以后，还会剩下一类例外：素数六次幂 \(p^6\)。
对单个素数指数 \(e\) 来说，如果我们要求平方部分和立方部分都真正出现，那么必须有
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$$
这个方程在 \(e=5\) 时可解，在所有 \(e\ge 7\) 时也可解，但在 \(e=6\) 时无解。因此 \(p^6\) 虽然是 powerful number，也不是前两步已经扣掉的两类边界情况，却仍然无法写成 \(a>1\)、\(b>1\) 的形式。
如果一个 powerful number 含有至少两个不同的素因子，并且没有在步骤 2 与步骤 3 中被排除，那么我们可以让某个素因子提供平方贡献，让另一个素因子提供立方贡献，于是它就是合法的。这样剩下唯一需要额外扣除的就是
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right),$$
也就是不超过 \(N\) 的素数六次幂个数。
数字 \(1\) 被包含在 \(P(N)\) 里，同时也会在“squarefree 立方修正”和“cubefree 平方修正”里各被减去一次。它本来只应该被排除一次，所以最后要补回 \(1\)。
最终得到
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
这正是 C++、Python 和 Java 实现共同计算的公式。
此时 \(\lfloor N^{1/3}\rfloor=4\)，其中 squarefree 的 \(v\) 只有 \(1,2,3\)。所以
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
接着 \(C(100)=3\)，对应 \(1^3,2^3,3^3\)。又因为 \(\lfloor\sqrt{100}\rfloor=10\)，而不超过 \(10\) 的 cubefree 整数是
$$1,2,3,4,5,6,7,9,10,$$
所以 \(Q(10)=9\)。最后 \(\lfloor 100^{1/6}\rfloor=2\)，因此 \(R(100)=\pi(2)=1\)。
于是
$$F(100)=14-3-9-1+1=2.$$
这两个合法整数正是 \(64=2^2\cdot 2^3\) 和 \(72=3^2\cdot 2^3\)。
C++、Python 和 Java 三个实现采用同一条计算流程。首先，它们分别求精确的整数平方根、立方根和六次根。做法是先取一个浮点近似值，再用很短的修正循环向上或向下校正，从而避免接近 \(64\) 位边界时的舍入误差。
然后，程序在 \(\lfloor N^{1/3}\rfloor\) 范围内筛出 squarefree 整数，方法是对所有 \(p\le \lfloor N^{1/6}\rfloor\) 的素数，把 \(p^2\) 的倍数标记掉。扫描这个布尔数组时，就能同时得到基础统计 \(P(N)\) 和修正项 \(C(N)\)。
接下来，为了计算 cubefree 修正，程序先用筛法求出 \(\lfloor N^{1/6}\rfloor\) 以内的 Möbius 值，再计算
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor.$$
最后，还要统计 \(\lfloor N^{1/6}\rfloor\) 以内的素数个数，以获得六次幂修正项，然后把四个部分合并。正式求目标输入之前，程序还会用 \(N=100\)、\(20000\)、\(3000000\) 这些较小样例做一致性检查。
设 \(V=\lfloor N^{1/3}\rfloor\)，\(D=\lfloor N^{1/6}\rfloor\)。在 \(V\) 以内筛 squarefree 数需要 \(O(V\log\log V)\) 时间和 \(O(V)\) 空间。Möbius 筛与 \(D\) 以内的素数统计需要 \(O(D)\) 到 \(O(D\log\log D)\) 的时间，以及 \(O(D)\) 的空间。由于 \(V\) 远大于 \(D\)，总复杂度由前者主导，因此整体为 \(O(N^{1/3}\log\log N)\) 时间和 \(O(N^{1/3})\) 空间。
Нужно подсчитать количество целых чисел \(n \le N\), где \(N=9\times 10^{18}\), которые можно представить в виде
$$n=a^2b^3,\qquad a>1,\qquad b>1.$$
Прямой перебор до \(N\) невозможен. Поэтому решение сначала считает более широкий класс чисел, а затем вычитает из него те особые случаи, которые все еще не удовлетворяют одновременно условиям \(a>1\) и \(b>1\).
Обозначим
$$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ для некоторых } a,b>1\right\}.$$
Если \(n=\prod p^{e_p}\) представимо в виде \(a^2b^3\), то каждый показатель \(e_p\) не меньше \(2\). Значит, каждое подходящее число является мощным числом. Поэтому реализации сначала считают все мощные числа до \(N\), а затем вычитают те из них, которые все равно не дают представления с обоими нетривиальными множителями.
Любое мощное число единственным образом представляется как
$$n=u^2v^3,$$
где \(v\) squarefree. Для каждого простого показателя \(e\ge 2\) можно единственным образом записать
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\}.$$
Значение \(\beta\) определяется четностью \(e\), то есть именно она решает, входит ли соответствующий простой множитель один раз в \(v\). Отсюда и следует единственность представления.
Поэтому число всех мощных чисел не больше \(N\) равно
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$$
Для каждого squarefree числа \(v\) любое \(u\), удовлетворяющее \(u^2v^3\le N\), дает одно мощное число.
Если \(u=1\), то \(n=v^3\), причем \(v\) squarefree. Тогда каждый ненулевой простой показатель равен ровно \(3\), а локальное уравнение
$$3=2x+3y,\qquad x,y\ge 0$$
допускает только \(x=0\). Значит, в любом таком представлении обязательно \(a=1\), а это запрещено.
Следовательно, нужно вычесть
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$$
Тот же самый решетчатый проход по squarefree числам, который используется для \(P(N)\), сразу дает и этот поправочный член.
Если \(v=1\), то \(n=u^2\) является полным квадратом. Но не каждый полный квадрат подходит. Проблема возникает ровно тогда, когда \(u\) cubefree.
Если \(u\) cubefree, то все простые показатели в \(n=u^2\) равны \(2\) или \(4\). Ни один из этих показателей не может дать положительный кубический вклад, потому что
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
имеет решения только при \(y=0\). Значит, во всяком представлении обязательно получается \(b=1\).
Если же \(u\) содержит кубический множитель \(p^3\), то в \(n\) присутствует \(p^6\), и можно отдать \(p^2\) квадратной части, а \(p^3\) кубической части. Тогда оба множителя становятся больше \(1\).
Поэтому нужно вычесть число cubefree целых чисел до \(\lfloor\sqrt N\rfloor\):
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
По формуле Мёбиуса
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$$
После вычитания двух граничных семейств остается еще один тип исключений: числа вида \(p^6\), где \(p\) простое.
Для одного простого показателя \(e\) условие нетривиальности обеих частей имеет вид
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$$
Это уравнение решается при \(e=5\) и при всех \(e\ge 7\), но не решается при \(e=6\). Поэтому \(p^6\) является мощным числом, не попадает ни в squarefree кубы, ни в квадраты с cubefree корнем, и все же не представимо с \(a>1\) и \(b>1\).
Если мощное число имеет хотя бы два различных простых множителя и не вычитается на шагах 2 и 3, то один простой множитель может дать квадратную часть, а другой кубическую. Значит, остается вычесть только
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right),$$
то есть количество простых шестых степеней, не превосходящих \(N\).
Число \(1\) входит в \(P(N)\), затем вычитается один раз в squarefree-кубической поправке и еще раз в cubefree-квадратной поправке. Поскольку его нужно исключить только один раз, в конце прибавляется \(1\).
Итак,
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
Именно эту формулу вычисляют реализации на C++, Python и Java.
Здесь \(\lfloor N^{1/3}\rfloor=4\), а squarefree значения равны \(1,2,3\). Поэтому
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
Далее, \(C(100)=3\), что соответствует \(1^3,2^3,3^3\). Кроме того, \(\lfloor\sqrt{100}\rfloor=10\), а cubefree числа до \(10\) таковы:
$$1,2,3,4,5,6,7,9,10,$$
поэтому \(Q(10)=9\). Наконец, \(\lfloor 100^{1/6}\rfloor=2\), следовательно \(R(100)=\pi(2)=1\).
Отсюда
$$F(100)=14-3-9-1+1=2.$$
Два допустимых числа: \(64=2^2\cdot 2^3\) и \(72=3^2\cdot 2^3\).
Реализации на C++, Python и Java используют одну и ту же схему. Сначала они вычисляют точные целые квадратные, кубические и шестые корни. Для этого берется приближенное вещественное значение, а затем короткими корректирующими циклами устраняются погрешности на границах.
Затем они отмечают squarefree числа до \(\lfloor N^{1/3}\rfloor\), вычеркивая кратные \(p^2\) для простых \(p\le \lfloor N^{1/6}\rfloor\). Проход по этому массиву одновременно дает базовую сумму \(P(N)\) и поправку \(C(N)\).
Для cubefree-поправки программа вычисляет значения функции Мёбиуса до \(\lfloor N^{1/6}\rfloor\) с помощью решета и затем считает
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor.$$
После этого остается посчитать простые числа до \(\lfloor N^{1/6}\rfloor\) для поправки шестых степеней и объединить все четыре члена. До запуска на целевом входе формула проверяется на малых значениях \(N=100\), \(20000\) и \(3000000\).
Пусть \(V=\lfloor N^{1/3}\rfloor\), \(D=\lfloor N^{1/6}\rfloor\). Отметка squarefree чисел до \(V\) требует \(O(V\log\log V)\) времени и \(O(V)\) памяти. Решето Мёбиуса и подсчет простых до \(D\) требуют от \(O(D)\) до \(O(D\log\log D)\) времени и \(O(D)\) памяти. Так как \(V\) значительно больше \(D\), итоговая сложность равна \(O(N^{1/3}\log\log N)\) по времени и \(O(N^{1/3})\) по памяти.
نريد حساب عدد الأعداد الصحيحة \(n \le N\) حيث \(N=9\times 10^{18}\) والتي يمكن كتابتها على الصورة
$$n=a^2b^3,\qquad a>1,\qquad b>1.$$
الفحص المباشر لكل القيم حتى \(N\) غير ممكن عمليًا. لذلك تعتمد الفكرة على عدّ فئة أوسع أولًا، ثم طرح الحالات الخاصة التي تبقى غير صالحة رغم أنها تنتمي إلى تلك الفئة الأوسع.
لنعرّف
$$F(N)=\#\left\{n\le N : n=a^2b^3,\ a>1,\ b>1\right\}.$$
إذا كان \(n=\prod p^{e_p}\) قابلاً للكتابة على صورة \(a^2b^3\)، فإن كل أسّ أولي يحقق \(e_p\ge 2\). إذن كل عدد مطلوب هو عدد قوي. لذلك تبدأ التطبيقات بعدّ جميع الأعداد القوية حتى \(N\)، ثم تطرح الأعداد القوية التي لا تزال غير قابلة لتمثيل مطلوب فيه كل من \(a\) و\(b\) أكبر من \(1\).
كل عدد قوي يملك تمثيلًا وحيدًا بالشكل
$$n=u^2v^3,$$
حيث يكون \(v\) squarefree. فلكل أسّ أولي \(e\ge 2\) نستطيع أن نكتب
$$e=2\alpha+3\beta,\qquad \beta\in\{0,1\}.$$
وتحدد فردية \(e\) هل يظهر ذلك العامل الأولي مرة واحدة داخل \(v\) أم لا، ولهذا يكون التحليل وحيدًا.
ومن ثم فإن عدد الأعداد القوية حتى \(N\) يساوي
$$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$$
فلكل \(v\) squarefree، كل قيمة \(u\) تحقق \(u^2v^3\le N\) تعطي عددًا قويًا واحدًا.
إذا كان \(u=1\)، يصبح \(n=v^3\) مع \(v\) squarefree. حينها يكون كل أسّ أولي غير صفري مساويًا تمامًا لـ\(3\)، والمعادلة المحلية
$$3=2x+3y,\qquad x,y\ge 0$$
تفرض \(x=0\). وهذا يعني أن أي تمثيل من هذا النوع يجعل \(a=1\)، وهو غير مسموح.
لذلك يجب طرح
$$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$$
والغربلة نفسها المستعملة لحساب \(P(N)\) تعطي هذا الحدّ التصحيحي أيضًا.
إذا كان \(v=1\)، فإن \(n=u^2\) مربع كامل. لكن ليس كل مربع كامل صالحًا. تظهر المشكلة بالضبط عندما يكون \(u\) cubefree.
إذا كان \(u\) cubefree، فإن كل أسّ أولي في \(n=u^2\) يكون \(2\) أو \(4\). ولا يمكن لأي من هذين الأسّين أن يوفّر مساهمة تكعيبية موجبة، لأن
$$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$$
لا يملك إلا حلولًا فيها \(y=0\). وبالتالي فإن أي تمثيل يفرض \(b=1\).
أما إذا احتوى \(u\) على عامل تكعيبي \(p^3\)، فإن \(n\) يحتوي على \(p^6\)، وعندها يمكن إسناد \(p^2\) إلى الجزء التربيعي و\(p^3\) إلى الجزء التكعيبي، فيصبح كل من \(a\) و\(b\) أكبر من \(1\).
إذن نطرح عدد الأعداد cubefree حتى \(\lfloor\sqrt N\rfloor\):
$$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$$
وباستخدام معكوس Möbius نحصل على
$$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$$
بعد طرح العائلتين السابقتين، تبقى حالة استثنائية واحدة: الأعداد من الشكل \(p^6\) حيث \(p\) أولي.
بالنسبة لأسّ أولي واحد \(e\)، فإن شرط أن يكون الجزآن غير تافهين هو
$$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$$
هذه المعادلة تُحل عند \(e=5\) وعند كل \(e\ge 7\)، لكنها لا تُحل عند \(e=6\). لذلك فإن \(p^6\) عدد قوي، وليس مكعبًا squarefree، وليس مربعًا جذره cubefree، ومع ذلك لا يمكن كتابته بحيث يكون كل من \(a>1\) و\(b>1\).
إذا كان العدد القوي يحوي عاملين أوليين مختلفين على الأقل، ونجا من الطرح في الخطوتين 2 و3، فيمكن لعامل أولي أن يزوّد الجزء التربيعي وعامل آخر أن يزوّد الجزء التكعيبي. لذا فإن العائق المتبقي الوحيد هو
$$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right),$$
أي عدد القوى السادسة الأولية حتى \(N\).
العدد \(1\) محسوب داخل \(P(N)\)، ثم يُطرح مرة في تصحيح المكعبات squarefree ومرة أخرى في تصحيح المربعات ذات الجذر cubefree. ولأنه يجب استبعاده مرة واحدة فقط، فإننا نضيف \(1\) في النهاية.
إذن
$$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$$
وهذه هي الصيغة نفسها التي تطبقها البرامج المكتوبة بـ C++ وPython وJava.
لدينا هنا \(\lfloor N^{1/3}\rfloor=4\)، والقيم squarefree هي \(1,2,3\). لذلك
$$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$$
ثم إن \(C(100)=3\)، وهي القيم القادمة من \(1^3,2^3,3^3\). كذلك \(\lfloor\sqrt{100}\rfloor=10\)، والأعداد cubefree حتى \(10\) هي
$$1,2,3,4,5,6,7,9,10,$$
ومن ثم \(Q(10)=9\). وأخيرًا \(\lfloor 100^{1/6}\rfloor=2\)، لذا \(R(100)=\pi(2)=1\).
وعليه
$$F(100)=14-3-9-1+1=2.$$
والعددان الصالحان هما \(64=2^2\cdot 2^3\) و\(72=3^2\cdot 2^3\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. تبدأ بحساب الجذر التربيعي الصحيح والجذر التكعيبي الصحيح والجذر السادس الصحيح. ويبدأ كل حساب بتقدير عائم، ثم تُستخدم حلقات تصحيح قصيرة لضبط القيمة بدقة عند الحدود الحساسة.
بعد ذلك تُعلَّم الأعداد squarefree حتى \(\lfloor N^{1/3}\rfloor\) عبر شطب مضاعفات \(p^2\) لكل عدد أولي \(p\le \lfloor N^{1/6}\rfloor\). والمسح على هذا الجدول يعطي في الوقت نفسه الحد الأساسي \(P(N)\) والتصحيح \(C(N)\).
أما تصحيح الأعداد cubefree، فيُحسب بعد توليد قيم Möbius حتى \(\lfloor N^{1/6}\rfloor\) باستخدام غربلة، ثم تقييم المجموع
$$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor.$$
وفي النهاية تُحسب أعداد الأوليات حتى \(\lfloor N^{1/6}\rfloor\) للحصول على تصحيح القوى السادسة، ثم تُجمع الحدود الأربعة. كما تُراجع الصيغة أولًا على قيم صغيرة مثل \(N=100\) و\(20000\) و\(3000000\) قبل تنفيذها على القيمة الهدف.
لنضع \(V=\lfloor N^{1/3}\rfloor\) و\(D=\lfloor N^{1/6}\rfloor\). تعليم الأعداد squarefree حتى \(V\) يكلف \(O(V\log\log V)\) زمنًا و\(O(V)\) ذاكرة. وغربلة Möbius مع عدّ الأوليات حتى \(D\) تكلف بين \(O(D)\) و\(O(D\log\log D)\) زمنًا مع \(O(D)\) ذاكرة. وبما أن \(V\) أكبر من \(D\)، فإن الكلفة الكلية تهيمن عليها مرحلة \(V\)، فتكون النتيجة \(O(N^{1/3}\log\log N)\) زمنًا و\(O(N^{1/3})\) ذاكرة.