A350313 - OEIS

%I #11 Dec 25 2021 06:46:10

%S 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,

%T 28,29,24,31,32,33,34,35,36,37,30,39,40,41,38,43,44,45,46,47,42,49,50,

%U 51,52,53,48,55,56,57,58,59,54,61,62,63,64,65,66,67,60,69,70

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

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

%C 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.

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

%e Catch-up points and initial segments:

%e [ 2]  2,  1,

%e [ 5]  4,  5,  3,

%e [11]  7,  8,  9, 10, 11,  6,

%e [17] 13, 14, 15, 16, 17, 12,

%e [23] 19, 20, 21, 22, 23, 18,

%e [29] 25, 26, 27, 28, 29, 24,

%e [37] 31, 32, 33, 34, 35, 36, 37, 30,

%e [41] 39, 40, 41, 38,

%e [47] 43, 44, 45, 46, 47, 42,

%e [53] 49, 50, 51, 52, 53, 48,

%e ...

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

%o (SageMath)

%o def generatePermutation(N, condition):

%o     a = {1:2, 2:1}; n = Integer(2)

%o     notYetOccured = [Integer(i) for i in range(3, N + 1)]

%o     while notYetOccured != []:

%o         n += 1

%o         found = False

%o         for r in notYetOccured:

%o             if condition(r, n):

%o                 a[n] = r

%o                 notYetOccured.remove(r)

%o                 found = True

%o                 break

%o         if not found: break

%o     return [a[i] for i in range(1, n)]

%o def isPrimeTo(m, n): return gcd(m, n) == 1

%o def isStrongPrimeTo(m, n): return isPrimeTo(m, n) and not m.divides(n - 1)

%o print(generatePermutation(70, isStrongPrimeTo))

%Y Cf. A350314, A350315, A181830, A000255.

%K nonn

%O 1,1

%A _Peter Luschny_, Dec 24 2021