|
%I #18 Jul 19 2019 17:54:40
%S 1,2,3,4,5,6,7,7,8,9,10,10,11,12,12,12,13,14,15,15,15,16,17,17,18,19,
%T 20,20,21,21,22,22,22,23,23,23,24,25,25,25,26,26,27,27,27,28,29,29,30,
%U 31,31,31,32,33,33,33,33,34,35,35,36,37,37,37,37,37,38,38,38,38,39,39,40,41,41,41,41,41,42,42,43,44,45,45,45,46,46,46,47,47,47,47,47,48,48,48,49,50,50,50
%N The number of positive integers that are less than or equal to n that have a primitive root.
%C Equivalently a(n) is the number of positive integers less than or equal to n that are 1,2,4 or of the form p^i or 2*p^i where p is an odd prime.
%C a(10^k) for k=1,2,...,7: 9, 50, 293, 1969, 14889, 120424, 1014032.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimitiveRoot.html">Primitive Root</a>
%F a(n) ~ 3/2 * n/log(n). - _Vaclav Kotesovec_, Dec 20 2014
%e a(12)=10 because there are 10 positive integers that are less than or equal to 12 that have a primitive root:1,2,3,4,5,6,7,9,10,11.
%t Table[Length[Select[Range[2, n], IntegerQ[PrimitiveRoot[#]] &]] +
%t 1, {n, 1, 100}]
%t Accumulate[Table[If[Length[PrimitiveRootList[n]]>0,1,0],{n,100}]]+1 (* _Harvey P. Dale_, Jul 19 2019 *)
%Y Cf. A033948.
%K nonn
%O 1,2
%A _Geoffrey Critzer_, Dec 19 2014
|
