This problem is motivated by the polymath4 project. There, the aim was to find an efficient deterministic algorithm for finding a prime larger than $N$. The hope was to find a polynomial algorithm in $n=\log N$ which can be done assuming the truth of either plausible but intractable number theory conjectures or plausible but intractable problems in computational complexity. What was achieved was an algorithm that runs in time $N^{1/2-c}$ for some small $c>0$ to find the parity of the number of primes in an arbitrary interval of integers smaller than $N$. In view of this, identifying a single interval with an odd number of primes could be useful. Here are some questions regarding primes and parity.

### 1)

Let $N$ be an integer. consider the intervals $[N,2N]$, $[2N,3N], \dots$ $[kN,(k+1)N]$ What is the smallest $k$ that we can guarantee that one of these intervals contain an odd number of primes?

Based on Cramer's probabilistic modeling we can expect $k=a \log N$ to work for every $N$ and some constant $a$. Results about gaps between primes assert that when $k$ is exponential in $N$ we can find such an interval with one, hence an odd number of, primes. (For that we need two consecutive large gaps, apparently this is known but I am not aware of an elementary argument as for one gap.)

Is there some hope to prove it for $k=N^{100}$, $k=N$? $k=N^{1/2}$? A proof for $k=N^{1/2-c}$ will allow us by divide and conquer to find a prime $p$ larger than $N$ is time $p^{1/2-c}$.

### 2)

For which of the following sequences of intervals $[a(n),2a(n)]$ would it be possible to prove that that (i) there are infinitely many cases of odd number of primes; (ii) this occurs in half the cases?

**2.1** $a(n)=n$ or an a.p. (I think (i) is ok);

**2.2** $a(n)=p_n$;

**2.3** $a_n=n^2$;

**2.4** $a_n=2^n$

Is showing that there are infinitely many $n$s for which there are odd number of $n$-digits primes entirely hopeless (like Cramer's conjecture)?

### 3)

Let $p_n$ be the $n$th prime. What can be said/proved about the zeta-like function $$ \prod_{k=1}^\infty {{1}\over{1-(-1)^kp_k^{-s}}}$$

### 4)

Beside polymath4, were such questions about primes and parity considered before?

### 5)

Mark Lewko proposed the following question in a comment below: Consider subsets $A\subset [n]$ of density $n/log(n)$. What is the smallest collection of arithmetic progressions such that at least one is **guaranteed** to intersect every such $A$ with odd parity?