Eulerian ordering of the integers modulo n

Question

Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.

An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\forall i \le n \ \forall j<i \ \exists k < i \text{ with } \frac{n}{gcd(n,r_k-r_i)} \text{ prime and } \frac{gcd(n,r_k-r_i)}{gcd(n,r_j-r_i)} \text{ integer.}$$

Remark: Let $p$ be a prime number. Then, $0,1, \dots , p-1$ is an Eulerian ordering of $C_p$.
In fact, any ordering of $C_p$ is Eulerian, so that $C_p$ has $p!$ Eulerian orderings.

Exercice: If $n$ is not square-free then $C_n$ has no Eulerian ordering.

Example: the (lexicographically first) Eulerian ordering for $C_n$ with $n \le 30$ square-free non-prime:
$C_6 : 0,2,3,1,4,5$
$C_{10} : 0, 2, 4, 5, 1, 3, 6, 7, 8, 9$
$C_{14} : 0, 2, 4, 6, 7, 1, 3, 5, 8, 9, 10, 11, 12, 13$
$C_{15} : 0, 3, 5, 2, 6, 1, 4, 7, 8, 9, 10, 11, 12, 13, 14$
$C_{21} : 0, 3, 6, 7, 1, 4, 8, 2, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20$
$C_{22} : 0, 2, 4, 6, 8, 10, 11, 1, 3, 5, 7, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21$
$C_{26} : 0, 2, 4, 6, 8, 10, 12, 13, 1, 3, 5, 7, 9, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25$
$C_{30} : 0, 6, 10, 4, 12, 2, 8, 14, 15, 16, 18, 3, 20, 5, 17, 21, 1, 7, 11, 13, 19, 9, 22, 23, 24, 25, 26, 27, 28, 29$

Main question: Is there an Eulerian ordering of $C_n$, for every $n>1$ square-free?
It is checked by Sage for $n\le 500$ (see below).

If yes, let $n>1$ be a square-free integer:
Stronger question: Can any partial Eulerian ordering of $C_n$ ($r_1, \dots, r_s$ with $s<n$) be completed?
Bonus questions: How many Eulerian orderings of $C_n$ are there? What is the lexicographically first?

Remark: $C_6$ has $6!/2$ Eulerian orderings, and $C_{10}$ has $10!/3$ ones (see computation below).

---

The motivation from algebraic combinatorics

Let $G$ be a finite group and $H$ a subgroup. Let $[H,G]$ be the interval in the subgroup lattice of $G$.
The Eulerian ordering as written above is a number-theoretic translation of the following more general property applied to $G=C_n$ (cyclic group) and $H = \{ e\}$.

Let $\hat{C}(H,G)$ be the coset lattice, i.e. the set $\{Kg \ | \ K \in [H,G] \text{, } g \in G\} \cup \{ \emptyset \}$, ordered by $\subseteq$, with $K_1g_1 \wedge K_2g_2 = K_1g_1 \cap K_2g_2$ and $K_1g_1 \vee K_2g_2 = \langle K_1,K_2,g_1g_2^{-1}\rangle g_2$.

An Eulerian ordering of the set of $H$-cosets $Hg$ is an ordering $Hg_1, Hg_2, \dots, Hg_n$ such that:

$$\forall i \le n \ \forall j<i \ \exists k < i \text{ with } \langle H,g_kg_i^{-1}\rangle \text{ atom of } [H,G] \text{ and } \langle H,g_kg_i^{-1}\rangle \subseteq \langle H,g_jg_i^{-1}\rangle.$$

This property is inspired from the notion of shelling of a simplicial complex, and the paper Shelling the coset poset by Russ Woodroofe. In fact, I can prove that if the interval $[H,G]$ is the face lattice of a regular convex polytope (which is an Eulerian lattice), and if the $H$-cosets admit an Eulerian ordering, then the coset poset $\hat{C}(H,G)$ is shellable, and its Möbius invariant (which is equal to the reduced Euler characteristic of the order complex of its proper part) is nonzero. It follows that the dual Euler totient $\hat{\varphi}(H,G)$, as defined in this paper, is also nonzero.

The above motivation involves the usual notions of Eulerian lattice, Euler characteristic and Euler totient, that is why the above ordering is denoted as an Eulerian ordering.

Finally, for $G=C_n$ and $H = \{ e \}$, note that $\langle H,g_kg_i^{-1}\rangle$ is an atom $[H,G]$ iff $ord(g_kg_i^{-1})$ is prime, and $\langle H,g_kg_i^{-1}\rangle \subseteq \langle H,g_jg_i^{-1}\rangle$ iff $\frac{ord(g_jg_i^{-1})}{ord(g_kg_i^{-1})}$ is an integer; moreover, $ord(r) = \frac{n}{gcd(n,r)}$.

---

Sage program

# %attach SAGE/IntegerOrder.spyx

from sage.all import *

cpdef IsEulerianOrdering(int n, list L): # It checks whether L is a (partial) Eulerian ordering.
    cdef int i,j,k,s1,s2,s3,a,b,c,g1,g2,p 
    for s1 in range(1,len(L)):
        i=L[s1]
        for s2 in range(s1):
            j=L[s2]
            for s3 in range(s1):
                c=0
                k=L[s3] 
                g1=gcd(n,i-k)
                g2=gcd(n,i-j)
                p=n/g1
                if is_prime(p) and g1 % g2 == 0:    
                    c=1
                    break
            if c==0:
                print([i,j])
                return False
    return True

cpdef IntegerOrder(int n, list LL): # If LL is not a partial Eulerian ordering, then it return False. Else it try to complete LL lexicographically (possibly return a partial Eulerian ordering).
    cdef int t,s,i,j,k,a,b,c,g1,g2,p,l
    cdef list L,T
    if IsEulerianOrdering(n,LL):
        T=range(n)
        l=len(LL)
        L=LL
        for t in LL:
            T.remove(t)
        for s in range(n-l):
            c=0
            for i in T:
                a=0
                for j in L:
                    b=0
                    for k in L:
                        g1=gcd(n,i-k)
                        g2=gcd(n,i-j)
                        p=n/g1
                        if is_prime(p) and g1 % g2 ==0:
                            b=1
                            break   
                    if b==0:
                        a=1
                        break
                if a==0:
                    L.append(i)
                    T.remove(i)
                    c=1
                    break   
            if c==0:
                break
        return L
    return False

cpdef TestSquareFree(int r1, int r2):
    cdef int n,l
    cdef list L
    for n in range(r1,r2+1):
        if is_squarefree(n) and not is_prime(n):
            L=IntegerOrder(n,[0])
            l=len(L)
            if l<n:
                return n
    return True

cpdef MixedBase(int n, list s):
    cdef int l, m, i, c
    cdef list b,
    l=len(s)
    b=[]
    m=n
    for i in range(l):
        c=m//s[i]
        b.append(m-s[i]*c)
        m=c
    return b

cpdef MixedBaseOrdering(list s):
    cdef list b,o
    cdef int p,l,i,n,m
    n=prod(s)
    o=[]
    for r in range(n):
        b=MixedBase(r,s)
        l=len(s)
        m=sum([b[i]*n/s[i] for i in range(l)]) % n
        o.append(m)
    return o 

cpdef HowManyEulerianOrdering(int n):
    cdef list L
    cdef int r
    L=Permutations(range(n)).list()
    r=0
    for l in L:
        if IsEulerianOrdering(n,list(l)):
            r+=1
    return r 

---

Computation

sage: IntegerOrder(22,[0])
[0, 2, 4, 6, 8, 10, 11, 1, 3, 5, 7, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
sage: IntegerOrder(210,[0])
[0, 30, 42, 12, 54, 24, 60, 18, 48, 6, 36, 66, 70, 72, 2, 78, 84, 90, 96, 100, 102, 32, 105, 108, 112, 82, 40, 114, 44, 14, 74, 120, 15, 124, 4, 88, 28, 58, 94, 10, 52, 98, 8, 38, 50, 20, 62, 80, 92, 22, 64, 104, 34, 76, 16, 46, 86, 26, 56, 68, 106, 110, 116, 118, 122, 126, 21, 111, 128, 130, 132, 27, 117, 134, 135, 9, 129, 3, 123, 136, 138, 33, 140, 35, 141, 1, 142, 144, 39, 146, 147, 148, 150, 45, 152, 153, 154, 155, 156, 51, 121, 158, 159, 160, 161, 41, 71, 125, 162, 57, 127, 7, 37, 91, 164, 165, 166, 167, 47, 5, 75, 77, 107, 65, 131, 61, 19, 49, 79, 109, 25, 55, 13, 43, 85, 97, 103, 113, 23, 53, 11, 81, 83, 93, 95, 115, 31, 73, 119, 29, 59, 17, 87, 89, 99, 101, 133, 63, 137, 67, 139, 69, 143, 145, 149, 151, 157, 163, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209]
sage: TestSquareFree(2,500)
True
sage: HowManyEulerianOrdering(6)
360
sage: HowManyEulerianOrdering(10)
1209600

Checking of @user44191's examples

sage: L=MixedBaseOrdering([5,3,2])
sage: L
[0, 6, 12, 18, 24, 10, 16, 22, 28, 4, 20, 26, 2, 8, 14,15, 21, 27, 3, 9, 25, 1, 7, 13, 19, 5, 11, 17, 23, 29]
sage: IsEulerianOrdering(30,L)
True
sage: L=MixedBaseOrdering([7,3,2])
sage: LL=[11*i for i in L]
sage: A=[1,2,3,4,5,6]
sage: LL.extend(A)
sage: IsEulerianOrdering(462,LL) # It checks whether LL is a partial Eulerian ordering.
True
sage: CL=IntegerOrder(462,LL); len(CL)==462 # It checks whether CL is a completion of LL
True
sage: CL
[0, 66, 132, 198, 264, 330, 396, 154, 220, 286, 352, 418, 22, 88, 308, 374, 440, 44, 110, 176, 242, 231, 297, 363, 429, 33, 99, 165, 385, 451, 55, 121, 187, 253, 319, 77, 143, 209, 275, 341, 407, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 155, 23, 89, 156, 24, 90, 157, 25, 91, 158, 26, 92, 159, 27, 93, 160, 28, 94, 161, 29, 95, 162, 30, 96, 163, 31, 97, 164, 32, 98, 177, 45, 111, 178, 46, 112, 179, 47, 113, 180, 48, 114, 181, 49, 115, 182, 50, 116, 183, 51, 117, 184, 52, 118, 185, 53, 119, 186, 54, 120, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 265, 34, 266, 35, 267, 36, 268, 37, 269, 38, 270, 39, 271, 40, 272, 41, 273, 42, 274, 43, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 309, 78, 12, 144, 166, 276, 310, 79, 13, 145, 167, 277, 311, 80, 14, 146, 168, 278, 312, 81, 15, 147, 169, 279, 313, 82, 16, 148, 170, 280, 314, 83, 17, 149, 171, 281, 315, 84, 18, 150, 172, 282, 316, 85, 19, 151, 173, 283, 317, 86, 20, 152, 174, 284, 318, 87, 21, 153, 175, 285, 320, 56, 122, 188, 210, 254, 100, 321, 57, 123, 189, 211, 255, 101, 322, 58, 124, 190, 212, 256, 102, 323, 59, 125, 191, 213, 257, 103, 324, 60, 126, 192, 214, 258, 104, 325, 61, 127, 193, 215, 259, 105, 326, 62, 128, 194, 216, 260, 106, 327, 63, 129, 195, 217, 261, 107, 328, 64, 130, 196, 218, 262, 108, 329, 65, 131, 197, 219, 263, 109, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461]

Answer 1

The basic idea is to separate out the action of each prime, to the maximal extent possible. In the example given in the above comments, the idea was to ignore (the remainder modulo) $2$ as long as possible, ignore (the remainder modulo) $3$ as long as possible given that $2$ was being ignored, etc. I was inspired by the examples you posted, since almost all of them started out with an arithmetic sequence by some prime fraction of $n$. My guess was that that could be extended until it would force a repeat.

For $0 \leq i < n$, write $i$ in mixed base (e.g. $23 = 1_2 1_3 3_5$). Let $d_p(i)$ denote the digit corresponding to $p$ (e.g. $d_3(23) = 1$). Then let $r_i = (\sum_{p \in P} d_p(i) \frac{n}{p}) (\text{mod n})$. Claim: this sequence is Eulerian.

Proof: Let $j < i$ (e.g. $14 = 0_2 2_3 4_5$). Then $j$ differs from $i$ in some digit for a prime $p$ in the mixed base (and, in the largest such digit, the digit for $j$ must be smaller than that for $i$). Then we can choose some $k$ that differs from $i$ only in that digit (e.g. for $i = 23, j = 14$, we can have $k = 0_2 1_3 3_5 = 8$).

We then have that $r_i - r_k$ will be a multiple of $\frac{n}{p}$, so the first part of your statement is satisfied. Further, as $j$ differs from $i$ in the digit for $p$, the coefficients for $\frac{n}{p}$ for $r_i, r_j$ are different (and their difference isn't divisible by $p$). All of the other $\frac{n}{p'}$ are divisible by $p$, so $r_i - r_j$ isn't divisible by $p$, which implies it satisfies the second part of your statement.