Note that for any permutation $\sigma\in S\_5$ the product $\prod\_{k=1}^5k^{\sigma(k)}$ is neither a square nor a cube.


**Question.** Let $n>5$ be an integer. Is the product $\prod\_{k=1}^nk^{\sigma(k)}$ a square for some $\sigma\in S\_n$? Is the product $\prod\_{k=1}^nk^{\sigma(k)}$ a cube for some $\sigma\in S\_n$?


The question looks not very challenging, and I believe that the answer should be positive. Any ideas to provide a proof?


The question can be refined further, for example, I conjecture that for any integer $n>5$ there is a permutation $\sigma\in S\_n$ with $\sigma(1)=1$ and $\sigma(2)=2$ such that $\prod\_{k=1}^n k^{\sigma(k)}=(p-1)^3$ for some prime $p$. Let $a(n)$ denote the number of such permutations $\sigma$. I find that
$$a(6)=1,\ a(7)=3,\ a(8)=2,\ a(9)=27,\ a(10)=44,\ a(11)=154.$$


For the above question, I ask for an actual proof of the positive answer, rather than inaccurate heuristic arguments.



Is $\prod_{k=1}^nk^{\sigma(k)}$ a square or a cube for some $\sigma\in S_n$?
We show the following.


**Theorem.** For any $n \geq 6$, there is a permutation $\sigma \in S\_n$ such that $\prod\_{k=1}^n k^{\sigma(k)}$ is a square (respectively, a cube).


**Proof.** Let us first handle the case of squares. It is equivalent to find a subset $A$ of $\{1,\ldots,n\}$ with cardinality $r = \lceil \frac{n}{2} \rceil$ such that the product of the elements of $A$ is a square (indeed, for such an $A$, choose any permutation $\sigma$ such that $\sigma(n)$ is odd for $n \in A$, and even for $n \notin A$). Consider the pairs of integers $(m,2m)$ with $1 \leq m \leq n/2$ and $v\_2(m) \equiv 0 \pmod{2}$. These pairs are disjoint. Let $N$ be the number of such pairs. Since the probability that an integer $m \geq 1$ satisfies $v\_2(m) \equiv 0 \pmod{2}$ is $\frac{1}{2} + \frac{1}{2}\times \frac{1}{4} + \frac{1}{2}\times \frac{1}{4^2} + \cdots = \frac{2}{3}$, we have $N \sim\_{n \to \infty} \frac{n}{3}$, and a closer analysis shows that $2N \geq r+1$ for $n \geq 8$. Let us put in $A$ the pairs $(m,2m)$ in increasing order until $|A| \in \{r+1,r+2\}$. Then the product $P$ of the elements of $A$ is a square or twice a square. If $|A|=r+1$, we remove the number $1$ or $2$ from $A$ according to whether $P$ is a square or twice a square. If $|A|=r+2$, we remove the numbers $\{1,4\}$ or $\{1,2\}$ according to whether $P$ is a square or twice a square (removing 4 is possible since $n \geq 8$). The cases $n=6,7$ are dealt with by hand.


Now the case of cubes. We need to find disjoint subsets $A,B$ of $\{1,\ldots,n\}$ with respective cardinality $r\_1 = \lceil \frac{n}{3} \rceil$ and $r\_2 = \lceil \frac{n-r\_1}{2} \rceil$ such that $PQ^2$ is a cube, where $P$ (resp. $Q$) is the product of the elements of $A$ (resp. $B$). We wish to use the pairs $(m,2m)$ as above. Given such a pair, we put one element in $A$ and the other in $B$, giving the products $m^1 \times (2m)^2 = 4m^3$ or $m^2 \times (2m)^1 = 2m^3$, which are either twice a cube or four times a cube. As we saw, the number $N$ of such pairs is roughly $n/3$, but it turns out this is not quite enough to fill in $A$ and $B$. So we use more pairs, namely $(3m,4m)$ with $n/6 < m \leq n/4$ and $v\_2(m) \equiv v\_3(m) \equiv 0 \pmod{2}$. These pairs are disjoint from the previous ones and their number $N'$ satisfies $N' \sim\_{n \to \infty} \frac{n}{24}$. A closer analysis shows that $N+N' \geq r\_1$ for $n \notin \{1,7,13\}$. Let us assume $n \geq 8$ and $n \neq 13$. In particular $r\_1 \geq 3$.


**Case 1.** $N'=0$. Then $N \geq r\_1 \geq 3$. We keep only the first $r\_1$ pairs $(m,2m)$. In particular, we still have $(1,2)$, $(3,6)$ and $(4,8)$. If $r\_1=r\_2$ then swapping $(1,2)$ or $(3,6)$ if necessary, we can get $|A|=r\_1$, $|B|=r\_2$ and $PQ^2$ is a cube. If $r\_1=r\_2+1$ then we remove ($4^2$ or $8^2$) and we possibly swap $(1,2)$ or $(3,6)$ to get the same result.


**Case 2.** $N'=1$. Let $(3m,4m)$ be the unique pair of the second type, which we will keep. We have $N \geq r\_1-1$. Let us first assume $N \geq r\_1$. Swapping $(3m,4m)$ if necessary, we may assume that $v\_3((3m)^a (4m)^b) \equiv 1 \pmod{3}$ with $\{a,b\}=\{1,2\}$. We keep only the first $r\_1$ pairs $(m,2m)$. In particular we still have $(1,2)$, $(3,6)$ and $(4,8)$. If $r\_1=r\_2$ then we remove ($3^1$ or $6^1$) and ($1^2$ or $2^2$) so that $|A|=r\_1$, $|B|=r\_2$ and $PQ^2$ is a cube. If $r\_1=r\_2+1$, we remove ($3^1$ or $6^1$) and ($1^2$ or $2^2$) and ($4^2$ or $8^2$) so that again $A$ and $B$ have the right cardinality and $PQ^2$ is a cube. Finally, the case $N = r\_1-1$ happens only for $n \in \{16, 17, 19, 25, 31\}$. These values of $n$ will be handled separately at the end.


**Case 3.** $N' \geq 2$. We may swap the numbers inside two of the pairs $(3m,4m)$ so that the power of $3$ becomes a cube. Now $N \geq r\_1-N' \geq 2$ for $n \geq 6$. We keep only the first $r\_1-N'$ pairs $(m,2m)$. If $r\_1=r\_2$ then we swap $(1,2)$ or $(3,6)$ if necessary so that the power of $2$ becomes a cube. If $r\_1=r\_2+1$ then we remove ($1^2$ or $2^2$) and possibly swap $(3,6)$ to get the correct power of $2$.


Finally, the cases $n=6,7,13,16,17,19,25,31$ can be handled with a computer, just looping over all disjoint subsets $A,B \subset \{1,\ldots,n\}$ of respective cardinality $r\_1$ and $r\_2$ (solutions are found quickly). Note that it is not necessary to compute the products $PQ^2$, just keep track of the exponents mod $3$ in the prime factorization of the integers $1 \leq k \leq n$ (these exponents mod $3$ should be precomputed).
$\Box$


