Prime number $01$ bitstrings. Can we represent all the prime positions perfectly with recursion?

42 Views Asked by At

Let $p(n) = 1 $ if $n$ is not prime or $1$ and $p(n) = 0$ if $n$ is prime or $1$. Define for prime $q$ the sequence $\hat{q}(n) = 1 $ if $n = 0 \pmod q$ and $\hat{q}(n) = 0 $ otherwise. Let $\oplus$ be pointwise boolean "or". Then $\hat{2}(n)\oplus \hat{3}(n)\oplus p(n)$ up to $n = 5^2 -1$ looks like (as a concatenated bitstring):

$$ (1\cdot 011101 \cdot 011101 \cdot 011101 \cdot 011101) $$

Check this by counting $0,1,2,3, \dots$ and verifying that there's a $1$ in each position of a composite or $2,3$. When we say prime we mean unital primes: the primes as well as $1$.

Define $\hat{0} = 10000\dots \ $ and $x(n) = 0011101000\dots \ $ where we have used bitstring notation since we're only dealing with two sequence values.

Then $\hat{2} \oplus \hat{3} \oplus p(n)$ up to $n = 5^2 - 1$ also can be written:

$$ \hat{0}\oplus x(n) \oplus x(n -6) \oplus x(n-12) \oplus x(n-18) = y(n) $$

where of course negative indices get assigned a sequence value of $0$. Of course $p(n)$ up to $7^2 - 1$ is given by:

$y(n) \oplus y(n - 25) \oplus \hat{5}$

My question is, can we keep on constructing like this (up to the next prime squared minus 1) or do weird things start happening on the boundaries?

1

There are 1 best solutions below

0
On BEST ANSWER

You are close to the Sieve of Erastosthanes. If you change the definition of $\hat q(n)$ to be zero for the prime you can just take the or over the primes and get zero for all the primes and one for all the composites. Your version using $6,12,18$ is trying to cover for the fact that you didn't define it properly for the prime, so if you fix $\hat q(n)$ you don't need that.