

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)).
Similar (if not the same) coincidences and differences occur between A072995 and A050399. Sequence A072989 lists these indices.  M. F. Hasler, Feb 23 2014


LINKS

T. D. Noe, Table of n, a(n) for n=1..10000


FORMULA

For n>0, a(A003277(n)) = 1, a(2^n) = 2^(n1), a(A065119(n)) = A065119(n)/3.
For n>1, a(A026383(n)) = A026383(n)/5.


MAPLE

1, seq(nops(select(t > t^n mod n = 1, [$1..n1])), 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

(PARI) A072994=n>sum(k=1, n, Mod(k, n)^n==1) \\ M. F. Hasler, Feb 23 2014


CROSSREFS

Sequence in context: A200219 A270120 A009195 * A052126 A094521 A321757
Adjacent sequences: A072991 A072992 A072993 * A072995 A072996 A072997


KEYWORD

easy,nonn


AUTHOR

Benoit Cloitre, Aug 21 2002


EXTENSIONS

Corrected by T. D. Noe, May 19 2007


STATUS

approved



