|
|
A072994
|
|
Number of solutions to x^n==1 (mod n), 1<=x<=n.
|
|
7
|
|
|
1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 8, 3, 2, 1, 8, 5, 2, 9, 4, 1, 4, 1, 16, 1, 2, 1, 12, 1, 2, 3, 16, 1, 12, 1, 4, 3, 2, 1, 16, 7, 10, 1, 8, 1, 18, 5, 8, 3, 2, 1, 16, 1, 2, 9, 32, 1, 4, 1, 8, 1, 4, 1, 24, 1, 2, 5, 4, 1, 12, 1, 32, 27, 2, 1, 24, 1, 2, 1, 8, 1, 12, 1, 4, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
More generally, if the equation a(x)*m=x has solutions, solutions are congruent to m: a(x)*7=x for x=7, 14, 21, 28, 49, 56, 63, 98, 112, ... . There are some composite values of m such that a(x)*m=x has solutions, as m=15. a(n) coincides with A009195(n) at many values of n, but not at n = 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, ... . It seems also that for n large enough sum_{k=1..n} a(k) > n*log(n)*log(log(n)).
|
|
LINKS
|
|
|
FORMULA
|
|
|
MAPLE
|
1, seq(nops(select(t -> t^n mod n = 1, [$1..n-1])), n=2..100); # Robert Israel, Dec 07 2014
|
|
MATHEMATICA
|
f[n_] := (d = If[ OddQ@ n, 1, 2]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = f[2] = 1; Array[f, 93] (* or *)
f[n_] := Length@ Select[ Range@ n, PowerMod[#, n, n] == 1 &]; f[n_] := 1 /; n<2; Array[f, 93] (* Robert G. Wilson v, Dec 06 2014 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|