2022/06/03 by Carl Pomerance, Pomerance, Carl
Computer Science · Mathematics · #05A05 #05A16 #11A05 #11B75 #11N45 #Advanced Combinatorial Mathematics #Analytic Number Theory Research #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2206.01699
openalex publication_date 2022/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let S\rm lcm(n) denote the set of permutations π of [n]=\1,2,…,n\ such that \rm lcm[j,π(j)]≤ n for each j∈[n]. Further, let S\rm div(n) denote the number of permutations π of [n] such that j|π(j) or π(j)| j for each j∈[n]. Clearly S\rm div(n)⊂ S\rm lcm(n). We get upper and lower bounds for the counts of these sets, showing they grow geometrically. We also prove a conjecture from a recent paper on the number of "anti-coprime" permutations of [n], meaning that each gcd(j,π(j))>1 except when j=1.