A396071 - OEIS

%I #39 Jul 11 2026 16:26:23

%S 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,

%T 24,24,28,29,30,27,32,33,34,31,36,37,38,35,40,41,42,38,40,45,46,41,46,

%U 46,50,45,52,48,54,49,56,57,58,52,60,61,56,55,64,65,66,59

%N 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}.

%H Yifan Xie, <a href="/A396071/b396071.txt">Table of n, a(n) for n = 1..146</a>

%H Art of Problem Solving, <a href="https://artofproblemsolving.com/community/c6h3812998p37777591">Serbia National Math Olympiad 2026 Problem 1</a>

%H Yifan Xie, <a href="/A396071/a396071.py.txt">Python program</a>

%H Yifan Xie, <a href="/A396071/a396071_1.pdf">Proof of the formulas</a>

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

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

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

%e 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.

%e 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.

%Y Cf. A397403.

%K nonn,new

%O 1,2

%A _Yifan Xie_, Jun 16 2026