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

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, 73, 108, 85, 78, 75, 102, 239, 74, 97, 74, 115, 102, 125, 110, 191, 108, 123, 118, 151, 140, 149, 162, 331, 134, 133, 128, 201, 184, 217, 178, 299, 202, 163, 178, 251

Offset

1,1

Comments

a(n) is always greater than n.

Links

Table of n, a(n) for n=1..60.

Project Euler, Problem 801: x^y == y^x, (2022)

Formula

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

Prog

(Python)
def a(n):
  count = 0
  for x in range(0, n + 1):
    for y in range(0, n + 1):
      if x == y or pow(x, y, n) == pow(y, x, n): count += 1
  return count
(PARI) a(n) = sum(x=0, n, sum(y=0, n, Mod(x, n)^y == Mod(y, n)^x)); \\ Michel Marcus, Jan 16 2023

Crossrefs

Cf. A355069.

Sequence in context: A200592 A021027 A289672 * A361849 A339409 A075246

Adjacent sequences: A359861 A359862 A359863 * A359865 A359866 A359867

Keyword

nonn

Author

Darío Clavijo, Jan 16 2023

Status

approved