Proposed by Arsenii Nikolaiev, Anton Trygub, Oleksii Masalitin, and me.

The problem for primes $n=p$ appears as Poland 2020 2nd round P5 here (not the same, but very similar): https://artofproblemsolving.com/community/c6h2003397p14012890

oVlad wrote: Determine all integers $n\geqslant 2$ with the following property: every $n$ pairwise distinct integers whose sum is not divisible by $n$ can be arranged in some order $a_1,a_2,\ldots, a_n$ so that $n$ divides $1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n.$ Arsenii Nikolaiev, Anton Trygub, Oleksii Masalitin, and Fedir Yudin

EDIT: this seems to conflict with the above answer, so I'm not 100% sure if this is right. I might have messed up the swapping to prove the odd numbers and powers of $2$ work but I'm pretty sure that the proof that nothing else works is solid (take $n = 6$ for instance). EDIT 2: I just checked with the packet, and I believe my answer is right (not 100% sure about my solution) I claim that the answer is all odd numbers and all powers of $2$ (which are greater than or equal to $2$). First of all, we can drop the pairwise distinct condition since we can replace $a$ with $a+kn$ for some integer $k$ to get that $a$ and $a+kn$ modulo $n$ are the same but the numbers themselves are different, and since the only relevant thing here are the numbers modulo $n$, we think of $a$ and $a+kn$ as the same object, hence the distinctness does not matter. Showing that nothing else works: We will show all even numbers which are not powers of $2$ do not work (which is equivalent since if an integer greater than or equal to $2$ is not odd or a power of $2$ then it must be even and not a power of $2$). Assume for the sake of contradiction that all powers of $2$ worked. Write $n = 2^k(2t+1)$ for some positive integers $k, t$ and take $\{a_1, a_2, \cdots, a_n\} = \{1+2^k, 1, 1, \cdots, 1\}$. $a_1 + a_2 + \cdots + a_n = n + 2^k$, which cannot be divisible by $n = 2^k(2t+1)$ since it would require $2t+1\mid 1$, absurd. So the first condition is satisfied. Then, say $a_i = 2^k + 1$ for some $1\leq i\leq n$. Then, $$1a_1 + 2a_2 + \cdots + na_n = 1 + 2 + \cdots + (i-1) + i(2^k+1) + (i+1) + \cdots + n = 2^ki + (1 + 2 + \cdots + n) = 2^ki + \frac{n(n+1)}{2} = 2^ki + \frac{(2^k(2t+1))(2^k(2t+1) + 1)}{2} = 2^{k-1}(2i + (2t+1)(2^k(2t+1) + 1)).$$The term in the parenthesis is odd since $2i$ is even and $(2t+1)(2^k(2t+1) + 1)$ is odd, so this is $2^{k-1}\pmod{2^k}$ for every $i$, and so it cannot be divisible by $2^k(2t+1)$ since it would at least have to be divisible by $2^k$, and since every permutation of $\{1+2^k, 1, 1, \cdots, 1\}$ has $a_i = 2^k + 1$ for some $1\leq i\leq n$ and $a_j = 1$ for all other $1\leq j\leq n$ with $j\neq i$, it follows that there does not exist such a rearrangement $a_1, a_2, \cdots, a_n$, a contradiction. Now, we will prove a crucial claim. Claim: Suppose the numbers are $x_1, x_2, \cdots, x_n$. Then, letting $g = \gcd\left(\sum_{i=1}^{n}x_i, n\right)$, it suffices to show that there exists a permutation $y_i$ of the $x_i$ such that $g \mid \sum_{i=1}^{n}iy_i$. Proof: It is possible that $g = 1$, but since $1$ divides any integer, $g=1$ works. So assume $g > 1$. Suppose that $\sum_{i=1}^{n}iy_i = g\ell$ for some integer $\ell$. Then, the key thing to note is that $$\sum_{i=1}^{n}iy_i - \sum_{i=1}^{n}y_i \equiv \sum_{i=1}^{n}(i-1)y_i\equiv ny_1 + 1y_2 + 2y_3 + \cdots + (n-1)y_n\pmod{n},$$which is in fact $\sum_{i=1}^{n}iy_{i+1}$, where indices are taken modulo $n$. Therefore, we see that subtracting $\sum_{i=1}^{n}y_i$ gives a new permutation that sums to $\sum_{i=1}^{n}iy_i - \sum_{i=1}^{n}y_i$ modulo $n$, so if $\sum_{i=1}^{n}y_i = gk$ for some integer $k$ (such an integer $k$ exists by the definition of $g$), doing this $r$ times gives a permutation $p_i$ of $x_i$ such that $$\sum_{i=1}^{n}ip_i \equiv g\ell - (gk)r \equiv g(\ell - kr)\pmod{n}.$$Now, since $k = \frac{\sum_{i=1}^{n}y_i}{g} = \frac{\sum_{i=1}^{n}x_i}{g}$, we have that $\gcd\left(k, \frac{n}{g}\right) = 1$, so letting $r \equiv \ell\cdot k^{-1}\pmod{\frac{n}{g}}$ gives $$\ell - kr \equiv \ell - \ell \equiv 0\pmod{\frac{n}{g}},$$so $$g(\ell-kr)\equiv 0\pmod{n},$$so we have a permutation $p_i$ such that $\sum_{i=1}^{n}ip_i \equiv 0\pmod{n},$ as wanted. Proof that all powers of $2$ (greater than or equal to $2$) work: Let $n = 2^k$. We strong induct on $k$, with base case $k = 1$, which is relatively clear since if the numbers are $x, y$ we have $2\nmid x+y$, so $(x, y)\in \{(1, 0), (0, 1)\}\pmod{2}.$ WLOG say $(x, y) \equiv (1, 0)\pmod{2}$. Then, $2x+y \equiv 0\pmod{2}$, as desired. Now assume $1\leq s\leq k$ work for some integer $k\geq 1$. We will show $k+1$ works. Let $a_1, a_2, \cdots, a_{2^{k+1}}$ be integers with $2^{k+1}\nmid a_1 + a_2 + \cdots + a_{2^{k+1}}.$ Then, by the claim, it suffices to show that if $g = \gcd\left(\sum_{i=1}^{2^{k+1}}a_i, 2^{k+1}\right)$, then $g\mid \sum_{i=1}^{2^{k+1}}ib_i$ for some permutation $b_i$ of the $a_i$. Since $g \mid 2^{k+1}$, $g = 2^{\ell}$ for some nonnegative integer $\ell$. Then, if $\ell < k$, then $2^{\ell+1} \nmid \sum_{i=1}^{2^{k+1}}a_i$, and since $\ell + 1 < k+1$, by the inductive hypothesis there exists such a permutation $b_i$ such that $2^{\ell+1}\mid \sum_{i=1}^{2^{k+1}}ib_i$, and so $2^{\ell}\mid \sum_{i=1}^{2^{k+1}}ib_i$, so we are done in that case. Else, $\ell = k$ ($\ell \neq k+1$ since $g < n$ by the first condition). Partition the $a_i$'s into multisets $A$ and $B$ such that $A = \{a_1, a_2, \cdots, a_{2^k}\}$ and $B = \{a_{2^k+1}, a_{2^k+2}, \cdots, a_{2^{k+1}}\}$. Then, if $2^k\nmid \sum_{a\in A}a_a, \sum_{b\in B}a_b$, then we are done by the inductive hypothesis applied to $A$ and $B$ (we can find such a permutation of the $a_i$ in $A$ and a permutation of the $a_i$ in $B$, so just concatenate them). Else, we have a few cases. If the sum of the elements in $A$ is divisible by $2^k$, then since the sum of all the $a_i$'s is divisible by $2^k$, so is the sum of all elements in $B$. If all the $a_i$'s are the same modulo $2^k$, then the sum of the elements is just $2^ka_1$, which is divisible by $2^k$. Else, the set of all distinct values the $a_i$'s take on modulo $2^k$ is at least $2$, so let $a\neq b$ be two elements of this set, and permute the $a_i$'s so the $a_1 = a$ and $a_{2^k+1} = b$ (I should say "make a new permutation $c_i$" or something, but especially when I prove that all odd numbers greater than or equal to $2$ work, I will probably run out of variable names (or at least meaningful ones) and/or lose track of them). Then, if the sum of all elements in $A$ is not divisible by $2^k$, then neither is the sum of elements of $B$ (since the sum of the $a_i$'s is divisible by $2^k$), so just apply the inductive hypothesis to $A$ and $B$. Else, swap $a_1$ and $a_{2^k+1}$. Then, the sum of the elements in $A$ is $b-a\pmod{2^k}$ and the sum of all elements in $B$ is $a-b\pmod{2^k}$ (since the sum of all elements in $B$ is divisible by $2^k$), none of which are zero modulo $2^k$, so we can apply the inductive hypothesis to $A$ and $B$, so we're done in all cases, so our inductive step is complete and so all powers of $2$ greater than or equal to $2$ work, as desired. Proof that all odd numbers (greater than or equal to $2$) work:We will use strong induction again. We will induct on the restated statement (the one in the claim), which in turn will imply the conclusion (for $n\geq 2$ odd). The idea is that we reduce the case from $n$ to a divisor of $n$. Our base case is $n = 1$, which is true since $\gcd(x_1, 1)\mid x_1$. Now assume $n = 2t-1$ works for all $1\leq t\leq k$ for some integer $k\geq 2$. We will show that $n = 2k+1$ works. We wish to show that if $x_1, x_2, \cdots, x_{2k+1}$ are integers with $2k+1\nmid x_1 + x_2 + \cdots + x_{2k+1}$, then if $g = \gcd\left(\sum_{i=1}^{2k+1}x_i, 2k+1\right)$, there exists a permutation $y_i$ of the $x_i$ such that $g\mid \sum_{i=1}^{2k+1}iy_i$. If $g = 1$, then we are done, so assume $g > 1$. Partition the multiset $\{x_1, x_2, \cdots, x_{2k+1}\}$ into the disjoint union of multisets $A_1\cup A_2\cup \cdots \cup A_{\frac{2k+1}{g}}$, where $A_i := \{x_j | g(i-1) + 1 \leq j \leq gi\}.$ ($A_i$ is a multiset, not a set). If the sum of all elements in $A_1$ is not divisible by $g$, then by the inductive hypothesis we can permute the elements in $A_1$ such that $\sum_{a_1\in A_1}a_1x_{a_1} \equiv 0\pmod{g}.$ Else, if all the elements in $A_1$ are equal to a common value $a$, then $$\sum_{a_1\in A_1}a_1x_{a_1} \equiv a\sum_{a_1\in A_1}a_1 \equiv a(1 + 2 + \cdots + g)\equiv a\cdot \frac{g+1}{2}\cdot g\equiv 0\pmod{g},$$as $g$ is odd. Else, then the number of distinct elements (modulo $g$) in $A_1$ is at least $2$, so let $a, b$ be two distinct elements in $A_1$. Permute $A_1$ such that $x_1 = a$ and $x_2 = b$. Then, the sum of the elements in $A_1$ is still divisible by $g$ since permuting them leaves the sum invariant. Furthermore, there exists a $x$ in $\{x_1, x_2, \cdots, x_{2k+1}\}\setminus A_1$ not equal to at least one of $a, b$ modulo $g$. If it is not equal to $a$, then swapping $x$ and $a$ gives that the sum of the elements in $A_1$ is $x-a\not \equiv 0\pmod{g}$ since the sum of the elements in $A_1$ was previously $0$ modulo $g$. If it is not equal to $b$, swap $x_1 = a$ and $x_2 = b$ and apply the same argument. By the inductive hypothesis, we can permute the $x_i$ such that $\sum_{a_1\in A_1}a_1x_{a_1}\equiv 0\pmod{g}$. Now, applying this argument to all $A_1, A_2, \cdots, A_{\frac{2k+1}{g} - 2}$ (the only major difference is we pick an $x$ in $\{x_1, x_2, \cdots, x_{2k+1}\} \setminus (A_1 \cup A_2 \cup \cdots \cup A_i)$ instead of $\{x_1, \cdots, x_{2k+1}\}\setminus A_i$) gives that $\sum_{a_i\in A_i}a_ix_{a_i}\equiv 0\pmod{g}$ for all $1\leq i\leq \frac{2k+1}{g} - 2$ (If $\frac{2k+1}{g} = 2$, then ignore what we just did. It cannot be less than $2$ though since by the problem statement, $g < 2k+1$.) Then, there consider $A_{\frac{2k+1}{g} - 1}$ and $A_{\frac{2k+1}{g}}$. If their union has only one distinct element modulo $g$, then by our previous work this means $\sum_{a_i\in A_i}a_ix_{a_i}\equiv 0\pmod{g}$ for all $i$, so adding up yields the result. If the sum of the entries in the $A_i$'s (from here on out, "the $A_i$'s" are referring to $A_{\frac{2k+1}{g} - 1}$ and $A_{\frac{2k+1}{g}}$) are both nonzero modulo $g$, then apply the inductive hypothesis and add up again. Else, at least one of the entries has sum zero modulo $g$ and there is at least $2$ distinct values modulo $g$ of all the elements of $A_{\frac{2k+1}{g} - 1}$ and $A_{\frac{2k+1}{g}}$. If there are at least $3$ distinct values, let $3$ of them be $a, b, c$ (all pairwise distinct modulo $g$). Then, permute the $x_i$ so that $x_{n-2g+1} \equiv a\pmod{g}$, $x_{n-g+1}\equiv b\pmod{g}$, $x_{n-g+2}\equiv c\pmod{g}$. If the sum of the values in each $A_i$'s are nonzero modulo $g$, then as previously discussed we are done by the inductive hypothesis. Else, at least one of the sums are nonzero modulo $g$. WLOG say $A_{\frac{2k+1}{g} - 1}$ is nonzero modulo $g$, else just swap $x_{n-g+2}$ and $x_{n-2g+2}$ and apply the same argument that we are about to perform. Then, if we swap $a$ and $b$ ($x_{n-2g+1}$ and $x_{n-g+1}$), we get that the sum of the values in $A_{\frac{2k+1}{g} - 1}$ is $b-a\not \equiv 0\pmod{g}$. If the sum of the values in $A_{\frac{2k+1}{g}}$ is zero modulo $g$, then swap $a$ and $c$ ($x_{n-2g+1}$ and $x_{n-g+2}$) instead since the sum of the values in $A_{\frac{2k+1}{g} - 1}$ would be $c-a\not \equiv 0\pmod{g}$ and the sum of the values in $A_{\frac{2k+1}{g}}$ would be $c-b\not \equiv 0\pmod{g}$, so the sum of the values in each of the $A_i$'s is nonzero modulo $g$, so if we apply the inductive hypothesis we are done. Else, there are exactly $2$ distinct values in the $A_i$'s, say $a$ and $b$. If there are an even number of $a$'s, say $2t$ $a's$, then permute the $x_i$ so that $x_{n-2g+1} = x_{n-2g+2} = \cdots = x_{n-2g+t} = x_{n-g+1} = x_{n-g+2} = \cdots = x_{n-g+t} = a$ (modulo $g$) and everything else is $b$. Then, if the sum of the values in each of the $A_i$'s are nonzero modulo $g$, then if we apply the inductive hypothesis we are done. Since the values are the same in each of the $A_i$'s, if one of the sums is zero modulo $g$ then so is the other. Now, If $t = g-1$, then swap $x_{n-g-1}$ with $x_{n-g}$ and $x_{n-1}$ with $x_n$. Then, swap $x_{n-2g+1}$ with $x_{n-1}$. The first one is $a$ and the second one is $b$, so the sum of all entries in $A_{\frac{2k+1}{g} - 1}$ is now $b-a\not \equiv 0\pmod{g}$ and the sum of all entries in $A_{\frac{2k+1}{g}}$ is the same thing since it is in the $g-1$th spot, so to speak (since $n-1\equiv g-1\pmod{g}$), so the sum is $-(a-b)\equiv b-a\pmod{g}.$ Thus, the sum of the entries in both of the $A_i$'s are nonzero modulo $g$, so by the inductive hypothesis we are done as discussed earlier. Else, the number of $a$'s are odd, so let this number be $2t+1$. Then, WLOG the sum of the entries in $A_{\frac{2k+1}{g} - 1}$ is zero modulo $g$ (since the rows are symmetric. If both rows sum to nonzero stuff modulo $g$, then we are done by the inductive hypothesis). Then, permute the $x_i$ so that $x_{n-2g+1} = x_{n-2g+2} = \cdots = x_{n-2g+(t+1)} = x_{n-g+2} = x_{n-g+3} = \cdots = x_{n-g + (t+1)} = a$ modulo $g$, and the rest $b$ modulo $g$. If $t = n-1$, then $\sum_{a\in A_{\frac{2k+1}{g} - 1}}ax_a$ is $0\pmod{g}$ and we can move the unitary $b$ to the $x_{n-g+1}$th position to get that the sum of the elements in $A_{\frac{2k+1}{g}}$ is nonzero modulo $g$, so we are done by the inductive hypothesis. Else, $t < n-1$ and so $x_{n-g} = b$. Then, swapping $x_{n-2g+1}$ and $x_{n-g+1}$ gives that the sum of the elements in $A_{\frac{2k+1}{g} - 1}$ is nonzero modulo $g$ ($(b-a)\pmod{g}$). If the sum of the elements in $A_{\frac{2k+1}{g}}$ is nonzero modulo $g$ as well, then we are done by the inductive hypothesis. Else, we can swap $x_{n-g}$ and $x_{n-g+1}$, which leaves the sum of the elements in $A_{\frac{2k+1}{g}-1}$ invariant modulo $g$, and makes the sum of the elements in $A_{\frac{2k+1}{g}}$ $b-a\not \equiv 0\pmod{g}$, so we are done by the inductive hypothesis, so we've exhausted all cases and we're done.

pi_quadrat_sechstel wrote: oVlad wrote: Determine all integers $n\geqslant 2$ with the following property: every $n$ pairwise distinct integers whose sum is not divisible by $n$ can be arranged in some order $a_1,a_2,\ldots, a_n$ so that $n$ divides $1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n.$ Arsenii Nikolaiev, Anton Trygub, Oleksii Masalitin, and Fedir Yudin We will prove a stronger claim by induction: For $n\geq2$ and integers $d,a_1,a_2,\ldots,a_n$ with $n\nmid a_1+a_2+\ldots+a_n$ we can arrange $a_1,a_2,\ldots,a_n$ in some order so that $a_1+2a_2+3a_3+\ldots+na_n\equiv d\pmod{n}$. If $n=p$ for a prime $p$ then $a_1+2a_2+3a_3+\ldots+pa_p,a_p+2a_1+3a_2+\ldots+pa_{p-1},a_{p-1}+2a_p+3a_1+\ldots+pa_{p-2},\ldots,a_2+2a_3+3a_4+\ldots+pa_1$ is an arithmetic progression $\pmod{p}$ with length $p$ and difference $a_1+a_2+\ldots+a_p\pmod{p}$. Since $p\nmid a_1+a_2+\ldots+a_p\pmod{p}$ the arithmetic progression is surjective $\mod{p}$. If $n$ is not a prime let $n=mp$ for a prime $p$. Note that \begin{align*} a_1+2a_2+3a_3+\ldots+na_n=(a_1+2a_2+\ldots+ma_m)+(a_{m+1}+2a_{m+2}+\ldots+ma_{2m})+\ldots+(a_{(p-1)m+1}+2a_{(p-1)m+2}+\ldots+ma_{pm})\\ +m[(a_{m+1}+a_{m+2}+\ldots+a_{2m})+2(a_{2m+1}+a_{2m+2}+\ldots+a_{3m})+3(a_{3m+1}+a_{3m+2}+\ldots+a_{4m})+\ldots+(p-1)(a_{(p-1)m+1}+a_{(p-1)m+2}+\ldots+a_{pm})] \end{align*}Since $n\mid a_1+a_2+\ldots+a_n$ at least one of $a_1+a_2+\ldots+a_m,a_{m+1}+a_{m+2}+\ldots+a_{2m},\ldots,a_{(p-1)m+1}+a_{(p-1)m+2}+\ldots+a_{pm}$ is not divisible by $m$. W.l.o.g. $a_1+a_2+\ldots+a_m$. Reorder $a_1,a_2,\ldots,a_m$ so that \[ (a_1+2a_2+\ldots+ma_m)+(a_{m+1}+2a_{m+2}+\ldots+ma_{2m})+\ldots+(a_{(p-1)m+1}+2a_{(p-1)m+2}+\ldots+ma_{pm})\equiv d\pmod{m} \]Now reorder $(a_1,a_2,\ldots,a_m),(a_{m+1},a_{m+2},\ldots,a_{2m}),\ldots,(a_{(p-1)m+1},a_{(p-1)m+2},\ldots,a_{pm})$ so that \begin{align*} (a_{m+1}+a_{m+2}+\ldots+a_{2m})+2(a_{2m+1}+a_{2m+2}+\ldots+a_{3m})+3(a_{3m+1}+a_{3m+2}+\ldots+a_{4m})+\ldots+(p-1)(a_{(p-1)m+1}+a_{(p-1)m+2}+\ldots+a_{pm})\\ \equiv-\frac{1}{m}[(a_1+2a_2+\ldots+ma_m)+(a_{m+1}+2a_{m+2}+\ldots+ma_{2m})+\ldots+(a_{(p-1)m+1}+2a_{(p-1)m+2}+\ldots+ma_{pm})-d]\pmod{p} \end{align*}implying \begin{align*} a_1+2a_2+3a_3+\ldots+na_n\equiv d\pmod{n} \end{align*} I think your solution doesn't handle the case where $n$ is a power of a prime.

The answer is $n$ odd or a power of two. Note that we can easily ignore the pairwise distinct condition by working modulo $n$. For the working $n$, we will additionally prove the following generalization: let $m=\gcd(n,a_1+\cdots+a_n)$. Then we can make $S:=1\cdot a_1+\cdots+n\cdot a_n$ equal to any multiple of $m$ modulo $n$. First we prove that even $n$ that aren't powers of two fail. Let $n=2^ka$ where $a$ is odd, and pick $\{a_1,\ldots,a_n\}=\{2^k+1,1,1,\ldots,1\}$. Then modulo $2^k$, $S \equiv 2^k(2^k+1)/2 \equiv 2^{k-1} \not \equiv 0 \pmod{2^k}$, so $n$ cannot divide $S$. For the case of $n=p^k$, if all the $n$ numbers are congruent modulo $p$ (not $p^k$), combine then into groups of size $p$ arbitrarily. Then, divide these groups by $p$, and induct down to the $k-1$ case (the base case of $p=1$ is vacuous), considering the $p^{k-1}$ groups as the new numbers. If $\nu_p(\text{original number sum})=v<k$, then $\nu_p(\text{new number sum})=v-1$ and thus for the $k-1$ case we can make $S$ into any multiple of $p^{v-1}$ modulo $p^{k-1}$. When we return to the original case of $k$, fix an ordering of the numbers in a group to $a_i,a_{i+p^{k-1}},a_{i+2p^{k-1}},\ldots$ regardless of what $i \leq p^{k-1}$ actually is—that is, no matter what our assignment of the groups to $a_1,\ldots,a_{p^{k-1}}$ was for the inductive hypothesis, the group assigned to $a_i$ "expands" consistently, for each $i$ independently. Therefore, the "expansion" changes $S$ by some fixed multiple of $p^{k-1}$. Therefore, since we also have to multiply everything by $p$, we can get $S$ to equal any multiple of $p^v$ modulo $p^k$. (Note: this section is mostly unnecessary, although we use the same ideas later, if we start the below section at higher powers of $p$ I think it works, except when $p=2$ since in that case we won't have $p^k \mid 1+\cdots+p^k$, so I think this section is useful anyways) Thus assume that they're not all congruent modulo $p$. By expectation we can find some modulo-$p$ residue class $c_1$ which contains at least $p^{k-1}$ of the numbers, as well as some number $a$ not in this residue. Then temporarily assign $p^{k-1}$ of these numbers to $a_1,\ldots,a_{p^{k-1}}$, with the specific positions to be assigned later, and also temporarily assign $a$ to $a_n$. Consider what happens when we swap $a_n$ and $a_1$, $a_n$ and $a_2$, and so on. Modulo $p$, $S$ changes by $a-c_1$, $2(a-c_1)$, and so on, so we can find some $i \leq p$ such that swapping $a_n$ with $a_i$ makes $S$ divisible by $p$. Now, by expectation again, we can find some modulo-$p^2$ residue class $c_2$ with $c_2 \equiv c_1 \pmod{p}$ which contains at least $p^{k-2}$ of the numbers. Then shuffle $a_1,\ldots,a_{p^{k-1}}$ such that every term of the form $a_{i+pm}$ is in the residue class $c_2$, which preserves $p \mid S$, and consider what happens when we swap $a_n$ with $a_i,a_{i+p},\ldots$ to get that some choice of $j<p$ will give us $p^2 \mid S$ upon swapping $a_n$ with $a_{i+pj}$. Repeating this process for $p^3$, etc., we get that we can find some assignment such that $p^{k-1} \mid S$. Finally, consider what happens when we "rotate" the assignments, so $a_1$ becomes what was previously $a_2$ and similar. It is clear that $S$ increases by $a_1+\cdots+a_n$, which can't be divisible by $p^k$, so by repeating this rotation a suitable number of times we can go from $p^{k-1} \mid S$ to $S$ hitting every multiple of $p^{\nu_p(\text{number sum})}$ modulo $p^k$, as desired. Now we extend from prime powers to composite numbers by induction, with the base cases being prime powers. For some odd composite number $n$, pick a prime $p \mid n$ which is not the only prime such that $v=\nu_p(\text{number sum})<\nu_p(n)$ and let $p^k$ be the maximal prime power dividing it. Similar to before, let $m=\gcd(n/p^k,a_1+\cdots+a_n)$ and combine elements into groups of size $p^k$ arbitrarily. By inductive hypothesis on $n/p^k$, with groups serving as the new numbers, we can get $S$ to be any multiple of $m$. Now similarly "expand" each group corresponding to $a_i$ in the arrangement for $n/p^k$ ($i \leq n/p^k$) to $a_i,a_{i+n/p^k},a_{i+2n/p^k},\ldots$, which preserves the value of $S$ modulo $n/p^k$. Pick some $i$ such that $a_i+a_{i+n/p^k}+\cdots+a_{i+(p^k-1)n/p^k}$ isn't divisible by $p^{v+1}$ (this exists, else the number sum is divisible by $p^{v+1}$). For every $j \neq i$, biject $j,j+n/p^k,j+2n/p^k,\ldots$ to $1,\ldots,p^k$, and therefore by inductive hypothesis rearrange $a_j,a_{j+n/p^k},a_{j+2n/p^k}$ such that $j\cdot a_j+\cdots$ is divisible by $p^k$. These rearrangements clearly preserve $S \pmod{n/p^k}$. Finally, by inductive hypothesis again we may rearrange $a_i,a_{i+n/p^k},a_{i+2n/p^k},\ldots$ such that $S$ hits every multiple of $p^v$ modulo $p^k$, so by the Chinese remainder theorem we can get $S$ to be any multiple of $mp^v$, which is simply $\gcd(n,a_1+\cdots+a_n)$, and we're done. $\blacksquare$

We will first show that if $n$ is odd or is a power of $2$, then $n$ works. Let the numbers be $a_1,a_2,\dots, a_n$. Let $$\mathcal{S}=\{x | x \in \mathbb{Z}/n\mathbb{Z} \text{ such that there exists a permutation } \pi[n] \text{ with } x \equiv \sum_{i=1}^{n} i\cdot a_{\pi(i)}\pmod n \}$$We intend to show that $0 \in \mathcal{S}$, which we will prove by strong induction on $\omega(n)$. Let $m=\gcd(n, a_1+\dots+a_n)$. Note that $m\mid n$, and $m<n$ since $n \nmid a_1+a_2+\dots+a_n$. Claim 1: Suppose $x\in \mathcal{S}$, and $x' \in \mathbb{Z}/n\mathbb{Z}$ such that $x'\equiv x+m\cdot k \pmod n$ for some $k \in \mathbb{Z}$, then $x'\in \mathcal{S}$. Proof: Let $x \equiv \sum_{i=1}^{n} i\cdot a_{\pi(i)} \pmod n$, then consider the permutation $\pi'$ obtained by cyclically shifting $\pi$ such that $\pi'(i) = \pi(i-k)$. Then $\sum_{i=1}^{n}i \cdot a_{\pi'(i)} = \sum_{i=1}^{n}(i+k)\cdot a_{\pi(i)}\equiv x + k\cdot \sum_{i=1}^{n}a_i \pmod n$. But on varying $k$ over $\mathbb{Z}$, $x + k\cdot \sum_{i=1}^{n}a_i$ takes all values of the form $x + k\cdot m$ over $\mathbb{Z}/n\mathbb{Z}$. By the existence of permutation $\pi'$, the claim is proven. $\blacksquare$ For base case of the strong induction, consider $\omega(n)=1$ that is, $n$ is a prime : Since $m=1$, it follows from Claim 1 that $0 \in \mathcal{S}$. Claim 2 : There exists $x \in \mathcal{S}$ such that $m \mid x$. Proof : We now split into two cases depending on whether we can pick $m$ numbers among the $a_i$'s whose sum is not divisible by $m$. Suppose we can pick and WLOG $m \nmid a_1+a_2 + \dots +a_m$. Hence by Induction hypothesis on $m$, we can find a permutation $\pi[m]$ such that $m \mid \sum_{i=1}^{m} i\cdot a_{\pi(i)}$. Now we will deal with the rest numbers. As $m \mid a_1 + a_2 + \dots + a_n$ it follows that $m \nmid a_{m+1} + a_{m+2} + \dots+ a_n$. For $1\leqslant i \leqslant m$, define $b_i = a_{m+i} + a_{2m+i} + \dots + a_{n-m+i}=\sum_{t=1}^{\frac{n-m}{m}} a_{tm+i}$. We have $m \nmid b_1 + b_2 + \dots + b_m=a_{m+1} + a_{m+2} + \dots + a_n$. Hence by Inductive hypothesis on $m$ we can find a permutation $\pi'[m]$ such that $m \mid \sum_{i=1}^{m} i\cdot b_{\pi'(i)}$. We extend the permutation $\pi$(which was earlier on $[m]$) by defining $\pi(tm+i) = tm+\pi'(i)$ for $1 \leqslant t \leqslant \frac{n-m}{m}$ and $1 \leqslant i \leqslant m$. Notice modulo $m$, $0 \equiv \sum_{i=1}^{m} i\cdot b_{\pi'(i)} =\sum_{i=1}^{m}\sum_{t=1}^{\frac{n-m}{m}} i\cdot a_{tm + \pi'(i)} \equiv \sum_{i=1}^{m} \sum_{t=1}^{\frac{n-m}{m}} (tm + i)\cdot a_{tm+\pi'(i)}= \sum_{j=m+1}^{n} j \cdot a_{\pi(j)} \pmod m$ Hence for the permutation $\pi[n]$ we can infer that $$ \sum_{i=1}^{n} i\cdot a_{\pi(i)} = \sum_{i=1}^{m} i\cdot a_{\pi(i)} + \sum_{j=m+1}^{n} j \cdot a_{\pi(j)} \equiv 0 + 0 \pmod m$$ Suppose we can't pick $m$ such numbers and hence, $m$ divides sum of any $m$ numbers among the $a_i$'s. It follows that $a_1 \equiv a_2 \equiv \dots \equiv a_n \pmod m$. Suppose the common value is $c \pmod m$. We first observe that $\frac{n}{2} \equiv 0 \pmod m$. This is because if $n$ is odd, then $m \mid n$. And if $n=2^t$, we have $m \mid n = 2^t$ and $m<n$ together imply $m \mid 2^{t-1} =\frac{n}{2}$. Hence, $$\sum_{i=1}^{n} i\cdot a_i \equiv c \cdot \sum_{i=1}^{n} i = c\cdot \frac{n(n+1)}{2} \equiv 0 \pmod m$$ In both of the cases, we have shown that $m \mid \sum_{i=1}^{n} i\cdot a_{\pi(i)}$ for some permutation $\pi[n]$. Since $m \mid n$, Claim 2 is proven. $\blacksquare$ From Claim 1 and Claim 2, we can infer that $0 \in \mathcal{S}$. Hence we are done! We are left with $n=2^t\cdot a$ where $a$ is odd, $a>1$ and $t\geqslant 1$. We will show that these $n$ fail. Just take the numbers to be $\underbrace{1,1,\dots,1}_{n-1},2^t+1$. Note that $a$ doesn't divide sum of these numbers, and hence $n$ doesn't divide as well. Since all the numbers are $1$ mod $2^t$, for any permutation $\pi[n]$, $\sum_{i=1}^{n} i\cdot a_{\pi(i)} \equiv \sum_{i=1}^{n} i \not\equiv 0 \pmod {2^t}$, which shows that these $n$ fail.

The answer is odd numbers and powers of $2$ only. First, remove the ``pairwise distinct" condition as we can add appropriate multiples of $n$ to each number so that pairwise distinctness is satisfied. Proof that all other numbers fail: Let all $a_i=1$. Then \[ n \mid 1 \cdot 1 +2 \cdot 1 + \dots + n \cdot 1 = \frac{n(n+1)}{2}, \]which implies $n$ odd, a contradiction. Proof that claimed solution set works: Let $X$ be any set of $n$ positive integers whose sum is not divisible by $n$, and denote $S$ by the sum of the numbers in $X$. Realize that given any ordering of the number, taking a cyclic shift by one to the right would increase $\small\sum i \cdot a_i$ by exactly $S$. In particular, if $\gcd(S, n)=1$, then we are done, since we can simply take any ordering and some cyclic shift works. Furthermore, it suffices to show that if $\gcd(S, n) = d > 1$, then there exists a permutation of the numbers in $X$ such that $d \mid \small\sum i \cdot a_i$. We prove the desired result by strong induction on $n$, with the base case $n=1$ trivial. For the inductive step, assume that $\gcd(S, n) > 1$; we split into two cases on the elements of $S$, where in the latter case, we rely on the $n=d$ result. Case 1, all numbers are congruent modulo $\color{blue} d$: Let all elements of $X$ be conguent to $a \pmod{d}$. Then \[ \sum i \cdot a_i \equiv \sum i \cdot a = a \cdot \frac{n(n+1)}{2} \equiv 0 \pmod{d}, \]because if $n$ is odd, $n+1$ is even, and if $n$ is a power of $2$, $a$ must be even. Case 2, two numbers are distinct modulo $\color{blue} d$: On the other hand, suppose that the elements of $X$ leave at least two distinct residues modulo $d$. I contend that there exists a subset of $X$ with size $d$ whose sum is not divisible by $d$. Assume for contradiction that all $d$-sized subsets have sum divisible by $d$. Let $x$ and $y$ be two distinct elements that are distinct modulo $d$, and fix a $d-1$-sized subset $T$ containing neither $x$ nor $y$. Then the set $T \cup \{x\}$ and the set $T \cup \{y\}$ have sum both divisible by $d$, a contradiction. Thus there exists a $d$-sized subset $A$ of $X$ with sum not divisible by $d$. By inductive hypothesis, there exists a permutation of $A$ such that $\sum i \cdot a_i$ over that permutation is divisible by $d$. Take this permutation to be the first $d$ terms of the desired permutation of $X$. Repeat this process on $X\setminus A$ to obtain the next $d$ terms, and so on. Thus the induction is complete.

Solved with $\mathbf{mathboy100}$. The answer is all odd numbers and powers of $2$. First we prove that everything else doesn't work. The pairwise distinct condition doesn't really matter as we can add each number by multiples of $n$ and this doesn't affect anything. Let the $n$ integers be $x_1, x_2, \ldots, x_n$ and $\sum x_i = x_1 + x_2 + \cdots + x_n$. To do this, consider some even $n$. Let $x_1 = 1 + 2^{\nu_2(n)}$ and $x_2 = x_3 = \cdots = x_n = 1$. We have $\sum x_i = n + 2^{\nu_2(n)}$. Since $2^{\nu_2(n)} < n$ as $n$ isn't a power of $2$, $n$ cannot divide $n + 2^{\nu_2(n)}$, hence $\sum x_i$ is not a multiple of $n$. Suppose there existed an ordering of the $(x_i)$ such that $n$ divided $a_1 + 2a_2 + \cdots n a_n$. Taking modulo $2^{\nu_2(n)}$, we find \[2^{\nu_2(n)}\mid 1 + 2 + \cdots + n = \frac{n(n+1)}{2}\]which is absurd as $\nu_2 \left ( \frac{n(n+1)}{2} \right) = \nu_2(n) - 1$. Hence this choice of $x_i$ is a valid counterexample. Now we prove that all other $n$ work. First we state the following key claim: Claim: If there is an ordering of the integers yielding a value of $m$ modulo $n$, then there is another ordering of the integers yielding a value of $m + \sum x_i$ modulo $n$. Proof: Let $x_1 + 2x_2 + \cdots + n x_n \equiv m\pmod n$. Then consider placing $x_i$ in the slot $x_{i+1}$ on previously, so that the sum becomes \[ 2x_1 + 3x_2 + \cdots + n x_{n-1} + x_n,\]and this is clearly the same as $m + \sum x_i$ in modulo $n$. $\square$ This implies that any value that is $m \pmod{\sum x_i } $ can be obtained through some ordering of the integers (when taken modulo $n$ of course). For prime $n$, since $\sum x_i$ must be relatively prime to $n$, there exists some postive integer by CRT that is $0\pmod n$ and $m \pmod{\sum x_i}$, implying that $0\pmod n$ can be obtained. Now for other $n$, we take cases based on whether or not $n$ is odd. Case 1: $n$ is odd. We can induct on the number of prime factors of $n$, counted with multiplicity. The base case of $1$ is proven already. Fix some $n$ and suppose it was true for everything with a lower number of (not necessarily distinct) prime factors. Fix some choice of the integers and let $\gcd(n, \sum(x_i)) = d$. We prove the following claim: Claim: We can choose and ordering of the $x_i$ that yields a value that is $0\pmod d$. Proof: Suppose we weren't able to do so. Then considering some random order $x_1, x_2, \ldots, x_n$, we see that taking the sum modulo $d$ gives $(x_1 + 2x_2 + \cdots +d x_d) + (x_{d+1} + 2x_{d+2} + d x_{2d}) + \cdots $. If each of the sums $x_1 + x_2 + \cdots + x_d, x_{d+1} + x_{d+2} + \cdots + x_{2d}, \cdots x_{n - d + 1} + \cdots + x_n$, were not multiples of $d$, then we could use the induction hypothesis and order them in a certain way such that $(x_1 + 2x_2 + \cdots +d x_d), (x_{d+1} + 2x_{d+2} + d x_{2d}) , \ldots, $ are all $0\pmod d$, contradiction. Thus, for any partition of the $n$ integers into disjoint sets of $d$ elements, at least one of these sets must have a sum of $0\pmod d$. Now, among all such partitions, let $m\le \frac nd$ be the minimal possible number of these sets that have a sum of $0\pmod d$, and consider such a partition achieving $m$. If $m = \frac nd$, then any $d$ of the integers sums to a multiple of $d$, meaning that all the integers have the same residue modulo $d$, which is a contradiction as we can just choose any ordering and get a sum of $a \frac{n}{d} \cdot \frac{d(d-1)}{2}$ for some $a$, which is clearly a multiple of $d$ as $d$ is odd. Hence $m < \frac nd$ Now fix two sets $A$ and $B$ where the sum of the elements of $A$ is $0\pmod d$ but the sum of elements of $B$ is not $0\pmod d$. Consider two elements $a\in A$ and $b\in B$ so that $a\not \equiv b\pmod d$. Notice that if we swap $a$ and $b$ (i.e. place $b\in A$ and $a\in B$), all sets other than $A,B$ will stay the same, the sum of elements in $A$ will become nonzero modulo $d$, and the sum of elements of $B$ will increase by $a - b$ modulo $d$. However, by the minimality of $m$, the sum of elements of $B$ must become a multiple of $d$, so among all $a\in A$ and $b\in B$, $a-b$ leaves a fixed remainder when divided by $d$. This implies that $A \cup B$ contains at most $2$ residues mod $d$. Additionally, since $a - b\not\equiv b-a \pmod d$, at least one of $A,B$ contains exactly one residue mod $d$. If this were the case for $B$, we would have a contradication as it implies the sum of elements of $B$ is a multiple of $d$. Therefore, $A$ contains exactly one residue mod $d$. If there were two elements in $B$ that are $b\pmod d$, then swapping two of the $a$'s in $A$ with the two $b$'s in $B$ gives that the sum of elements in $B$ plus $2(a-b)$ is also a multiple of $d$. But then this means that $(a-b)\equiv 2(a-b) \pmod d$, so $a-b \equiv 0\pmod d$, contradiction. Since all the elements in $B$ cannot add to a multiple of $d$, the elements in $B$ cannot all the be the same mod $d$. Hence $B$ must have exactly one element that is $b\pmod d$ and everything else is $a\pmod d$. We can get that any set in the partition has at least $d-1$ numbers $a\pmod d$, with at least $m$ of them having exactly $d$ numbers $a\pmod d$. Now, this means we can do the following: Assign $x_1, x_2, x_3, \ldots, x_n$ as all $a\pmod d$ except for $x_{(m+1)d}, x_{(m+2) d} , \ldots, x_n$. This is possible since there are at most $\frac nd - m$ (as at least $m$ of the sets are all $a\pmod d$) numbers in $(x_i)$ that are not $a\pmod d$. Notice that in the sum $x_1 + 2x_2 + \cdots + n x_n$, for each $k$, $(kd) x_{kd}\equiv 0\pmod d$. Hence for each $k$, \[(kd + 1) x_{kd + 1} + (kd + 2) x_{kd + 2} + \cdots + (kd + (d-1)) + x_{kd + (d-1))} + ((k+1) d) x_{(k+1)} d\]is $a \cdot \frac{(d-1)d}{2} \equiv 0\pmod d$ as $d$ is odd. Therefore, the ordering $x_1, x_2, \ldots, x_n$ yields a value that's $0\pmod d$, contradiction. $\square$ Now, once we do this, let the ordering yield $L \cdot d$ for some positive integer $L$ and $\sum x_i = M \cdot d$ for some $M$ relatively prime to $ \frac nd$. By our earlier key claim, we can choose an ordering that yields $d(L + c M)$ in mod $n$ for any positive integer $c$. Since $M$ is relatively prime to $ \frac nd $, we can choose $c$ such that $\frac nd$ divides $L + cM$, so the ordering is a multiple of $n$, so the induction is complete. Case 2: $n$ is a power of $2$. Let $n = 2^k$. We induct on $k$. The base case $k = 1$ is true because for two numbers $x_1, x_2$, we can WLOG that $x_1$ is odd and $x_2$ is even, and take $2\mid x_2 + 2x_1$. Now suppose it was true for $n = 1, 2,4, \ldots, k$. We show it's true for $n = 2^{k+1}$. also. Claim: There exists an ordering of $x_1, x_2, \ldots, x_n$ such that $x_1 + 2x_2 + \cdots + n x_n$ is a multiple of $2^k$. Proof: Suppose this was not the case for some choice of $(x_i)$. The sum is \[ \left( x_1 + 2x_2 + \cdots + (2^k-1) x_{2^k - 1}\right) + \left( x_{2^k + 1} + 2x_{2^k + 2} + \cdots + (2^k - 1) x_{2^{k+1} - 1} \right) \]If $x_1 + x_2 + \cdots + x_{2^k}$ and $x_{2^k + 1} + x_{2^k + 2}+ \cdots + x_{2^{k+1}}$ both didn't sum to $0\pmod{2^k}$, we could order $(x_i)$ in a way so that it yields a multiple of $2^k$ by the inductive hypothesis, contradiction. Hence for any partition of the $n$ integers into two equally sized subsets, at least one of the subsets sums to a multiple of $2^k$. If all the $2^k$ element subsets of the $n$ integers summed to a multiple of $2^k$, then all the numbers are the same modulo $2^k$, meaning for any ordering, $\sum_{i=1}^n i x_i \equiv a \cdot \frac{2^{k+1} (2^{k+1} +1)}{2}$ if $x_i \equiv a$, which is a multiple of $2^k$. Henceforth assume that at least one of the subsets does not sum to a multiple of $2^k$. Take two complementary subsets $A$ and $B$ such that sum of elements in $A$ is $0\pmod{2^k}$, and $2^k$ doesn't divide the sum of elements of $B$. If $a\in A$ and $b\in B$ for $a\not \equiv b\pmod{2^k}$, swapping $a$ and $b$ so that $a\in B$ and $b\in A$, gives that the sum of elements of $B$ plus $(a-b)$ is a multiple of $2^k$. Since this means that the difference between a residue in $B$ and a residue in $A$ is either a fixed number or $0$, $A \cup B$ contains only numbers $a, b\pmod{2^k}$. Since $b-a \not \equiv a-b\pmod{2^k}$ and $B$ contains both $a$ and $b$ (as the sum of elements of $b$ isn't a multiple of $2^k$ so $B$ can't be constant mod $2^k$), every element of $A$ is $a\pmod{2^k}$. Now, when we swap one element in $A$ with one in $B$ (that is $b\pmod{2^k}$), we see that $B$ has a sum that is $0\pmod{2^k}$, while $A$ doesn't, which we just proved means that $B$ is constant mod $2^k$. Hence originally $B$ has exactly one number that isn't $a\pmod{2^k}$, meaning that the $n$ integers contains exactly one number that is $b\pmod{2^k}$ and everything else $a\pmod{2^k}$. Now, let $x_1 \equiv x_2 \equiv \cdots \equiv x_{n - 1} \equiv a\pmod{2^k}$ and $x_n \equiv b\pmod{2^k}$. We have \[\sum i x_i \equiv a \cdot \frac{n(n-1)}{2}\equiv 0\pmod{2^k},\]as desired.$\square$ For the finish, choose such an ordering and let $\sum i x_i = 2^k \cdot t$ for some odd $t$. Now we see that by our previous key claim that there exists an ordering yielding $2^k \cdot t + c \cdot \sum x_i$. If $\nu_2 \left(\sum x_i \right) \le k$, then we may choose $c$ such that $c\cdot \sum x_i$ is $2^k$ times an odd number, so $2^k \cdot t + c\cdot \sum x_i \equiv 0\pmod{2^{k+1}}$, as desired. Otherwise if $\nu_2 \left (\sum x_i \right )> k$, then $2^{k+1} = n \mid \sum x_i$, absurd. Hence the induction is complete and all powers of $2$ work.

Dunno, but I found this pretty easy might be wrong tho. Answer: Odd numbers and powers of $2$. Note that we can pretty much throw out the "pairwise distict" condition since we are working with the numbers modulo $n$. Now we provide a counterexample for even numbers that are not powers of $2$. Let $n = 2^\alpha k$ where $k$ is odd. Consider the $n$-tuple $(1, 1, 1, \dots , 2^\alpha +1)$. It is clear that the sum of these numbers are not divisible by $n$, but however we arrange these numbers $a_1, a_2, \dots, a_n$, the sum $1 \cdot a_1 + 2 \cdot a_2 + \dots + n \cdot a_n$ is always congruent to $\frac{n(n+1)}{2} \equiv 2^{\alpha-1}$ modulo $2^\alpha$. $\square$ Now we are left to show that our answer indeed works. Part 1: We say that we can reach a number $x$ if there exists a permutation of our numbers such that the given sum is congruent to $x$ modulo $n$. Let the sum of our numbers be $k$. Let $a_1, a_2, \dots a_n$ be an permutation of our numbers. Notice that $1\cdot a_1+2\cdot a_2+\dots+n\cdot a_n + k \equiv 1 \cdot a_n + 2 \cdot a_1 + \dots n \cdot a_{n-1} \pmod{n}$ which is also a permutation of our numbers. This implies that if we can reach $x$, we can reach $x+yk$ for all integers $y$. Therefore, we just need to find a permutation where $\gcd(k, n)$ divides $1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n$. Observe that this is enough to solve the problem when $n$ is prime. Now we induct on $\Omega(n)$. (As usual, $\Omega(n)$ is the number of prime factors of $n$ counting multiplicities.) We have already solved the base case in the previous paragraph. First, suppose that $n$ is a power of $2$. Let $n = 2^\alpha$, $k = \frac{n}{2}$ and let $x_1, x_2, \dots x_n$ be the numbers. Obviously, we may assume that all of the numbers are not congruent to each other modulo $2^{\alpha-1}$. Then we can find $k$ numbers $a_1, a_2, \dots, a_k$ among $x_1, x_2, \dots, x_n$ whose sum is not divisible by $2^{\alpha-1}$. Let $a_{k+1}, a_{k+2}, \dots a_n$ be the rest of the numbers. Suppose that $\sum\limits_{i=k-1}^n ia_i$ is divisible by $2^{\alpha-1}$. Then by part 1, we can relabel the numbers $a_1, a_2, \dots a_k$ such that $k = 2^{\alpha-1} \mid \sum\limits_{i=1}^k ia_i$ creating a valid permutation. Otherwise, if there are at least $3$ distinct integers among our numbers, there must exist a pair of positive integers $x$ and $y$ where swapping the values of $a_x$ and $a_y$ makes the sums $\sum\limits_{i=0}^k a_i$ and $\sum\limits_{i=k+1}^{n} a_i$ not divisible by $2^{\alpha-1}$. Then we can finish similarly as in the previous case. If our numbers consist of only $2$ distict integers $x, y$ appearing $s, n-s$ times respectively where $s \leq k$, we can simply pick $a_{i}=x$ for all $1 \leq i \leq s-1$. Then if we pick $a_{k+i}=x$ for some $i$ we get $a_1 + 2 \cdot a_2 + \dots + n \cdot a_n \equiv y\frac{n(n+1)}{2} + (x-y)i$ since $k \mid s(x-y) \implies 2 \mid x-y$. This means we can make our sum congruent to any number divisible by $\gcd(x-y, k)$ modulo $k$ which includes $0$. The case where the numbers $a_{k+1}, a_{k+2}, \dots a_n$ consist of only one integer is trivial. $\square$ Now suppose that $n$ is odd. Let $m$ be the sum of our numbers and let $k = \gcd(m, n)$. Let $p = \frac{n}{k}$. We prove that among any $ks$ integers, we can find $k$ of them such that $k \mid 1 \cdot a_1 + 2 \cdot a_2 + \dots + k \cdot a_k$. By induction, it suffices to find $k$ numbers such that $k \nmid a_1 + a+2 + \dots + a_k$ so assume that no such $k$-tuples exist among our numbers. Then all of our numbers are congruent modulo $k$ so picking any $k$ of them would suffice. This implies that we can pick $a_1, a_2, \dots, a_{n-k}$ such that $\sum\limits_{i=sk+1}^{(s+1)k} ia_i$ is divisible by $k$ for all $1 \leq s < p$. Suppose that $k \nmid \sum\limits_{n-k+1}^n ia_i$ Similarly as in the previous case, if there are at least $3$ distinct integers among our numbers, there must exist a pair of positive integers $x$ and $y$ such that swapping the values of $x$ and $y$ makes it so that each of the sums $\sum\limits_{i=sk+1}^{(s+1)k} a_i$ are not divisible by $k$. Then we can finish by induction. If our numbers consist of only $2$ distinct integers $x, y$ appearing $s, n-s$ times respectively, we can simply pick $a_i=x=a_{n-i}$ for all $1 \leq i \leq \lfloor \frac{s}{2} \rfloor$ and $a_n=x$ if $2 \nmid s$ otherwise $a_n=y$. It is clear that $n \mid \sum\limits_{i=1}^{n} ia_i$ in this case. The case where all of the numbers are equal modulo $n$ is trivial. $\blacksquare$

We claim the answer is odd numbers and powers of $2$. For $x_1, \dots, x_n \in \mathbb{Z}/n\mathbb{Z}$, let a number $N\in \mathbb{Z}/n\mathbb{Z}$ be achievable if there is a permutation $a_1, \dots, a_n$ of the $x_i$'s with \[\sum_{k=1}^{n} ka_k = N.\]By cyclic shifts, if $N$ is achievable, then $N + x_1 + \dots + x_n$ is also achievable. So, the problem is equivalent to there being a permutation $a_1, \dots, a_n$ of $x_1, \dots, x_n$ such that $\gcd(n, x_1 + \dots + x_n)\mid \sum_{k=1}^n ka_k$. Claim: Powers of $2$ work. Proof: Let $n = 2^r$ be a power of $2$. We will prove the claim by induction on $r$. Because $\gcd(n, x_1 + \dots + x_n)\mid 2^{r-1}$, this is equivalent to showing we can achieve \[\sum_{k = 1}^{n} ka_k \equiv 0 \pmod{\frac n2}.\] The base case $n = 1, 2$ is clear. Assume toward a contradiction that $x_1, \dots, x_n$ is a set of nonnegative integers with minimum sum that cannot be rearranged into $a_1, \dots, a_n$ with $\sum_{k=1}^n ka_k \equiv 0 \pmod{n}$. Case 1: The set $X = \{x_1, \dots, x_n\}$ can be partitioned into equally-sized sets $A$ and $B$ such that $\sum_{a\in A} a, \sum_{b\in B} b \not \equiv 0 \pmod{\frac n2}$ Then, we can let \[\begin{aligned} \{a_1, \dots, a_{\frac n2}\} &= A\\ \{a_{\frac n2 +1}, \dots, a_n\} &= B. \end{aligned}\]By the inductive hypothesis, we can make it so that \[\sum_{k = 1}^{\frac n2} ka_k \equiv \sum_{k = \frac n2 + 1}^{n} ka_k \equiv 0 \pmod{\frac n2}.\]So, $\sum_{k = 1}^{n} ka_k \equiv 0 \pmod{\frac n2}$. Case 2: $x_1, \dots, x_n$ cannot be partitioned into equally-sized sets $A$ and $B$ such that $\sum_{a\in A} a, \sum_{b\in B} b \not \equiv 0 \pmod{\frac n2}$ If $\sum_{k=1}^n x_k$ is odd, we can finish by cyclic shifts. So, $\sum_{k=1}^n x_k$ is even. Split the elements into two equally sized sets $A$ and $B$. If any two elements have different parity, we can swap an element of $A$ with an element of $B$ to make both sets have odd sum, a contradiction. Otherwise, all elements have the same parity. So, we can replace each element $x_i$ with $\lfloor \frac {x_i}2 \rfloor$, so $x_1, \dots, x_n$ isn't minimal, a contradiction. Claim: If $n$ is odd and $x_1, \dots, x_n \in \mathbb{Z}$ such that $x_1 + \dots + x_n \not \equiv 0 \pmod{n}$ or $x_1, \dots, x_n$ has at most $2$ residues $\pmod{p}$, there is a permutation $a_1, \dots, a_n$ of $x_1, \dots, x_n$ with \[\sum_{k=1}^n ka_k \equiv 0\pmod{n}.\] Proof: Case 1: $x_1, \dots, x_n$ has only $1$ residue $\pmod{p}$ Then, for any permutation $a_1, \dots, a_n$, \[\sum_{k=1}^n ka_k \equiv \frac{n(n+1)}2 \equiv 0\pmod{n}.\] Case 2: $x_1, \dots, x_n$ has $2$ residues $\pmod{n}$ This reduces to the case where $x_1, \dots, x_n$ are all $1$ or $0$. Let $a_1, \dots, a_n$ be any permutation of the $x_i$'s. By taking $i$ such that $a_i \equiv 1 \pmod{n}$ and $a_{i+1} \equiv 0\pmod{n}$ and swapping $a_i$ with $a_{i+1}$, we can add $1$ to the sum until it's a multiple of $n$. Case 3: $x_1 + \dots + x_n \not \equiv 0 \pmod{n}$ Assume toward a contradiction that $n$ is the smallest odd number that doesn't work. Assume that $x_1, \dots, x_n$ is a sequence with the minimum possible sum that has no permutation $a_1, \dots, a_n$ with $\sum_{k=0}^n ka_k \equiv 0 \pmod{n}$. If $\gcd (n, x_1 + \dots + x_n) = 1$, then we're done. Otherwise, let $g = \gcd (n, x_1 + \dots + x_n)$. Let $r=\frac gn$. Let $A_1, \dots, A_r$ be a partition of $\{x_1, \dots, x_n\}$ into $r$ sets of size $g$. Assume some set $A_i$ has sum $0\pmod{g}$ and its elements have at least $3$ different residues $\pmod{g}$. Assume $a, b, c\in A_i$ have different residues $\pmod{g}$. Let $j\neq i$ and let $m\in A_j$. Swapping one of $a$, $b$, and $c$ with $m$ will make it so neither $A_i$ nor $A_j$ has a sum of $0\pmod{g}$. We can repeat this process until every set either has at most $2$ residues $\pmod{g}$ or has a sum that isn't a multiple of $g$. Then, let $\{a_{g(i-1)}, \dots, a_{g(i-1)+g-1}\} = A_i$. Then, either by induction or by cases $1$ and $2$, we can arrange the values so that \[\sum_{k=a_{g(i-1)}}^{a_{g(i-1)+g-1}} ka_k \equiv 0\pmod{g}.\]So, \[\sum_{k=1}^{n} ka_k \equiv 0\pmod{g}.\] Claim: Numbers that are not odd or a power of $2$ do not work. Proof: Let $n = 2^mr$ where $r>1$ is odd. Let $x_1, \dots, x_{n-1} = 1$ and $x_n = 2^m+1$. Then, $x_1 + \dots + x_n \equiv 2^m \pmod{n}$, so their sum is not a multiple of $n$. Let $a_1, \dots, a_n$ be a permutation of $x_1, \dots, x_{n-1}$. We have \[\begin{aligned} \sum_{k=1}^n ka_k &\equiv \sum_{k=1}^n k \pmod{2^k}\\ &\equiv \frac{n(n+1)}2 \pmod{2^k}\\ &\equiv 2^{k-1}(n+1)r \pmod{2^k}\\ &\equiv 2^{k-1} \pmod{2^k}. \end{aligned}\]Therefore, $\sum_{k=1}^n ka_k$ is not a multiple of $2^k$, so it's not a multiple of $r$.

The answer is that $n$ must either be odd or a power of $2$. Denote the given $n$ integers, before reordering, as $b_1, \dots, b_n$. Let $S = \sum_{i=1}^n b_i$. $n$ is even and not a power of 2. We want to choose distinct $b_1, \dots, b_n$ so that $n \nmid S$ and no sum of the form $a_1 + 2a_2 + \cdots + na_n$ is a multiple of $n$. By adding suitable multiples of $n$ to each $b_i$, we may ignore the "distinct" condition. Let $n = 2^x \cdot m$, where $x$ is a positive integer, $m$ is odd, and $m > 1$. Consider $b_1 = \cdots = b_{n-1} = 1$ and $b_n = 2^x + 1$. The sum of these numbers is $n + 2^x$, which is not a multiple of $n$. Moreover, since all $b_i$ are congruent to $1 \pmod{2^x}$, we have $a_1 + 2a_2 + \cdots + na_n \equiv \frac{n(n+1)}{2} \not \equiv 0 \pmod{2^x}$, so $n \nmid a_1 + 2a_2 + \cdots + na_n$. $n = p^x$, where $p$ is prime and $x$ is a positive integer. Let $y$ be the maximum nonnegative integer such that $b_1 \equiv \cdots \equiv b_n \pmod{p^y}$, and let $z = \nu_p(S)$. Then $z < x$ since $n \nmid S$. Also, $y \le z$ since $S \equiv nb_1 \pmod{p^y}$; if $y \ge x$ this implies $n \mid S$, contradiction, so $y < x$, $p^y \mid nb_1$, and $p^y \mid S$. We first find some $A \subseteq \{b_1, \dots, b_n\}$ such that $|A| = p^z$ and $p^{y+1} \nmid \sum_{a \in A} a$. We do that by taking some pair $b_i, b_j$ such that $b_i \not \equiv b_j \pmod{p^{y+1}}$, adding $p^z - 1$ arbitrary elements of $b$ other than $b_i$ or $b_j$ to $A$ (which can be done since $p^z < n$), and picking whichever of $b_i$ and $b_j$ that gives a sum of $A$ not divisible by $p^{y+1}$. Start with some arbitrary reordering $a_1, \dots, a_n$ such that $A = \{a_1, \dots, a_{p^z}\}$. Initially, $\sum_{i=1}^n ia_i \equiv \frac{n(n+1)}{2} a_1 \equiv 0 \pmod{p^y}$ since $y < x$. Now consider repeated cyclic shifts of $a_1, \dots, a_{p^z}$ (i.e. repeatedly moving $a_{p^z}$ to the beginning). Each cyclic shift changes $\sum_{i=1}^n ia_i$ by $\sum_{a \in A} a$ modulo $p^z$. Since $p^{y+1} \nmid \sum_{a \in A} a$, we can achieve any $\sum_{i=1}^n ia_i \pmod{p^z}$ that is a multiple of $p_y$, including $0 \pmod{p^z}$. After doing that, we cyclically shift the entire sequence $a_1, \dots, a_n$, which by similar logic, allows for any $\sum_{i=1}^n ia_i \pmod{n}$ that is a multiple of $p^z$, including $0 \pmod{n}$. The general case where $n$ is odd. Use induction on the number of distinct prime factors of $n$; the case of one prime factor is addressed above. Suppose $n$ has at least two distinct prime factors. Then we can find a prime $p \mid n$ such that if $n = p^x q$ where $x = \nu_p(n)$, then $q \nmid S$. Again, let $y$ be the maximum nonnegative integer such that $b_1 \equiv \cdots \equiv b_n \pmod{p^y}$. By adding multiples of $n$ to the $b_i$ we may assume $y \le x$. Similar to before we can pick a subset $A$ such that $|A| = p^x$ and $p^{y+1} \nmid \sum_{a \in A} a$. We need to assign to each $b_i$ a position $p_i$ (so $a_{p_i} = b_i$) modulo $p^x$ and a position modulo $q$ such that each combination is used exactly once, and such that $\sum_{i=1}^n b_i p_i$ is zero modulo both $p^x$ and $q$. First we assign $p_i \equiv 0 \pmod{q}$ for all $i$ such that $b_i \in A$, and arbitrarily assign nonzero $p_i \pmod{q}$ to all other $b_i$ such that each $p_i \pmod{q}$ is used $p^x$ times. Then arbitrarily assign $p_i \pmod{p^x}$ such that each $p_i$ from $1$ to $n$ is used exactly once. At this point, $\sum_{i=1}^n b_i p_i \equiv \frac{n(n+1)}{2} b_1 \equiv 0 \pmod{p^y}$. Now we repeatedly increment all $p_i \pmod{p^x}$ for $i$ such that $b_i \in A$ by one; each time we do so, $\sum_{i=1}^n b_i p_i$ changes by $\sum_{a \in A} a \pmod{p^x}$ (a multiple of $p^y$ since all $a$ are congruent modulo $p^y$, but not a multiple of $p^{y+1}$), giving access to all $\sum_{i=1}^n b_i p_i \pmod{p^x}$ that is a multiple of $p^y$. Now we have $\sum_{i=1}^n b_i p_i \equiv 0 \pmod{p^x}$, we also need to ensure $\sum_{i=1}^n b_i p_i \equiv 0 \pmod{q}$. This can be done by grouping the $b_i$ by the values of $p_i \pmod{q}$ (so $q$ groups of $p^x$ elements each), taking the sum of each group, and applying the inductive hypothesis on the resulting $q$ values (which works since we assumed $q \nmid S$ earlier). This gives a permutation of the residue classes mod $q$ that we can apply on all $p_i$.