login
A373768
Number of permutations of {1...n} P such that P <= R, lexicographically, for all R that is a root of P (i.e., R^k = P for some k).
0
1, 1, 2, 5, 15, 57, 308, 1731, 12276, 97646, 884948, 8069602, 90805706
OFFSET
0,3
COMMENTS
All permutations that satisfy this property can be found using an algorithm that is akin to the sieve of Eratosthenes.
EXAMPLE
a(3) = 5; the sole permutation not counted is P = (3,1,2) since it fails to have P <= R at root R = (2,3,1) (that R being P = R^2 in this case).
PROG
(Python)
from itertools import permutations
def a(n):
perms = permutations(range(n))
not_term = set()
i = 0
for p in perms:
if p not in not_term:
P = tuple(p[i] for i in p)
while P != p:
not_term.add(P)
P = tuple(p[i] for i in P)
i += 1
return i
CROSSREFS
Sequence in context: A351158 A187981 A334155 * A348365 A048192 A078792
KEYWORD
nonn,hard,more
AUTHOR
Bryle Morga, Jun 18 2024
EXTENSIONS
a(12) from Michael S. Branicky, Jun 18 2024
STATUS
approved