A396071 a(n) is the maximum number of distinct residues modulo n among {i*f(i): 1 <= i <= n}, as f ranges over all permutations of {1, 2, ..., n}.

1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 12, 13, 14, 13, 16, 16, 18, 17, 20, 21, 22, 21, 23, 25, 24, 24, 28, 29, 30, 27, 32, 33, 34, 31, 36, 37, 38, 35, 40, 41, 42, 38, 40, 45, 46, 41, 46, 46, 50, 45, 52, 48, 54, 49, 56, 57, 58, 52, 60, 61, 56, 55, 64, 65, 66, 59

Offset

1,2

Links

Yifan Xie, Table of n, a(n) for n = 1..146

Art of Problem Solving, Serbia National Math Olympiad 2026 Problem 1

Yifan Xie, Python program

Yifan Xie, Proof of the formulas

Formula

If n <= 2, a(n) = n;

If n > 2 is squarefree, a(n) = n - 1;

If p^2 divides n, where p is a prime, a(n) <= n*(2*p^2 - p + 1)/(2*p^2).

Example

For n = 6, one permutation that realizes the maximum value is 1, 2, 3, 6, 4, 5. There are 5 distinct residues mod 6 among {1*1, 2*2, 3*3, 4*6, 5*4, 6*5}. Hence a(6) = 5.
For n = p, where p is an odd prime, one permutation f that realizes the maximum value is f(x) = 1 + x^(-1) for 1 <= x <= p-2, f(p-1) = p and f(p) = 1, where x^(-1) is the inverse of x modulo p.

Crossrefs

Cf. A397403.

Sequence in context: A289188 A111633 A273662 * A034138 A254667 A011879

Adjacent sequences: A396068 A396069 A396070 * A396072 A396073 A396074

Keyword

nonn,new

Author

Yifan Xie, Jun 16 2026

Status

approved