|
%I #31 Dec 08 2014 02:56:20
%S 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,
%T 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,
%U 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
%N Number of solutions to x^n==1 (mod n), 1<=x<=n.
%C 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)).
%C Similar (if not the same) coincidences and differences occur between A072995 and A050399. Sequence A072989 lists these indices. - _M. F. Hasler_, Feb 23 2014
%H T. D. Noe, <a href="/A072994/b072994.txt">Table of n, a(n) for n=1..10000</a>
%F For n>0, a(A003277(n)) = 1, a(2^n) = 2^(n-1), a(A065119(n)) = A065119(n)/3.
%F For n>1, a(A026383(n)) = A026383(n)/5.
%p 1, seq(nops(select(t -> t^n mod n = 1, [$1..n-1])),n=2..100); # _Robert Israel_, Dec 07 2014
%t 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 *)
%t 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 *)
%o (PARI) A072994=n->sum(k=1,n,Mod(k,n)^n==1) \\ _M. F. Hasler_, Feb 23 2014
%K easy,nonn
%O 1,4
%A _Benoit Cloitre_, Aug 21 2002
%E Corrected by _T. D. Noe_, May 19 2007
|
