Numbers from $1$ to $n$ are permuted such that the sum of any three consecutive numbers is divisible by the leftmost of them

Numbers from $1$ to $n$ are permuted such that the sum of any three consecutive numbers is divisible by the leftmost of them.

Example for $n=6$: $1,2,3,5,4,6$. The questions are:

1. For which values of $n$ exists such permutation?
2. Is it possible for $n$ to be arbitrarily large?
3. What is the biggest possible value of $n$?

Examples for $n=15$:

$$ \begin{aligned} &15,11,4,7,5,9,1,8,3,13,14,12,2,10,6 \\ &3,14,13,15,11,4,7,5,9,1,8,6,2,10,12 \\ &15,1,14,3,11,13,9,4,5,7,8,6,2,10,12 \\ &14,9,5,4,1,3,13,11,15,7,8,6,2,10,12 \end{aligned} $$

Example for $n=38$:

$$ \begin{gathered} 35,3,32,1,31,33,29,4,25,11,14,19,23,15, \\ 8,37,27,10,17,13,21,5,16,9,7,38,18,20, \\ 34,6,28,2,26,22,30,36,24,12 \end{gathered} $$

And two examples for $n=51$:

$$ \begin{gathered} 46,45,1,44,49,39,10,29,21,37,5,32,23,41,51,31,20, \\ 11,9,2,43,35,8,27,13,14,25,3,47,40,7,33,16,17, \\ 15,19,26,50,28,22,6,38,34,4,30,18,42,48,36,12,24 \end{gathered} $$

and

$$ \begin{aligned} &46,45,1,44,49,39,10,29,21,37,5,32,23,41,51,31,20, \\ &11,9,2,43,35,8,27,13,14,25,3,47,40,7,33,16,17, \\ &15,19,26,50,28,22,6,38,34,4,30,42,18,24,12,36,48 \end{aligned} $$

P.S. At the moment, this is a record! These are the only two solutions for $n$ between $39$ and $64$, inclusive. It was checked by brute force. I would also be glad if someone could add more appropriate tags to this question.

P.S.S. There is also an idea to generate chains of length $\frac{n}{2}$ (with values from $1$ to $n$), and then "pair" them. I do not know to what extent this will speed up the process.

P.S.S.S. Here's a nifty Sage program using recursively enumerated sets and MapReduce. For example, $n=21$ is taken, but you can replace it with any other. Especially the power of this approach can be felt on a multiprocessor system, where MapReduce is automatically parallelized and everything is greatly accelerated. The program is not mine!

useful thoughts

If $x+y+z$ is divisible by $x$ then so is $y+z$. We can therefore generate the permutation $P$ backwards by starting with two numbers $y,z \in N$ where $N = [1,n]$ and then backtracking over all divisors of $y+z$ in $N$ until we used all numbers.

Even numbers can only divide even numbers but odd numbers can divide both. So looking at a valid permutation mod $2$ notice that after a $0$ there can be either two zeros or ones (green). In the second case, there also have to be two ones before the $0$ (blue) as you can see on the left for $n = 8 :$

The longest valid permutation where only the last element is even occurs at $n=7$ (or equivalently, which ends in $110$ as discussed above). For the longest valid permutation that ends in two even numbers $n = 11$. Conversely, all valid permutations for $n > 10$ must end in at least two even numbers from which we can start the recursion:

def factor(n):  # return all numbers that divide n
    F = [1,n]
    for x in range(2,n//2 + 1):
        if n%x == 0: F.append(x)
    return set(F)

def foo(N,P):
    if len(N) == 0: print(P[::-1])  # end recursion
    # iterate over divisors in N
    for f in N.intersection(factor(P[-1] + P[-2])):
        M = N.copy(); M.remove(f); foo(M,P + [f])

n = 5
N = set(range(1,n+1))
for a in range(2,n+1,2):    # iterate over starting pairs
    for b in range(a+2,n+1,2):
        M = N.difference(set([a,b]))
        foo(M.copy(),[a,b])    # start recursion
        foo(M.copy(),[b,a])

In general, a valid permutation of length $n$ must end in at least $\lfloor \frac{n}4 \rfloor$ zeros, the only exception being $n = 5$ as shown on the right. So it is possible to first generate all valid permutations of even numbers in $N$ of that length with the same method we use to find the whole permutation. I have not tried when this gets faster than the method described above.