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,1

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).

Links

Table of n, a(n) for n=1..69.

Example

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,
...

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 *)

Prog

(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))

Crossrefs

Cf. A350314, A350315, A181830, A000255.

Sequence in context: A330402 A075302 A352520 * A257911 A257882 A326766

Adjacent sequences: A350310 A350311 A350312 * A350314 A350315 A350316

Keyword

nonn

Author

Peter Luschny, Dec 24 2021

Status

approved