Let \(\mathcal{P}_n\) be the set of primes not exceeding \(n\). The task is to count ordered \(k\)-tuples \((p_1,\dots,p_k)\in \mathcal{P}_n^k\) such that their bitwise OR is itself a prime in \(\mathcal{P}_n\), and to report the count modulo \(10^9+7\).
Equivalently, if we write
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\},$$
then the implementations evaluate \(F(10^6,999983)\pmod{10^9+7}\). A direct enumeration over all prime \(k\)-tuples is hopeless, so the solution works on the Boolean lattice of bitmasks instead.
The key observation is that the bitwise OR of integers corresponds to set union of their 1-bit positions. That makes subset transforms the natural tool for counting tuples by their exact OR-mask.
Choose the smallest integer \(B\) such that
$$2^B>n.$$
Every integer \(x\le n\) then fits into \(B\) binary digits, so we may identify \(x\) with the subset of bit positions where its binary expansion has a 1.
If \(S\) is such a bitmask, define the prime-indicator function
$$a(S)=\begin{cases} 1,&\text{if the integer represented by }S\text{ is prime and }\le n,\\ 0,&\text{otherwise.} \end{cases}$$
For two masks \(T\) and \(S\), the relation \(T\subseteq S\) means that every 1-bit of \(T\) also appears in \(S\). In ordinary bit language, this is exactly the statement that \(T\) is a submask of \(S\).
Define the subset zeta transform of \(a\) by
$$A(S)=\sum_{T\subseteq S} a(T).$$
This quantity counts how many primes in \(\mathcal{P}_n\) have all their 1-bits contained in \(S\). In other words, \(A(S)\) is the number of primes \(p\le n\) such that \(p\subseteq S\) as a bitmask.
This is the crucial relaxation: instead of asking for tuples whose OR is exactly \(S\), we first count tuples whose OR stays inside \(S\).
If every entry of an ordered \(k\)-tuple must be chosen from the \(A(S)\) admissible primes contained in \(S\), then the number of such tuples is simply
$$B(S)=A(S)^k.$$
Why does this help? Because
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}.$$
So after the zeta transform, a pointwise \(k\)-th power converts “available single primes” into “available ordered prime tuples whose OR does not leave \(S\)”.
Now let
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}.$$
Then every tuple counted by \(B(S)\) has exact OR equal to some submask \(T\subseteq S\), so
$$B(S)=\sum_{T\subseteq S} E(T).$$
This is precisely the setting for Möbius inversion on the subset lattice. Therefore
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T).$$
After this inversion, \(E(S)\) is the exact number of ordered prime tuples whose bitwise OR equals \(S\), not merely a submask of \(S\).
The problem does not ask for all exact OR-masks. It asks only for those masks that are themselves prime numbers not exceeding \(n\). Hence the final answer is
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
Substituting the inversion formula gives the fully explicit expression
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}.$$
This is exactly the mathematics behind the sieve, subset transforms, and pointwise exponentiation used by the implementation.
Here \(\mathcal{P}_5=\{2,3,5\}\). Since \(2^3=8>5\), we work with \(B=3\) bits:
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
For the mask \(010_2\), only the prime \(2\) is a submask, so \(A(010)=1\), hence \(B(010)=1^2=1\), and therefore \(E(010)=1\).
For the mask \(011_2\), both \(2\) and \(3\) are submasks, so \(A(011)=2\), whence \(B(011)=2^2=4\). The proper submasks contribute only \(E(010)=1\), so Möbius inversion gives
$$E(011)=4-1=3.$$
For the mask \(101_2\), only the prime \(5\) is a submask, so \(E(101)=1\).
Thus
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
The five ordered pairs are \((2,2)\), \((2,3)\), \((3,2)\), \((3,3)\), and \((5,5)\).
The C++, Python, and Java implementations all follow the same pipeline. They first sieve all primes up to \(n\) and mark those prime values inside an array indexed by masks from \(0\) to \(2^B-1\).
Next they perform the in-place subset zeta transform, bit by bit, so that each entry stores \(A(S)\), the number of prime masks contained in \(S\). After that, each entry is raised to the \(k\)-th power modulo \(10^9+7\), which produces the relaxed tuple count \(B(S)\).
They then run the inverse subset transform, again bit by bit, using subtraction modulo \(10^9+7\). This turns the relaxed counts into exact counts \(E(S)\). Finally they sum \(E(S)\) only over those indices \(S\) that correspond to primes not exceeding \(n\).
One implementation also checks the intermediate values \(F(100,3)=3355\) and \(F(1000,10)=2071632\), which are consistent with the same derivation.
Let \(B\) be the smallest integer with \(2^B>n\). The prime sieve costs \(O(n\log\log n)\) time. The subset zeta transform and the subset Möbius inversion each cost \(O(B2^B)\) time. Pointwise modular exponentiation over all masks costs \(O(2^B\log k)\).
Therefore the overall running time is
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right).$$
The memory usage is \(O(n+2^B)\): the sieve needs space up to \(n\), and the transform arrays need space for all masks. For \(n=10^6\), we have \(B=20\) and \(2^B=1{,}048{,}576\), which makes the transform-based approach practical.
Sei \(\mathcal{P}_n\) die Menge aller Primzahlen \(\le n\). Gesucht ist die Anzahl geordneter \(k\)-Tupel \((p_1,\dots,p_k)\in \mathcal{P}_n^k\), deren bitweises OR selbst wieder eine Primzahl aus \(\mathcal{P}_n\) ist. Das Ergebnis soll modulo \(10^9+7\) ausgegeben werden.
Mit
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\}$$
berechnen die Implementierungen also \(F(10^6,999983)\pmod{10^9+7}\). Direkte Enumeration ist völlig unrealistisch, daher wird auf dem Booleschen Verband der Bitmasken gearbeitet.
Die zentrale Beobachtung lautet: Das bitweise OR entspricht der Vereinigungsbildung der gesetzten Bits. Deshalb passen Teilmengen-Transformationen hier genau zur Struktur des Problems.
Wähle das kleinste \(B\) mit
$$2^B>n.$$
Jede Zahl \(x\le n\) passt dann in \(B\) Binärstellen und kann mit der Menge ihrer 1-Bit-Positionen identifiziert werden.
Für eine solche Maske \(S\) definieren wir den Primindikator
$$a(S)=\begin{cases} 1,&\text{falls die durch }S\text{ dargestellte Zahl prim und }\le n\text{ ist},\\ 0,&\text{sonst.} \end{cases}$$
Die Relation \(T\subseteq S\) bedeutet, dass jedes in \(T\) gesetzte Bit auch in \(S\) gesetzt ist. In der Sprache der Bitoperationen ist \(T\) also eine Untermaske von \(S\).
Nun bilden wir die Teilmengen-Zeta-Transformation
$$A(S)=\sum_{T\subseteq S} a(T).$$
Damit zählt \(A(S)\) genau die Primzahlen \(p\le n\), deren 1-Bits vollständig in \(S\) enthalten sind. Anders gesagt: \(A(S)\) ist die Anzahl der Primmasken, die Untermasken von \(S\) sind.
So wird das Problem zunächst entspannt: Statt Tupel mit exakt gegebener OR-Maske zu zählen, zählen wir Tupel, deren OR höchstens \(S\) ist.
Wenn aus \(A(S)\) zulässigen Primzahlen gewählt werden darf und die Reihenfolge zählt, dann gibt es
$$B(S)=A(S)^k$$
geordnete \(k\)-Tupel. Zugleich gilt
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}.$$
Nach der Zeta-Transformation genügt also eine punktweise \(k\)-te Potenz, um aus lokalen Primzahlanzahlen die Anzahl aller Tupel mit OR innerhalb von \(S\) zu erhalten.
Sei
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}.$$
Dann trägt jedes Tupel, dessen exaktes OR gleich \(T\) ist, zu allen \(B(S)\) mit \(T\subseteq S\) bei. Deshalb
$$B(S)=\sum_{T\subseteq S} E(T).$$
Auf dem Teilmengenverband invertiert man diese Beziehung mit Möbius-Inversion:
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T).$$
Danach ist \(E(S)\) die exakte Anzahl geordneter Prim-Tupel mit bitweisem OR gleich \(S\).
Gesucht sind nicht alle exakten Masken, sondern nur jene \(S\), die selbst Primzahlen \(\le n\) darstellen. Somit lautet die Endformel
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
Setzt man die Inversionsformel ein, erhält man
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}.$$
Genau diese Struktur wird durch Sieb, Zeta-Transformation, Potenzierung und inverse Transformation umgesetzt.
Hier ist \(\mathcal{P}_5=\{2,3,5\}\). Weil \(2^3=8>5\), genügen \(B=3\) Bits:
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
Für die Maske \(010_2\) ist nur \(2\) eine Untermaske. Also gilt \(A(010)=1\), damit \(B(010)=1^2=1\), also auch \(E(010)=1\).
Für \(011_2\) sind sowohl \(2\) als auch \(3\) Untermasken. Daher \(A(011)=2\) und somit \(B(011)=2^2=4\). Der einzige nichttriviale Beitrag echter Teilmasken ist \(E(010)=1\), also
$$E(011)=4-1=3.$$
Für \(101_2\) ist nur \(5\) zulässig, also \(E(101)=1\).
Folglich
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
Die fünf geordneten Paare sind \((2,2)\), \((2,3)\), \((3,2)\), \((3,3)\) und \((5,5)\).
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst werden alle Primzahlen bis \(n\) gesiebt und in einem Array markiert, dessen Indizes direkt die Bitmasken \(0,\dots,2^B-1\) darstellen.
Anschließend läuft die Teilmengen-Zeta-Transformation bitweise in-place. Danach enthält jedes Feld den Wert \(A(S)\), also die Zahl der Primmasken unterhalb von \(S\). Dann wird jedes Feld modulo \(10^9+7\) in die \(k\)-te Potenz erhoben und liefert so \(B(S)\).
Danach folgt die inverse Teilmengen-Transformation mit modularen Subtraktionen. Dadurch entstehen die exakten OR-Zahlen \(E(S)\). Zum Schluss summiert das Programm nur noch die Werte an jenen Indizes, die selbst Primzahlen \(\le n\) sind.
Eine der Implementierungen prüft außerdem die Zwischenwerte \(F(100,3)=3355\) und \(F(1000,10)=2071632\), was dieselbe Herleitung bestätigt.
Sei \(B\) minimal mit \(2^B>n\). Das Primzahlsieb benötigt \(O(n\log\log n)\) Zeit. Die Teilmengen-Zeta-Transformation und die Möbius-Inversion kosten jeweils \(O(B2^B)\) Zeit. Die punktweisen modularen Potenzen über alle Masken kosten \(O(2^B\log k)\).
Insgesamt ergibt sich also
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right).$$
Der Speicherbedarf beträgt \(O(n+2^B)\): Platz für das Sieb bis \(n\) plus Platz für die Masken-Arrays. Für \(n=10^6\) gilt \(B=20\) und \(2^B=1{,}048{,}576\), weshalb der Ansatz praktisch ausführbar ist.
\(\mathcal{P}_n\), \(n\)'i aşmayan asal sayıların kümesi olsun. Amaç, \((p_1,\dots,p_k)\in \mathcal{P}_n^k\) biçimindeki sıralı \(k\)-lileri saymaktır; burada bu sayıların bit düzeyinde OR'u yine \(\mathcal{P}_n\) içinde bir asal olmalıdır. Sonuç \(10^9+7\) modunda istenir.
Yani
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\}$$
tanımıyla, uygulamalar \(F(10^6,999983)\pmod{10^9+7}\) değerini hesaplar. Tüm asal \(k\)-lileri doğrudan denemek imkansız olduğundan çözüm, bitmaskelerin oluşturduğu Boole kafesi üzerinde çalışır.
Ana gözlem şudur: Bitwise OR, 1 olan bit konumlarının birleşimine karşılık gelir. Bu yüzden tam OR maskesini saymak için altküme dönüşümleri doğal araç haline gelir.
İlk olarak
$$2^B>n$$
olacak en küçük \(B\) seçilir. Böylece \(x\le n\) olan her sayı \(B\) bit içinde temsil edilir ve \(x\), ikilik yazımında 1 olan konumların kümesi olarak görülebilir.
Bir \(S\) maskesi için asal gösterge fonksiyonunu
$$a(S)=\begin{cases} 1,&\text{eğer }S\text{ tarafından temsil edilen sayı asal ve }\le n\text{ ise},\\ 0,&\text{aksi halde} \end{cases}$$
şeklinde tanımlayalım. \(T\subseteq S\) ifadesi, \(T\)'deki her 1-bitin \(S\)'de de 1 olduğu anlamına gelir; yani bitmask diliyle \(T\), \(S\)'nin altmaskesidir.
Şimdi altküme zeta dönüşümünü
$$A(S)=\sum_{T\subseteq S} a(T)$$
olarak tanımlayalım. Bu değer, bitleri tamamen \(S\)'nin içinde kalan asal sayıların sayısını verir. Başka bir deyişle \(A(S)\), \(S\)'nin altmaskesi olan asal maskelerin sayısıdır.
Bu adım problemi gevşetir: önce OR'u tam olarak \(S\) olanları değil, OR'u \(S\)'nin dışına taşmayan tüm tuple'ları sayarız.
Eğer her bileşen \(A(S)\) adet uygun asal arasından seçilebiliyorsa ve sıra önemliyse, bu seçimlerin sayısı
$$B(S)=A(S)^k$$
olur. Ayrıca
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}$$
eşitliği geçerlidir. Yani zeta dönüşümünden sonra noktasal \(k\). kuvvet almak, OR'u \(S\)'nin içinde kalan tüm sıralı asal \(k\)-lilerini verir.
Şimdi
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}$$
olsun. O halde \(B(S)\), tam OR'u \(T\subseteq S\) olan tüm tuple'ların toplamıdır:
$$B(S)=\sum_{T\subseteq S} E(T).$$
Bu ilişki, altküme kafesinde tam olarak Möbius terslemenin konusudur. Dolayısıyla
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T)$$
elde edilir. Böylece \(E(S)\), bitwise OR'u tam olarak \(S\) olan sıralı asal \(k\)-lilerinin sayısı olur.
Aradığımız şey tüm maskeler değil, kendisi de asal sayı olan maskelerdir. Bu yüzden son formül
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
olur. Tersleme formülünü açarsak
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}$$
elde edilir. Elek, altküme dönüşümleri ve noktasal üs alma tam olarak bu eşitliği uygular.
Burada \(\mathcal{P}_5=\{2,3,5\}\) olur. \(2^3=8>5\) olduğu için \(B=3\) yeterlidir:
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
\(010_2\) maskesi için altmaske olarak yalnızca \(2\) vardır. Bu nedenle \(A(010)=1\), dolayısıyla \(B(010)=1^2=1\) ve \(E(010)=1\).
\(011_2\) maskesi için hem \(2\) hem \(3\) altmaskedir; bu yüzden \(A(011)=2\) ve \(B(011)=2^2=4\). Gerçek altmaskelerden gelen tek katkı \(E(010)=1\) olduğundan
$$E(011)=4-1=3$$
olur.
\(101_2\) maskesinde yalnızca \(5\) uygun olduğundan \(E(101)=1\) bulunur.
Sonuç olarak
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
Bu beş sıralı çift \((2,2)\), \((2,3)\), \((3,2)\), \((3,3)\) ve \((5,5)\) şeklindedir.
C++, Python ve Java implementasyonlarının akışı aynıdır. Önce \(n\)'e kadar asal sayılar elenir ve bu asal değerler, indisleri doğrudan maske olan bir dizide işaretlenir.
Daha sonra altküme zeta dönüşümü her bit için yerinde uygulanır. Bu aşamadan sonra her hücre \(A(S)\), yani \(S\)'nin içinde kalan asal maskelerin sayısını tutar. Ardından her hücre \(10^9+7\) modunda \(k\). kuvvete yükseltilir ve böylece \(B(S)\) elde edilir.
Sonraki adım, çıkarma işlemleriyle yapılan ters altküme dönüşümüdür. Bu dönüşüm gevşetilmiş sayıları tam OR sayıları \(E(S)\)'ye çevirir. En sonda yalnızca kendisi de asal olan indekslerdeki değerler toplanır.
Uygulamalardan biri ayrıca \(F(100,3)=3355\) ve \(F(1000,10)=2071632\) kontrol değerlerini doğrular; bunlar aynı matematiği teyit eder.
\(2^B>n\) koşulunu sağlayan en küçük \(B\) için, asal eleği \(O(n\log\log n)\) zamanda çalışır. Altküme zeta dönüşümü ve Möbius tersleme ayrı ayrı \(O(B2^B)\) zaman gerektirir. Tüm maskelerde noktasal modüler üs alma ise \(O(2^B\log k)\) sürer.
Toplam süre
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right)$$
olur. Bellek kullanımı \(O(n+2^B)\)'dir: eleğin \(n\)'e kadar olan kısmı ve tüm maskeler için ayrılan diziler birlikte bu maliyeti oluşturur. \(n=10^6\) için \(B=20\) ve \(2^B=1{,}048{,}576\) olduğundan yöntem pratiktir.
Sea \(\mathcal{P}_n\) el conjunto de primos no mayores que \(n\). Debemos contar las \(k\)-tuplas ordenadas \((p_1,\dots,p_k)\in \mathcal{P}_n^k\) cuyo OR bit a bit vuelve a ser un primo de \(\mathcal{P}_n\). El resultado se toma módulo \(10^9+7\).
En otras palabras, si definimos
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\},$$
las implementaciones calculan \(F(10^6,999983)\pmod{10^9+7}\). Enumerar directamente todas las tuplas de primos es inviable, así que la solución cambia al retículo booleano de las máscaras binarias.
La idea central es que el OR bit a bit coincide con la unión de las posiciones donde hay un 1. Eso permite trabajar con transformadas de subconjuntos y recuperar después el OR exacto.
Tomamos el menor entero \(B\) tal que
$$2^B>n.$$
Así, cualquier entero \(x\le n\) cabe en \(B\) bits y puede identificarse con el conjunto de posiciones donde su escritura binaria vale 1.
Para una máscara \(S\), definimos el indicador de primo
$$a(S)=\begin{cases} 1,&\text{si el entero representado por }S\text{ es primo y }\le n,\\ 0,&\text{en otro caso.} \end{cases}$$
La relación \(T\subseteq S\) significa que todo bit encendido en \(T\) también aparece encendido en \(S\); es decir, \(T\) es una submáscara de \(S\).
Aplicamos la transformada zeta de subconjuntos
$$A(S)=\sum_{T\subseteq S} a(T).$$
Este valor cuenta cuántos primos \(p\le n\) tienen todos sus bits activos contenidos en \(S\). En lenguaje de máscaras, son exactamente los primos que son submáscaras de \(S\).
Con ello primero resolvemos un problema más fácil: no contamos tuplas con OR exacto igual a \(S\), sino tuplas cuyo OR queda contenido en \(S\).
Si cada componente de la tupla puede elegirse entre \(A(S)\) primos permitidos y el orden importa, entonces hay
$$B(S)=A(S)^k$$
tuplas posibles. Además,
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}.$$
Por tanto, después de la transformada zeta, una potencia punto a punto convierte el conteo de primos permitidos en el conteo de tuplas ordenadas cuyo OR no sale de \(S\).
Definamos
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}.$$
Entonces toda tupla contada por \(B(S)\) tiene OR exacto igual a alguna submáscara \(T\subseteq S\), de modo que
$$B(S)=\sum_{T\subseteq S} E(T).$$
La inversión de Möbius sobre el retículo de subconjuntos da
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T).$$
Tras esta inversión, \(E(S)\) cuenta exactamente las \(k\)-tuplas ordenadas de primos cuyo OR bit a bit es \(S\).
La respuesta final no usa todas las máscaras exactas, sino únicamente aquellas que representan un primo \(\le n\). Por ello,
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
Si sustituimos la fórmula de inversión, obtenemos
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}.$$
Esa es exactamente la estructura matemática explotada por la criba, la transformada zeta, la potenciación punto a punto y la inversión final.
Aquí \(\mathcal{P}_5=\{2,3,5\}\). Como \(2^3=8>5\), basta trabajar con \(B=3\) bits:
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
Para la máscara \(010_2\), solo \(2\) es submáscara, así que \(A(010)=1\), luego \(B(010)=1^2=1\), y por tanto \(E(010)=1\).
Para \(011_2\), las submáscaras primas son \(2\) y \(3\), de modo que \(A(011)=2\) y \(B(011)=2^2=4\). El único aporte propio de submáscaras ya determinado es \(E(010)=1\), por lo que
$$E(011)=4-1=3.$$
Para \(101_2\), solo aparece \(5\), así que \(E(101)=1\).
En consecuencia,
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
Las cinco parejas ordenadas son \((2,2)\), \((2,3)\), \((3,2)\), \((3,3)\) y \((5,5)\).
Las implementaciones en C++, Python y Java siguen exactamente la misma secuencia. Primero generan todos los primos hasta \(n\) con una criba y marcan esos valores en un arreglo indexado por máscaras desde \(0\) hasta \(2^B-1\).
Después ejecutan la transformada zeta de subconjuntos in situ, bit a bit. Al terminar, cada posición contiene \(A(S)\), el número de máscaras primas incluidas en \(S\). Luego elevan cada posición a la potencia \(k\) módulo \(10^9+7\), lo que produce \(B(S)\).
A continuación aplican la transformada inversa de subconjuntos mediante restas módulo \(10^9+7\). Eso convierte los conteos relajados en los conteos exactos \(E(S)\). Finalmente suman solo las posiciones que corresponden a primos no mayores que \(n\).
Una de las implementaciones también verifica los valores de control \(F(100,3)=3355\) y \(F(1000,10)=2071632\), coherentes con la misma deducción matemática.
Sea \(B\) el menor entero con \(2^B>n\). La criba de primos cuesta \(O(n\log\log n)\) tiempo. La transformada zeta de subconjuntos y la inversión de Möbius cuestan cada una \(O(B2^B)\). La potenciación modular punto a punto sobre todas las máscaras cuesta \(O(2^B\log k)\).
En total, el tiempo es
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right).$$
La memoria es \(O(n+2^B)\): la criba necesita espacio hasta \(n\), y las estructuras de transformada necesitan espacio para todas las máscaras. Para \(n=10^6\), se tiene \(B=20\) y \(2^B=1{,}048{,}576\), así que el método sigue siendo práctico.
设 \(\mathcal{P}_n\) 表示所有不超过 \(n\) 的素数集合。题目要求统计有序 \(k\) 元组 \((p_1,\dots,p_k)\in \mathcal{P}_n^k\) 的个数，使得它们的按位 OR 结果本身仍然是 \(\mathcal{P}_n\) 中的一个素数，并对 \(10^9+7\) 取模。
也就是说，若定义
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\},$$
那么实现所求的是 \(F(10^6,999983)\pmod{10^9+7}\)。直接枚举所有素数 \(k\) 元组完全不可行，因此解法改为在位掩码对应的布尔格上进行计数。
核心事实是：一个整数的按位 OR，正好等于它的所有 1 位位置所构成集合的并集。因此“精确 OR 等于某个掩码”的问题，可以先转成“OR 落在某个掩码内部”的问题，再用子集反演恢复回来。
取最小的整数 \(B\)，使得
$$2^B>n.$$
这样每个 \(x\le n\) 都能写成一个长度为 \(B\) 的二进制掩码。于是我们可以把整数 \(x\) 与“哪些二进制位为 1”的那个集合直接对应起来。
对于任意掩码 \(S\)，定义素数指示函数
$$a(S)=\begin{cases} 1,&\text{如果 }S\text{ 所表示的整数是一个不超过 }n\text{ 的素数},\\ 0,&\text{否则。} \end{cases}$$
当我们写 \(T\subseteq S\) 时，意思是 \(T\) 的每一个 1 位在 \(S\) 中也都是 1。换成位运算语言，就是说 \(T\) 是 \(S\) 的一个子掩码。
定义子集 zeta 变换
$$A(S)=\sum_{T\subseteq S} a(T).$$
它表示有多少个素数 \(p\le n\) 的所有 1 位都包含在 \(S\) 里面。也就是说，\(A(S)\) 统计的是“作为位掩码时不超出 \(S\) 的素数个数”。
这一步的重要意义在于，我们暂时不去区分 OR 是否刚好等于 \(S\)，而是先数 OR 是否被限制在 \(S\) 内部。这样计数会一下子变成可乘的形式。
如果对某个固定的 \(S\)，每一项都可以从这 \(A(S)\) 个允许的素数里独立挑选，而且顺序有区别，那么总共有
$$B(S)=A(S)^k$$
种有序选择方式。
另一方面，这个数量恰好就是
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}.$$
原因很直接：一个元组的 OR 不超过 \(S\)，当且仅当元组中每个素数的 1 位都不超出 \(S\)。所以做完 zeta 变换后，对每个掩码做一次点值 \(k\) 次幂，就能得到“OR 落在 \(S\) 内”的元组总数。
现在定义
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}.$$
如果某个元组的精确 OR 是 \(T\)，那么只要 \(T\subseteq S\)，它就会被算进 \(B(S)\) 里。因此
$$B(S)=\sum_{T\subseteq S} E(T).$$
这正是布尔子集格上的 Möbius 反演场景，所以可以倒推出
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T).$$
到这一步为止，我们已经把“OR 被 \(S\) 包含”转换成了“OR 恰好等于 \(S\)”的精确计数。
题目真正需要的不是所有 \(E(S)\)，而只是那些掩码 \(S\) 自己对应一个不超过 \(n\) 的素数。因此最终答案为
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
把前面的定义全部代回去，可以写成显式公式
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}.$$
这正是程序中“筛素数 + 子集 zeta 变换 + 点值幂 + 子集 Möbius 反演 + 在素数掩码上求和”这一整条流程的数学含义。
此时 \(\mathcal{P}_5=\{2,3,5\}\)。因为 \(2^3=8>5\)，所以只需要 \(B=3\) 位：
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
先看掩码 \(010_2\)。它的素数子掩码只有 \(2\)，所以 \(A(010)=1\)，从而 \(B(010)=1^2=1\)，于是 \(E(010)=1\)。
再看 \(011_2\)。它的素数子掩码有 \(2\) 和 \(3\)，所以 \(A(011)=2\)，于是 \(B(011)=2^2=4\)。在它的真子掩码中，只有 \(010_2\) 会贡献一个已经算出的精确值，因此
$$E(011)=4-1=3.$$
对于 \(101_2\)，唯一的素数子掩码是 \(5\)，因此 \(E(101)=1\)。
总答案就是
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
这 5 个有序二元组分别是 \((2,2)\)、\((2,3)\)、\((3,2)\)、\((3,3)\) 和 \((5,5)\)。这个小例子完整展示了“先放宽、再反演”的整个思路。
C++、Python 和 Java 实现遵循完全相同的流程。首先，它们用筛法找出所有不超过 \(n\) 的素数，并在一个长度为 \(2^B\) 的数组中，把那些“下标本身就是素数”的位置标成 1，其余位置标成 0。
接着，程序按位执行原地的子集 zeta 变换。变换完成后，每个数组单元就表示 \(A(S)\)，也就是掩码 \(S\) 能容纳多少个素数子掩码。然后对每个单元做模 \(10^9+7\) 的 \(k\) 次幂，得到 \(B(S)\)。
下一步是按同样的位顺序做逆变换，通过模意义下的减法恢复出精确计数 \(E(S)\)。最后，只把那些下标本身对应素数且不超过 \(n\) 的位置累加起来。
其中一个实现还校验了两个中间测试点：\(F(100,3)=3355\) 和 \(F(1000,10)=2071632\)。这些数值与上面的推导完全一致。
设 \(B\) 是满足 \(2^B>n\) 的最小整数。筛法需要 \(O(n\log\log n)\) 时间。子集 zeta 变换和子集 Möbius 反演各需要 \(O(B2^B)\) 时间。对全部掩码做模幂计算需要 \(O(2^B\log k)\) 时间。
因此总时间复杂度为
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right).$$
空间复杂度是 \(O(n+2^B)\)：前者来自筛数组，后者来自存储全部位掩码状态。对 \(n=10^6\) 而言，\(B=20\)，因此 \(2^B=1{,}048{,}576\)，这个规模仍然在可接受范围内。
Пусть \(\mathcal{P}_n\) обозначает множество простых чисел, не превосходящих \(n\). Нужно посчитать число упорядоченных \(k\)-кортежей \((p_1,\dots,p_k)\in \mathcal{P}_n^k\), для которых побитовое OR снова является простым числом из \(\mathcal{P}_n\). Ответ требуется по модулю \(10^9+7\).
То есть, если определить
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\},$$
то реализации вычисляют \(F(10^6,999983)\pmod{10^9+7}\). Полный перебор всех простых \(k\)-кортежей невозможен, поэтому решение переводит задачу на решетку битовых масок.
Главное наблюдение такое: побитовое OR совпадает с объединением позиций, в которых стоят единицы. Значит, удобно сначала считать кортежи, OR которых содержится в маске \(S\), а затем через инверсию восстановить количество с точным OR, равным \(S\).
Выберем минимальное \(B\), для которого
$$2^B>n.$$
Тогда любое число \(x\le n\) помещается в \(B\) двоичных разрядов, и его можно отождествить с множеством позиций, где в двоичной записи стоит 1.
Для маски \(S\) введем индикатор простоты
$$a(S)=\begin{cases} 1,&\text{если число, задаваемое маской }S,\text{ простое и }\le n,\\ 0,&\text{иначе.} \end{cases}$$
Запись \(T\subseteq S\) означает, что каждый единичный бит из \(T\) присутствует и в \(S\). Иными словами, \(T\) является подмаской \(S\).
Рассмотрим zeta-преобразование по подмножествам
$$A(S)=\sum_{T\subseteq S} a(T).$$
Величина \(A(S)\) показывает, сколько простых чисел \(p\le n\) имеют все свои единичные биты внутри \(S\). То есть это количество простых подмасок маски \(S\).
Именно здесь задача упрощается: вместо точного OR мы пока считаем более слабое условие “OR не выходит за пределы \(S\)”.
Если для фиксированной маски \(S\) разрешено выбирать каждый элемент кортежа из \(A(S)\) допустимых простых и порядок важен, то число вариантов равно
$$B(S)=A(S)^k.$$
При этом
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}.$$
Следовательно, после zeta-преобразования достаточно возвести каждое значение в степень \(k\), чтобы получить число всех упорядоченных простых кортежей, чей OR целиком помещается в \(S\).
Теперь определим
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}.$$
Тогда любой кортеж с точным OR, равным \(T\), учитывается во всех \(B(S)\), для которых \(T\subseteq S\). Поэтому
$$B(S)=\sum_{T\subseteq S} E(T).$$
Это стандартная ситуация для инверсии Мёбиуса на булевой решетке, и мы получаем
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T).$$
После этого \(E(S)\) уже означает точное число упорядоченных простых кортежей, чей побитовый OR равен именно \(S\).
Нас интересуют не все точные маски, а только те, которые сами кодируют простое число \(\le n\). Поэтому окончательная формула имеет вид
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
Подставляя предыдущие определения, получаем
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}.$$
Именно эта формула реализуется с помощью решета, прямого подмножественного преобразования, поэлементного возведения в степень и обратного преобразования.
Здесь \(\mathcal{P}_5=\{2,3,5\}\). Поскольку \(2^3=8>5\), достаточно трех бит:
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
Для маски \(010_2\) единственная простая подмаска — это \(2\). Значит, \(A(010)=1\), затем \(B(010)=1^2=1\), и потому \(E(010)=1\).
Для маски \(011_2\) простые подмаски — \(2\) и \(3\), так что \(A(011)=2\), а \(B(011)=2^2=4\). Из собственных подмасок уже известен вклад \(E(010)=1\), следовательно
$$E(011)=4-1=3.$$
Для \(101_2\) допустима только маска \(5\), поэтому \(E(101)=1\).
Итак,
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
Это соответствует пяти упорядоченным парам: \((2,2)\), \((2,3)\), \((3,2)\), \((3,3)\) и \((5,5)\).
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала строится решето простых до \(n\), а затем значения, являющиеся простыми, отмечаются в массиве длины \(2^B\), индексируемом масками.
Далее выполняется in-place zeta-преобразование по подмножествам. После него каждая ячейка хранит \(A(S)\), то есть число простых подмасок внутри \(S\). Затем каждое значение возводится в степень \(k\) по модулю \(10^9+7\), и получается \(B(S)\).
После этого запускается обратное подмножественное преобразование с вычитаниями по модулю. Оно превращает ослабленные количества в точные значения \(E(S)\). Наконец, программа суммирует только те позиции, которые сами соответствуют простым числам \(\le n\).
В одной из реализаций дополнительно проверяются контрольные значения \(F(100,3)=3355\) и \(F(1000,10)=2071632\); они совпадают с тем же математическим выводом.
Пусть \(B\) — минимальное число, для которого \(2^B>n\). Решето требует \(O(n\log\log n)\) времени. Прямое zeta-преобразование и инверсия Мёбиуса по подмножествам требуют по \(O(B2^B)\) времени. Поэлементное модульное возведение в степень по всем маскам стоит \(O(2^B\log k)\).
Итоговая временная сложность равна
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right).$$
Память составляет \(O(n+2^B)\): нужна память и для решета до \(n\), и для массивов по всем маскам. При \(n=10^6\) имеем \(B=20\) и \(2^B=1{,}048{,}576\), поэтому метод остается вполне практичным.
لتكن \(\mathcal{P}_n\) مجموعة الأعداد الأولية التي لا تتجاوز \(n\). المطلوب هو عدّ جميع الـ \(k\)-tuples المرتبة \((p_1,\dots,p_k)\in \mathcal{P}_n^k\) التي يكون فيها الناتج من عملية OR على مستوى البتات عدداً أولياً آخر ضمن \(\mathcal{P}_n\)، ثم أخذ النتيجة بترديد \(10^9+7\).
بصيغة مكافئة، إذا عرّفنا
$$F(n,k)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\in \mathcal{P}_n\right\},$$
فإن التنفيذات تحسب \(F(10^6,999983)\pmod{10^9+7}\). العد المباشر لجميع tuples الأولية مستحيل عملياً، لذلك تنتقل الفكرة إلى العمل على شبكة الأقنعة الثنائية.
الفكرة الأساسية هي أن OR على مستوى البتات يساوي اتحاد مواضع البتات التي قيمتها 1. لذلك يمكن أولاً عدّ الـ tuples التي يكون OR الخاص بها محتوى داخل قناع معيّن، ثم استرجاع العدّ الدقيق للقناع النهائي بواسطة Möbius inversion على شبكة المجموعات الجزئية.
نختار أصغر عدد صحيح \(B\) يحقق
$$2^B>n.$$
عندها كل عدد \(x\le n\) يمكن تمثيله داخل \(B\) بتات، وبالتالي يمكن النظر إليه باعتباره مجموعة المواضع التي يظهر فيها البت 1.
ولأي قناع \(S\)، نعرّف دالة المؤشر
$$a(S)=\begin{cases} 1,&S\in \mathcal{P}_n,\\ 0,&S\notin \mathcal{P}_n. \end{cases}$$
أما العلاقة \(T\subseteq S\) فتعني أن كل بت يساوي 1 في \(T\) يظهر أيضاً في \(S\)، أي أن \(T\) submask من \(S\).
نعرّف subset zeta transform كما يلي:
$$A(S)=\sum_{T\subseteq S} a(T).$$
هذا المقدار يساوي عدد الأعداد الأولية \(p\le n\) التي تقع جميع بتاتها المساوية لـ 1 داخل \(S\). بعبارة أخرى، هو عدد الأقنعة الأولية التي تُعد submasks للقناع \(S\).
هذه هي خطوة التخفيف الأساسية: بدلاً من أن نطلب OR يساوي \(S\) بالضبط، نعدّ أولاً جميع الـ tuples التي لا يخرج OR الخاص بها خارج \(S\).
إذا كان لدينا \(A(S)\) اختيارات أولية مسموح بها داخل القناع \(S\)، وكان اختيار كل عنصر مستقلاً مع احتساب الترتيب، فإن عدد الـ tuples الممكنة هو
$$B(S)=A(S)^k.$$
كما أن هذا العدد يساوي بالضبط
$$B(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i\subseteq S\right\}.$$
إذن بعد zeta transform، يكفي رفع كل خلية إلى القوة \(k\) لكي نحصل على عدد جميع الـ tuples المرتبة التي يبقى OR الخاص بها داخل \(S\).
لنعرّف
$$E(S)=\#\left\{(p_1,\dots,p_k)\in \mathcal{P}_n^k:\bigvee_{i=1}^{k} p_i=S\right\}.$$
عندئذٍ كل tuple له OR دقيق يساوي \(T\) سيُحسب داخل كل \(B(S)\) يحقق \(T\subseteq S\)، وبالتالي
$$B(S)=\sum_{T\subseteq S} E(T).$$
هذه العلاقة تُعكس مباشرة بواسطة Möbius inversion على شبكة المجموعات الجزئية:
$$E(S)=\sum_{T\subseteq S}(-1)^{\lvert S\rvert-\lvert T\rvert}B(T).$$
بعد هذه الخطوة يصبح \(E(S)\) هو العدد الدقيق للـ tuples المرتبة التي يساوي OR الخاص بها القناع \(S\) نفسه.
الجواب النهائي لا يحتاج كل الأقنعة، بل يحتاج فقط الأقنعة التي تمثل أعداداً أولية لا تتجاوز \(n\). لذا تكون الصيغة النهائية
$$\boxed{F(n,k)=\sum_{p\in\mathcal{P}_n} E(p)\pmod{10^9+7}.}$$
وبإدخال الصيغ السابقة نحصل على التعبير الصريح
$$F(n,k)=\sum_{p\in\mathcal{P}_n}\ \sum_{T\subseteq p}(-1)^{\lvert p\rvert-\lvert T\rvert}\left(\sum_{U\subseteq T} a(U)\right)^k \pmod{10^9+7}.$$
وهذا هو بالضبط الأساس الرياضي الذي تستعمله التنفيذات: غربال للأوليات، ثم subset zeta transform، ثم رفع نقطي للأس، ثم Möbius inversion، ثم جمع على الأقنعة الأولية فقط.
في هذه الحالة \(\mathcal{P}_5=\{2,3,5\}\). وبما أن \(2^3=8>5\)، فنحتاج فقط إلى \(B=3\) بتات:
$$2=010_2,\qquad 3=011_2,\qquad 5=101_2.$$
بالنسبة إلى القناع \(010_2\)، العدد الأولي الوحيد الذي يُعد submask له هو \(2\). لذلك \(A(010)=1\)، ومن ثم \(B(010)=1^2=1\)، وبالتالي \(E(010)=1\).
أما القناع \(011_2\)، فله قناعان أوليان فرعيان هما \(2\) و\(3\)، لذا \(A(011)=2\) ومنه \(B(011)=2^2=4\). والإسهام غير الصفري الوحيد من الأقنعة الأصغر هو \(E(010)=1\)، لذا
$$E(011)=4-1=3.$$
وبالنسبة إلى \(101_2\)، القناع الأولي الوحيد المحتوى فيه هو \(5\)، ولهذا \(E(101)=1\).
إذن
$$F(5,2)=E(2)+E(3)+E(5)=1+3+1=5.$$
والـ five ordered pairs هنا هي \((2,2)\) و\((2,3)\) و\((3,2)\) و\((3,3)\) و\((5,5)\).
تنفيذات C++ وPython وJava تتبع المسار نفسه. أولاً تُولِّد جميع الأعداد الأولية حتى \(n\) باستخدام الغربال، ثم تضع 1 في الخانات التي يكون فهرسها نفسه عدداً أولياً داخل مصفوفة طولها \(2^B\).
بعد ذلك تُطبَّق subset zeta transform بشكل in-place وعلى كل بت على حدة. عند انتهاء هذه المرحلة، تحتوي كل خانة على \(A(S)\)، أي عدد الأقنعة الأولية الموجودة داخل \(S\). ثم تُرفع كل قيمة إلى القوة \(k\) بترديد \(10^9+7\) للحصول على \(B(S)\).
في الخطوة التالية تُنفَّذ العملية العكسية بطرح القيم بترديد \(10^9+7\)، فينتج لدينا العدّ الدقيق \(E(S)\). وفي النهاية تُجمع فقط الخانات التي تقابل أعداداً أولية لا تتجاوز \(n\).
كما أن إحدى التنفيذات تتحقق أيضاً من قيمتي الاختبار \(F(100,3)=3355\) و\(F(1000,10)=2071632\)، وهما متوافقتان تماماً مع الاشتقاق الرياضي السابق.
إذا كان \(B\) هو أصغر عدد يحقق \(2^B>n\)، فإن الغربال يحتاج إلى \(O(n\log\log n)\) زمناً. وكل من subset zeta transform وMöbius inversion يحتاج إلى \(O(B2^B)\) زمناً. أما رفع جميع الخلايا إلى القوة \(k\) بترديد ثابت فيكلف \(O(2^B\log k)\).
إذن زمن التنفيذ الكلي هو
$$O\!\left(n\log\log n + B2^B + 2^B\log k\right).$$
واستهلاك الذاكرة هو \(O(n+2^B)\): جزء للغربال حتى \(n\)، وجزء لمصفوفات الأقنعة كلها. وعند \(n=10^6\) يكون \(B=20\) وبالتالي \(2^B=1{,}048{,}576\)، وهو حجم عملي تماماً.