I will try to answer my question based on my findings so far:

First, I will slightly change the definition of $\trianglelefteq$ without changing the fractal appereance of the image much:

If $m = p_1 p_2 \cdots p_r$ and $n = q_1 q_2 \cdots q_s$ are the decompositions of $m,n$ in prime factors with repetitions allowed and $p_i \le p_{i+1}$ then we define $m \trianglelefteq n$ as :

$$m \trianglelefteq n :\iff (p_1,\cdots,p_r) \le (q_1,\cdots,q_s)$$

where the right hand side is the lexicographic ordering which coincides with the usual ordering on tuples of length one.

Let us look at the matrix $m_{a,b}$ defined by $m_{a,b} = 1$ if $\gcd(a,b)>1$ and $0$ otherwise, where the numbers $1,\cdots,n$ are sorted by $\trianglelefteq$. Plotting this matrix for some large number, we get the following picture:

To explain the visually perceived self-similarity, let me introduce for each natural number $n$, a factorization tree $T_n$ as follows:

Let $$a_p(n):= |\{ m | 1 < m \le n , \min_{q|m, q \text{ prime}}q=p\}|$$

and let $a_1(n):=1$. We define $T_n$ recursively:

• $T_1 := (1)$
• $T_{n} := (1 \rightarrow \sum_{p \le n, p \text{ prime}} p \cdot T_{a_p(n)})$

where $p \cdot T_m$ denotes that we multiply each of the node $v$ in $T_m$ by $p$.

Here are some examples of these tree:

These trees can also be defined by successively puttting the node $n+1$ into the tree $T_n$ to get the rooted and ordered tree $T_{n+1}$, if one knows the prime factorization of $n+1$. The tree has the following property:

Sorting the nodes by pre-order, we get the same ordering as $\trianglelefteq$.

Furthermore, by this definition, we see that the tree has some self-similar property, which explains some of the visually perceived self-similarity on the image.

Also notice that the blocks on the main diagonal of the blue fractal image have size $a_p(n)$ equal to the sizes of the smaller subtrees in the recursive definition.

I will try to answer my question based on my findings so far:

First, I will slightly change the definition of $\trianglelefteq$ without changing the fractal appereance of the image much:

If $m = p_1 p_2 \cdots p_r$ and $n = q_1 q_2 \cdots q_s$ are the decompositions of $m,n$ in prime factors with repetitions allowed and $p_i \le p_{i+1}$ then we define $m \trianglelefteq n$ as :

$$m \trianglelefteq n :\iff (p_1,\cdots,p_r) \le (q_1,\cdots,q_s)$$

where the right hand side is the lexicographic ordering which coincides with the usual ordering on tuples of length one.

Let us look at the matrix $m_{a,b}$ defined by $m_{a,b} = 1$ if $\gcd(a,b)>1$ and $0$ otherwise, where the numbers $1,\cdots,n$ are sorted by $\trianglelefteq$. Plotting this matrix for some large number, we get the following picture:

To explain the visually perceived self-similarity, let me introduce for each natural number $n$, a factorization tree $T_n$ as follows:

Let $P_1(n) := 1$ if $n=1$ and $\max_{q|n, \text{ }q\text{ prime}} q$ otherwise, denote the largest prime divisor of $n$.

Let us define some rooted trees $T_{n,m}$ for $1 \le m \le n$ by:

1. $T_{n,m}$ has as root the number $m$.
2. If there are primes $p$ such that $P_1(m) \le p \le \frac{n}{m}$, then the children of $m$ are $T_{n,mp}$, otherwise $m$ is a leaf.

We set $T_n := T_{n,1}$.

Here are some examples of these tree:

These trees can also be defined by successively puttting the node $n+1$ into the tree $T_n$ to get the rooted and ordered tree $T_{n+1}$, if one knows the prime factorization of $n+1$. The tree has the following property:

Sorting the nodes by pre-order, we get the same ordering as $\trianglelefteq$.

Furthermore, by this definition, we see that the tree has some self-similar property, which explains some of the visually perceived self-similarity on the image.

Also notice that the blocks on the main diagonal of the blue fractal image have size $a_p(n)$ equal to the sizes of the smaller subtrees in the recursive definition.