Let $Log(n) = \sum\_{i=1}^r \alpha\_i \cdot e\_i$, where $n = \prod\_{i=1}^r p\_i^{\alpha\_i}$ and $p\_i$ is the $i$-th prime, $\alpha\_i \ge 0$, $e\_i$ is the $i$-th standard basis vector. For example $6 = 2\cdot3$, hence:
$$Log(6) = (1,1,0,0,0,\cdots)$$
$$Log(15) = (0,1,1,0,0,\cdots)$$
$$Log(7) = (0,0,0,1,0,\cdots)$$
Consider the matrix $A\_n = (Log(1)^T,Log(2)^T,\cdots,Log(n)^T)$. Then one can think about that $rank(A\_n) = \Pi(n)$, where $\Pi$ is the prime counting function. For fun, we might compute the Smith normal form of this matrix:
$$D\_n = U\_n A\_n V\_n$$
I conjecture that $V\_n = 1\_n$ and that $D\_n$ consists of $\Pi(n)$ ones on the diagonal. Now the mysterious part is the irreducible factors of the characteristic polynomial of $U\_n$.


Here is a list for $1 \le n \le 20$ computed with SAGEMATH:



```
1 x - 1
2 x^2 + 1
3 (x - 1) * (x^2 + x + 1)
4 (x - 1)^2 * (x^2 + x + 1)
5 (x - 1) * (x^4 + 1)
6 (x - 1)^2 * (x^4 + 1)
7 (x - 1) * (x^2 + 1) * (x^4 + 1)
8 (x - 1)^2 * (x^2 + 1) * (x^4 + 1)
9 (x - 1)^3 * (x^2 + 1) * (x^4 + 1)
10 (x - 1)^4 * (x^2 + 1) * (x^4 + 1)
11 (x - 1)^5 * (x^2 + 1) * (x^4 + x^3 + x^2 + x + 1)
12 (x - 1)^6 * (x^2 + 1) * (x^4 + x^3 + x^2 + x + 1)
13 (x - 1)^5 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
14 (x - 1)^6 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
15 (x - 1)^7 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
16 (x - 1)^8 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
17 (x - 1)^9 * (x^2 + 1) * (x^2 + x + 1) * (x^4 + x^3 + x^2 + x + 1)
18 (x - 1)^10 * (x^2 + 1) * (x^2 + x + 1) * (x^4 + x^3 + x^2 + x + 1)
19 (x - 1)^9 * (x^2 + x + 1) * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
20 (x - 1)^10 * (x^2 + x + 1) * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)

```

It occurs that the irreducible factors are cyclotomic polynomials $p(x)$ with $\deg(p(x))=\phi(m)$ for some number $m$.
But how does one compute the numbers $m$, given $n$?
I think this would give an interesting decomposition of $n$ in summands and products.


For example:
$$ 13 = 5\cdot\phi(1)+2\phi(4)+1\phi(5)$$
$$ 5 = 1\cdot\phi(1) + 1\cdot \phi(8)$$


I have tried to search OEIS for various related sequences but without success.


Thanks for you help.


**Edit**:
Here is some sage code, to get the matrix $U\_5,\cdots,U\_{10}$ and the corresponding matrices.



```
MAXN=100

def Log(a,N=MAXN):
    return vector([valuation(a,p) for p in primes(N)])

def Exp(v,N=MAXN):
    P = list(primes(N))
    return prod([P[i]**v[i] for i in range(len(P))])


def AA(n,N=MAXN):
    return matrix([Log(n,N=N) for n in range(1,n+1)],ring=QQ)


def UU(n,N=MAXN):
    D,U,V = (AA(n,N=N)).smith_form()
    return U


[ 0  1  0  0  0]
[ 0  0  1  0  0]
[ 0  0  0  0  1]
[ 0 -2  0  1  0]
[-1  0  0  0  0]
[ 0  1  0  0  0  0]
[ 0  0  1  0  0  0]
[ 0  0  0  0  1  0]
[ 0 -2  0  1  0  0]
[-1  0  0  0  0  0]
[ 0 -1 -1  0  0  1]
[ 0  1  0  0  0  0  0]
[ 0  0  1  0  0  0  0]
[ 0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  1]
[-1  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0]
[ 0  2  0 -1  0  0  0]
[ 0  1  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0]
[ 0  0  0  0  0  0  1  0]
[-1  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0]
[ 0  2  0 -1  0  0  0  0]
[ 0 -3  0  0  0  0  0  1]
[ 0  1  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0]
[-1  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0  0]
[ 0  2  0 -1  0  0  0  0  0]
[ 0 -3  0  0  0  0  0  1  0]
[ 0  0 -2  0  0  0  0  0  1]
[ 0  1  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0]
[-1  0  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0  0  0]
[ 0  2  0 -1  0  0  0  0  0  0]
[ 0 -3  0  0  0  0  0  1  0  0]
[ 0  0 -2  0  0  0  0  0  1  0]
[ 0 -1  0  0 -1  0  0  0  0  1]

```

**Update**:
Here are the matrices and corresponding characteristic polynomials for $n=23,29,31$:



```
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 0 -1  0  0 -1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
23 (x - 1)^11 * (x^2 + x + 1) * (x^2 + 1)^3 * (x^4 + x^3 + x^2 + x + 1)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -3 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  0 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0 -2  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
[ 0  1  0  0  1  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
29 (x - 1)^15 * (x^2 + x + 1) * (x^2 + 1)^4 * (x^4 + x^3 + x^2 + x + 1)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -3 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0 -2  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  1  0  0  1  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
[-1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
31 (x - 1)^15 * (x^2 + x + 1) * (x^2 + 1)^5 * (x^4 - x^2 + 1)

```

**Update to the answer given by Denis Serre**:
I can not see how, $D\_4 = U\_1 \cdot A\_4$ or $D\_4 = U\_2 \cdot A\_4$:



```
sage: AA(4)
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: U1
[0 1 0 0]
[0 0 1 0]
[1 0 0 0]
[0 0 0 1]
sage: U2
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 0 0 0]
sage: U1*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: U2*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: UU(4)*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

```


Is there a pattern for the irreducible factors and degrees of a characteristic polynomial?
I made hand calculations for $n\le4$. It turns out that even with $V\_n=1\_n$, the factor $U\_n$ is not unique. In other words, the factorisation problem is underdetermined. This is due to the fact that the few last columns of $A\_n$ vanish. For instance, if $n=3$, the general $U\_3$ is
$$\begin{pmatrix} a & 1 & 0 \\ b & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.$$
Therefore the characteristic polynomial can be any of the polynomials $X^3-aX^2-bX-1$. You may prefer to select the "simplest" matrix $U\_n$, which gives you here the polynomial $X^3-1$, but how will you proceed for higher values of $n$ ? 


**Edit** (after miscalculation in my original answer.) The case $n=4$ yields even more freedom. You may choose the matrices
$$U\_4=\begin{pmatrix} a & 1 & 0 & 0 \\ b & 0 & 1 & 0 \\ c & -2 & 0 & 1 \\ -1 & 0 & 0 & 0 \end{pmatrix}$$
and even this list is incomplete. What is the simplest among them ? At least the second and third columns are mandatory. The corresponding characteristic polynomial $X^4-aX^3+(2-b)X^2-(2a+c)X+1$ can be any polynomial $X^4+\cdots+1$ with integer coefficients.


