A252649 The number of positive integers that are less than or equal to n that have a primitive root.

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, 20, 20, 21, 21, 22, 22, 22, 23, 23, 23, 24, 25, 25, 25, 26, 26, 27, 27, 27, 28, 29, 29, 30, 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

Offset

1,2

Comments

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.

a(10^k) for k=1,2,...,7: 9, 50, 293, 1969, 14889, 120424, 1014032.

Links

Table of n, a(n) for n=1..100.

Eric Weisstein's World of Mathematics, Primitive Root

Formula

a(n) ~ 3/2 * n/log(n). - Vaclav Kotesovec, Dec 20 2014

Example

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.

Mathematica

Table[Length[Select[Range[2, n], IntegerQ[PrimitiveRoot[#]] &]] +
  1, {n, 1, 100}]
Accumulate[Table[If[Length[PrimitiveRootList[n]]>0, 1, 0], {n, 100}]]+1 (* Harvey P. Dale, Jul 19 2019 *)

Crossrefs

Cf. A033948.

Sequence in context: A337979 A265359 A271490 * A095703 A101041 A093697

Adjacent sequences: A252646 A252647 A252648 * A252650 A252651 A252652

Keyword

nonn

Author

Geoffrey Critzer, Dec 19 2014

Status

approved