A008330 -id:A008330 - cp's OEIS frontend

A250211 Square array read by antidiagonals: A(m,n) = multiplicative order of m mod n, or 0 if m and n are not coprime.

1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 1, 1, 2, 4, 1, 1, 0, 2, 0, 4, 0, 1, 1, 1, 0, 1, 2, 0, 3, 1, 1, 0, 1, 0, 0, 0, 6, 0, 1, 1, 1, 2, 2, 1, 2, 3, 2, 6, 1, 1, 0, 0, 0, 4, 0, 6, 0, 0, 0, 1, 1, 1, 1, 1, 4, 1, 2, 2, 3, 4, 10, 1, 1, 0, 2, 0, 2, 0, 0, 0, 6, 0, 5, 0, 1, 1, 1, 0, 2, 0, 0, 1, 2, 0, 0, 5, 0, 12, 1

Offset: 1

Eric Chen, Dec 29 2014

Read by antidiagonals:
m\n   1    2    3    4    5    6    7    8    9    10    11    12    13
1     1    1    1    1    1    1    1    1    1     1     1     1     1
2     1    0    2    0    4    0    3    0    6     0    10     0    12
3     1    1    0    2    4    0    6    2    0     4     5     0     3
4     1    0    1    0    2    0    3    0    3     0     5     0     6
5     1    1    2    1    0    2    6    2    6     0     5     2     4
6     1    0    0    0    1    0    2    0    0     0    10     0    12
7     1    1    1    2    4    1    0    2    3     4    10     2    12
8     1    0    2    0    4    0    1    0    2     0    10     0     4
9     1    1    0    1    2    0    3    1    0     2     5     0     3
10    1    0    1    0    0    0    6    0    1     0     2     0     6
11    1    1    2    2    1    2    3    2    6     1     0     2    12
12    1    0    0    0    4    0    6    0    0     0     1     0     2
13    1    1    1    1    4    1    2    2    3     4    10     1     0
etc.
A(m,n) = Least k>0 such that m^k=1 (mod n), or 0 if no such k exists.
It is easy to prove that column n has period n.
A(1,n) = 1, A(m,1) =1.
If A(m,n) differs from 0, it is period length of 1/n in base m.
The maximum number in column n is psi(n) (A002322(n)), and all numbers in column n (except 0) divide psi(n), and all factors of psi(n) are in column n.
Except the first row, every row contains all natural numbers.

			A(3,7) = 6 because:
3^0 = 1 (mod 7)
3^1 = 3 (mod 7)
3^2 = 2 (mod 7)
3^3 = 6 (mod 7)
3^4 = 4 (mod 7)
3^5 = 5 (mod 7)
3^6 = 1 (mod 7)
...
And the period is 6, so A(3,7) = 6.

Cf. A002322, A111076, A111725, A001918, A008330, A007733, A002326, A007732, A051626, A066799.

See A139366 for another version.

f:= proc(m,n)
  if igcd(m,n) <> 1 then 0
  elif n=1 then 1
  else numtheory:-order(m,n)
  fi
end proc:
seq(seq(f(t-j,j),j=1..t-1),t=2..65); # Robert Israel, Dec 30 2014

a250211[m_, n_] = If[GCD[m, n] == 1, MultiplicativeOrder[m, n], 0]
Table[a250211[t-j, j], {t, 2, 65}, {j, 1, t-1}]

A254309 Irregular triangular array read by rows: T(n,k) is the least positive primitive root of the n-th prime p=prime(n) raised to successive powers of k (mod p) where 1<=k<=p-1 and gcd(k,p-1)=1.

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 2, 8, 7, 6, 2, 6, 11, 7, 3, 10, 5, 11, 14, 7, 12, 6, 2, 13, 14, 15, 3, 10, 5, 10, 20, 17, 11, 21, 19, 15, 7, 14, 2, 8, 3, 19, 18, 14, 27, 21, 26, 10, 11, 15, 3, 17, 13, 24, 22, 12, 11, 21, 2, 32, 17, 13, 15, 18, 35, 5, 20, 24, 22, 19

Offset: 1

Geoffrey Critzer, May 03 2015

Each row is a complete set of incongruent primitive roots.
Each row is a permutation of the corresponding row in A060749.
Row lengths are A008330.
T(n,1) = A001918(n).

			1;
2;
2,  3;
3,  5;
2,  8,  7,  6;
2,  6, 11,  7;
3, 10,  5, 11, 14,  7, 12,  6;
2, 13, 14, 15,  3, 10;
5, 10, 20, 17, 11, 21, 19, 15,  7, 14;
2,  8,  3, 19, 18, 14, 27, 21, 26, 10, 11, 15;
Row 6 contains 2,6,11,7 because 13 is the 6th prime number. 2 is the least positive primitive root of 13. The integers relatively prime to 13-1=12 are {1,5,7,11}. So we have: 2^1==2, 2^5==6, 2^7==11, and 2^11==7 (mod 13).

Alois P. Heinz, Rows n = 1..120, flattened

Cf. A001918, A008330, A060749.
Last elements of rows give A255367.
Row sums give A088144.

with(numtheory):
T:= n-> (p-> seq(primroot(p)&^k mod p, k=select(
         h-> igcd(h, p-1)=1, [$1..p-1])))(ithprime(n)):
seq(T(n), n=1..15);  # Alois P. Heinz, May 03 2015

Table[nn = p;Table[Mod[PrimitiveRoot[nn]^k, nn], {k,Select[Range[nn - 1], CoprimeQ[#, nn - 1] &]}], {p,Prime[Range[12]]}] // Grid

A066902 Integers k such that phi(prime(k)+1) = phi(prime(k)-1).

Original entry on oeis.org

3, 5, 20, 156, 254, 377, 593, 1800, 5903, 5981, 7925, 18669, 19240, 41274, 48296, 135700, 146866, 228028, 234303, 251216, 407377, 654288, 802222, 886223, 938654, 1063412, 1072766, 1212140, 1238668, 1515063, 1609346, 2080991, 2097725, 2363130, 2408674, 2916514

Offset: 1

Benoit Cloitre, Jan 26 2002

nonn

Integers k such that A008331(k) = A008330(k).

Giovanni Resta, Table of n, a(n) for n = 1..675

Cf. A000010, A008864, A006093, A008330, A008331, A067890.

Select[Range[1000000],EulerPhi[Prime[#]-1]==EulerPhi[Prime[#]+1]&] (* Harvey P. Dale, Feb 25 2012 *)

isok(k) = my(p=prime(k)); eulerphi(p+1) == eulerphi(p-1); \\ Michel Marcus, Apr 06 2020

a(n) = primepi(A067890(n)). - Giovanni Resta, Apr 06 2020

More terms from Harvey P. Dale, Feb 25 2012

More terms from Jinyuan Wang, Apr 05 2020

A067933 Primes p such that p == -1 (mod phi(p-1)).

Original entry on oeis.org

2, 3, 5, 7, 11, 31, 71, 2591, 131071

Offset: 1

Benoit Cloitre, Feb 22 2002

No more terms up to 373587883 (the 20 millionth prime).

Cf. A000010, A008330.

Do[p = Prime[n]; If[ Mod[p + 1, EulerPhi[p - 1]] == 0, Print[p]], {n, 1, 10^8}] (* Cloitre *)
Select[Prime[Range[10^5]], Mod[#, EulerPhi[# - 1]] == EulerPhi[# - 1] - 1 &] (* Alonso del Arte, Sep 26 2011 *)

list(lim) = forprime(p  = 1, lim, if(!((p+1) % eulerphi(p-1)), print1(p,", "))); \\ Amiram Eldar, Apr 18 2025

Edited by Robert G. Wilson v, Feb 27 2002

A219028 Number of non-primitive roots for prime(n), less than prime(n).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 8, 12, 12, 16, 22, 24, 24, 30, 24, 28, 30, 44, 46, 46, 48, 54, 42, 48, 64, 60, 70, 54, 72, 64, 90, 82, 72, 94, 76, 110, 108, 108, 84, 88, 90, 132, 118, 128, 112, 138, 162, 150, 114, 156, 120, 142, 176, 150, 128, 132, 136, 198, 188, 184, 190

Offset: 1

V. Raman, Nov 10 2012

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A008330 (number of primitive roots for the n-th prime, less than n-th prime).
Cf. A046144 (number of primitive roots for n, less than n).
Cf. A010554 (value of phi(phi(n))).

Table[c=Prime[n];c-1-EulerPhi[EulerPhi[c]],{n,70}] (* Harvey P. Dale, Feb 12 2013 *)

forprime(i=2,600,p=0;for(q=1,i-1,if(znorder(Mod(q,i))!=eulerphi(i),p++));print1(p","))

a(n) = p - 1 - phi(phi(p)), where p is the n-th prime.

a(n) = p - 1 - A008330(n) = p - 1 - A010554(p), where p is the n-th prime. - V. Raman, Nov 22 2012

A266986 The indices of primes p for which the average of the primitive roots equals p/2.

Original entry on oeis.org

1, 3, 6, 7, 8, 10, 12, 13, 16, 18, 21, 24, 25, 26, 29, 30, 33, 35, 37, 40, 42, 44, 45, 50, 51, 53, 55, 57, 59, 60, 62, 63, 65, 66, 68, 70, 71, 74, 77, 78, 79, 80, 82, 84, 87, 88, 89, 97, 98, 100, 102, 104, 106, 108, 110, 112, 113, 116, 119, 121, 122, 123, 126, 127, 130, 134, 135, 136, 137, 139, 140, 142, 145

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

The average of the primitive roots of a prime p are <,=, or > p/2 (observation).
The indices of all primes p==1(mod 4) are in this sequence since for primes of form 4k+1 b a primitive root implies -b a primitive root.
The indices of some primes p==3 (mod 4) are also in this sequence although for most such primes the average of the primitive roots is <> p/2.(observation)

			p(a(1))=p(1)=2. 2 has the primitive root 1. The average primitive root is 1 and 1=2/2.
p(a(2))=p(3)=5. The primitive roots of 5 are 2 and 3. Their average equals (2+3)/phi(4)=5/2=p/2.

Dimitri Papadopoulos, Table of n, a(n) for n = 1..505

Cf. A008330, A060749, A088144, A266987.

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 &)]]

A266989 Primes for which the average of the primitive roots is < p/2.

Original entry on oeis.org

31, 43, 67, 223, 379, 491, 619, 631, 643, 683, 859, 883, 907, 1051, 1091, 1423, 1747, 1987, 2143, 2347, 2371, 2467, 2531, 2767, 3307, 3643, 3691, 3739, 3823, 3931, 4019, 4219, 4519, 4691, 4987, 5059, 5107, 5347, 5683, 5827, 6043

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

These primes are congruent to 3 (mod 4).

			a(1)=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.

Robert Israel, Table of n, a(n) for n = 1..1000

Cf. A008330, A060749, A088144, A266987, A266988, A267010.

f:= proc(p) local g;
  if not isprime(p) then return false fi;
  g:= numtheory[primroot](p);
  evalb(add(g&^i mod p, i = select(t->igcd(t,p-1)=1, [$1..p-2]))
     < p/2 * numtheory:-phi(p-1))
end proc:
select(f, [seq(i,i=3..10000,4)]); # Robert Israel, Feb 09 2016

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,100}]; Prime[Flatten[Position[A, _?(# < 1 &)]]]

ar(p) = my(r, pr, j); r=vector(eulerphi(p-1)); pr=znprimroot(p); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); vecsort(r) ;
isok(p) = my(vr = ar(p)); vecsum(vr)/#vr < p/2;
lista(nn) = forprime(p=2, nn, if (isok(p), print1(p, ", "))); \\ Michel Marcus, Feb 09 2016

a(n) = prime(A266988(n)).

A266990 The indices of primes p for which the average of the primitive roots is > p/2.

Original entry on oeis.org

2, 4, 5, 9, 15, 17, 20, 22, 23, 27, 28, 31, 32, 34, 36, 38, 39, 41, 43, 46, 47, 49, 52, 54, 56, 58, 61, 64, 67, 69, 72, 73, 76, 81, 83, 85, 86, 90, 91, 92, 93, 95, 96, 99, 101, 103, 105, 107, 109, 111, 118, 120, 125, 128, 129, 131, 132, 133, 138, 141, 143, 144, 146, 150

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

It appears that these primes are all congruent to 3 (mod 4).

			a(2) = 4 is a term since prime(a(2)) = prime(4) = 7, the primitive roots of 7 are 3 and 5 and their average is (3+5)/2 = 8/2 > 7/2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000720, A008330, A060749, A088144, A267009.

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 &)]]
Select[Range[150], Mean[PrimitiveRootList[(p = Prime[#])]] > p/2 &] (* Amiram Eldar, Oct 09 2021 *)

a(n) = A000720(A267009(n)). - Amiram Eldar, Oct 09 2021

A267009 Primes p for which the average of the primitive roots is > p/2.

Original entry on oeis.org

3, 7, 11, 23, 47, 59, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 227, 239, 251, 263, 271, 283, 311, 331, 347, 359, 367, 383, 419, 431, 439, 443, 463, 467, 479, 487, 499, 503, 523, 547, 563, 571, 587, 599, 607, 647, 659, 691, 719, 727

Offset: 1

Dimitri Papadopoulos, Jan 08 2016

nonn

It appears that these primes are all congruent to 3 (mod 4).

			a(2) = 7 since the primitive roots of 7 are 3 and 5 and their average is (3+5)/2 = 8/2 > 7/2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A008330, A060749, A088144, A266990.

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}]; Prime[Flatten[Position[A, _?(# > 1 &)]]]
Select[Range[1000], PrimeQ[#] && Mean[PrimitiveRootList[#]] > #/2 &] (* Amiram Eldar, Oct 09 2021 *)

a(n) = prime(A266990(n)).

A094051 a(n) = phi(phi(p))/2 where p = prime(n).

Original entry on oeis.org

1, 1, 2, 2, 4, 3, 5, 6, 4, 6, 8, 6, 11, 12, 14, 8, 10, 12, 12, 12, 20, 20, 16, 20, 16, 26, 18, 24, 18, 24, 32, 22, 36, 20, 24, 27, 41, 42, 44, 24, 36, 32, 42, 30, 24, 36, 56, 36, 56, 48, 32, 50, 64, 65, 66, 36, 44, 48, 46, 72, 48, 60, 48, 78, 40, 48, 86, 56, 80, 89, 60, 60, 54, 95, 96, 60

Offset: 3

Matthijs Coster, Apr 29 2004

Offset is 3 as a(1) and a(2) would be fractional. - Michel Marcus, Aug 13 2013

Amiram Eldar, Table of n, a(n) for n = 3..10000

Cf. A000010, A000040, A008330, A023022.

EulerPhi[Prime[Range[3, 100]] - 1]/2 (* Amiram Eldar, Jan 12 2024 *)

a(n) = eulerphi(eulerphi(prime(n)))/2; \\ Michel Marcus, Aug 13 2013

From Amiram Eldar, Jan 12 2024: (Start)
a(n) = A008330(n)/2.
a(n) = A023022(A000040(n)-1). (End)

cp's OEIS Frontend

A250211 Square array read by antidiagonals: A(m,n) = multiplicative order of m mod n, or 0 if m and n are not coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

A254309 Irregular triangular array read by rows: T(n,k) is the least positive primitive root of the n-th prime p=prime(n) raised to successive powers of k (mod p) where 1<=k<=p-1 and gcd(k,p-1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A066902 Integers k such that phi(prime(k)+1) = phi(prime(k)-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A067933 Primes p such that p == -1 (mod phi(p-1)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A219028 Number of non-primitive roots for prime(n), less than prime(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A266986 The indices of primes p for which the average of the primitive roots equals p/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A266989 Primes for which the average of the primitive roots is < p/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A266990 The indices of primes p for which the average of the primitive roots is > p/2.

Views

Author