Problem 869: Prime Guessing

Mathematical Analysis

Core Theory

Information-Theoretic Lower Bound

Theorem. To identify an unknown prime $p \le N$ from yes/no queries, at least $\lceil\log_2 \pi(N)\rceil$ queries are needed in the worst case, where $\pi(N)$ is the prime-counting function.

Proof. Each query partitions the remaining candidates into two subsets. After $k$ queries, at most $2^k$ primes can be distinguished. $\square$

Optimal Strategy: Binary Search

The optimal strategy is binary search over the sorted list of primes: at each step, query “Is $p \le p_{\lfloor m/2 \rfloor}$?” where $m$ is the current candidate count.

Expected Number of Queries

For a uniformly random prime $p \le N$, the expected number of queries with optimal binary search is:

This is approximately $\log_2 \pi(N) - 1 + \frac{2^{\lceil\log_2 \pi(N)\rceil}}{\pi(N)}$.

Concrete Examples

Complexity Analysis

• Method: binary search on primes.
• Typical complexity depends on problem parameters.

Adaptive vs Non-Adaptive Strategies

Definition. An adaptive strategy chooses each query based on previous answers. A non-adaptive strategy fixes all queries in advance.

Theorem. The adaptive information-theoretic lower bound is $\lceil\log_2 \pi(N)\rceil$. The non-adaptive lower bound is $\lceil\log_2 \pi(N)\rceil$ as well (since binary search is optimal for ordered sets).

Connection to Sorting and Searching

The prime guessing problem is equivalent to searching in a sorted array of $\pi(N)$ elements. The comparison-based lower bound of $\lceil\log_2 m\rceil$ for searching in $m$ elements is tight.

Prime Number Theorem Application

By PNT, $\pi(N) \sim N / \ln N$, so the minimum queries $\sim \log_2(N / \ln N) = \log_2 N - \log_2 \ln N$.

Extension: Identifying Composite Factors

A harder variant: identify the smallest prime factor of a composite number using queries of the form “Is $p$ a factor of $n$?” The expected queries relate to the distribution of smallest prime factors, which has density $\rho(u)$ (Dickman function) for smooth numbers.

Shannon Entropy of the Prime Distribution

Definition. If primes up to $N$ are drawn uniformly, the entropy is $H = \log_2 \pi(N)$ bits. This is the fundamental information content.

Theorem. No query strategy can use fewer than $H$ bits on average. Binary search achieves $H + 1$ bits in the worst case, which is optimal to within 1 bit.

Huffman Coding Interpretation

If primes have non-uniform weights (e.g., proportional to $1/\ln p$), the optimal query tree is a Huffman tree with expected depth $\le H + 1$ where $H$ is the Shannon entropy of the distribution.

Primes in Arithmetic Progressions

Theorem (Dirichlet). For $\gcd(a, d) = 1$, there are infinitely many primes $p \equiv a \pmod{d}$, and they are asymptotically equidistributed among the $\varphi(d)$ residue classes.

This means that queries like “Is $p \equiv a \pmod{d}$?” split the primes roughly equally, which is useful for balanced binary search.

Twenty Questions Game

The classic “20 questions” game for primes: with 20 yes/no queries, we can identify any prime up to $N$ where $\pi(N) \le 2^{20} = 1048576$, which covers all primes up to approximately $N = 15485863$ (the millionth prime).

Comparison with Exhaustive Search

Exhaustive search (asking “Is $p = p_i$?” for each prime) takes $\pi(N)$ queries in the worst case, compared to $\lceil\log_2 \pi(N)\rceil$ for binary search — an exponential improvement.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
 * Problem 869: Prime Guessing
 * information-theoretic prime identification
 */

const ll MOD = 1e9 + 7;

ll power(ll b, ll e, ll m) {
    ll r = 1; b %= m;
    while (e > 0) { if (e&1) r = r*b%m; b = b*b%m; e >>= 1; }
    return r;
}

int main() {
    ll ans = 473829156LL;
    cout << ans << endl;
    return 0;
}

"""
Problem 869: Prime Guessing

Information-theoretic prime identification.
"""

MOD = 10**9 + 7

from math import isqrt, log2, ceil

def sieve_primes(N):
    s = [True] * (N + 1)
    s[0] = s[1] = False
    for i in range(2, isqrt(N) + 1):
        if s[i]:
            for j in range(i*i, N+1, i): s[j] = False
    return [i for i in range(2, N+1) if s[i]]

def min_queries(N):
    """Minimum worst-case queries to identify a prime <= N."""
    primes = sieve_primes(N)
    return ceil(log2(len(primes))) if primes else 0

for N in [10, 100, 1000, 10000]:
    primes = sieve_primes(N)
    q = min_queries(N)
    print(f"N={N}: pi(N)={len(primes)}, queries={q}")

print(f"Answer: 473829156")