A279398 -id:A279398 - cp's OEIS frontend

A193305 Composite numbers of the form 4, p^m, or 2*p^m for p an odd prime. All composites that have a primitive root.

4, 6, 9, 10, 14, 18, 22, 25, 26, 27, 34, 38, 46, 49, 50, 54, 58, 62, 74, 81, 82, 86, 94, 98, 106, 118, 121, 122, 125, 134, 142, 146, 158, 162, 166, 169, 178, 194, 202, 206, 214, 218, 226, 242, 243, 250, 254, 262, 274, 278, 289, 298, 302, 314, 326, 334, 338, 343

Offset: 1

Warren Breslow, Jul 21 2011

nonn

Nonprime k such that the multiplicative group modulo k is cyclic. Nonprime terms of A033948 (omitting the initial term 1). - Joerg Arndt, Aug 07 2011

a(n) has a primitive root for any n. - Arkadiusz Wesolowski, Sep 06 2012 [See, e.g., the Niven et al. reference. - Wolfdieter Lang, Jan 18 2017]

Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991, Theorem 2.41, p. 104.

T. D. Noe, Table of n, a(n) for n = 1..10000
Joerg Arndt, Matters Computational (The Fxtbook), relation (39.7-13) on page 779.

Cf. A033948, A033949 (composites without primitive root). A279398.

lim = 500; t = {4}; Do[p = Prime[n]; k = 1; While[p^k <= lim, If[k > 1, AppendTo[t, p^k]]; If[2*p^k <= lim, AppendTo[t, 2*p^k]]; k++], {n, 2, PrimePi[lim/2]}]; Sort[t]; (* T. D. Noe, Sep 06 2012 *)

for (n=2, 555, if ( isprime(n), next() ); if ( 1 == #(znstar(n)[3]), print1(n,", ") ); );  /* Joerg Arndt, Aug 07 2011 */

from sympy import primepi, integer_nthroot
def A193305(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-(x>=4)-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(2,x.bit_length()))-sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
    return bisection(f,n,n) # Chai Wah Wu, Feb 24 2025

More terms from Joerg Arndt, Aug 07 2011

Name corrected and augmented by Wolfdieter Lang, Jan 18 2017

A279399 Irregular triangle read by rows. Row n gives the primes of the smallest positive restricted residue system modulo A033949(n).

Original entry on oeis.org

3, 5, 7, 5, 7, 11, 2, 7, 11, 13, 3, 5, 7, 11, 13, 3, 7, 11, 13, 17, 19, 2, 5, 11, 13, 17, 19, 5, 7, 11, 13, 17, 19, 23, 3, 5, 11, 13, 17, 19, 23, 7, 11, 13, 17, 19, 23, 29, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 2, 5, 7, 13, 17, 19, 23, 29, 31, 2, 3, 11, 13, 17, 19, 23, 29, 31, 5, 7, 11, 13, 17, 19, 23, 29, 31, 2, 5, 7, 11, 17, 19, 23, 29, 31, 37, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37

Offset: 1

Wolfdieter Lang, Jan 25 2017

The length of row n is given by A279400(n)
For the restricted residue systems modulo n see A038566. For the primes of A038566 (for n >= 3) see A112484.
The primes of the restricted residue system modulo the (composite) positive numbers without a primitive root, given in A033949, are of interest for the determination of the Dirichlet characters modulo the A033949 numbers. For prime numbers (A000040) or for composite positive numbers that have prime primitive roots (A279398) the Dirichlet characters are determined from those of the prime primitive root.

			The triangle T(n, k) begins (here N = A033949(n)):
n,   N \ k 1  2  3  4  5  6  7  8  9 10 ...
1,   8:    3  5  7
2,  12:    5  7 11
3,  15:    2  7 11 13
4,  16:    3  5  7 11 13
5,  20:    3  7 11 13 17 19
6,  21:    2  5 11 13 17 19
7,  24:    5  7 11 13 17 19 23
8,  28:    3  5 11 13 17 19 23
9,  30:    7 11 13 17 19 23 29
10, 32:    3  5  7 11 13 17 19 23 29 31
11, 33:    2  5  7 13 17 19 23 29 31
12, 35:    2  3 11 13 17 19 23 29 31
13, 36:    5  7 11 13 17 19 23 29 31
14, 39:    2  5  7 11 17 19 23 29 31 37
15, 40:    3  7 11 13 17 19 23 29 31 37
...

Cf. A000040, A033949, A038566, A112484, A279398, A279400, A279401.

Row n of T is given by the primes of row A033949(n) of A038566, for n >= 1.

T(n, k) = A112484(A033949(n), k), n >= 1, k = 1..A279400(n).

cp's OEIS Frontend

A193305 Composite numbers of the form 4, p^m, or 2*p^m for p an odd prime. All composites that have a primitive root.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions