The parity tag has no usage guidance.

**10**

votes

**1**answer

457 views

### Parity of the Prime Counting Function

I am interested in the distribution of the parity of $\pi(x)$, the prime counting function, over the natural numbers.
Let:
$\ \ E_n := \left\{ k \in \left\{1,\dots,n\right\} : \pi(k) \equiv 0 \mod 2 ...

**15**

votes

**2**answers

939 views

### Parity of $\lfloor 1/(x y) \rfloor$ not equally distributed

A curious puzzle for which I would appreciate an explanation.
For $x$ and $y$ both uniformly and independently distributed in $[0,1]$,
the value of $\lfloor 1/(x y) \rfloor$ has a bias toward odd ...

**11**

votes

**3**answers

1k views

### Proofs of parity results via the Handshaking lemma

I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...

**6**

votes

**2**answers

946 views

### How hard is it to solve SAT if the promise is that it has an odd number of solutions?

SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known ...