cp's OEIS Frontend

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

%I A350313 #11 Dec 25 2021 06:46:10
%S A350313 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 A350313 28,29,24,31,32,33,34,35,36,37,30,39,40,41,38,43,44,45,46,47,42,49,50,
%U A350313 51,52,53,48,55,56,57,58,59,54,61,62,63,64,65,66,67,60,69,70
%N A350313 The Redstone permutation: a(1) = 2, a(2) = 1, otherwise the smallest number not occurring earlier which is strongly prime to n.
%C A350313 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 A350313 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 A350313 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 A350313 Catch-up points and initial segments:
%e A350313 [ 2]  2,  1,
%e A350313 [ 5]  4,  5,  3,
%e A350313 [11]  7,  8,  9, 10, 11,  6,
%e A350313 [17] 13, 14, 15, 16, 17, 12,
%e A350313 [23] 19, 20, 21, 22, 23, 18,
%e A350313 [29] 25, 26, 27, 28, 29, 24,
%e A350313 [37] 31, 32, 33, 34, 35, 36, 37, 30,
%e A350313 [41] 39, 40, 41, 38,
%e A350313 [47] 43, 44, 45, 46, 47, 42,
%e A350313 [53] 49, 50, 51, 52, 53, 48,
%e A350313 ...
%t A350313 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 A350313 (SageMath)
%o A350313 def generatePermutation(N, condition):
%o A350313     a = {1:2, 2:1}; n = Integer(2)
%o A350313     notYetOccured = [Integer(i) for i in range(3, N + 1)]
%o A350313     while notYetOccured != []:
%o A350313         n += 1
%o A350313         found = False
%o A350313         for r in notYetOccured:
%o A350313             if condition(r, n):
%o A350313                 a[n] = r
%o A350313                 notYetOccured.remove(r)
%o A350313                 found = True
%o A350313                 break
%o A350313         if not found: break
%o A350313     return [a[i] for i in range(1, n)]
%o A350313 def isPrimeTo(m, n): return gcd(m, n) == 1
%o A350313 def isStrongPrimeTo(m, n): return isPrimeTo(m, n) and not m.divides(n - 1)
%o A350313 print(generatePermutation(70, isStrongPrimeTo))
%Y A350313 Cf. A350314, A350315, A181830, A000255.
%K A350313 nonn
%O A350313 1,1
%A A350313 _Peter Luschny_, Dec 24 2021