I suggested in a comment, to look for colorings that are the same for each <i>a</i>, except for a fixed permutation.

Suppose the colors are given by function c(x), for x &ge; 1. And a permutation function p(i,j), where i,j &isin; [1..n]. Where i is the index of the permutation, and j the index of the permutation of the color.

If n = 4 and the coloring starts with abcd, then p(1,1) = a, p(1,2) = b, p(1,3) = c, p(1,4) = d, p(2,1) = b, p(2,2) = d.

If the coloring is the same for each <i>a</i>, then we get the following equation:

c(an) = p(c(a),c(n))

It is more important to give a condition when the above condition is met.

<b>Lemma 1:</b> If p(x,y) is reflexive (p(x,y)=p(y,x)) and associative (p(x,p(y,z))=p(p(x,y),z)) and p(x,y)=p(1,xy) for xy &le; n, then a coloring can be constructed.

<b>Lemma 2:</b> For each n a permutation exists such that it reflexive and associative and for p(x,y)=p(1,xy) for xy &le; n.

To see how this works, for n = 4, we start the following permutation matrix:<br/>
abcd<br/>
bd..<br/>
c...<br/>
d...<br/>

Fill in the second row:<br/>
abcd<br/>
bdac<br/>
ca..<br/>
dc..<br/>

And complete it:<br/>
abcd<br/>
bdac<br/>
cadb<br/>
dcba<br/>

From this construct the coloring:
abcdxaxcdxxbxxxa

By each prime number a > n (the x values in the coloring), you can choose a color for c(a), but you have to continue with the permutation of that color for c(ma).

Lemma 1 is trivial to prove, because the associative and reflexive conditions makes that reaching a number by different values of a, factoring the number and re-arranging makes that it must have the same value. For the values xy &le; n, you can't factor anymore, and the condition must just met.

I haven't proven lemma 2 fully. A permutation matrix with reflexive and associative conditions, can be constructed by starting with 1 permutation that has a single cycle. The full matrix can be constructed by applying this permutation multiple times, up to n.
It can be proven, that such matrix has the reflexive and associative condition, but not necessary the condition that p(x,y)=p(1,xy) for xy &le; n;

The solution of François as matrix looks like this:<br/>
abcdef<br/>
bdface<br/>
cfbead<br/>
daebfc<br/>
ecafdb<br/>
fedcba<br/>

The permutation from first row to second row is not a permutation with a single cycle. It brings you from row 1, to row 2 to row 4, back to row 1. However, this can still be categorized as 1 cycle permutation, because the permutation from first row to third row, is a permutation with a single cycle.

Instead of looking at the permutation per color, it is better to look which colors are passed, when the permutation is applied multiple times. In above example the cycle is (first row to third row) a->c->b->f->d->e->a. 

If we just make the second row a permutation with one cycle, then the cycle starts with:
1->2->4->8->16->32->64 etc. Then we can add 3 and the other primes.

For n = 27 we can get:<br/>
1->2->4->8->16->3->6->12->24->x->9->18->5->10->20->27->x->15->7->14->11->22->x->21->25->13->26->1

In above sequence, multiplications with 2, have 1 step, multiplication with 3, 5 steps, multiplications with 5 have 12 steps. The remaining primes 17, 19, 23 can be placed on any of the x values. The short parts 11->22 and 13->26 can easily be exchanged. From this cycle, you can make a permutation and permutation matrix that has the condition that p(x,y) = p(1,xy) for xy &le; n. From that permutation the coloring can be constructed.

As you can see, it is not very difficult to construct a coloring this way. But, the sequence is also rather crowded. It is not a prove yet that it is always possible.