A036997 -id:A036997 - cp's OEIS frontend

A048597 Very round numbers: reduced residue system consists of only primes and 1.

1, 2, 3, 4, 6, 8, 12, 18, 24, 30

Offset: 1

According to Ribenboim, Schatunowsky and Wolfskehl independently showed that 30 is the largest element in the sequence. This gives a lower bound for the maximum of the smallest prime in a, a+d, a+2d, ... taken over all a with 1 < a < d and gcd(a,d) = 1 for d > 30 [see Ribenboim].
It appears that 2, 4, 6, 10, 12 are all the numbers n with the property that every number m in the range n < m < 2n that is coprime to n is also prime. - Ely Golden, Dec 05 2016
Golden's guess is true. See a proof in the links section. - FUNG Cheok Yin, Jun 19 2021

			The reduced residue systems of these numbers are as follows: {{1, {1}}, {2, {1}}, {3, {1, 2}}, {4, {1, 3}}, {6, {1, 5}}, {8, {1, 3, 5, 7}}, {12, {1, 5, 7, 11}}, {18, {1, 5, 7, 11, 13, 17}}, {24, {1, 5, 7, 11, 13, 17, 19, 23}}, {30, {1, 7, 11, 13, 17, 19, 23, 29}}}.

A. H. Beiler, Recreations in the Theory of Numbers, page 91.
H. Rademacher and O. Toeplitz, Von Zahlen und Figuren, Springer Verlag, Berlin, 1933, Zweite Auflage, see last chapter.
H. Rademacher & O. Toeplitz, The Enjoyment of Mathematics, pp. 187-192 Dover Publications, NY 1990.
P. Ribenboim, The little book of big primes, Chapter on primes in arithmetic progression.
J. E. Roberts, Lure of Integers, pp. 179-180 MAA 1992.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 89.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 111.

H. Bonse, Über eine bekannte Eigenshaft der Zahl 30 und ihre Verallgemeinerung, Archiv d. Math. u. Physik (3) vol. 12 (1907) 292-295.
Ross Honsberger, Mathematical Gems, The Two-Year College Mathematics Journal, Vol. 10, No. 3 (Jun., 1979), pp. 195-197 (3 pages).
Ross Honsberger, Two distinguished integers, in Mathematical Diamonds, MAA, 2003, see p. 79. [Added by _N. J. A. Sloane_, Jul 05 2009]
Yuto Kaneko and Hirofumi Nakai, A Generalization of Schatunowsky's Theorem, Amer. Math. Monthly (2025). See p. 1.
Bill Taylor, Posting to sci.math, Sep 13 1999 [Broken link]
Fung Cheok Yin, A property of the set "2, 4, 6, 10, 12", Dec 24 2020.

The sequences consists of the n with A036997(n)=0.

Select[Range[10^3], Function[n, Times @@ Boole@ Map[Or[# == 1, PrimeQ@ #] &, Select[Range@ n, CoprimeQ[#, n] &]] == 1]] (* Michael De Vlieger, Dec 13 2016 *)

is(n)=forcomposite(k=2,n-1,if(gcd(n,k)==1, return(0))); 1 \\ Charles R Greathouse IV, Apr 28 2015

Additional comments from Ulrich Schimke (ulrschimke(AT)aol.com), May 29 2001

A048864 Number of nonprime numbers (composites and 1) in the reduced residue system of n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 6, 1, 7, 2, 4, 3, 10, 1, 11, 2, 6, 4, 14, 1, 12, 5, 10, 5, 19, 1, 20, 6, 11, 7, 15, 3, 25, 8, 14, 6, 28, 2, 29, 8, 12, 10, 32, 3, 28, 7, 19, 11, 37, 4, 26, 10, 22, 14, 42, 2, 43, 14, 20, 15, 32, 5, 48, 15, 27, 8, 51, 6, 52, 17, 21, 17, 41, 6, 57, 12, 33, 20

Offset: 1

Labos Elemer

nonn

Differs from A039776 at n = 20, 21, ...

			At n = 10, we see that the numbers below 10 coprime to 10 are 1, 3, 7, 9. Removing 3 and 7, which are prime, we are left with two numbers, 1 and 9. Hence a(10) = 2.
At n = 100, phi(100) = 40, phi(100) - (pi(100) - A001221(100)) = 17, thus a(100) = 17.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Abhijit A J, A. Satyanarayana Reddy, Number of non-primes in the set of units modulo n, arXiv:1907.09908 [math.GM], 2019.
Abhijit A. J. and A. Satyanarayana Reddy, Number of non-primes in the set of units modulo n, The Mathematics Student, Vol. 88, No. 1-2 (2019), 147-152.

Cf. A039776, A000010, A000720, A001221, A037228, A072022, A072023, A074915.

A048864 := n -> nops(select(k->gcd(k,n)=1,remove(isprime,[$1..n]))); # Peter Luschny, Oct 22 2010

Array[EulerPhi@ # - (PrimePi@ # - PrimeNu@ #) &, 82] (* Michael De Vlieger, Jul 03 2016 *)
Table[Length[Select[Range[n], GCD[n, #] == 1 && Not[PrimeQ[#]] &]], {n, 80}] (* Alonso del Arte, Oct 02 2017 *)

a(n) = eulerphi(n) - (primepi(n) - omega(n)); \\ Indranil Ghosh, Apr 27 2017

from sympy import totient, primepi, primefactors
def a(n): return totient(n) - (primepi(n) - len(primefactors(n))) # Indranil Ghosh, Apr 27 2017

a(n) = A036997(n) + 1. - Peter Luschny, Oct 22 2010

a(n) = A000010(n) - (A000720(n) - A001221(n)).

Converted second formula to an equation, added commas to the example - R. J. Mathar, Oct 23 2010

A144740 Partial totient function phi(c, n) for c = 2: number of semiprimes less than and coprime to n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 4, 0, 4, 1, 2, 2, 6, 0, 6, 1, 2, 3, 8, 0, 6, 4, 6, 3, 10, 0, 10, 4, 5, 5, 7, 2, 13, 6, 8, 4, 15, 1, 15, 6, 6, 7, 16, 2, 13, 5, 10, 8, 18, 3, 12, 7, 11, 11, 21, 1, 21, 11, 11, 11, 15, 4, 23, 11, 14, 6, 24, 5, 24, 13, 11, 12, 18, 5, 26, 9, 17, 14, 27, 3, 19, 15, 19

Offset: 1

Reikku Kulon, Sep 20 2008

phi(c, n) = 0 iff n is in A048597.

			phi(2, 7) = 2: the two semiprimes less than 7 are 4 and 6.
phi(2, 15) = 2: there are five semiprimes less than 15 (4, 6, 9, 10, 14), but only 4 and 14 are relatively prime to 15.

Reikku Kulon, Table of n, phi(2, n) for n = 1..10000

Cf. A048597.

Cf. A036997 (phi(n) - max(phi(c, n)) over all nonnegative integers c).

A164297 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each non-coprime with at least one other member of S(n).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 4, 0, 3, 2, 8, 0, 9, 2, 5, 4, 13, 0, 14, 2, 7, 6, 18, 0, 15, 7, 14, 6, 24, 0, 25, 8, 14, 10, 19, 4, 31, 11, 19, 9, 35, 2, 36, 11, 17, 14, 40, 4, 35, 10, 25, 15, 45, 5, 32, 14, 28, 20, 51, 2, 52, 20, 28, 21, 40, 7, 58, 20, 35, 13, 61, 9, 62, 24, 30, 23, 50, 8, 68, 18, 43, 27

Offset: 1

Leroy Quet, Aug 12 2009

nonn

A164296(n) + A164297(n) = phi(n) (= A000010(n) = the number of elements in S(n)).

			The positive integers that are <= 9 and are coprime to 9 are: 1,2,4,5, 7,8. 1 is coprime to each other member in S(9). While 2, 4, and 8 are non-coprime to each other. 5 is coprime to each other member of S(9). And 7 is also coprime to each other member. Since there are 3 integers in S(9) that are each non-coprime with at least one other member of S(9) -- these integers being 2, 4, and 8 -- then a(9) = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A164296, A036997, A048597.

Cf. A038566, A000010.

import Data.List ((\\))
a164297 n = length [m | let ts = a038566_row n, m <- ts,
                        any ((> 1) . gcd m) (ts \\ [m])]
-- Reinhard Zumkeller, May 28 2015

Extended by Ray Chandler, Mar 16 2010

A049011 Composite numbers k such that number of composite d with 3 < d < k, gcd(k, d) = 1, is pi(k).

Original entry on oeis.org

27, 286, 370, 520, 550, 1332, 13530, 38220

Offset: 1

Naohiro Nomoto

Composite numbers k such that phi(k) + omega(k) = 2*pi(k) + 1. - Jinyuan Wang, Sep 05 2020

			gcd(27,d)=1: d=4,8,10,14,16,20,22,25,26, pi(27)=9, so 27 is a term.

Cf. A036997.

isok(n) = {if (isprime(n) , return (0)); nb = 0; forcomposite (d=4, n-1, if (gcd(n, d) == 1, nb++);); return (nb == primepi(n));} \\ Michel Marcus, Jul 14 2013

a(6)-a(8) from Michel Marcus, Jul 14 2013

A144764 Partial totient function phi(c, n) for c = 3: number of 3-semiprimes less than and coprime to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 3, 0, 2, 0, 4, 0, 3, 0, 2, 1, 6, 0, 7, 1, 3, 1, 4, 0, 7, 1, 3, 1, 7, 0, 8, 1, 3, 2, 10, 0, 8, 1, 5, 2, 12, 0, 7, 2, 6, 2, 12, 0, 12, 2, 5, 3, 8, 0, 14, 3, 7, 1, 16, 0, 16, 3, 5, 4, 12, 0, 19, 2, 9, 4, 19, 0, 12, 4, 9, 4, 19, 0, 13, 4, 10, 4, 13, 0, 20, 3

Offset: 1

Reikku Kulon, Sep 20 2008

Cf. A000010, A014612, A144740

Cf. A036997 (phi(n) - max(phi(c, n)) over all nonnegative integers c)

cp's OEIS Frontend

A048597 Very round numbers: reduced residue system consists of only primes and 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A048864 Number of nonprime numbers (composites and 1) in the reduced residue system of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A144740 Partial totient function phi(c, n) for c = 2: number of semiprimes less than and coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A164297 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each non-coprime with at least one other member of S(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions

A049011 Composite numbers k such that number of composite d with 3 < d < k, gcd(k, d) = 1, is pi(k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A144764 Partial totient function phi(c, n) for c = 3: number of 3-semiprimes less than and coprime to n.

Views

Author

Keywords

Crossrefs