Special permutations

My Solution:

The answer is 333. The beautiful numbers are only the ones coprime with 6, and from this we easily get the answer. Now we must prove the beautiful numbers are the ones coprime with 6.

First, assume $n$ is coprime with 6. Then call $p_1=1$ , $p_3=2$ , $p_5=3$ , ..., $p_n = (n+1)/2$ , and then call $p_2=((n+1)/2)+1$ , $p_4=p_2+1$ , ..., $p_{n-1} = n$ . We can easily verify that $\{ p_1-1, ..., p_n -1 \}$ is equivalent to $\{ 0, (n-1)/2, -1, (n-3)/2, -2, ..., 1, -(n-1)/2 \} \equiv \{ 1, 2, ..., n \}$ and so it works. Also, we can verify that $\{ p_1+1, ..., p_n+1 \}$ is an arithmetic progression (not in order) that starts with 2 and has common difference 3, and so it also works.

Now we must prove numbers divisible by 2 or 3 don't work.

If $n$ works, then $p_1+...+p_n \equiv p_1 -1 + p_2 -2 + ... + p_n-n$ mod $n$ , therefore $n | 1+...+n = n(n+1)/2$ and so clearly $n$ is odd.

Also, note that $2n(n+1)(2n+1)/3 = 4(1^2+...+n^2) \equiv 2((p_1^2 + 1^2) + ... + (p_n ^2 + n^2)) =$ $((p_1-1)^2 + (p_1+1)^2) + ... + ((p_n-n)^2 + (p_n+n)^2) \equiv 2(1^2+...+n^2)$ $= n(n+1)(2n+1)/3$ mod $n$ . From this, $n | n(n+1)(2n+1)/3$ and so $(n+1)(2n+1)/3$ is an integer, and therefore clearly $n$ cannot me a multiple of 3.

So beautiful numbers are the ones coprime with 6 and the answer is 333.

For an integer $n$ , suppose $k$ is an integer coprime to $n$ . Then we claim that the sequence $\{k(1),k(2),k(3), \cdots ,k(n)\} = \{ki\}_{i=1}^n \equiv \{i\}_{i=1}^n = \{1,2,3, \cdots ,n\} \pmod{n}$ . This claim is true because for any $i \in \{1,2, \cdots ,n-1\}$ , we have $k(i+1)-k(i) = k$ which is coprime to $n$ , and hence whatever the value of $k(1) \pmod{n}$ is, the sequence $\{ki\}_{i=1}^n = \{k(1) + k(i)\}_{i=0}^{n-1}$ traces out all values modulo $n$ .

The question states $\{a_1,a_2,a_3, \cdots ,a_n\} \equiv \{a_1-1,a_2-2,a_3-3, \cdots ,a_n-n\} \equiv \{a_1+1,a_2+2,a_3+3, \cdots ,a_n+n\}$ . By the above lemma, this implies there must exist $3$ consecutive integers, that are coprime to $n$ which implies $\gcd(n,6) = 1$ . Precisely, there are $\boxed{333}$ such integers less than $1000$ .