A046144 -id:A046144 - cp's OEIS frontend

A231773 Numbers k such that there are no numbers with k primitive roots.

3, 5, 7, 9, 11, 13, 14, 15, 17, 19, 21, 23, 25, 26, 27, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 50, 51, 53, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 81, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95

Offset: 1

Arkadiusz Wesolowski, Nov 13 2013

nonn

Numbers k such that A231772(k) = 0.

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

Cf. A007617, A010554, A046144, A231772.

r=95; for(n=2, r, m=0; for(c=2*n+1, n^2+1, if(n%2==1, break); e=eulerphi(c); if(e==lcm(znstar(c)[2])&&eulerphi(e)==n, m=1; break)); if(m==0, print1(n, ", ")));

a(n) = A007617(n) for n <= 16.

A376008 Primes p such that there exists a cyclic permutation of the nonzero residues modulo p such that v^2 - 4uw == 0 (mod p) for any three consecutive residues u,v,w.

Original entry on oeis.org

3, 17, 251, 257, 433, 641, 1459, 3457, 3889, 21169, 39367, 54001, 65537, 110251, 114689, 139969, 210913, 246241, 274177, 319489, 629857, 746497, 974849, 995329, 1161217, 1299079, 1492993, 1769473, 2020001, 2424833, 2555521, 2654209, 5038849, 5304641, 5419387, 5746001, 6049243, 6561001

Offset: 1

Nikolay Osipov, Dmitry Petukhov, and Max Alekseyev, Sep 05 2024

nonn

In other words, for any three consecutive residues u,v,w, the quadratic polynomial u*x^2 + v*x + w has zero discriminant modulo p.

It is shown that all suitable permutations q for prime p = a(n) can be constructed by starting with q(1) = 1, q(2) = a primitive root modulo p, and then defining q(k) = q(k-1)^2/(4*q(k-2)) mod p for k >= 3. Hence, the number of suitable permutations (up to cyclic rotations) is given by A046144(a(n)).

			For a(2) = 17, a suitable cyclic permutation is (1, 3, 15, 6, 4, 12, 9, 7, 16, 14, 2, 11, 13, 5, 8, 10).

Max Alekseyev, Table of n, a(n) for n = 1..100
N. Osipov et al., Residues on a circle (in Russian), dxdy.ru, 2024.

Contains Fermat primes (A019434) as a subsequence.

Cf. A001918, A002326, A046144, A376010.

forprime(p=3,10^8, s=(p-1)/znorder(Mod(2,p)); if(factor(p-1)[,1]==factor(2*s)[,1] && !(p%4==1 && s%2==1),print1(p,", ")) );

An odd prime p is a term iff for s:=(p-1)/A002326((p-1)/2), radicals of p-1 and 2s coincide, excluding the case p==1 (mod 4) and s==1 (mod 2).

A380594 a(n) is the number of positive integers having 2*n primitive roots.

Original entry on oeis.org

6, 4, 4, 6, 2, 8, 0, 4, 2, 2, 2, 8, 0, 2, 0, 4, 0, 4, 0, 12, 0, 2, 0, 12, 0, 2, 4, 0, 0, 2, 0, 6, 0, 0, 0, 10, 0, 0, 0, 2, 2, 6, 0, 4, 0, 2, 0, 12, 0, 2, 0, 0, 0, 4, 0, 6, 0, 0, 0, 10, 0, 0, 0, 6, 2, 2, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 2, 0, 8, 4, 2, 0, 6, 0

Offset: 1

David James Sycamore, Michael De Vlieger, and Amiram Eldar, Jan 27 2025

nonn

Let [n] be the set {k; A046144(k) = 2*n}; n >= 1, then a(n) = |[n]|.

If 2*n is a term in A378508, [n] is nonempty and a(n) > 0. Otherwise, if 2*n is not in A378508 then there is no number having 2*n primitive roots, so a(n) = 0; see Example, and A380604.

			For n = 1, 2*n = 2 and there are 6 distinct numbers having 2 primitive roots; [2] = {5,7,9,10,14,18}; so a(10) = 6.
For n = 5, 2*n = 10 and there are just 2 distinct numbers having 10 primitive roots; [5] = {23,46}; so a(5) = 2.
For n = 7, 2*n = 14 and there are no numbers having 14 primitive roots, so a(7) = 0.
The sets [n] listed in rows start as follows; length of row n = a(n):
  n          [n]                   a(n)
  1    {5,7,9,10,14,18}             6;
  2    {11,13,22,26}                4;
  3    {29,27,30,54}                4;
  4    {17,25,31,34,50,62}          6;
  5    {23,46}                      2;
  6    {29,37,43,49,58,74,86,98}    8;
  7    { }                          0;
  8    {41,61,82,122}               4;
  9    {81,162}                     2;
  10   {67,134}                     2;
  ...

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
David M. Bressoud, A Course in Computational Number Theory (web page), CNT.m, Computational Number Theory Mathematica package.

Cf. A046144, A007617, A010554, A033949, A231772, A378506, A378508, A380604.

a[n_] := Count[Join @@ PhiInverse[PhiInverse[2*n]], ?(IntegerQ[PrimitiveRoot[#]] &)]; Array[a, 100] (* _Amiram Eldar, Jan 27 2025, using David M. Bressoud's CNT.m *)

isA033948(n) = {my(f = factor(n)); lcm(znstar(f)[2]) == eulerphi(f);}
a(n) = {my(v = invphi(2*n), w, c = 0); for(i = 1, #v, c += vecsum(apply(x -> isA033948(x), invphi(v[i])))); c;} \\ Amiram Eldar, Jan 27 2025, using Max Alekseyev's invphi.gp

a(n) <= A378506(2*n), with equality iff n is in A007617.

A216322 Number of primitive roots Modd n (see A216321).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 0, 2, 2, 2, 4, 4, 2, 6, 0, 2, 4, 10, 0, 4, 4, 6, 0, 6, 0, 8, 8, 4, 8, 4, 0, 6, 6, 4, 0, 8, 0, 12, 8, 4, 10, 22, 8, 12, 8, 8, 8, 12, 6, 8, 8, 6, 12, 28, 8, 8, 8, 6, 16, 8, 8, 20, 16, 10, 8, 24, 8, 12, 12, 8, 12, 8, 8, 24, 16, 18, 16, 40, 8, 16, 12

Offset: 1

Wolfdieter Lang, Sep 21 2012

nonn

This sequence coincides with A216321 for all n values from A206551 (cyclic multiplicative Modd n group) and the entry is 0 otherwise (if no primitive root exists, that is, n is from the complementary sequence A206552).

			a(8) = phi(phi(2*8)/2) = 2 , with phi = A000010, because 8 = A206551(8).
a(12) = 0 because 12 = A206552(1).

Cf. A216321, A046144 (modulo n analog).

a(n) = A216321(n) if n belongs to the sequence A206551 and a(n)=0 if n belongs to A206552.

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++)

A380500 Table T(n,k) = phi(phi(prime(n)^k)), n >= 1, k >= 0, read by upwards antidiagonals, where phi = A000010.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 8, 6, 4, 1, 4, 12, 40, 18, 8, 1, 4, 40, 84, 200, 54, 16, 1, 8, 48, 440, 588, 1000, 162, 32, 1, 6, 128, 624, 4840, 4116, 5000, 486, 64, 1, 10, 108, 2176, 8112, 53240, 28812, 25000, 1458, 128, 1, 12, 220, 2052, 36992, 105456, 585640, 201684, 125000, 4374, 256

Offset: 1

Michael De Vlieger, Feb 04 2025

For n >= 2, k >= 1, T(n,k) is the number of primitive roots of prime(n)^k.

			Table begins as follows:
n\k  0   1     2      3       4        5          6           7
---------------------------------------------------------------
1:   1   1     1      2       4        8         16          32
2:   1   1     2      6      18       54        162         486
3:   1   2     8     40     200     1000       5000       25000
4:   1   2    12     84     588     4116      28812      201684
5:   1   4    40    440    4840    53240     585640     6442040
6:   1   4    48    624    8112   105456    1370928    17822064
7:   1   8   128   2176   36992   628864   10690688   181741696

Michael De Vlieger, Table of n, a(n) for n = 1..11476 (rows n = 1..150, flattened).

Cf. A000010, A000040, A001248, A008330, A010554, A046144, A104039, A246655.

Table[EulerPhi[EulerPhi[Prime[#]^k]] &[n - k + 1], {n, 0, 10}, {k, 0, n}] // Flatten

T(n,k) = A010554(prime(n)^k) = A046144(prime(n)^k).
T(n,0) = 1.
T(n,1) = phi(prime(n)-1) = A008330(n).
T(n,2) = (prime(n)-1) * phi(prime(n)-1)
       = (prime(n)-1)^2 * Product_{q|(prime(n)-1)} 1-1/q, prime q.
       = A104039(n).
For k > 1, T(n,k) = prime(n)^(k-2) * A104039(n).
T(n,2) > prime(n) for n > 2.
T(n,k) < prime(n)^k for all n and for k > 0.

A345674 Euler totient function phi(n) - number of primitive roots modulo n.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 4, 4, 4, 2, 6, 4, 8, 4, 8, 8, 8, 4, 12, 8, 12, 6, 12, 8, 12, 8, 12, 12, 16, 8, 22, 16, 20, 8, 24, 12, 24, 12, 24, 16, 24, 12, 30, 20, 24, 12, 24, 16, 30, 12, 32, 24, 28, 12, 40, 24, 36, 16, 30, 16, 44, 22, 36, 32, 48, 20, 46, 32, 44, 24

Offset: 1

Robert Hutchins, Jun 22 2021

nonn

Cf. A000010, A046144.

a:= proc(n) uses numtheory; `if`(n=1, 0, (p->
      p-add(`if`(order(i, n)=p, 1, 0), i=0..n-1))(phi(n)))
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Jun 22 2021

a[n_] := (e = EulerPhi[n]) - If[n == 1 || IntegerQ @ PrimitiveRoot[n], EulerPhi[e], 0]; Array[a, 100] (* Amiram Eldar, Jun 23 2021 *)

a(n) = A000010(n) - A046144(n).

A377402 Least k such that the ratio of the number of residues mod k coprime to k and the number of primitive roots mod k is greater than or equal to n for k such that at least one primitive root mod k exists. Equivalently, k such that floor(phi(k)/phi(phi(k)) is a record value for those k belonging to A033948.

Original entry on oeis.org

1, 3, 7, 211, 43891, 300690391

Offset: 1

Miles Englezou, Oct 26 2024

These are the numbers k with the least proportion of primitive roots mod k to residues mod k coprime to k, of all m < k.
Let U(k) be the group of units of the ring Z/kZ, and Gen(k) the set of distinct single element generators of U(k). Then a(n) is equivalently those k for which floor(|U(k)|/|Gen(k)|) is a record value for those k with cyclic U(k).
Some data:
---------------------------------------------------------------------------------
n   a(n)        log(a(n))   phi(a(n))                max prime(r)#|phi(a(n))   r
---------------------------------------------------------------------------------
1   1           0           1                        0                         0
2   3           1.10...     2                        2                         1
3   7           1.96...     2*3                      6                         2
4   211         5.35...     2*3*5*7                  210                       4
5   43891       10.69...    2*3*5*7*11*19            2310                      5
6   300690391   19.52...    2*3*5*7*11*13*17*19*31   9699690                   8
---------------------------------------------------------------------------------
For n > 1, is a(n) necessarily prime? Furthermore, is a(n) necessarily a prime such that phi(a(n)) is squarefree? Lastly, is every phi(a(n)) divisible by a maximal primorial prime(r)# of length r <= omega(phi(a(n))), such that if a maximal prime(s)# divides phi(a(m)) and n < m, then r < s?
Based on the behavior of log(a(n)), we may expect a(7) to be found in the vicinity of floor(exp(40)) = 235385266837019985.

			There are 2 residues mod 3 coprime to 3, and only 1 is a primitive root. 3 is the least k for which the floor of the ratio is 2, and so a(2) = 3.
There are 210 residues mod 211 coprime to 211, and 48 are primitive roots. Floor(210/48) = 4, and 211 is the least k for which the floor of the ratio is 4, and so a(4) = 211.

Cf. A000010, A010554, A033948, A046144.

S=[1]; for(n=1,100000, if(#znstar(n).cyc>1,next); f=eulerphi; if(floor(f(n)/f(f(n)))>floor(f(S[length(S)])/f(f(S[length(S)]))), S=concat(S,n))); print(S)

Numbers k for which floor(A000010(A033948(k))/A046144(A033948(k)) is a record value.

cp's OEIS Frontend

A231773 Numbers k such that there are no numbers with k primitive roots.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A376008 Primes p such that there exists a cyclic permutation of the nonzero residues modulo p such that v^2 - 4*u*w == 0 (mod p) for any three consecutive residues u,v,w.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A380594 a(n) is the number of positive integers having 2*n primitive roots.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A216322 Number of primitive roots Modd n (see A216321).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A380500 Table T(n,k) = phi(phi(prime(n)^k)), n >= 1, k >= 0, read by upwards antidiagonals, where phi = A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A345674 Euler totient function phi(n) - number of primitive roots modulo n.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

A376008 Primes p such that there exists a cyclic permutation of the nonzero residues modulo p such that v^2 - 4uw == 0 (mod p) for any three consecutive residues u,v,w.