login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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^(n-1), 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..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

(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 A159272

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 21:15 EST 2017. Contains 295919 sequences.