Lexicographically earliest permutation of the initial segment of nonnegative integers subject to divisibility constraints

Question

The challenge is simple: Reorder the first integers {0, 1, 2, ..., n} into an ordered list so that the following three conditions are met:

1. If k is the last element in the list, then all of its prime factors divide its immediate predecessor.

2. If a term k lies between two other terms of the list and p is a prime factor of k, then p divides either the predecessor of k or the successor of k, but not both.

For n = 0, the solution is by convention (0). You can ignore this edge case as we exclude it from the requirement for simplicity.

3. The list is the lexicographically earliest list among all lists whose terms satisfy conditions (1) and (2).

The first few permutations of {0,1,...,n} that meet these conditions are:

0 -> (0)
1 -> (0, 1)
2 -> (0, 2, 1)
3 -> (1, 2, 0, 3)
4 -> (0, 3, 1, 2, 4)
5 -> (1, 2, 4, 3, 0, 5)
6 -> (1, 2, 0, 5, 3, 6, 4)
7 -> (2, 1, 3, 6, 4, 5, 0, 7)
8 -> (1, 2, 4, 3, 6, 8, 5, 0, 7)
9 -> (3, 1, 2, 4, 5, 0, 7, 8, 6, 9)

0 and 1 have no prime factors. Recall that all numbers divide 0.

(If this last remark surprises you, read it on page 14 of Apostol's Introduction to Analytic Number Theory.)

Hint: this is a finite variant of the OEIS-sequence A280864 by Rémy Sigrist.

Summary:

Input: A positive integer n. (We exclude the edge case n=0 for simplicity.)

Output: A permutation of {0,1,...,n} subject to the conditions (1), (2) and (3).

This is code-golf, so each language's shortest code in bytes wins.

Answer 1

Picat, 224 bytes

import cp.
f(N)=A,N<17=>A=new_list(N+1),A::0..N,A.all_distinct,table_in(zip(A,A[2..N+1],A[3..N+1]++[1]),[{X,Y,Z}:X in 0..N,Y in 0..N,Z in 0..N,foreach(P in[2,3,5,7,11,13])Y<1;Y mod P>0;X*Z mod P<1,(X+Z)mod P>0 end]),A.solve.

Attempt This Online!

Given N, returns the lexicographically smallest permutation that satisfies the condition if such an answer exists, and fails otherwise. It fails immediately when N >= 17 based on my own comment, so that I could hardcode the small primes instead of dynamically computing them.

Solves N = 1 through 14 in a minute. For N = 16, I had to switch to sat solver and repeatedly constrain the answer to lexicographically earlier than already found to get the answer. The cp solver assigns values to variables in the given order (i.e. from left to right) and values from smallest to largest, so it finds the lexicographically smallest answer by default.

The full list of solutions are presented below:

1 => [0,1]
2 => [0,2,1]
3 => [1,2,0,3]
4 => [0,3,1,2,4]
5 => [1,2,4,3,0,5]
6 => [1,2,0,5,3,6,4]
7 => [2,1,3,6,4,5,0,7]
8 => [1,2,4,3,6,8,5,0,7]
9 => [3,1,2,4,5,0,7,8,6,9]
10 => [1,2,4,3,9,5,10,8,7,0,6]
11 => [6,1,2,4,3,9,5,10,8,7,0,11]
12 => [1,2,4,3,6,8,5,10,12,9,7,0,11]
13 => [7,1,2,4,3,6,8,5,10,12,9,11,0,13]
14 => [2,1,3,6,4,5,10,8,7,14,12,9,11,0,13]
16 => [11,1,2,4,3,6,8,5,10,12,9,7,14,16,13,0,15]

A brief explanation of code:

• A=new_list(N+1),A::0..N,A.all_distinct specifies that A is a permutation containing 0 through N inclusive.
• table_in specifies that each tuple of variables must appear in the list of allowed tuples.
  • zip(A,A[2..N+1],A[3..N+1]++[1]) creates the list of 3-tuples that contain 3 consecutive elements of A, plus the last two with constant 1 attached.
  • [{X,Y,Z}:X in 0..N,Y in 0..N,Z in 0..N,...] creates the list of allowed 3-tuples that satisfy the condition "for each prime P, if P is a prime factor of Y, P divides exactly one of X or Z".
  • foreach(P in[2,3,5,7,11,13]) ... end specifies that the loop body must be satisfied for all P's in the list.
  • Y<1;Y mod P>0;X*Z mod P<1,(X+Z)mod P>0 is satisfied if "Y is 0" or "P does not divide Y" or "exactly one of X and Z is divisible by P". ; is logical OR and , is logical AND, and , has higher precedence.
• Finally A.solve invokes the CP solver to instantiate A with the first solution found, if any.

Answer 2

Python + SymPy, 181 169 bytes

lambda n:[l for l in i.permutations(range(n+1))if all((a%f>0)^(c%f>0)for a,b,c in zip(l,l[1:],l[2:]+(1,))for f in sympy.factorint(b)if f)][0]
import itertools as i,sympy

Attempt This Online! (only tests up to n=7 because it gets slow otherwise)

Relatively direct translation of the criteria laid out in the challenge description. No longer has a double application of itertools.pairwise, thanks to one of three improvements by @Jakque.

Ungolfed:

import itertools
import sympy

def f(n):
    # itertools.permutations generates permutations in lexicographic order
    return [lst for lst in itertools.permutations(range(n + 1))
                if meets_conditions(lst)][0]

def meets_conditions(lst):
    # condition 1 is really just condition 2 except there is no successor
    #     for the prime factors to divide; using a successor
    #     that is never divided by any prime factor works just as well
    # the golfed code combines the nested all(all(z for z in y) for y in x)
    #     into the form all(z for y in x for z in y)
    return all(term_meets_conditions(prev, curr, next_)
               for prev, curr, next_ in triplewise(lst + (1,)))

def term_meets_conditions(prev, curr, next_):
    # a XOR b <=> (not a) XOR (not b),
    #     where a and b in this case denote divisibility by the prime factor
    # sympy.factorint(0) returns {0: 1}, so we need to filter out keys of 0
    return all((prev % prime_factor > 0) ^ (next_ % prime_factor > 0)
               for prime_factor in sympy.factorint(curr) if prime_factor != 0)

def triplewise(seq):
    # in the golfed code: zip((l + [x])[0:], (l + [x])[1:], (l + [x])[2:])
    #     is equivalent to zip(l[0:], l[1:], l[2:] + [x])
    return zip(seq[0:], seq[1:], seq[2:])

Answer 3

Jelly, 24 bytes

.ṭ2ịÆfȧḍ¥€Ʋ3ƤḄ3ḍȦ
ŻŒ!ÇƇḢ

A monadic link that accepts a non-negative integer and yields the permutation as a list if possible or the integer zero if not.

Try it online! (Times out for 8 or more.)

How?

Convert condition 1 into another instance of condition 2 by appending a \$\frac{1}{2}\$ to the right of each permutation being tested.

ŻŒ!ÇƇḢ - Main Link: non-negative integer, N
Ż      - zero range -> [0..N]
 Œ!    - all permutations (sorted lexicographically)
    Ƈ  - filter keep those for which:
   Ç   -   call Link 1 - f(Permutation)
     Ḣ - head -> the first remaining Permutation or 0 if none exist

.ṭ2ịÆfȧḍ¥€Ʋ3ƤḄ3ḍȦ - Link 1: Permutation
.ṭ                - tack a 0.5 to the right
           3Ƥ     - for all slices of three values:
          Ʋ       -   last four links as a monad:
  2               -     two
   ị              -     index into -> middle value
    Æf            -     prime factors (1 gives []; 0 gives [0])
         €        -     for each:
        ¥         -       last two links as a dyad - f(Factor, Slice)
       ḍ          -         divides? (vectorises)
      ȧ           -         {Factor} logical AND {that} (replace result at 0 with [0])
             Ḅ    - convert from binary
              3ḍ  - test if 3 divides each (i.e. each was either [0], [1,1,0] or [0,1,1])
                Ạ - any and all?

Answer 4

Charcoal, 106 105 bytes

ＮθＦ…²φＦ⬤υ﹪ικ⊞υι≔Ｅ⊕θΦυ∧ι¬﹪ιλη≔Ｅη⟦κι⟦⟧⟧ζＦζ«≔⊟ιδ≔⊟ιεＦ⊕θ¿¬∨№ικ⊙ε﹪κλ¿⬤δ﹪κλ⊞ζ⁺⁺⟦κ⟧ι⎇§ι⁰⟦⁻§ηκεε⟧⟦⟦⟧§ηκ⟧»Ｉ⌊Φζ›Ｌιθ

Try it online! Link is to verbose version of code. Explanation: Trying an "efficient" (it used to be able to reach n=10 before I finished golfing; Try it online!) algorithm first that can reach n=9 on TIO.

Ｎθ

Input n.

Ｆ…²φＦ⬤υ﹪ικ⊞υι

Find all the primes up to n 1000. (If we could assume that we are only given those inputs that have a valid permutation then by @Bubbler's result we only need the primes up to 13; that would then save a further byte.)

≔Ｅ⊕θΦυ∧ι¬﹪ιλη

For all the numbers up to n, get a list of primes that are factors of it, except for 0, where we use an empty list.

≔Ｅη⟦κι⟦⟧⟧ζ

Starting from the last element in the list working backwards, create trial suffixes of the list containing all potential last elements, their prime factors (which the next number needs to be divisible by) and an empty list of factors that the next number must not be divisible by.

Ｆζ«≔⊟ιδ≔⊟ιε

Loop over the trial suffixes and extract the lists of excluded and required prime factors.

Ｆ⊕θ

Loop over the numbers up to n.

¿¬∨№ικ⊙ε﹪κλ

Ensure that it's not already in the list and is divisible by all of the required prime factors.

¿⬤δ﹪κλ

Ensure that it's not divisible by any of the excluded prime factors.

⊞ζ⁺⁺⟦κ⟧ι⎇§ι⁰⟦⁻§ηκεε⟧⟦⟦⟧§ηκ⟧

Prefix the number to the trial suffix and append the new required and excluded prime factors, which depend on whether the previous trial suffix began with 0; if it did then there are no required prime factors and the excluded prime factors are all of the number's prime factors, while if it didn't then the required prime factors are the number's prime factors that remain after the previously required prime factors are removed and the excluded prime factors are the previously required prime factors.

»Ｉ⌊Φζ›Ｌιθ

Output the lexicographically earliest complete list.

76 bytes for a brute force version that can only handle up to n=7 on ATO:

≔…·⁰Ｎθ≔⟦υ⟧ηＦθ≔ΣＥηＥ⁻θκ⁺κ⟦μ⟧ηＦ✂θ²Ｆ⬤υ﹪ικ⊞υιＩ⌊Φη⬤ι∨¬∧λμ⬤υ∨﹪λν⁻¬﹪§ι⊖μν¬﹪§⁺ι⟦¹⟧⊕μν

Attempt This Online! Link is to verbose version of code. Explanation:

≔…·⁰Ｎθ

Make a list from 0 to n.

≔⟦υ⟧ηＦθ≔ΣＥηＥ⁻θκ⁺κ⟦μ⟧η

Make a list of all of its permutations.

Ｆ✂θ²Ｆ⬤υ﹪ικ⊞υι

Make a list of all the primes up to n.

Ｉ⌊Φη⬤ι∨¬∧λμ⬤υ∨﹪λν⁻¬﹪§ι⊖μν¬﹪§⁺ι⟦¹⟧⊕μν

Find the lexicographically earliest permutation that satisfies the conditions.

Answer 5

JavaScript (Node.js), 163 bytes

f=(n,i=0,...p)=>1/p[n]?p.every((v,j)=>!j||v<2|p.every((u,k)=>k>1&&v%k<!f[f[-~j*k]=k]?p[j-1]%k<1^p[j+1]%k<1:1))&&p:!p.includes(i)&&f(n,0,...p,i)||i-n&&f(n,1+i,...p)

Try it online!

Store non-prime in f

Answer 6

Julia, 253 bytes

We restrict ourselves to cases n <= 16 because a solution exists only in these cases. (Bubbler gives the proof in the comments.)

using Combinatorics;P=[[],[],[2],[3],[2],[5],[2,3],[7],[2],[3],[2,5],[11],[2,3],[13],[2,7],[2,3],[2]];f(n)=for s in permutations(collect(0:n)) d(k,p)=k>n+1 ? false : s[k]%p==0; all(all(d(i,p)!=d(i+2,p) for p in P[s[i+1]+1]) for i in 1:n) && return s end

Answer 7

Ruby, 157 bytes

->n{(r=[0,0,1,8,12,158,853,11000,46988,1134848,4081198,243581246,526635830,44115776240,181186519640,p,231558565690988][n])&&[*0..n].permutation.find{0>r-=1}}

Try it online!

Hardcoded values for 0..14 and 16

Times out on TIO for n>10

Ruby, 184 bytes

->n{[0,2,15,201,2790,39685,580371,14863562,304498540,9687054213,157299614275,8213025950514,257349829821462,10365703842174317,381020573286364067,p,732273679382407884664][n].digits(n+1)}

Try it online!

Still hardcoded but faster.

Answer 8

JavaScript (ES6),  178  162 bytes

f=(n,g,m,...p)=>-~m>>n?p.every((v,i)=>(g=k=>k>v?1:v%k?g(k+1):!(p[i-1]%k)^i<n-1&!(p[i+1]%k)&&g(k,v/=k))(2))?o=p:0:(g=i=>i--?g(i,m&1<<i||f(n,0,m|1<<i,...p,i)):o)(n)

Try it online!