A117986 Number of functions f:[n]->[n] such that f[(x*y) mod n]=[f(x)*f(y)] mod n for all x,y in [n], for n=1,2,3,... Here [n] denotes {0,1,2,...,n-1}.

1, 3, 4, 6, 6, 35, 8, 50, 20, 55, 12, 160, 14, 75, 160, 194, 18, 195, 20, 256, 220, 115, 24, 3936, 102, 135, 164, 352, 30, 5301, 32, 770, 340, 175, 352, 2496, 38, 195, 400, 6396, 42, 7353, 44, 544, 928, 235, 48, 15456, 296, 1015, 520, 640, 54, 1635, 544, 8856

Offset

1,2

Comments

If, instead, the modular functional equation f[(x+y) mod n]=[f(x)+f(y)] mod n is considered, it is found that for each n=1,2,3,... there appears to be exactly n functions with the desired property. See A117987 and A117988 for results on other modular functional equations.

Links

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

Rémy Sigrist, C++ program for A117986

Formula

Apparently, a(p) = p + 1 for any prime number p. - Rémy Sigrist, Sep 19 2019

Example

For n=5 the six functions are (0,0,0,0,0), (0,1,1,1,1), (1,1,1,1,1), (0,1,4,4,1), (0,1,3,2,4), (0,1,2,3,4). For the 5th of these, (0,1,3,2,4), the x=2, y=3 case is verified by the calculations f(2*3 mod 4) = f(1) = 1 and f(2)*f(3) mod 5 = 3*2 mod 5 = 1.

Prog

(C++) See Links section.

Crossrefs

Cf. A117987, A117988.

Sequence in context: A349217 A065967 A345209 * A248738 A070737 A225647

Adjacent sequences: A117983 A117984 A117985 * A117987 A117988 A117989

Keyword

nonn

Author

John W. Layman, Apr 07 2006

Extensions

More terms from Rémy Sigrist, Sep 19 2019

Status

approved