A380816 Number of pairs (x, y) with 0 < x < y < n such that x^y = y^x modulo n.

0, 0, 0, 0, 1, 1, 5, 2, 2, 3, 5, 6, 8, 8, 6, 18, 11, 7, 20, 16, 15, 17, 28, 28, 15, 23, 32, 27, 24, 22, 35, 88, 20, 31, 19, 34, 32, 43, 35, 72, 33, 40, 37, 52, 45, 51, 57, 134, 36, 37, 38, 73, 65, 73, 61, 118, 72, 52, 59, 94, 61, 74, 111, 428, 67, 65, 69

Offset: 1

Author

Peter Schorn, Feb 04 2025

Keywords

• nonn
• nice

Examples

			For n < 5 there are no (x, y) with 0 < x < y < n such that x^y = y^x modulo n. Therefore a(n) = 0.
For n = 5 and 6 there is only 2^4 = 4^2 modulo n which makes a(5) = a(6) = 1.
For n = 7, there is 2^4=4^2, 2^5=5^2, 2^6=6^2, 4^5=5^4 and 4^6=6^4 modulo 7 which makes a(7) = 5.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..1000

Programs

Mathematica

A380816[n_] := Sum[Boole[PowerMod[x, y, n] == PowerMod[y, x, n]], {x, 2, n-2}, {y, x+1, n-1}];
Array[A380816, 100] (* Paolo Xausa, Mar 17 2025 *)

PARI

a(n)={my(c=0);for(x=1,n-1,for(y=x+1,n-1,if(Mod(x,n)^y==Mod(y,n)^x,c++)));c}

Python

def A380816(n): return sum(1 for x in range(1,n-1) for y in range(x+1,n) if pow(x,y,n)==pow(y,x,n)) # Chai Wah Wu, Feb 12 2025