|
|
A350313
|
|
The Redstone permutation: a(1) = 2, a(2) = 1, otherwise the smallest number not occurring earlier which is strongly prime to n.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|