Let \(\pi(x)\) denote the prime-counting function. A \(\pi\)-sequence is any finite sequence of positive integers \(u=(u_0,\dots,u_r)\) with \(r\ge 1\) and
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r).$$
For a fixed starting value \(u_0\), the valid sequences are exactly the positive prefixes of the iterated chain
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
having at least two terms. Let \(c(u)\) be the number of non-prime terms in \(u\), with \(1\) counted as non-prime. Then \(p(n,k)\) counts the \(\pi\)-sequences with \(u_0\le n\) and \(c(u)=k\), and the target quantity is
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k).$$
We must compute \(P(10^8)\bmod(10^9+7)\). The central observation is that many different starts share the same tail after the first application of \(\pi\), so the problem can be compressed by counting groups of starts together instead of processing each start independently.
Write
$$M=\pi(n),$$
and let \(q_m\) denote the \(m\)-th prime. The only number with \(\pi(u_0)=0\) is \(u_0=1\), which cannot begin a valid positive sequence of length at least \(2\), so the useful first values are \(m=1,2,\dots,M\).
For each \(m\), consider the set of starting values \(x\le n\) satisfying \(\pi(x)=m\). Because \(\pi(x)\) increases exactly when \(x\) passes a prime, these sets are intervals:
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
Let \(B_m=|I_m|\). Then
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
Each interval contains exactly one prime starting value, namely \(q_m\). Every other element of \(I_m\) is composite. This prime-versus-composite split is the only distinction that remains inside a fixed interval.
If \(x\in I_m\), then the first step of the sequence is always \(\pi(x)=m\). After that point the future no longer depends on the original start \(x\). Define the common tail by
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j}).$$
Every valid sequence beginning from the block \(I_m\) is therefore of the form
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
for some \(j\ge 0\). Since \(\pi(y)<y\) for every integer \(y>1\), the tail strictly decreases until it reaches \(1\), so each block produces only a short list of prefixes.
For a fixed block \(m\), let \(r_{m,j}\) be the number of non-prime terms among
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}.$$
If the start is the unique prime \(q_m\), then the sequence \((q_m,t_{m,0},\dots,t_{m,j})\) has exactly \(r_{m,j}\) non-prime terms, because the first term contributes nothing to \(c(u)\).
If the start is any other element of \(I_m\), then the first term is composite, so the corresponding sequence has
$$r_{m,j}+1$$
non-prime terms. Thus every prefix of the common tail contributes
$$1$$
sequence to the bucket \(k=r_{m,j}\), and
$$B_m-1$$
sequences to the bucket \(k=r_{m,j}+1\). This is the key counting rule implemented in all three languages.
Once the values \(r_{m,j}\) are known, the counting function can be written directly as
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
The first term counts the prefixes whose start is the unique prime in \(I_m\). The second term counts the prefixes coming from the composite starts in the same interval. After all buckets are accumulated, the required answer is simply
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}.$$
The important simplification is that the algorithm never iterates through every \(u_0\le n\). It iterates through the much smaller set of first images \(m=1,\dots,\pi(n)\), and each such value represents an entire interval of starting points.
After the first step, every later term of every sequence is at most \(M=\pi(n)\). Therefore the implementation needs two different kinds of precomputation:
the full sieve up to \(n\), in order to know which numbers are prime and where the prime intervals begin and end, and a short prime-count table only for inputs \(0,1,\dots,M\), in order to continue the tails \(m,\pi(m),\pi(\pi(m)),\dots\).
This explains the structure seen in the implementations: the expensive work is the initial sieve up to \(n\), while the dynamic tail processing happens on the much smaller domain \([1,M]\).
For \(n=10\), we have
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7).$$
Hence the intervals of starting values are
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}.$$
The corresponding tails and running non-prime counts are
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2). \end{aligned}$$
If we write each block's contribution to
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr),$$
we obtain
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3). \end{aligned}$$
Therefore
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3,$$
and the product is
$$P(10)=3\cdot 8\cdot 9\cdot 3=648.$$
This small example shows exactly why interval grouping works: one short tail walk simultaneously counts the prime start in the interval and all composite starts beside it.
The C++, Python, and Java implementations begin with a sieve up to \(n\). From that sieve they obtain both a primality lookup for every value up to \(n\) and the ordered list of all primes not exceeding \(n\). The number of primes in that list is \(M=\pi(n)\), and consecutive primes immediately determine every interval size \(B_m\).
Next, the implementation builds a prime-count table only on the range \(0\) through \(M\). That table is enough because once a sequence has taken its first step, all later values belong to \([1,M]\). The program then loops through the blocks \(I_1,\dots,I_M\), computes the number of composite starts in each block, and walks the common tail
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1.$$
While walking the tail it maintains the running number of non-prime tail values. At every tail position it performs two logical updates: one for the unique prime start of the block, and one for the \(B_m-1\) composite starts. The C++ and Java versions store the bucket counts in growable arrays, while the Python version uses a sparse mapping, but the mathematical update is identical in all three cases.
After all blocks have been processed, the implementation multiplies every non-zero bucket size modulo \(10^9+7\). Because this final product is taken only once, the real cost lies in the sieve and the short iterated-\(\pi\) tail walks.
Building the sieve and the prime list up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory. This is the dominant part of the algorithm.
Let \(M=\pi(n)\). For each \(m\le M\), the tail length is \(O(\log m)\): for every \(x\ge 2\), at most one out of every two integers up to \(x\) can be prime, so
$$\pi(x)\le \frac{x+1}{2}.$$
Repeated application of \(\pi\) therefore shrinks the value geometrically until it reaches \(1\). Summing the tail-walk cost over all \(m\le M\) gives \(O(M\log M)\) additional time.
Since \(M=\pi(n)=O(n/\log n)\), the post-sieve work is asymptotically smaller than the sieve itself. The overall complexity is therefore
$$O(n\log\log n)\text{ time and }O(n)\text{ memory}.$$
Sei \(\pi(x)\) die Primzahlzählfunktion. Eine \(\pi\)-Folge ist jede endliche Folge positiver ganzer Zahlen \(u=(u_0,\dots,u_r)\) mit \(r\ge 1\) und
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r).$$
Für einen festen Startwert \(u_0\) sind die gültigen Folgen also genau die positiven Präfixe der iterierten Kette
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
mit mindestens zwei Gliedern. Sei \(c(u)\) die Anzahl nicht-primer Terme in \(u\), wobei \(1\) als nicht prim zählt. Dann bezeichnet \(p(n,k)\) die Anzahl der \(\pi\)-Folgen mit \(u_0\le n\) und \(c(u)=k\), und gesucht ist
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k).$$
Zu berechnen ist \(P(10^8)\bmod(10^9+7)\). Die zentrale Beobachtung lautet, dass viele verschiedene Startwerte nach dem ersten Anwenden von \(\pi\) denselben Schwanz teilen. Deshalb lässt sich das Problem stark komprimieren, wenn man ganze Startintervalle gemeinsam zählt.
Setze
$$M=\pi(n),$$
und sei \(q_m\) die \(m\)-te Primzahl. Der Fall \(\pi(u_0)=0\) tritt nur bei \(u_0=1\) auf; daraus entsteht keine gültige positive Folge der Länge mindestens \(2\). Relevante erste Werte sind also genau \(m=1,2,\dots,M\).
Für jedes \(m\) betrachten wir die Menge aller Startwerte \(x\le n\) mit \(\pi(x)=m\). Da sich \(\pi(x)\) genau beim Überschreiten einer Primzahl erhöht, sind diese Mengen Intervalle:
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
Mit \(B_m=|I_m|\) gilt daher
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
In jedem Intervall liegt genau ein primen Startwert, nämlich \(q_m\). Alle anderen Elemente von \(I_m\) sind zusammengesetzt. Innerhalb eines festen Intervalls ist das der einzige Unterschied zwischen den Startwerten.
Gilt \(x\in I_m\), so ist der erste Schritt der Folge immer \(\pi(x)=m\). Danach hängt die weitere Entwicklung nicht mehr vom ursprünglichen Startwert \(x\) ab. Definiere den gemeinsamen Schwanz durch
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j}).$$
Jede gültige Folge aus dem Block \(I_m\) hat dann die Form
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
für ein \(j\ge 0\). Da \(\pi(y)<y\) für jedes \(y>1\) gilt, fällt dieser Schwanz strikt ab, bis er \(1\) erreicht. Jeder Block erzeugt also nur eine kurze Liste möglicher Präfixe.
Für einen festen Block \(m\) sei \(r_{m,j}\) die Anzahl nicht-primer Terme unter
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}.$$
Beginnt die Folge beim einzigen primen Start \(q_m\), so besitzt \((q_m,t_{m,0},\dots,t_{m,j})\) genau \(r_{m,j}\) nicht-prime Glieder, weil der erste Term nichts zu \(c(u)\) beiträgt.
Beginnt die Folge bei einem anderen Element von \(I_m\), so ist der erste Term zusammengesetzt. Dann enthält die entsprechende Folge
$$r_{m,j}+1$$
nicht-prime Terme. Somit liefert jedes Präfix des gemeinsamen Schwanzes
$$1$$
Beitrag zum Bucket \(k=r_{m,j}\) und
$$B_m-1$$
Beiträge zum Bucket \(k=r_{m,j}+1\). Genau diese Zählregel setzen alle drei Implementierungen um.
Sobald die Werte \(r_{m,j}\) bekannt sind, lässt sich die Zählfunktion direkt schreiben als
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
Der erste Summand zählt die Präfixe, deren Start der einzige Primeintrag des Intervalls ist. Der zweite Summand zählt die Präfixe, die von den zusammengesetzten Startwerten desselben Intervalls kommen. Sind alle Buckets bestimmt, so ist die gesuchte Größe einfach
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}.$$
Die entscheidende Vereinfachung ist also, dass der Algorithmus nicht alle \(u_0\le n\) einzeln durchläuft. Stattdessen verarbeitet er nur die viel kleinere Menge \(m=1,\dots,\pi(n)\), wobei jeder dieser Werte ein ganzes Startintervall repräsentiert.
Nach dem ersten Schritt ist jeder spätere Term jeder Folge höchstens \(M=\pi(n)\). Deshalb benötigt die Implementierung zwei verschiedene Vorberechnungen:
das vollständige Sieb bis \(n\), um Primzahlen zu erkennen und die Startintervalle zu bestimmen, und eine kurze Tabelle der Primzahlzählfunktion nur für die Eingaben \(0,1,\dots,M\), um die Schwänze \(m,\pi(m),\pi(\pi(m)),\dots\) fortzusetzen.
Genau dadurch entsteht die Struktur der Programme: teuer ist das anfängliche Sieben bis \(n\), während die eigentliche dynamische Verarbeitung nur auf dem viel kleineren Bereich \([1,M]\) stattfindet.
Für \(n=10\) gilt
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7).$$
Damit sind die Startintervalle
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}.$$
Die zugehörigen Schwänze und laufenden Nicht-Prim-Zahlen sind
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2). \end{aligned}$$
Schreibt man den Beitrag jedes Blocks zu
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr),$$
so erhält man
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3). \end{aligned}$$
Also
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3,$$
und damit
$$P(10)=3\cdot 8\cdot 9\cdot 3=648.$$
Dieses kleine Beispiel zeigt präzise, warum die Gruppierung nach Intervallen funktioniert: Ein einziger kurzer Schwanzlauf zählt gleichzeitig den primen Startwert des Intervalls und alle zusammengesetzten Startwerte daneben.
Die C++-, Python- und Java-Implementierungen beginnen mit einem Sieb bis \(n\). Daraus gewinnen sie sowohl eine Primzahlmarkierung für jeden Wert bis \(n\) als auch die geordnete Liste aller Primzahlen bis \(n\). Die Länge dieser Liste ist \(M=\pi(n)\), und aufeinanderfolgende Primzahlen bestimmen unmittelbar jede Intervallgröße \(B_m\).
Anschließend baut die Implementierung eine Tabelle der Primzahlzählfunktion nur auf dem Bereich \(0\) bis \(M\). Das genügt, weil nach dem ersten Schritt alle weiteren Werte jeder Folge in \([1,M]\) liegen. Dann durchläuft das Programm die Blöcke \(I_1,\dots,I_M\), berechnet die Anzahl zusammengesetzter Startwerte in jedem Block und wandert den gemeinsamen Schwanz
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1$$
entlang.
Während dieses Laufs hält es die bisherige Zahl nicht-primer Schwanzwerte fest. An jeder Schwanzposition erfolgen zwei logische Aktualisierungen: eine für den einzigen primen Start des Blocks und eine für die \(B_m-1\) zusammengesetzten Startwerte. Die C++- und Java-Versionen verwenden dafür vergrößerbare Arrays, die Python-Version eine dünn besetzte Zuordnung; mathematisch sind die Aktualisierungen jedoch identisch.
Nachdem alle Blöcke verarbeitet wurden, multipliziert die Implementierung alle positiven Bucket-Größen modulo \(10^9+7\). Weil dieses Produkt erst ganz am Ende gebildet wird, liegt der eigentliche Aufwand im Sieb und in den kurzen iterierten-\(\pi\)-Schwanzläufen.
Der Aufbau des Siebs und der Primzahlliste bis \(n\) kostet \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Das ist der dominante Teil des Verfahrens.
Mit \(M=\pi(n)\) hat jeder Schwanz für \(m\le M\) Länge \(O(\log m)\): Für jedes \(x\ge 2\) kann unter den Zahlen bis \(x\) höchstens jede zweite prim sein, also gilt
$$\pi(x)\le \frac{x+1}{2}.$$
Wiederholtes Anwenden von \(\pi\) verkleinert den Wert daher geometrisch bis \(1\). Summiert über alle \(m\le M\) ergibt das zusätzliche Zeit \(O(M\log M)\).
Da \(M=\pi(n)=O(n/\log n)\) ist, bleibt diese Nachbearbeitung asymptotisch kleiner als das Sieb selbst. Insgesamt beträgt die Komplexität also
$$O(n\log\log n)\text{ Zeit und }O(n)\text{ Speicher}.$$
\(\pi(x)\) asal sayma fonksiyonu olsun. Bir \(\pi\)-sekansı, \(r\ge 1\) olmak üzere pozitif tamsayılardan oluşan sonlu bir
$$u=(u_0,\dots,u_r)$$
dizisidir ve
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r)$$
koşulunu sağlar. Sabit bir \(u_0\) için geçerli sekanslar,
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
zincirinin en az iki terimli tüm pozitif önekleridir. \(c(u)\), \(u\) içindeki asal olmayan terim sayısı olsun; burada \(1\) de asal olmayan kabul edilir. O zaman \(p(n,k)\), \(u_0\le n\) ve \(c(u)=k\) koşullarını sağlayan \(\pi\)-sekanslarının sayısıdır. Aranan ifade
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)$$
olur.
Hesaplamamız gereken değer \(P(10^8)\bmod(10^9+7)\)'dir. Temel fikir şudur: farklı başlangıçların çok büyük bir kısmı, \(\pi\) fonksiyonu bir kez uygulandıktan sonra aynı kuyruğu paylaşır. Bu yüzden başlangıçları tek tek saymak yerine, aynı ilk \(\pi\)-değerine sahip tüm başlangıçları birlikte işlemek çok daha etkilidir.
Şöyle yazalım:
$$M=\pi(n),$$
ve \(q_m\) ile \(m\). asal sayıyı gösterelim. \(\pi(u_0)=0\) ancak \(u_0=1\) için mümkündür; bu da uzunluğu en az \(2\) olan pozitif bir sekans başlatmaz. Dolayısıyla anlamlı ilk değerler tam olarak \(m=1,2,\dots,M\) olur.
Her \(m\) için \(\pi(x)=m\) ve \(x\le n\) olan başlangıçları düşünelim. \(\pi(x)\) yalnızca bir asal sayı geçildiğinde arttığı için bu kümeler aralık oluşturur:
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
\(B_m=|I_m|\) dersek
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
elde edilir. Her aralıkta tam bir tane asal başlangıç vardır: \(q_m\). \(I_m\)'nin geri kalan tüm elemanları bileşiktir. Sabit bir aralık içinde asıl fark yalnızca bu asal-başlangıç ve bileşik-başlangıç ayrımıdır.
Eğer \(x\in I_m\) ise ilk adım her zaman \(\pi(x)=m\) olur. Bu noktadan sonra gelecekteki terimler artık başlangıçtaki \(x\) değerine bağlı değildir. Ortak kuyruğu
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j})$$
şeklinde tanımlayalım.
Böylece \(I_m\) bloğundan gelen her geçerli sekans
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
biçimindedir. Ayrıca \(y>1\) için \(\pi(y)<y\) olduğundan kuyruk katı biçimde küçülür ve sonunda \(1\)'e ulaşır. Yani her blok yalnızca kısa bir önekler listesi üretir.
Sabit bir \(m\) için \(r_{m,j}\),
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}$$
arasındaki asal olmayan terim sayısı olsun.
Eğer başlangıç tek asal değer olan \(q_m\) ise, \((q_m,t_{m,0},\dots,t_{m,j})\) sekansında asal olmayan terim sayısı tam olarak \(r_{m,j}\) olur; çünkü ilk terim asaldır ve \(c(u)\)'ya katkı yapmaz.
Eğer başlangıç \(I_m\) içindeki diğer bir eleman ise, ilk terim bileşiktir. Bu durumda ilgili sekansın asal olmayan terim sayısı
$$r_{m,j}+1$$
olur. Dolayısıyla ortak kuyruğun her öneki,
$$1$$
adet katkıyı \(k=r_{m,j}\) kovasına ve
$$B_m-1$$
adet katkıyı \(k=r_{m,j}+1\) kovasına gönderir. Üç dildeki uygulamanın özündeki sayım kuralı tam olarak budur.
\(r_{m,j}\) değerleri bilindiğinde sayım fonksiyonu doğrudan şöyle yazılır:
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
İlk terim, aralıktaki tek asal başlangıçtan gelen önekleri sayar. İkinci terim ise aynı aralıktaki bileşik başlangıçlardan gelen önekleri sayar. Tüm kovalar hesaplandıktan sonra sonuç
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}$$
olur.
Asıl sadeleştirme şurada yatar: algoritma tüm \(u_0\le n\) değerlerini tek tek dolaşmaz. Bunun yerine çok daha küçük olan \(m=1,\dots,\pi(n)\) kümesini dolaşır; her böyle \(m\) değeri ise başlangıçların tamamını kapsayan bir aralığı temsil eder.
İlk adımdan sonra her sekansın sonraki tüm terimleri en fazla \(M=\pi(n)\) olur. Bu yüzden uygulama iki tür ön hesap kullanır:
başlangıç aralıklarını bulmak ve hangi sayıların asal olduğunu bilmek için \(n\)'e kadar tam elek, kuyrukları \(m,\pi(m),\pi(\pi(m)),\dots\) biçiminde ilerletmek için ise yalnızca \(0,1,\dots,M\) aralığında kısa bir asal sayma tablosu.
Uygulamaların yapısı da bu yüzden böyledir: maliyetli bölüm \(n\)'e kadar olan ilk elektir; dinamik güncelleme ise çok daha küçük \([1,M]\) bölgesinde gerçekleşir.
\(n=10\) için
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7)$$
olur. Başlangıç aralıkları
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}$$
şeklindedir.
Karşılık gelen kuyruklar ve biriken asal olmayan sayıları
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2) \end{aligned}$$
olur.
Her bloğun
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr)$$
üzerindeki katkısı ise
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3) \end{aligned}$$
şeklindedir. Buradan
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3$$
ve dolayısıyla
$$P(10)=3\cdot 8\cdot 9\cdot 3=648$$
elde edilir. Bu küçük örnek, aralık gruplamasının neden doğru bakış açısı olduğunu açıkça gösterir: tek bir kısa kuyruk yürüyüşü, hem aralıktaki asal başlangıcı hem de yanındaki tüm bileşik başlangıçları aynı anda sayar.
C++, Python ve Java uygulamaları önce \(n\)'e kadar bir elek çalıştırır. Bu elek sayesinde hem \(n\)'e kadar her değer için asal bilgisi hem de \(n\)'i aşmayan tüm asalların sıralı listesi elde edilir. Bu listenin uzunluğu \(M=\pi(n)\)'dir ve ardışık asallar her aralığın \(B_m\) boyutunu doğrudan verir.
Daha sonra uygulama, asal sayma tablosunu yalnızca \(0\) ile \(M\) arasındaki değerler için kurar. Bu yeterlidir; çünkü bir sekans ilk adımını attıktan sonra tüm kalan terimler \([1,M]\) içinde kalır. Ardından program \(I_1,\dots,I_M\) bloklarını dolaşır, her bloktaki bileşik başlangıç sayısını bulur ve ortak kuyruğu
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1$$
boyunca ilerler.
Kuyruk boyunca yürürken, o ana kadar görülen asal olmayan kuyruk terimlerinin sayısı tutulur. Her kuyruk konumunda iki mantıksal güncelleme yapılır: biri bloğun tek asal başlangıcı için, diğeri \(B_m-1\) bileşik başlangıç için. C++ ve Java sürümleri bu kovaları büyüyebilen dizilerde tutar; Python sürümü seyrek bir sözlük kullanır. Fakat matematiksel güncelleme üçünde de aynıdır.
Tüm bloklar işlendiğinde, uygulama sıfır olmayan tüm kova boyutlarını \(10^9+7\) modunda çarpar. Son çarpım yalnızca bir kez yapıldığı için asıl maliyet elek ve kısa iteratif-\(\pi\) kuyruk yürüyüşlerindedir.
\(n\)'e kadar elek ve asal listesi oluşturmak \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir. Algoritmanın baskın kısmı budur.
\(M=\pi(n)\) olsun. Her \(m\le M\) için kuyruk uzunluğu \(O(\log m)\)'dir; çünkü \(x\ge 2\) için \(x\)'e kadar olan sayılardan en fazla her iki sayıdan biri asal olabilir, dolayısıyla
$$\pi(x)\le \frac{x+1}{2}.$$
\(\pi\) fonksiyonunu tekrar tekrar uygulamak değeri bu yüzden geometrik olarak küçültür ve sonunda \(1\)'e indirir. Tüm \(m\le M\) üzerinde toplandığında ek maliyet \(O(M\log M)\) olur.
\(M=\pi(n)=O(n/\log n)\) olduğundan, elek sonrası bölüm asimptotik olarak elekten küçüktür. Toplam karmaşıklık
$$O(n\log\log n)\text{ zaman ve }O(n)\text{ bellek}$$
olur.
Sea \(\pi(x)\) la función contadora de primos. Una sucesión \(\pi\) es cualquier sucesión finita de enteros positivos \(u=(u_0,\dots,u_r)\) con \(r\ge 1\) y
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r).$$
Para un valor inicial fijo \(u_0\), las sucesiones válidas son exactamente los prefijos positivos de la cadena iterada
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
que tienen al menos dos términos. Sea \(c(u)\) el número de términos no primos de \(u\), contando también a \(1\) como no primo. Entonces \(p(n,k)\) cuenta las sucesiones \(\pi\) con \(u_0\le n\) y \(c(u)=k\), y la cantidad buscada es
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k).$$
Debemos calcular \(P(10^8)\bmod(10^9+7)\). La observación clave es que muchos inicios distintos comparten la misma cola después de aplicar \(\pi\) una sola vez. Por eso conviene agrupar los inicios y contarlos por bloques, en lugar de procesarlos uno por uno.
Escribamos
$$M=\pi(n),$$
y sea \(q_m\) el \(m\)-ésimo primo. El caso \(\pi(u_0)=0\) solo ocurre cuando \(u_0=1\), y eso no puede iniciar una sucesión positiva válida de longitud al menos \(2\). Por tanto, los primeros valores útiles son exactamente \(m=1,2,\dots,M\).
Para cada \(m\), consideremos los valores iniciales \(x\le n\) que satisfacen \(\pi(x)=m\). Como \(\pi(x)\) solo aumenta al pasar por un primo, estos conjuntos son intervalos:
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
Si \(B_m=|I_m|\), entonces
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
Cada intervalo contiene exactamente un inicio primo, que es \(q_m\). Todos los demás elementos de \(I_m\) son compuestos. Dentro de un mismo intervalo, esa es la única diferencia relevante entre los inicios.
Si \(x\in I_m\), el primer paso siempre produce \(\pi(x)=m\). A partir de ahí, el resto de la sucesión ya no depende del valor inicial \(x\). Definimos la cola común por
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j}).$$
Toda sucesión válida que sale del bloque \(I_m\) tiene entonces la forma
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
para algún \(j\ge 0\). Como \(\pi(y)<y\) para todo entero \(y>1\), la cola decrece estrictamente hasta llegar a \(1\), así que cada bloque genera solo una lista corta de prefijos.
Para un bloque fijo \(m\), sea \(r_{m,j}\) el número de términos no primos entre
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}.$$
Si el inicio es el único primo \(q_m\), la sucesión \((q_m,t_{m,0},\dots,t_{m,j})\) tiene exactamente \(r_{m,j}\) términos no primos, porque el primer término no añade nada a \(c(u)\).
Si el inicio es cualquier otro elemento de \(I_m\), entonces el primer término es compuesto y la sucesión correspondiente tiene
$$r_{m,j}+1$$
términos no primos. Por tanto, cada prefijo de la cola común aporta
$$1$$
sucesión al cubo \(k=r_{m,j}\), y
$$B_m-1$$
sucesiones al cubo \(k=r_{m,j}+1\). Esta es exactamente la regla de conteo usada en las tres implementaciones.
Una vez conocidos los valores \(r_{m,j}\), la función de conteo puede escribirse directamente como
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
El primer sumando cuenta los prefijos cuyo inicio es el único primo del intervalo. El segundo cuenta los prefijos originados en los inicios compuestos del mismo intervalo. Cuando todos los cubos ya están acumulados, el resultado es
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}.$$
La simplificación decisiva es que el algoritmo no recorre cada \(u_0\le n\). Recorre solo el conjunto mucho más pequeño \(m=1,\dots,\pi(n)\), y cada uno de esos valores representa un intervalo completo de inicios.
Después del primer paso, todos los términos restantes de cualquier sucesión son a lo sumo \(M=\pi(n)\). Por eso la implementación necesita dos precomputaciones distintas:
una criba completa hasta \(n\), para saber qué números son primos y dónde empiezan y terminan los intervalos, y una tabla corta de la función \(\pi\) solo para las entradas \(0,1,\dots,M\), para continuar las colas \(m,\pi(m),\pi(\pi(m)),\dots\).
Eso explica la forma del código: el trabajo caro es la criba inicial hasta \(n\), mientras que la parte dinámica se hace en el dominio mucho más pequeño \([1,M]\).
Para \(n=10\) se tiene
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7).$$
Los intervalos de inicio son
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}.$$
Las colas correspondientes y las cuentas acumuladas de no primos son
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2). \end{aligned}$$
Si escribimos el aporte de cada bloque a
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr),$$
obtenemos
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3). \end{aligned}$$
Por tanto,
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3,$$
y el producto final es
$$P(10)=3\cdot 8\cdot 9\cdot 3=648.$$
Este ejemplo pequeño muestra con claridad por qué la agrupación por intervalos es la perspectiva correcta: una sola caminata por una cola corta cuenta a la vez el inicio primo del bloque y todos los inicios compuestos que lo acompañan.
Las implementaciones en C++, Python y Java comienzan con una criba hasta \(n\). De esa criba obtienen tanto una consulta de primalidad para cada valor hasta \(n\) como la lista ordenada de todos los primos no mayores que \(n\). La longitud de esa lista es \(M=\pi(n)\), y los primos consecutivos determinan inmediatamente cada tamaño \(B_m\).
Luego la implementación construye una tabla de la función contadora de primos solo en el intervalo \(0\) a \(M\). Eso basta porque, después del primer paso, todos los valores restantes de cualquier sucesión viven en \([1,M]\). A continuación, el programa recorre los bloques \(I_1,\dots,I_M\), calcula cuántos inicios compuestos tiene cada uno y sigue la cola común
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1.$$
Mientras avanza por la cola, mantiene el número acumulado de valores no primos ya vistos. En cada posición de la cola realiza dos actualizaciones lógicas: una para el único inicio primo del bloque y otra para los \(B_m-1\) inicios compuestos. Las versiones de C++ y Java guardan los cubos en arreglos ampliables, mientras que la versión de Python usa un mapa disperso; matemáticamente, la actualización es la misma.
Una vez procesados todos los bloques, la implementación multiplica todos los tamaños de cubo no nulos módulo \(10^9+7\). Como ese producto final solo se toma una vez, el coste real está en la criba y en las caminatas cortas por las colas iteradas de \(\pi\).
Construir la criba y la lista de primos hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Esa es la parte dominante del algoritmo.
Sea \(M=\pi(n)\). Para cada \(m\le M\), la longitud de la cola es \(O(\log m)\): para todo \(x\ge 2\), como mucho uno de cada dos enteros hasta \(x\) puede ser primo, así que
$$\pi(x)\le \frac{x+1}{2}.$$
Aplicar \(\pi\) repetidamente reduce el valor de forma geométrica hasta llegar a \(1\). Sumando el coste de todas las colas para \(m\le M\), se obtiene \(O(M\log M)\) tiempo adicional.
Dado que \(M=\pi(n)=O(n/\log n)\), el trabajo posterior a la criba es asintóticamente menor que la propia criba. En conjunto, la complejidad total es
$$O(n\log\log n)\text{ de tiempo y }O(n)\text{ de memoria}.$$
设 \(\pi(x)\) 为素数计数函数。一个 \(\pi\)-序列是任意有限的正整数序列 \(u=(u_0,\dots,u_r)\)，其中 \(r\ge 1\)，并满足
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r).$$
对于固定的起点 \(u_0\)，所有合法序列恰好就是迭代链
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
的所有长度至少为 \(2\) 的正整数前缀。记 \(c(u)\) 为序列 \(u\) 中非素数项的个数，其中 \(1\) 也视为非素数。于是 \(p(n,k)\) 表示满足 \(u_0\le n\) 且 \(c(u)=k\) 的 \(\pi\)-序列总数，题目要求计算
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k).$$
我们需要求出 \(P(10^8)\bmod(10^9+7)\)。真正的突破点在于：许多不同的起点在第一次应用 \(\pi\) 之后，会落入完全相同的后续尾链。因此没有必要逐个起点暴力统计，而是可以把具有相同第一步结果的整段起点区间一起处理。
记
$$M=\pi(n),$$
并令 \(q_m\) 表示第 \(m\) 个素数。只有 \(u_0=1\) 才会出现 \(\pi(u_0)=0\)，而这不能形成长度至少为 \(2\) 的正整数序列，所以真正有用的第一步取值正好是 \(m=1,2,\dots,M\)。
对每个 \(m\)，考虑所有满足 \(\pi(x)=m\) 且 \(x\le n\) 的起点 \(x\)。由于 \(\pi(x)\) 只会在越过一个素数时增加 \(1\)，这些起点天然组成区间：
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
若记 \(B_m=|I_m|\)，则有
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
每个区间里恰好只有一个素数起点，就是 \(q_m\) 本身；区间里的其他数全部都是合数。于是，在固定区间内部，唯一需要区分的只是“起点是那个唯一的素数”还是“起点是其余的合数”。
如果 \(x\in I_m\)，那么第一步一定满足 \(\pi(x)=m\)。从这一刻开始，后续项已经与原始起点 \(x\) 无关。定义公共尾链
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j}).$$
于是，来自区间 \(I_m\) 的任意合法序列都可以写成
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
其中 \(j\ge 0\)。又因为对每个 \(y>1\) 都有 \(\pi(y)<y\)，所以这条尾链会严格递减，最终到达 \(1\)。这说明每个区间只会产生一小段很短的前缀列表，而不会产生巨大的状态空间。
对固定的区间 \(m\)，令 \(r_{m,j}\) 表示
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}$$
这些尾链项里非素数的个数。
如果起点取该区间中唯一的素数 \(q_m\)，那么序列 \((q_m,t_{m,0},\dots,t_{m,j})\) 中的非素数项个数恰好就是 \(r_{m,j}\)，因为首项本身是素数，对 \(c(u)\) 没有额外贡献。
如果起点取同一区间中的其他元素，那么首项必为合数，因此对应序列的非素数项个数就是
$$r_{m,j}+1.$$
也就是说，共享尾链的每一个前缀都会向 \(k=r_{m,j}\) 这个计数桶贡献
$$1$$
条序列，同时向 \(k=r_{m,j}+1\) 这个计数桶贡献
$$B_m-1$$
条序列。三份实现代码本质上都在执行这一条更新规则。
一旦 \(r_{m,j}\) 已知，计数函数就可以直接写成
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
第一项统计的是“素数起点”产生的前缀；第二项统计的是同一区间中所有“合数起点”产生的前缀。把所有 \(k\) 对应的桶统计完之后，最终答案就是
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}.$$
真正重要的简化在于：算法并不遍历所有 \(u_0\le n\) 的起点，而是只遍历更小的集合 \(m=1,\dots,\pi(n)\)。每一个这样的 \(m\) 实际上代表了整整一段起点区间。
经过第一步之后，任意序列后续出现的所有值都不会超过 \(M=\pi(n)\)。因此实现中需要两类预处理：
第一类是做到 \(n\) 的完整筛法，用来判断素性，并确定每个起点区间的边界；第二类是只在 \(0,1,\dots,M\) 上建立一张较短的素数计数表，用来继续推进尾链 \(m,\pi(m),\pi(\pi(m)),\dots\)。
这也解释了程序结构：最重的工作是最开始做到 \(n\) 的筛，而真正的动态遍历只发生在远小于 \(n\) 的区间 \([1,M]\) 内。
当 \(n=10\) 时，有
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7).$$
于是起点区间为
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}.$$
对应的尾链以及累计非素数个数为
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2). \end{aligned}$$
如果把每个区间对
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr)$$
的贡献写出来，就得到
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3). \end{aligned}$$
因此
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3,$$
从而
$$P(10)=3\cdot 8\cdot 9\cdot 3=648.$$
这个小例子完整展示了区间分组的威力：只走一次短尾链，就能同时统计该区间中的唯一素数起点以及旁边所有合数起点。
C++、Python 和 Java 实现都先对 \(n\) 做一次筛。筛法同时提供两样信息：一是到 \(n\) 为止每个整数是否为素数，二是不超过 \(n\) 的全部素数的有序表。这个素数表的长度正是 \(M=\pi(n)\)，而相邻素数之间的差直接给出了各个区间的长度 \(B_m\)。
接下来，实现只在 \(0\) 到 \(M\) 之间建立素数计数表。因为一条序列在走完第一步之后，后续所有值都落在 \([1,M]\) 内，所以这张较短的表已经足够。随后程序依次处理区间 \(I_1,\dots,I_M\)，先算出每个区间内合数起点的数量，再沿着公共尾链
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1$$
向下行走。
在尾链行走过程中，程序维护“到当前位置为止已经遇到多少个非素数尾项”这一运行计数。每到一个尾链位置，就做两次逻辑更新：一次对应区间里唯一的素数起点，一次对应其余 \(B_m-1\) 个合数起点。C++ 和 Java 版本用可扩展数组保存各个桶的计数，Python 版本则使用稀疏映射；但数学意义上的更新完全相同。
所有区间处理完以后，程序把所有非零桶的大小在模 \(10^9+7\) 下相乘。由于这个乘积只在最后进行一次，真正花时间的部分是筛法和这些很短的迭代 \(\pi\) 尾链遍历。
构造到 \(n\) 的筛和素数表需要 \(O(n\log\log n)\) 时间以及 \(O(n)\) 空间。这是整个算法的主导成本。
设 \(M=\pi(n)\)。对于每个 \(m\le M\)，对应尾链的长度是 \(O(\log m)\)：因为对任意 \(x\ge 2\)，不超过 \(x\) 的整数里最多只有约一半可能是素数，所以
$$\pi(x)\le \frac{x+1}{2}.$$
不断重复应用 \(\pi\) 会把数值按几何级数压缩，直到到达 \(1\)。把所有 \(m\le M\) 的尾链成本加总，就得到额外的 \(O(M\log M)\) 时间。
又因为 \(M=\pi(n)=O(n/\log n)\)，所以筛之后的部分在渐近上比筛本身更小。总复杂度因此为
$$O(n\log\log n)\text{ 时间，}O(n)\text{ 空间}.$$
Пусть \(\pi(x)\) обозначает функцию подсчёта простых чисел. \(\pi\)-последовательностью называется любая конечная последовательность положительных целых чисел \(u=(u_0,\dots,u_r)\), где \(r\ge 1\), удовлетворяющая условию
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r).$$
Для фиксированного старта \(u_0\) все допустимые последовательности — это ровно положительные префиксы итерационной цепочки
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
длины не менее двух. Обозначим через \(c(u)\) число непростых членов последовательности \(u\), причём \(1\) тоже считается непростым. Тогда \(p(n,k)\) — это количество \(\pi\)-последовательностей с \(u_0\le n\) и \(c(u)=k\), а искомая величина равна
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k).$$
Нужно вычислить \(P(10^8)\bmod(10^9+7)\). Ключевая идея состоит в том, что после первого применения \(\pi\) многие разные стартовые значения попадают в одну и ту же хвостовую цепочку. Поэтому выгодно считать не каждый старт по отдельности, а целые группы стартов сразу.
Положим
$$M=\pi(n),$$
а через \(q_m\) обозначим \(m\)-е простое число. Случай \(\pi(u_0)=0\) возможен только для \(u_0=1\), но такое значение не может породить допустимую положительную последовательность длины хотя бы \(2\). Следовательно, полезные первые значения — это ровно \(m=1,2,\dots,M\).
Для каждого \(m\) рассмотрим все стартовые значения \(x\le n\), для которых \(\pi(x)=m\). Поскольку функция \(\pi(x)\) увеличивается только при прохождении через простое число, эти множества являются интервалами:
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
Если обозначить \(B_m=|I_m|\), то
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
В каждом таком интервале есть ровно один простой старт, а именно \(q_m\). Все остальные элементы \(I_m\) составные. Внутри одного интервала это и есть единственное существенное различие между стартами.
Если \(x\in I_m\), то первый шаг всегда даёт \(\pi(x)=m\). После этого дальнейшее развитие уже не зависит от исходного \(x\). Определим общий хвост так:
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j}).$$
Тогда любая допустимая последовательность, начинающаяся в блоке \(I_m\), имеет вид
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
для некоторого \(j\ge 0\). Так как для каждого \(y>1\) верно \(\pi(y)<y\), хвост строго убывает, пока не достигнет \(1\). Значит, каждый блок порождает лишь короткий набор префиксов.
Для фиксированного блока \(m\) обозначим через \(r_{m,j}\) количество непростых членов среди
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}.$$
Если стартом служит единственное простое число \(q_m\), то последовательность \((q_m,t_{m,0},\dots,t_{m,j})\) содержит ровно \(r_{m,j}\) непростых членов, поскольку первый элемент прост и не добавляет ничего к \(c(u)\).
Если стартом служит любой другой элемент из \(I_m\), то первый член составной, и число непростых членов становится равным
$$r_{m,j}+1.$$
Следовательно, каждый префикс общего хвоста даёт
$$1$$
последовательность в корзину \(k=r_{m,j}\) и
$$B_m-1$$
последовательностей в корзину \(k=r_{m,j}+1\). Именно это правило подсчёта реализовано во всех трёх версиях программы.
Как только значения \(r_{m,j}\) известны, функцию подсчёта можно записать в явном виде:
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
Первое слагаемое считает префиксы, стартующие в единственном простом элементе интервала. Второе слагаемое учитывает префиксы, порождённые составными стартами из того же интервала. После накопления всех корзин ответ равен
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}.$$
Главное упрощение состоит в том, что алгоритм не проходит все \(u_0\le n\) по отдельности. Он перебирает только гораздо меньший набор значений \(m=1,\dots,\pi(n)\), причём каждое такое \(m\) представляет целый интервал стартов.
После первого шага все дальнейшие значения любой последовательности не превосходят \(M=\pi(n)\). Поэтому реализации нужны два разных типа предварительных данных:
полное решето до \(n\), чтобы знать простоту чисел и границы стартовых интервалов, и короткая таблица значений функции \(\pi\) только на диапазоне \(0,1,\dots,M\), чтобы продолжать хвосты \(m,\pi(m),\pi(\pi(m)),\dots\).
Этим и объясняется структура программы: дорого стоит начальное решето до \(n\), а вся динамическая часть работает уже на гораздо меньшем диапазоне \([1,M]\).
При \(n=10\) имеем
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7).$$
Следовательно, интервалы стартов равны
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}.$$
Соответствующие хвосты и накопленные числа непростых элементов таковы:
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2). \end{aligned}$$
Если записать вклад каждого блока в вектор
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr),$$
то получим
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3). \end{aligned}$$
Отсюда
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3,$$
и, следовательно,
$$P(10)=3\cdot 8\cdot 9\cdot 3=648.$$
Этот маленький пример наглядно показывает, почему группировка по интервалам работает: один короткий проход по хвосту одновременно учитывает и единственный простой старт блока, и все составные старты рядом с ним.
Реализации на C++, Python и Java начинают с решета до \(n\). Это решето сразу даёт две вещи: проверку простоты для каждого числа до \(n\) и упорядоченный список всех простых, не превосходящих \(n\). Длина этого списка равна \(M=\pi(n)\), а соседние простые числа немедленно задают размеры интервалов \(B_m\).
Затем реализация строит таблицу функции подсчёта простых только на диапазоне от \(0\) до \(M\). Этого достаточно, потому что после первого шага все последующие значения любой последовательности лежат в \([1,M]\). После этого программа перебирает блоки \(I_1,\dots,I_M\), вычисляет число составных стартов в каждом блоке и проходит общий хвост
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1.$$
Во время этого прохода поддерживается текущее число непростых хвостовых значений. В каждой позиции хвоста выполняются два логических обновления: одно для единственного простого старта блока и одно для \(B_m-1\) составных стартов. Версии на C++ и Java хранят корзины в расширяемых массивах, а версия на Python использует разреженное отображение; математически это одна и та же операция.
После обработки всех блоков программа перемножает размеры всех ненулевых корзин по модулю \(10^9+7\). Так как это произведение берётся только в самом конце, основная стоимость сосредоточена в решете и коротких проходах по итерационным хвостам \(\pi\).
Построение решета и списка простых до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Это доминирующая часть алгоритма.
Пусть \(M=\pi(n)\). Для каждого \(m\le M\) длина хвоста равна \(O(\log m)\): для любого \(x\ge 2\) среди чисел до \(x\) простыми могут быть не более примерно половины, поэтому
$$\pi(x)\le \frac{x+1}{2}.$$
Повторное применение \(\pi\) геометрически уменьшает значение, пока оно не достигнет \(1\). Суммарная стоимость всех проходов по хвостам для \(m\le M\) равна \(O(M\log M)\).
Поскольку \(M=\pi(n)=O(n/\log n)\), после-решетная часть асимптотически меньше самого решета. Итак, общая сложность равна
$$O(n\log\log n)\text{ по времени и }O(n)\text{ по памяти}.$$
لتكن \(\pi(x)\) دالة عدّ الأعداد الأولية. متتالية \(\pi\) هي أي متتالية منتهية من الأعداد الصحيحة الموجبة \(u=(u_0,\dots,u_r)\) حيث \(r\ge 1\) وتحقق
$$u_{i+1}=\pi(u_i)\qquad(0\le i<r).$$
ولقيمة بداية ثابتة \(u_0\)، فإن جميع المتتاليات الصحيحة المسموح بها هي بالضبط البوادئ الموجبة للسلسلة المتكررة
$$u_0,\ \pi(u_0),\ \pi(\pi(u_0)),\ \dots$$
التي طولها على الأقل حدان. ولتكن \(c(u)\) عدد الحدود غير الأولية في \(u\)، مع اعتبار \(1\) عددًا غير أولي. عندئذٍ فإن \(p(n,k)\) هو عدد متتاليات \(\pi\) التي تحقق \(u_0\le n\) و \(c(u)=k\)، والكمية المطلوبة هي
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k).$$
المطلوب حساب \(P(10^8)\bmod(10^9+7)\). الفكرة الجوهرية هي أن عددًا كبيرًا من قيم البداية المختلفة يشترك في الذيل نفسه بعد التطبيق الأول للدالة \(\pi\). لذلك يمكن ضغط المسألة عبر عدّ مجموعات كاملة من البدايات دفعة واحدة بدل معالجة كل بداية على حدة.
لنكتب
$$M=\pi(n),$$
ولنرمز إلى العدد الأولي رقم \(m\) بالرمز \(q_m\). الحالة \(\pi(u_0)=0\) لا تحدث إلا عندما \(u_0=1\)، وهذه لا تعطي متتالية موجبة صحيحة طولها على الأقل \(2\). لذلك فإن القيم الأولى المفيدة هي فقط \(m=1,2,\dots,M\).
لكل \(m\)، ننظر إلى جميع قيم البداية \(x\le n\) التي تحقق \(\pi(x)=m\). وبما أن \(\pi(x)\) تزداد فقط عند تجاوز عدد أولي، فإن هذه المجموعات تكون فترات:
$$I_m=\{x\le n:\pi(x)=m\}=\begin{cases} [q_m,q_{m+1}-1], & 1\le m<M,\\ [q_M,n], & m=M. \end{cases}$$
إذا كتبنا \(B_m=|I_m|\)، فسنحصل على
$$B_m=\begin{cases} q_{m+1}-q_m, & 1\le m<M,\\ n-q_M+1, & m=M. \end{cases}$$
كل فترة تحتوي بداية أولية واحدة بالضبط، وهي \(q_m\). أما بقية عناصر \(I_m\) فهي جميعًا أعداد مركبة. داخل الفترة الواحدة لا يبقى فرق مهم سوى هذا الفصل بين بداية أولية وحيدة وبدايات مركبة.
إذا كان \(x\in I_m\)، فإن أول خطوة تعطي دائمًا \(\pi(x)=m\). بعد هذه الخطوة لا يعود المسار اللاحق معتمدًا على قيمة البداية الأصلية \(x\). نعرّف الذيل المشترك بالعلاقة
$$t_{m,0}=m,\qquad t_{m,j+1}=\pi(t_{m,j}).$$
وعندئذٍ تكون كل متتالية صحيحة ناتجة من الكتلة \(I_m\) على الصورة
$$\bigl(x,\ t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}\bigr)$$
لبعض \(j\ge 0\). وبما أن \(\pi(y)<y\) لكل \(y>1\)، فإن هذا الذيل يتناقص تناقصًا صارمًا حتى يصل إلى \(1\). لذا فإن كل كتلة تنتج عددًا صغيرًا فقط من البوادئ الممكنة.
للكتلة الثابتة \(m\)، ليكن \(r_{m,j}\) هو عدد الحدود غير الأولية بين
$$t_{m,0},\ t_{m,1},\ \dots,\ t_{m,j}.$$
إذا كانت البداية هي العدد الأولي الوحيد \(q_m\)، فإن المتتالية \((q_m,t_{m,0},\dots,t_{m,j})\) تحتوي بالضبط على \(r_{m,j}\) حدًا غير أولي، لأن الحد الأول أولي ولا يضيف شيئًا إلى \(c(u)\).
أما إذا كانت البداية عنصرًا آخر من \(I_m\)، فإن الحد الأول يكون مركبًا، وعندها يصبح عدد الحدود غير الأولية
$$r_{m,j}+1.$$
وبالتالي فإن كل بادئة من الذيل المشترك تضيف
$$1$$
متتالية إلى الفئة \(k=r_{m,j}\)، وتضيف
$$B_m-1$$
متتالية إلى الفئة \(k=r_{m,j}+1\). هذه هي قاعدة العد الأساسية التي تطبقها جميع النسخ.
بمجرد معرفة القيم \(r_{m,j}\)، يمكن كتابة دالة العد مباشرة على الصورة
$$p(n,k)=\sum_{m=1}^{M}\left(\#\{j:r_{m,j}=k\}+(B_m-1)\#\{j:r_{m,j}=k-1\}\right).$$
الحد الأول يعدّ البوادئ الناتجة من البداية الأولية الوحيدة في الفترة، والحد الثاني يعدّ البوادئ الناتجة من جميع البدايات المركبة في الفترة نفسها. وبعد ملء جميع الفئات، يكون الجواب النهائي هو
$$P(n)=\prod_{k:\,p(n,k)>0} p(n,k)\pmod{10^9+7}.$$
التبسيط الحاسم هنا هو أن الخوارزمية لا تمر على كل \(u_0\le n\) على حدة، بل تمر فقط على المجموعة الأصغر كثيرًا \(m=1,\dots,\pi(n)\)، وكل قيمة \(m\) من هذه القيم تمثل فترة كاملة من بدايات ممكنة.
بعد الخطوة الأولى، تصبح جميع القيم اللاحقة في أي متتالية محصورة في المجال حتى \(M=\pi(n)\). لذلك تحتاج الخوارزمية إلى نوعين من التحضير المسبق:
غربال كامل حتى \(n\) لمعرفة الأولية وحدود فترات البداية، وجدول قصير لقيم دالة العد \(\pi\) فقط على القيم \(0,1,\dots,M\) من أجل متابعة الأذيال من الشكل \(m,\pi(m),\pi(\pi(m)),\dots\).
وهذا يفسر بنية التنفيذ: الكلفة الكبيرة تأتي من الغربال الأولي حتى \(n\)، أما الجزء الديناميكي الحقيقي فيجري على المجال الأصغر بكثير \([1,M]\).
عندما \(n=10\) يكون لدينا
$$M=\pi(10)=4,\qquad (q_1,q_2,q_3,q_4)=(2,3,5,7).$$
ومن ثم فإن فترات البداية هي
$$I_1=\{2\},\qquad I_2=\{3,4\},\qquad I_3=\{5,6\},\qquad I_4=\{7,8,9,10\}.$$
أما الأذيال المقابلة وأعداد الحدود غير الأولية المتراكمة فهي
$$\begin{aligned} m=1&:\quad 1,\qquad r=(1),\\ m=2&:\quad 2\to 1,\qquad r=(0,1),\\ m=3&:\quad 3\to 2\to 1,\qquad r=(0,0,1),\\ m=4&:\quad 4\to 2\to 1,\qquad r=(1,1,2). \end{aligned}$$
إذا كتبنا مساهمة كل كتلة في المتجه
$$\bigl(p(10,0),\,p(10,1),\,p(10,2),\,p(10,3)\bigr),$$
فإننا نحصل على
$$\begin{aligned} m=1&:\quad (0,1,0,0),\\ m=2&:\quad (1,2,1,0),\\ m=3&:\quad (2,3,1,0),\\ m=4&:\quad (0,2,7,3). \end{aligned}$$
وعليه
$$p(10,0)=3,\qquad p(10,1)=8,\qquad p(10,2)=9,\qquad p(10,3)=3,$$
ومن ثم
$$P(10)=3\cdot 8\cdot 9\cdot 3=648.$$
هذا المثال الصغير يوضح تمامًا سبب نجاح التجميع بحسب الفترات: فمرور واحد على ذيل قصير يكفي لعدّ البداية الأولية الوحيدة في الكتلة وجميع البدايات المركبة المجاورة لها في الوقت نفسه.
تبدأ تطبيقات C++ وPython وJava بغربال حتى \(n\). ومن هذا الغربال تستخرج أمرين معًا: اختبار أولية لكل قيمة حتى \(n\)، والقائمة المرتبة لجميع الأعداد الأولية التي لا تتجاوز \(n\). طول هذه القائمة هو \(M=\pi(n)\)، كما أن الفروق بين الأعداد الأولية المتتالية تعطي مباشرة أطوال الفترات \(B_m\).
بعد ذلك يبني التنفيذ جدولًا لدالة عدّ الأوليات فقط على المجال من \(0\) إلى \(M\). وهذا كافٍ لأن أي متتالية بعد خطوتها الأولى تبقى بالكامل داخل \([1,M]\). ثم يمر البرنامج على الكتل \(I_1,\dots,I_M\)، ويحسب عدد البدايات المركبة في كل كتلة، ثم يسير على الذيل المشترك
$$m,\ \pi(m),\ \pi(\pi(m)),\ \dots,\ 1.$$
أثناء هذا السير يحتفظ التنفيذ بعدّاد جارٍ لعدد الحدود غير الأولية التي شوهدت حتى تلك اللحظة. وفي كل موضع من الذيل تُجرى عمليتا تحديث منطقيتان: واحدة للبداية الأولية الوحيدة في الكتلة، وواحدة للبدايات المركبة وعددها \(B_m-1\). نسختا C++ وJava تخزنان الفئات في مصفوفات قابلة للتمدد، أما نسخة Python فتستخدم بنية متناثرة؛ لكن التحديث الرياضي نفسه واحد في الجميع.
بعد الانتهاء من جميع الكتل، يضرب التنفيذ جميع أحجام الفئات غير الصفرية بترديد \(10^9+7\). وبما أن هذا الضرب النهائي يتم مرة واحدة فقط، فإن الكلفة الحقيقية تتمثل في الغربال وفي المرور القصير على أذيال \(\pi\) المتكررة.
بناء الغربال وقائمة الأعداد الأولية حتى \(n\) يكلف \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. وهذا هو الجزء المسيطر في الخوارزمية.
لتكن \(M=\pi(n)\). لكل \(m\le M\)، طول الذيل هو \(O(\log m)\)، لأن عدد الأعداد الأولية حتى أي \(x\ge 2\) لا يمكن أن يتجاوز تقريبًا نصف الأعداد الموجودة حتى \(x\)، ومن ثم
$$\pi(x)\le \frac{x+1}{2}.$$
لذلك فإن التكرار المستمر لتطبيق \(\pi\) يقلص القيمة هندسيًا حتى تصل إلى \(1\). وبجمع كلفة جميع الأذيال من أجل \(m\le M\)، نحصل على زمن إضافي قدره \(O(M\log M)\).
وبما أن \(M=\pi(n)=O(n/\log n)\)، فإن الجزء اللاحق للغربال أصغر أسيمبتوطيًا من الغربال نفسه. وعليه تكون الكلفة الكلية \(O(n\log\log n)\) زمنيًا و\(O(n)\) من حيث الذاكرة.