I am trying to prove the properties below, and by doing this, I hope to find a way to speed up the computation of the below defined addition and multiplication. I am also interested if these finite semirings are known (If the algebraic structure can be proven to be a semiring).

Context:
I am interpreting the factorization trees, such as $T_{19}$ shown here, which knows the factorization of every number $1 \le m \le 19$, as decision trees for numbers which might be larger then $19$. For this interpretation I take every node of the tree as asking recursively the number $N$ a question concerning its smallest prime divisor.

[![factorization_tree_for_n=_19][1]][1]

Each number $N$ then is classified / projected on one of the numbers $1,\cdots,19$, which I denote as $\pi_n(N)$.

Idea: First we define $\pi_n(N):= \max_{ x \le N, x \in D(N) \cap [n]} x $, where $D(N)$ denotes the set of divisors of $N$ which are sorted with the lexicographic prime factorization ordering, which 
is denoted as $\le$ and the $\max$ is being taken with respect to this ordering and $[n]:=\{1,2,\cdots,n\}$.


Here are some values calculated for $\pi_n(N)$:


[![table_for_pi_n(N)][2]][2]



Properties of $\pi_n(N)$:


* $\forall m \leq n \in \mathbb{N}: \pi_n(m) = m$
* $\forall N \in \mathbb{N}: 1 \leq \pi_n(N) \leq n$
* $\forall N \in \mathbb{N}: \pi_n(N) \, | \, N$
* $\forall N \in \mathbb{N}: \pi_n(\pi_n(N)) = \pi_n(N)$
* (?) $\forall a,b \in \mathbb{N}: \pi_n(a \cdot b) \le \pi_n(a) \cdot \pi_n(b)$



We define the "successor" function on $[n]:=\{1,2,\ldots,n\}$:

$$
\psi: [n] \rightarrow [n]
$$

$$
m \mapsto \pi_n(m+1)
$$

We define addition on $[n]$ as $\oplus$:

$$
\oplus: [n] \times [n] \rightarrow [n]
$$


$$(a , b) \mapsto \psi^{(b)}(a) = \psi(\psi(...(\psi(a))...))$$

where the successor function $\psi$ is iterated $b$ times.

We define the multiplication on $[n]$ as $\otimes$:

$$\otimes: [n] \times [n] \rightarrow [n]$$


$$
(a , b) \mapsto a \oplus a \oplus \ldots \oplus a
$$

where the addition will be iterated $b$ times.

**Conjectured properties of the operations**


* $([n], \oplus,\otimes)$ is an abelian semiring (without neccessarily having a $0$ and a $1$).


**Idea for notation**

Idea for notation: $a \equiv b \operatorname{proj}(n)$ if and only if $\pi_n(a) = \pi_n(b)$.

Therefore,


* $a \operatorname{proj}(n) := \pi_n(a)$
* $a + b \operatorname{proj}(n) := \pi_n(a) \oplus \pi_n(b)$
* $a \cdot b \operatorname{proj}(n) := \pi_n(a) \otimes \pi_n(b)$ (Definition consisent on equivalence classes?)


**Conjectured properties (semiring definition)**


* $a + b \operatorname{proj}(n) \equiv b + a \operatorname{proj}(n)$
* $a \cdot b \operatorname{proj} \equiv b \cdot a \operatorname{proj}(n)$
* $a \cdot (b + c) \operatorname{proj}(n) \equiv a \cdot b + a \cdot c \operatorname{proj}(n)$
* $a + (b+c) \operatorname{proj}(n) \equiv (a+b) + c \operatorname{proj}(n)$
* $a \cdot (b \cdot c) \operatorname{proj}(n) \equiv (a \cdot b) \cdot c \operatorname{proj}(n)$


We get:

$$
a = b \iff \forall n \in \mathbb{N}: a \operatorname{proj}(n) \equiv b \operatorname{proj}(n)
$$

If, $a = b \implies \forall n \in \mathbb{N}: \pi_n(a) = \pi_n(b)$, thus $a \equiv b \operatorname{proj}(n)$.
On the other hand, if we let $n = \max(a,b)$, then $1 \leq a, b \leq n \implies a = \pi_n(a) = \pi_n(b) = b$.

**Examples of addition and multiplication tables**
$\oplus$ for $n=1$
$$ \left(\begin{array}{r}1\end{array}\right) $$

$\otimes$ for $n=1$
$$ \left(\begin{array}{r}1\end{array}\right) $$

$\oplus$ for $n=2$
$$ \left(\begin{array}{rr}2 & 1 \\ 1 & 2 \end{array}\right) $$

$\otimes$ for $n=2$
$$ \left(\begin{array}{rr}1 & 2 \\ 2 & 2 \end{array}\right) $$

$\oplus$ for $n=3$
$$ \left(\begin{array}{rrr}2 & 3 & 2 \\ 3 & 2 & 3 \\ 2 & 3 & 2\end{array}\right) $$

$\otimes$ for $n=3$
$$ \left(\begin{array}{rrr}
1 & 2 & 3 \\ 
2 & 2 & 2 \\ 
3 & 2 & 3\end{array}\right) $$

$\oplus$ for $n=4$
$$ \left(\begin{array}{rrrr}2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4\end{array}\right) $$

$\otimes$ for $n=4$
$$ \left(\begin{array}{rrrr}1 & 2 & 3 & 4 \\ 2 & 4 & 2 & 4 \\ 3 & 2 & 1 & 4 \\ 4 & 4 & 4 & 4\end{array}\right) $$

$\oplus$ for $n=5$
$$ \left(\begin{array}{rrrrr}
2 & 3 & 4 & 5 & 2 \\
3 & 4 & 5 & 2 & 3 \\
4 & 5 & 2 & 3 & 4 \\
5 & 2 & 3 & 4 & 5 \\
2 & 3 & 4 & 5 & 2
\end{array}\right) $$

$\otimes$ for $n=5$
$$ \left(\begin{array}{rrrrr}
1 & 2 & 3 & 4 & 5 \\
2 & 4 & 2 & 4 & 2 \\
3 & 2 & 5 & 4 & 3 \\
4 & 4 & 4 & 4 & 4 \\
5 & 2 & 3 & 4 & 5
\end{array}\right) $$



**Visualization of addition and multiplication tables for** $n=100$

[![addition_table_for_n=100][3]][3]

[![multiplication_table_for_n=100][4]][4]


**Successor Graphs**
Let $G_n = ([n],E_n)$ be the directed graph defined on the vertices $[n]$ and between the vertices $a,b$ is an edge $a \rightarrow b \iff b = \pi_n(a+1)$.

Some graphs are shown in the following two tables.
[![table_with_successor_graph_for_n=3,4,5,6][5]][5]

[![table_with_successor_graph_for_n=7,8,9,10][6]][6]


We can see from this graphs a certain modularity and make the conjecture, that we have:

\begin{equation}
    a \oplus b = 
    \begin{cases} 
      a+b & \text{if } a+b \le n, \\
      (a+b-\pi_n(n+1)) (\mod n-\pi_n(n+1)+1) + \pi_n(n+1), \text{ otherwise}
    \end{cases}
\end{equation}

\begin{equation}
    a \otimes b = 
    \begin{cases} 
      a \cdot b & \text{if } a \cdot b \le n, \\
      (a \cdot b-\pi_n(n+1)) (\mod n-\pi_n(n+1)+1) + \pi_n(n+1), \text{ otherwise}
    \end{cases}
\end{equation}

These two equations could be used to speed up the computation of $\oplus, \otimes$ and would prove that the structure above is an abelian semiring.

**Question: Can these two equation above about $\oplus,\otimes$ be proven?**


  [1]: https://i.sstatic.net/eObpP.png
  [2]: https://i.sstatic.net/ZCPcC.png
  [3]: https://i.sstatic.net/DUAqW.png
  [4]: https://i.sstatic.net/HMpsC.png
  [5]: https://i.sstatic.net/bpgVW.png
  [6]: https://i.sstatic.net/6s3Wl.png