Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Encode Integers as Sets of Active Bits

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\).

Step 2: Count Primes Contained in Each Mask

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\).

Step 3: Lift from Single Primes to Ordered \(k\)-Tuples

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\)”.

Step 4: Recover Exact OR-Masks by Möbius Inversion

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\).

Step 5: Sum Only the Prime OR-Values

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.

Worked Example: \(n=5,\ k=2\)

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)\).

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=734
2. Prime numbers: Wikipedia — Prime number
3. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
4. Bitwise operations: Wikipedia — Bitwise operation
5. Möbius inversion formula: Wikipedia — Möbius inversion formula
6. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle