From the statement we have
$$\tau(na_{n+1}^n + (n+1)a_n^{n+1}) \vdash n. \qquad (1)$$
Let $a_1 = 1$ and $a_2 = 2$. Suppose that we have constructed the numbers $a_1, a_2, \dots, a_m$ so that they are different natural numbers and (1) satisfied for each $n = 1, 2, \dots, m-1$. Let $L$ be the smallest positive integer that does not occur among the numbers $a_1, a_2, \dots, a_m$. We set $a_{m+2} = L$ and choose $a_{m+1}$ so that $a_{m+1} > a_1 + a_2 + \dots + a_m + L$ and (1) is true for $n = m$ and $n = m+1$. Repeating this process we obtain a permutation of all positive integers satisfying (1) for any positive integer $n$.

For a prime $p$ and a positive integer $k$, we denote by $\psi_p(k)$ the largest integer $l$ such that $k$ is divisible by $p^l$.

Lemma. Given positive integers $a, b, k, l, M$. Then there is a prime number $p > M$ and a positive integer $x$ such that $\psi_p(ax^k + b) = l$.

Proof. Let $d = M + k + b$ and $p$ be a prime divisor of $ab^{k-1}(d!)^k + 1$. Then $p > d > M$. By induction on $N$, we prove that for any positive integer $N$ there exists a positive integer $x$ such that the number $ax^k + b$ is divisible by $p^N$.

Base: for $N = 1$ the number $x = d!b$.

Suppose that for $N$ there exist positive integers $x$ and $t$ such that $ax^k + b = p^N t$. Let $z$ be a positive integer such that the number $ax^{n-1} z k + t$ is divisible by $p$ (such a number exists, since the number $p$ is coprime with $d!a$, and hence with the number $akx$). Then
$$\begin{aligned} a(x + z p^N)^k + b &\equiv a x^k + a x^{k-1} z p^N k + b \equiv p^N t + a x^{k-1} z p^N k \\ &\equiv p^N(a x^{k-1} z k + t) \equiv 0 \pmod{p^{N+1}}, \end{aligned}$$
and the induction step is proved.

Therefore, there are positive integers $x, t$ with $a x^k + b = p^{l+1} t$. Then
$$a(x + p^l)^k + b \equiv a x^k + a x^{k-1} p k + b \equiv a x^{k-1} k p^l \pmod{p^{l+1}},$$
i.e. $\psi_p(a(x + p^l)^k + b) = l$, and the lemma is proved.

From the lemma for $a = m, b = (m+1)a_m^{m+1}, M = 1, k = m, l = m-1$ there is a prime $p > 1$ and a positive integer $x$ such that $\psi_p(m x^m + (m+1)a_m^{m+1}) = m-1$ and from the lemma for $a = m+2, b = (m+1)k^{m+1}, M = p, k = m+2, l = m$ there is a prime $q > p$ and a positive integer $y$ such that $\psi_q((m+1)k^{m+1} + (m+2)y^{m+2}) = m$. By the Chinese remainder theorem, there is a positive integer $z$ such that $z > a_1 + a_2 + \dots + a_m + L, z \equiv x \pmod{p^m}$ and $z \equiv y \pmod{q^{m+1}}$. Then it is easy to see that $a_{m+1} = z$ works.