A350313 The Redstone permutation: a(1) = 2, a(2) = 1, otherwise the smallest number not occurring earlier which is strongly prime to n.

2, 1, 4, 5, 3, 7, 8, 9, 10, 11, 6, 13, 14, 15, 16, 17, 12, 19, 20, 21, 22, 23, 18, 25, 26, 27, 28, 29, 24, 31, 32, 33, 34, 35, 36, 37, 30, 39, 40, 41, 38, 43, 44, 45, 46, 47, 42, 49, 50, 51, 52, 53, 48, 55, 56, 57, 58, 59, 54, 61, 62, 63, 64, 65, 66, 67, 60, 69, 70

Offset: 1

Author

Peter Luschny, Dec 24 2021

Keywords

• nonn

Comments

We say 'k is strongly prime to n' if and only if k is prime to n and k does not divide n - 1 (see A181830).

The sequence is a fixed-point-free permutation of the positive integers beginning with 2. According to Don Knuth, the number of fixed-point-free permutations beginning with 2 of [n] = {1, 2, ..., n} were already computed by Euler, see A000255.

We say n is a 'catch-up point' of a permutation p of the positive integers if and only if p restricted to [n] is a permutation of [n]. The catch-up points of this sequence start 2, 5, 11, 17, ... and are in A350314. This structure allows the sequence to be seen as an irregular triangle, as shown in the example section. The lengths of the resulting rows are a periodic sequence (see A350315).

Examples

			Catch-up points and initial segments:
[ 2]  2,  1,
[ 5]  4,  5,  3,
[11]  7,  8,  9, 10, 11,  6,
[17] 13, 14, 15, 16, 17, 12,
[23] 19, 20, 21, 22, 23, 18,
[29] 25, 26, 27, 28, 29, 24,
[37] 31, 32, 33, 34, 35, 36, 37, 30,
[41] 39, 40, 41, 38,
[47] 43, 44, 45, 46, 47, 42,
[53] 49, 50, 51, 52, 53, 48,
...
		

Crossrefs

Cf. A350314, A350315, A181830, A000255.

Programs

Mathematica

s = {2, 1}, c[] = 0; Array[Set[c[s[[#]]], #] &, Length[s]]; j = Last[s]; u = 3; s~Join~Reap[Monitor[Do[If[j == u, While[c[u] > 0, u++]]; k = u; While[Nand[c[k] == 0, CoprimeQ[i, k], ! Divisible[i - 1, k]], k++]; Sow[k]; Set[c[k], i]; j = k, {i, Length[s] + 1, 69}], i]][[-1, -1]] (* _Michael De Vlieger, Dec 24 2021 *)

SageMath

def generatePermutation(N, condition):
    a = {1:2, 2:1}; n = Integer(2)
    notYetOccured = [Integer(i) for i in range(3, N + 1)]
    while notYetOccured != []:
        n += 1
        found = False
        for r in notYetOccured:
            if condition(r, n):
                a[n] = r
                notYetOccured.remove(r)
                found = True
                break
        if not found: break
    return [a[i] for i in range(1, n)]
def isPrimeTo(m, n): return gcd(m, n) == 1
def isStrongPrimeTo(m, n): return isPrimeTo(m, n) and not m.divides(n - 1)
print(generatePermutation(70, isStrongPrimeTo))