Anisphia Wynn Palettia and Good Permutations

The main trap is thinking adjacent gcds matter. They do not. A bad index needs all three pairwise gcds to be $1$, so a triple is already safe if any two numbers inside it share a factor.

The pattern

Suppose we have a pile of numbers $x_1,x_2,\dots$ that all share some divisor $d>1$. Then this shape is extremely useful:

${}- , x, x, - , x, x, - , x, x, \dots$

Here - means any number at all. Every length-$3$ window contains two of the $x$ numbers:

• -, x, x has the two adjacent $x$ values.
• x, x, - also has them.
• x, -, x has two $x$ values from neighboring blocks.

So none of these windows can be bad. That is the whole trick. No wizardry, just shoving shared-factor pairs everywhere.

Which shared-factor piles do we use?

Use these three groups:

• $E$: even numbers. They all share divisor $2$.
• $M$: odd multiples of $3$. They all share divisor $3$.
• $R$: everything else, meaning odd numbers not divisible by $3$.

The numbers in $R$ are the filler - values. They do not need to share anything.

First, while possible, output blocks

$r, e_1, e_2$

where $r\in R$ and $e_1,e_2\in E$.

Then, while possible, output blocks

$r, m_1, m_2$

where $r\in R$ and $m_1,m_2\in M$.

Finally, append all leftovers in any order. The leftovers are allowed to be a bit cursed; the limit is $6$, so we only need almost everything protected.

Why there are enough blocks

There are $\lfloor n/2\rfloor$ even numbers, so evens give

$\left\lfloor \frac{\lfloor n/2\rfloor}{2} \right\rfloor = \left\lfloor \frac n4 \right\rfloor$

pairs. That creates a protected segment of length

$3\left\lfloor \frac n4 \right\rfloor.$

The odd multiples of $3$ are $3,9,15,\dots$, so there are $\left\lfloor \frac{n+3}{6}\right\rfloor$ of them. They give

$\left\lfloor \frac{n+3}{12}\right\rfloor$

pairs, creating another protected segment of length

$3\left\lfloor \frac{n+3}{12}\right\rfloor.$

The filler group $R$ has enough numbers for both phases. This is just checking residues modulo $12$: $R$ consists of numbers congruent to $1,5,7,11 \pmod{12}$, and that count is at least

$\left\lfloor \frac n4 \right\rfloor + \left\lfloor \frac{n+3}{12}\right\rfloor.$

So the construction really does make both protected segments.

Bounding the bad indices

Let

$L=3\left\lfloor \frac n4 \right\rfloor+3\left\lfloor \frac{n+3}{12}\right\rfloor.$

This is the total length of the two protected segments.

For the first segment, all starting positions except possibly the very last one are guaranteed safe, so it gives $3\lfloor n/4\rfloor-1$ safe starts.

For the second segment, all fully internal starts are guaranteed safe, so it gives at least $3\lfloor (n+3)/12\rfloor-2$ safe starts. We ignore boundary bonuses because we do not need them.

Thus at least

$L-3$

starting positions are definitely good.

Now write $n=12q+r$, where $0\le r<12$. Then

$L=12q+3\left\lfloor \frac r4\right\rfloor+3\cdot [r\ge 9].$

Checking the $12$ possible values of $r$ gives

$L\ge n-5.$

So the number of guaranteed good starts is at least

$L-3\ge n-8.$

There are only $n-2$ total starting positions, therefore the number of bad indices is at most

$(n-2)-(n-8)=6.$

For $n\le 8$, literally any permutation works because there are only $n-2\le 6$ triples total. Sometimes brute force is not even needed; the constraint just gives up.