Representations of natural numbers by arithmetic properties

Question

Consider $N=2^k$ and the set $[N] = \{0,1,\dots,N-1\}$. For each $n\in[N]$ there are $k$ unique numbers $n_i \in \{0,1\}$, $i = 0,\dots,k-1$ such that $n = \sum_i\ n_i\cdot 2^i$. The tupel $\langle n_{k-1}\dots n_0\rangle$ is the binary representation of $n$.

The tuple can be interpreted in another way, namely as a tuple of truth values, indicating which of $k$ independent arithmetic properties $p_0,\dots p_{k-1}$ a number $n$ possesses or not.

These properties can be defined via the parametrized arithmetic function $r_i(n) = n / 2^i \mod 2$:

$$p_i(n) :\equiv r_i(n) = 1$$

This yields a "truth table", e.g. for the numbers $n\in [8] = \{0,\dots,7\}$ (with $0$ for FALSE and $1$ for TRUE):

\begin{array}{|c|c|c|c|} \hline n& p_2 & p_1 & p_0 \\ \hline 0 & 0 & 0 & 0\\ \hline 1 & 0 & 0 & 1\\ \hline 2 & 0 & 1 & 0 \\ \hline 3 & 0 & 1 & 1 \\ \hline 4 & 1 & 0 & 0 \\ \hline 5 & 1 & 0 & 1 \\ \hline 6 & 1 & 1 & 0 \\ \hline 7 & 1 & 1 & 1 \\ \hline \end{array}

Note, that the columns indicate the extensions of the predicates $p_i$.

By permuation of $\{0,\dots,7\}$ it is easy to see that there are exactly $8!=40320$ triples of subsets $\langle q_2,q_1,q_0\rangle$ such that each $n \in [8]$ is uniquely defined by its membership in these subsets.

Some of these triples can be defined not just by the extensions of the $q_i$ but by some arithmetic properties.

We know already one such triple of arithmetic properties, and there are eight similar triples, because for each $p_i$ we could have independently chosen $r_i(n) = 1$ or $r_i(n) = 0$.

My question is:

Which "naturally" definable triples $\langle q_2,q_1,q_0\rangle$ of arithmetic properties come to mind, such that each $n < 8$ can be uniquely defined by them?

"Naturally" means: not by just giving their extensions.

Are there other parametrized properties like the $p_i$?

Are there properties not making use of the functions $r_i$?

The language in which the properties may be defined is intentionally unspecified.

Answer 1

(1) I found one triple of arithmetic properties, that is not parametrized like the $p_i$, but still makes use of the functions $r_i$.

They have their origin in somehow "physical" properties of the original binary representation:

Let $\mathsf{symm}(n)$ iff the binary representation of $n$ is symmetric, i.e.

$\mathsf{symm}(n) :\equiv r_0(n) = r_2(n)$.

Let $\mathsf{right}(n)$ iff (the binary representation is NOT symmetric AND the right most digit is $1$) OR (the binary representation is symmetric AND the middle digit is $1$), i.e.

$\mathsf{right}(n) :\equiv (r_0(n) \neq r_2(n) \wedge r_0(n)=1) \vee (r_0(n) = r_2(n) \wedge r_1(n)=1)$

Let $\mathsf{heavy}(n)$ iff the binary representation of $n$ contains more $1$s than $0$s, i.e.

$\mathsf{heavy}(n) :\equiv (r_0(n) = r_1(n) = 1) \vee (r_0(n) = r_2(n) = 1) \vee (r_1(n) = r_2(n) = 1)$.

This is the "truth" or "property table":

\begin{array}{|c|c|c|c|c|c|c|c|} \hline n& p_2 & p_1 & p_0 & \mathsf{symm} & \mathsf{right} & \mathsf{heavy} & \pi(n)\\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 4\\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 0 & 2\\ \hline 2 & 0 & 1 & 0 & 1 & 1 & 0 & 6\\ \hline 3 & 0 & 1 & 1 & 0 & 1 & 1 & 3\\ \hline 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 5 & 1 & 0 & 1 & 1 & 0 & 1 & 5\\ \hline 6 & 1 & 1 & 0 & 0 & 0 & 1 & 1\\ \hline 7 & 1 & 1 & 1 & 1 & 1 & 1 & 7\\ \hline \end{array}

Could this be some kind of a blue print for constructing further such triples of properties?

Answer 2

(2) I found some other arithmetic properties that suffice to characterize each number $n < 8$:

$\mathsf{large\_mod4}(n) :\equiv \ n \mod 4 > 1$

$\mathsf{large\_mod2}(n) :\equiv \ n \mod 2 > 0$

$\mathsf{extremal}(n) :\equiv \ n < 2 \vee n > 5$

\begin{array}{|c|c|c|c|c|c|c|c|} \hline n& p_2 & p_1 = \mathsf{large\_mod4} & p_0 = \mathsf{large\_mod2} & \mathsf{extremal} & \pi(n)\\ \hline 0 & 0 & 0 & 0 & 1 & 1\\ \hline 1 & 0 & 0 & 1 & 1 & 3\\ \hline 2 & 0 & 1 & 0 & 0 & 4\\ \hline 3 & 0 & 1 & 1 & 0 & 6\\ \hline 4 & 1 & 0 & 0 & 0 & 0\\ \hline 5 & 1 & 0 & 1 & 0 & 2\\ \hline 6 & 1 & 1 & 0 & 1 & 5\\ \hline 7 & 1 & 1 & 1 & 1 & 7\\ \hline \end{array}

Answer 3

(3) Here are three further arithmetic properties that suffice to characterize each number $n < 8$:

$\mathsf{odd}(n) :\equiv\ 0 < n\mod 2$

$\mathsf{small}(n) :\equiv 0 < n < 5$

$\mathsf{large}(n) :\equiv 2 < n < 7$

$\mathsf{small}$ means "small, but not minimal", $\mathsf{large}$ means "large, but not maximal". Note that numbers $3,4$ are both small and large.

\begin{array}{|c|c|c|c|c|c|c|c|} \hline n& p_2 & p_1 & p_0 = \mathsf{odd} & \mathsf{small} & \mathsf{large} & \pi(n)\\ \hline 0 & 0 & 0 & 0 & 0 & 0& 0\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 6\\ \hline 2 & 0 & 1 & 0 & 1 & 0 & 2\\ \hline 3 & 0 & 1 & 1 & 1 & 1 & 7\\ \hline 4 & 1 & 0 & 0 & 1 & 1 & 3\\ \hline 5 & 1 & 0 & 1 & 0 & 1 & 5\\ \hline 6 & 1 & 1 & 0 & 0 & 1 & 1\\ \hline 7 & 1 & 1 & 1 & 0 & 0 & 4\\ \hline \end{array}

Answer 4

(4) Two more arithmetic properties that together with $\mathsf{odd}$ suffice to characterize each number $n < 8$:

Let $\mathsf{seq0}(n)$ iff the binary representation of $n$ contains no $0$s or a sequence of $0$s, i.e.

$\mathsf{seq0}(n) :\equiv r_0(n)=r_1(n)=r_2(n)=1 \vee r_0(n)=r_1(n)=0 \vee r_1(n)=r_2(n)=0$

Let $\mathsf{seq1}(n)$ iff the binary representation of $n$ contains no $1$s or a sequence of $1$s, i.e.

$\mathsf{seq1}(n) :\equiv r_0(n)=r_1(n)=r_2(n)=0 \vee r_0(n)=r_1(n)=1 \vee r_1(n)=r_2(n)=1$

\begin{array}{|c|c|c|c|c|c|c|c|} \hline n& p_2 & p_1 & p_0 = \mathsf{odd} & \mathsf{seq0} & \mathsf{seq1} & \pi(n)\\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 3\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 6\\ \hline 2 & 0 & 1 & 0 & 0 & 0 & 0\\ \hline 3 & 0 & 1 & 1 & 0 & 1 & 5\\ \hline 4 & 1 & 0 & 0 & 1 & 0 & 2\\ \hline 5 & 1 & 0 & 1 & 0 & 0 & 4\\ \hline 6 & 1 & 1 & 0 & 0 & 1 & 1\\ \hline 7 & 1 & 1 & 1 & 1 & 1 & 7\\ \hline \end{array}