A008330 -id:A008330 - cp's OEIS frontend

A128860 Let p be the n-th odd prime; a(n) is the number of primitive roots of p which are relatively prime to p-1.

0, 1, 1, 1, 2, 4, 1, 6, 5, 3, 5, 6, 3, 13, 11, 10, 5, 5, 10, 8, 9, 16, 19, 11, 16, 10, 22, 13, 23, 12, 15, 30, 9, 35, 8, 17, 15, 46, 41, 37, 14, 34, 20, 36, 16, 10, 21, 49, 26, 54, 43, 17, 38, 64, 71, 65, 23, 32, 33, 22, 71, 30, 56, 28, 77, 16, 26, 79, 38, 74

Offset: 1

N. J. A. Sloane, Apr 20 2007

The number of primitive roots without the restriction of relative primality is in A008330, so a(n) <= A008330(n+1). A table of prime moduli is in A128250. - R. J. Mathar, Oct 31 2007

R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, Austin, TX, 1961, pp. 69-70.

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

A128250 := proc(g,p) local k ; if gcd(g,p) > 1 then RETURN(0) ; fi ; for k from 1 do if (g^k mod p ) = 1 then RETURN(k) ; fi ; od: end: proots := proc(p) local a,g ; a := 0 ; for g from 1 to p do if A128250(g,p) = p-1 and gcd(g,p-1) = 1 then a := a+1 ; fi ; od: RETURN(a) ; end: A128860 := proc(n) local p; p := ithprime(n+1) ; proots(p) ; end: seq(A128860(n),n=1..60) ; # R. J. Mathar, Oct 31 2007

a[n_] := Count[PrimitiveRootList[(p = Prime[n+1])], ?(CoprimeQ[#, (p-1)] &)]; Array[a, 70] (* _James C. McMahon, Jan 12 2025 *)

More terms from R. J. Mathar, Oct 31 2007

A251865 Irregular triangle read by rows in which row n lists the maximal-order elements (

Original entry on oeis.org

0, 1, 2, 3, 2, 3, 5, 3, 5, 3, 5, 7, 2, 5, 3, 7, 2, 6, 7, 8, 5, 7, 11, 2, 6, 7, 11, 3, 5, 2, 7, 8, 13, 3, 5, 11, 13, 3, 5, 6, 7, 10, 11, 12, 14, 5, 11, 2, 3, 10, 13, 14, 15, 3, 7, 13, 17, 2, 5, 10, 11, 17, 19, 7, 13, 17, 19, 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 5, 7, 11, 13, 17, 19, 23, 2, 3, 8, 12, 13, 17, 22, 23

Offset: 1

Eric Chen, May 20 2015

Conjecture: Triangle contains all nonsquare numbers infinitely many times.
The orders of the numbers in n-th row mod n are equal to A002322(n).
First and last terms of the n-th row are A111076(n) and A247176(n).
Length of the n-th row is A111725(n).
The n-th row is the same as A046147 for n with primitive roots.

			Read by rows:
n     maximal-order elements (<n) mod n
1     0
2     1
3     2
4     3
5     2, 3
6     5
7     3, 5
8     3, 5, 7
9     2, 5
10    3, 7
11    2, 6, 7, 8
12    5, 7, 11
13    2, 6, 7, 11
14    3, 5
15    2, 7, 8, 13
16    3, 5, 11, 13
17    3, 5, 6, 7, 10, 11, 12, 14
18    5, 11
19    2, 3, 10, 13, 14, 15
20    3, 7, 13, 17
etc.

Eric Chen, First 160 rows of triangle, flattened
Eric Chen, First 1000 rows of triangle

Cf. A111076, A247176, A111725, A046147, A046145, A046146, A046144, A060749, A001918, A071894, A008330.

a[n_] := Select[Range[0, n-1], GCD[#, n] == 1 && MultiplicativeOrder[#, n] == CarmichaelLambda[n]& ]; Table[a[n], {n, 1, 36}]

c(n)=lcm((znstar(n))[2])
a(n)=for(k=0,n-1,if(gcd(k, n)==1 && znorder(Mod(k,n))==c(n), print1(k, ",")))
n=1; while(n<37, a(n); n++)

A266988 The indices of primes for which the average of the primitive roots is < p/2.

Original entry on oeis.org

11, 14, 19, 48, 75, 94, 114, 115, 117, 124, 149, 153, 155, 177, 182, 224, 272, 300, 324, 348, 351, 365, 370, 403, 465, 510, 515, 522, 531, 546, 555, 578, 614, 634, 667, 677, 683, 707, 748, 765, 788, 795, 802, 808, 832, 850, 871, 876, 886, 888, 966, 980

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

These primes are all of the form p==3 (mod 4). (conjecture)

			p(a[1])=p(11)=31. The primitive roots of 31 are 3, 11, 12, 13, 17, 21, 22, and 24.
Their average is (3+11+12+13+17+21+22+24)/phi(30)=123/8<31/2.

Cf. A008330, A060749, A088144, A266989.

A = Table[Total[Flatten[Position[Table[MultiplicativeOrder[i, Prime[k]], {i, Prime[k] - 1}],Prime[k] - 1]]]/(EulerPhi[Prime[k] - 1] Prime[k]/2), {k, 1, 1000}];Flatten[Position[A, _?(# < 1 &)]]

A280729 (p-1)/2 + phi(p-1) as p runs through the odd primes.

Original entry on oeis.org

2, 4, 5, 9, 10, 16, 15, 21, 26, 23, 30, 36, 33, 45, 50, 57, 46, 53, 59, 60, 63, 81, 84, 80, 90, 83, 105, 90, 104, 99, 113, 132, 113, 146, 115, 126, 135, 165, 170, 177, 138, 167, 160, 182, 159, 153, 183, 225, 186, 228, 215, 184, 225, 256, 261, 266, 207, 226, 236, 233

Offset: 1

Vincenzo Librandi, Jan 10 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A098006.

[(NthPrime(n)-1)/2+EulerPhi(NthPrime(n)-1): n in [2..100]];

A280729 := proc(n)
    local p;
    p := ithprime(n+1) ;
    (p-1)/2+numtheory[phi](p-1) ;
end proc: # R. J. Mathar, Jan 10 2017

Table[(n - 1)/2 + EulerPhi[n - 1], {n, Prime[Range[2, 100]]}]

a(n) = A098006(n)+2*A008330(n). - R. J. Mathar, Jan 10 2017

A286510 Number of primitive roots g mod prime(n) for which there is no solution to g^x == x (mod p) with 2 <= x <= prime(n)-2.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 2, 1, 6, 5, 2, 9, 11, 12, 5, 7, 9, 8, 8, 17, 12, 11, 16, 12, 23, 20, 16, 17, 17, 23, 17, 26, 18, 19, 25, 26, 32, 38, 21, 21, 18, 27, 25, 24, 27, 52, 30, 44, 33, 19, 44, 54, 45, 57, 14, 29, 27, 39, 58, 28, 41, 39, 62, 26, 25, 69, 48, 51, 61, 44, 47, 37, 63, 77, 55, 55, 41

Offset: 1

Robert Israel, May 10 2017

nonn

Robert Israel, Table of n, a(n) for n = 1..1000
M. Levin, C. Pomerance, K. Soundararajan, Fixed Points for Discrete Logarithms. In: Hanrot G., Morain F., Thomé E. (eds) Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg (2010).
Math Overflow, Fixed points of g^x (modulo a prime)

Cf. A008330, A174407.

f:= proc(n) local p, r, S, R,x;
   p:= ithprime(n);
   r:= numtheory:-primroot(p);
   S:= select(t -> igcd(t,p-1) = 1, {$1..p-1});
   R:= map(s -> r &^ s mod p, S);
   for x from 2 to p-2 do
     R:= remove(t -> (t &^ x - x mod p = 0), R);
   od;
   nops(R);
end proc;
map(f, [$1..100]);

Join[{1}, Table[p = Prime[n]; EulerPhi[EulerPhi[p]] - Length[Select[ PrimitiveRootList[p], MemberQ[PowerMod[#, Range[p-1], p] - Range[p-1], 0] &]], {n, 2, 100}]] (* Jean-François Alcover, Oct 11 2020, after T. D. Noe in A174407 *)

a(n) = A008330(n) - A174407(n) for n >= 2.

A293605 Primes p such that phi(p-1) < (p-1)/4.

Original entry on oeis.org

211, 331, 421, 631, 661, 991, 1051, 1171, 1321, 1471, 1951, 2311, 2341, 2521, 2731, 2971, 3121, 3301, 3361, 3511, 3571, 3631, 4201, 4621, 4831, 4951, 5281, 5851, 5881, 6007, 6091, 6271, 6301, 7351, 7411, 7561, 7591, 8191, 8581, 8779, 8821, 8971, 9241, 9283, 9661, 9871, 9901

Offset: 1

Michel Marcus, Oct 13 2017

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Tamiru Jarso and Tim Trudgian, Quadratic non-residues that are not primitive roots, Mathematics of Computation, Vol. 88, No. 317 (2019), pp. 1251-1260; arXiv preprint, arXiv:1710.04320 [math.NT], 2017.

Cf. A000010, A008330, A241196.

Select[Prime[Range[1500]],EulerPhi[#-1]<(#-1)/4&] (* Harvey P. Dale, Oct 27 2018 *)

lista(nn) = forprime(p=2, nn, if (eulerphi(p-1) < (p-1)/4, print1(p, ", ")));

A303549 Lesser of twin primes p for which phi(p-1) = phi(p+1), where phi(n) is the Euler totient function (A000010).

Original entry on oeis.org

5, 11, 71, 2591, 208391, 16692551, 48502931, 92012201, 249206231, 419445251, 496978301, 1329067391, 1837151681, 2277479051, 2647600061, 4733566391, 6435087011, 10327948751, 14089345691, 14923624031, 22415286251, 27508270301, 39662281331, 59013882071, 70353395351

Offset: 1

Amiram Eldar, Apr 26 2018

nonn

Intersection of A001359 and A067890 (or A066812).

The terms below 10^8 were taken from the paper by Garcia et al.

			p = 5 is the lesser of the twin primes (5, 7), and phi(5-1) = phi(5+1) = 2.

Stephan Ramon Garcia, Elvis Kahoro and Florian Luca, Primitive root bias for twin primes, Experimental Mathematics (2017), pp. 1-10, alternative link, preprint, arXiv:1705.02485 [math.NT], 2017.

Cf. A000010, A001359, A006512, A008330, A066812, A067890, A067933, A286714, A286715.

seq={}; Do[p = Prime[i]; If[PrimeQ[p+2] && EulerPhi[p-1] == EulerPhi[p+1], AppendTo[seq, p]], {i, 1, 1000000}]; seq

isok(p) = isprime(p) && isprime(p+2) && (eulerphi(p-1) == eulerphi(p+1)); \\ Michel Marcus, Apr 26 2018

a(12)-a(16) from Michel Marcus, Apr 26 2018

a(17)-a(25) from Giovanni Resta, Apr 26 2018

A326356 Lesser of twin primes p >= 5 for which phi(p+1)/phi(p-1) reaches record value, where phi(n) is the Euler totient function (A000010).

Original entry on oeis.org

5, 2381, 3851, 20021, 50051, 52361, 424271, 470471, 602141, 2302301, 6806801, 16926911, 17497481, 69989921, 78278201, 183953771, 242662421, 468818351, 2156564411, 24912037151, 43874931101, 73769375681, 131104243271, 1360122864101, 1943064533411, 2635321709021, 3075260848661, 4078063299311

Offset: 1

Amiram Eldar, Sep 11 2019

nonn

Terms a(2)-a(23) were taken from the paper by Garcia et al.
Garcia et al. proved that assuming Dickson's conjecture, {phi(p+1)/phi(p-1) : p and p+2 are prime} is dense in [0, oo), and thus this sequence is infinite.
They give an example of a term p with 1099 digits with phi(p+1)/phi(p-1) = 3.11615...
What is the least value of lesser of twin primes p such that phi(p+1)/phi(p-1) > 2?
A candidate is p = 8183287190196092135163947564054981234789530779544672356881 for which the ratio is equal to 2.00047615... . - Giovanni Resta, Nov 01 2019

			The values of phi(p+1)/phi(p-1) for the first terms are 1 < 1.031... < 1.06 < 1.118... < 1.12 < ...

Stephan Ramon Garcia, Florian Luca, Kye Shi, Gabe Udell, Primitive root bias for twin primes II: Schinzel-type theorems for totient quotients and the sum-of-divisors function, arXiv:1906.05927 [math.NT], 2019.
Wikipedia, Dickson's conjecture.

Cf. A000010, A001359, A006512, A008330, A008331, A286714, A303549, A326391.

Except for 5, subsequence of A286715.

s = {}; rm = 0; p = 5; Do[q = NextPrime[p]; If[q - p != 2, p = q; Continue[]]; r = EulerPhi[p + 1]/EulerPhi[p - 1]; If[r > rm, rm = r; AppendTo[s, p]]; p = q, {10^6}]; s

a(24)-a(28) from Giovanni Resta, Nov 01 2019

A333315 a(n) = Sum_{k=1..n} phi(prime(k)-1), where phi is the Euler totient function (A000005).

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 22, 28, 38, 50, 58, 70, 86, 98, 120, 144, 172, 188, 208, 232, 256, 280, 320, 360, 392, 432, 464, 516, 552, 600, 636, 684, 748, 792, 864, 904, 952, 1006, 1088, 1172, 1260, 1308, 1380, 1444, 1528, 1588, 1636, 1708, 1820, 1892, 2004, 2100, 2164

Offset: 1

Amiram Eldar, Mar 14 2020

nonn

József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, page 30.

Amiram Eldar, Table of n, a(n) for n = 1..10000
S. S. Pillai, On the sum function connected with primitive roots, Proceedings of the Indian Academy of Sciences - Section A, Vol. 13 (1941), pp. 526-529, alternative link.
Eric Weisstein's World of Mathematics, Logarithmic Integral.
Wikipedia, Logarithmic integral function.

Partial sums of A008330.

Cf. A000005, A005596.

Accumulate @ EulerPhi[Select[Range[300], PrimeQ] - 1]

a(n) = sum(k=1, n, eulerphi(prime(k)-1)); \\ Michel Marcus, Mar 15 2020

a(n) = Sum_{k=1..n} A008330(k).

a(n) ~ A * Li(n^2), where A is Artin's constant (A005596), and Li(x) is the logarithmic integral function.

A338364 a(n) = Product_{k=1..n} phi(prime(k)-1).

Original entry on oeis.org

1, 1, 1, 2, 4, 16, 64, 512, 3072, 30720, 368640, 2949120, 35389440, 566231040, 6794772480, 149484994560, 3587639869440, 100453916344320, 1607262661509120, 32145253230182400, 771486077524377600, 18515665860585062400, 444375980654041497600, 17775039226161659904000

Offset: 0

Marc LeBrun and N. J. A. Sloane, Nov 04 2020

nonn

			a(5) = phi(1)*phi(2)*phi(4)*phi(6)*phi(10) = 1*1*2*2*4 = 16.

Cf. A000010, A008330, A002110.

with(NumberTheory);
f:=n->mul(phi(ithprime(k)-1),k=1..n);
[seq(f(n),n=1..32)];

a(n) = prod(k=1, n, eulerphi(prime(k)-1)); \\ Michel Marcus, Nov 04 2020

cp's OEIS Frontend

A128860 Let p be the n-th odd prime; a(n) is the number of primitive roots of p which are relatively prime to p-1.

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

Extensions

A251865 Irregular triangle read by rows in which row n lists the maximal-order elements (

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A266988 The indices of primes for which the average of the primitive roots is < p/2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A280729 (p-1)/2 + phi(p-1) as p runs through the odd primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A286510 Number of primitive roots g mod prime(n) for which there is no solution to g^x == x (mod p) with 2 <= x <= prime(n)-2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A293605 Primes p such that phi(p-1) < (p-1)/4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A303549 Lesser of twin primes p for which phi(p-1) = phi(p+1), where phi(n) is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A326356 Lesser of twin primes p >= 5 for which phi(p+1)/phi(p-1) reaches record value, where phi(n) is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples