A359864 - OEIS

%I #25 Jul 12 2023 11:20:00

%S 4,3,4,7,8,9,18,19,18,17,22,27,30,31,28,67,40,37,60,55,52,57,80,87,64,

%T 73,108,85,78,75,102,239,74,97,74,115,102,125,110,191,108,123,118,151,

%U 140,149,162,331,134,133,128,201,184,217,178,299,202,163,178,251

%N a(n) is the number of solutions to the congruence x^y == y^x (mod n) where 0 <= x,y <= n.

%C a(n) is always greater than n.

%H Project Euler, <a href="https://projecteuler.net/problem=801">Problem 801: x^y == y^x</a>, (2022)

%F a(n) = Sum_{x=0..n} Sum_{y=0..n} [x^y == y^x (mod n)].

%o (Python)

%o def a(n):

%o   count = 0

%o   for x in range(0, n + 1):

%o     for y in range(0, n + 1):

%o       if x == y or pow(x, y, n) == pow(y, x, n): count += 1

%o   return count

%o (PARI) a(n) = sum(x=0, n, sum(y=0, n, Mod(x, n)^y == Mod(y, n)^x)); \\ _Michel Marcus_, Jan 16 2023

%Y Cf. A355069.

%K nonn

%O 1,1

%A _Darío Clavijo_, Jan 16 2023