A051250 -id:A051250 - cp's OEIS frontend

A139555 a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.

1, 1, 2, 2, 4, 2, 5, 4, 6, 4, 8, 4, 9, 6, 7, 7, 11, 6, 12, 8, 10, 8, 13, 8, 13, 10, 13, 11, 16, 8, 17, 14, 15, 13, 16, 11, 19, 14, 16, 13, 20, 12, 21, 16, 17, 16, 22, 15, 22, 17, 20, 18, 24, 17, 22, 18, 21, 19, 25, 16, 26, 21, 22, 22, 25, 18, 28, 22, 25, 19, 29, 21, 30, 24, 26, 24

Offset: 1

Leroy Quet, Apr 27 2008

nonn

Indices of first occurrence of each natural number: 1, 3, 5, 7, 9, 15, 11, 13, 21, 17, 19, 23, 32, 33, ..., . - Robert G. Wilson v
From Reinhard Zumkeller, Oct 27 2010: (Start)
a(n) <= A000010(n); a(A051250(n)) = A000010(A051250(n)), 1 <= n <= 17;
conjecture: a(n) < A000010(n) for n > 60, cf. A051250. (End)

			All the positive integers <= 21 that are coprime to 21 are 1,2,4,5,8,10,11,13,16,17,19,20. Of these integers, only 1,2,4,5,8,11,13,16,17,19 are prime-powers. There are 10 of these prime-powers; so a(21) = 10.

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

Cf. A139556.

Cf. A065515. - Reinhard Zumkeller, Oct 27 2010

a139555 = sum . map a010055 . a038566_row
-- Reinhard Zumkeller, Feb 23 2012, Oct 27 2010

isA000961 := proc(n) if n = 1 or isprime(n) then true; else RETURN(nops(ifactors(n)[2]) =1) ; fi ; end: A139555 := proc(n) local a,i; a := 0 ; for i from 1 to n do if isA000961(i) and gcd(i,n) = 1 then a := a+1 ; fi ; od: a ; end: seq(A139555(n),n=1..100) ; # R. J. Mathar, May 12 2008

f[n_] := Length@ Select[Range@ n, Length@ FactorInteger@ # == 1 == GCD[n, # ] &]; Array[f, 76] (* Robert G. Wilson v *)

a(n) = Sum_{k=1..A000010(n)} A010055(A038566(n,k)). - Reinhard Zumkeller, Feb 23 2012

More terms from R. J. Mathar and Robert G. Wilson v, May 12 2008

A051265 Maximal value of prime divisors of numbers in reduced residue system for n.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 1, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 3, 1, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2

Offset: 1

Labos Elemer

The smallest number for which a(n)=k is the n-th Euclid number (A006862=A002110 + 1).

Largest value of A001221(k) for 1 <= k <= n such that gcd(k, n) = 1. - Michael De Vlieger, Aug 10 2017

			For n=60 a(n)=1 since in RRS[ 60 ] only 1 and prime powers occur (see A051250).

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Z. Abel, E. Demaine, M. Demaine, H. Matsui and G. Rote, Common Developments of Several Different Orthogonal Boxes, CCCG 2011, Toronto ON, August 10-12, 2011.

Records are A006862.

Cf. A001221, A002110, A051250, A051266, A051267, A051268.

Table[Max@ Map[PrimeNu, Cases[Range[n - 1], k_ /; CoprimeQ[n, k]]] /. k_ /; ! IntegerQ@ k -> 0, {n, 105}] (* Michael De Vlieger, Aug 10 2017 *)

a(n)=my(k=1,s); forprime(p=2,, if(n%p==0, next); k*=p; if(k>n, return(s)); s++) \\ Charles R Greathouse IV, Aug 10 2017

a(n) << log n/log log n. - Charles R Greathouse IV, Aug 10 2017

A051266 Numbers n such that maximal value of prime divisors of reduced residue system for n is 2.

Original entry on oeis.org

7, 11, 13, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 28, 29, 32, 33, 34, 35, 36, 38, 39, 40, 44, 45, 46, 48, 50, 51, 52, 54, 56, 57, 58, 62, 63, 64, 66, 68, 69, 70, 72, 74, 75, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 105, 108, 110, 112, 114, 120, 126

Offset: 1

Labos Elemer

nonn

Largest value of A001221(k) = 2 for 1 <= k <= n such that gcd (k, n) = 1, i.e., k in row n of A038566. - Michael De Vlieger, Aug 10 2017

			n = 29 is here because for terms of RRS(29) = {1, 2, ..., 27, 28} the number of prime divisors is 0(for 1), 1(for prime powers) or 2 (for 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28).

Michael De Vlieger, Table of n, a(n) for n = 1..161

Cf. A001221, A002110, A038566, A048597, A051250, A051265, A051267, A051268.

Block[{n = 2, P}, P = Product[Prime@ i, {i, n}]; P + Position[#, n][[All, 1]] &@ Array[Max@ Map[PrimeNu, Cases[Range@ #, k_ /; CoprimeQ[#, k]]] &, 120, P + 1]] (* Michael De Vlieger, Aug 10 2017 *)

A051267 Numbers n such that maximal value of prime divisors of reduced residue system for n is 3.

Original entry on oeis.org

31, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 106, 107, 109, 111, 113, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 127, 128, 129, 131, 133, 134, 136, 137, 139, 141, 142, 143, 145, 146, 147

Offset: 1

Labos Elemer

nonn

Largest value of A001221(k) = 3 for 1 <= k <= n such that gcd(k, n) = 1, i.e., k in row n of A038566. - Michael De Vlieger, Aug 10 2017

Michael De Vlieger, Table of n, a(n) for n = 1..2446

Cf. A001221, A002110, A038566, A048597, A051250, A051265, A051266, A051268.

Block[{n = 3, P}, P = Product[Prime@ i, {i, n}]; P + Position[#, n][[All, 1]] &@ Array[Max@ Map[PrimeNu, Cases[Range@ #, k_ /; CoprimeQ[#, k]]] &, 117, P + 1]] (* Michael De Vlieger, Aug 10 2017 *)

A051268 Numbers n such that maximal value of prime divisors of reduced residue system for n is 4.

Original entry on oeis.org

211, 221, 223, 227, 229, 233, 239, 241, 247, 251, 253, 257, 263, 269, 271, 277, 281, 283, 289, 293, 299, 307, 311, 313, 317, 319, 323, 331, 337, 341, 343, 347, 349, 353, 359, 361, 367, 371, 373, 377, 379, 383, 389, 391, 397, 401, 403, 407, 409, 413

Offset: 1

Labos Elemer

nonn

Largest value of A001221(k) = 4 for 1 <= k <= n such that gcd(k, n) = 1, i.e., k in row n of A038566. - Michael De Vlieger, Aug 10 2017

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A001221, A002110, A006862, A038566, A048597, A051250, A051265, A051266, A051267.

Block[{n = 4, P}, P = Product[Prime@ i, {i, n}]; P + Position[#, n][[All, 1]] &@ Array[Max@ Map[PrimeNu, Cases[Range@ #, k_ /; CoprimeQ[#, k]]] &, 175, P + 1]] (* Michael De Vlieger, Aug 10 2017 *)

More terms from Michael De Vlieger, Aug 10 2017

A122937 3-Round numbers: numbers n such that every number less than n and relatively prime to n has at most three prime factors (counting multiplicities).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 84, 90, 96, 102, 108, 114, 120, 126, 132, 138, 144, 150, 156, 162, 168, 174, 180, 186, 192

Offset: 1

T. D. Noe, Sep 21 2006

This sequence, for r=3 prime factors, is finite. Maillet proved that such sequences are finite for any fixed r. The case r=1 is A048597; case r=2 is A122936.

Dickson, History of the Theory of Numbers, Vol. I, Chelsea, New York, 1952, p. 134.

T. D. Noe, Table of n, a(n) for n=1..265 (complete sequence)

Cf. A048597 (very round numbers), A051250, A089016 (largest n-round number).

Omega[n_] := If[n==1, 0, Plus@@(Transpose[FactorInteger[n]][[2]])]; nn=60060; r=3; moreThanR=Select[Range[nn], Omega[ # ]>r&]; lst={1}; Do[s=Select[Range[n],GCD[n,# ]==1&]; If[Intersection[s,moreThanR]=={}, AppendTo[lst,n]], {n,2,nn}]; lst

A122936 2-Round numbers: numbers n such that every number less than n and relatively prime to n has at most two prime factors (counting multiplicities).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96, 102, 108, 114, 120, 150, 180, 210, 240, 270, 300, 330, 420, 630, 840, 1050, 1260

Offset: 1

T. D. Noe, Sep 21 2006

This sequence, for r=2 prime factors, is finite. Maillet proved that such sequences are finite for any fixed r. The case r=1 is A048597; case r=3 is A122937.

Dickson, History of the Theory of Numbers, Vol. I, Chelsea, New York, 1952, p. 134.

H. Bonse, Über eine bekannte Eigenshaft der Zahl 30 und ihre Verallgemeinerung, Archiv d. Math. u. Physik (3) vol. 12 (1907) 292-295. See page 295.

Cf. A048597 (very round numbers), A051250, A089016 (largest n-round number).

Omega[n_] := If[n==1, 0, Plus@@(Transpose[FactorInteger[n]][[2]])]; nn=1260; r=2; moreThanR=Select[Range[nn], Omega[ # ]>r&]; lst={1}; Do[s=Select[Range[n],GCD[n,# ]==1&]; If[Intersection[s,moreThanR]=={}, AppendTo[lst,n]], {n,2,nn}]; lst
tpfQ[n_] :=Max[PrimeOmega /@ Select[Range[n - 1], CoprimeQ[#, n] &]] < 3; Select[Range[1300],tpfQ] (* Harvey P. Dale, Mar 16 2016 *)

A381805 Smallest composite squarefree number that is coprime to n.

Original entry on oeis.org

6, 15, 10, 15, 6, 35, 6, 15, 10, 21, 6, 35, 6, 15, 14, 15, 6, 35, 6, 21, 10, 15, 6, 35, 6, 15, 10, 15, 6, 77, 6, 15, 10, 15, 6, 35, 6, 15, 10, 21, 6, 55, 6, 15, 14, 15, 6, 35, 6, 21, 10, 15, 6, 35, 6, 15, 10, 15, 6, 77, 6, 15, 10, 15, 6, 35, 6, 15, 10, 33, 6, 35

Offset: 1

Michael De Vlieger, Mar 31 2025

Let p be the smallest prime that is coprime to n and let q be the second smallest prime that is coprime to n. Then a(n) = p*q.

Records in this sequence are set by n in A002110.

			a(1) = 6 = 2*3, since p = 2, q = 3.
a(2) = 15 = 3*5, since p = 3, q = 5.
a(3) = 10 = 2*5, since p = 2, q = 5.
a(4) = 15 = 3*5, since p = 3, q = 5, a(2^i) = 15 for i > 0.
a(6) = 35 = 5*7, since p = 5, q = 7.
a(9) = 20 = 2*5, since p = 2, q = 5, a(3^i) = 10 for i > 0.
a(10) = 21 = 3*7, since p = 3, q = 7.
a(12) = 35 = 5*7, since p = 5, q = 7, a(k) = 35 for n in A033845 (i.e., n such that rad(n) = 6).
a(20) = 21 = 3*7, since p = 3, q = 7, a(k) = 21 for n in A033846 (i.e., n such that rad(n) = 10).
a(30) = 77 = 7*11, since p = 7, q = 11, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A002110, A007947, A051250, A053669, A120944, A380539, A382248.

Table[c = 0; q = 2; Times @@ Reap[While[c < 2, While[Divisible[n, q], q = NextPrime[q]]; Sow[q]; q = NextPrime[q]; c++] ][[-1, 1]], {n, 120}]

a(n) = my(k=2); while (isprime(k) || !issquarefree(k) || (gcd(k, n) != 1) , k++); k; \\ Michel Marcus, Apr 01 2025

a(n) = A053669(n) * A380539(n) = A382248(n)/A020639(n).
For k and m such that rad(k) = rad(m), a(k) = a(m), where rad = A007947.
n < a(n) for n in A051250, a finite sequence whose largest term is 60.

A382659 Numbers k such that k < A053669(k)^2 * A380539(k), i.e., k < A382248(k).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 48, 50, 54, 60, 66, 70, 72, 78, 84, 90, 96, 102, 108, 114, 120, 126, 132, 138, 144, 150, 156, 162, 168, 174, 180, 210, 240, 252, 270, 300, 330, 360, 390

Offset: 1

Michael De Vlieger, Apr 14 2025

Numbers k whose reduced residue system (RRS) does not intersect A126706 (i.e., the sequence of numbers that are neither squarefree nor prime powers). Alternatively, numbers k whose RRS is a subset of A303554 (i.e., the union of powers of primes and squarefree numbers).
Let p = A053669(k), and let q = A380539(k). Thus, p and q are the smallest and second smallest primes, respectively, that do not divide k. Let m = p^2 * q = A382248(k). Then this sequence is that of k such that k < m.
There are 72 terms in this sequence.
Sequences A048597 and A051250 are proper subsets of this sequence.

			Let omega = A001221.
For omega = 0, we have the subset {1}. 1 is in the sequence since 1 < m, m = 2^2 * 3 = 12.
For omega = 1, we have the subset {2, 3, 4, 5, 7, 8, 9, 11, 16, 32}.
  11 is in the sequence since 11 < m, m = 2^2 * 3 = 12, but 13 is not, since 13 > 12.
  9 is in the sequence since 9 < m, m = 2^2 * 5 = 20.
  25 is not a term since 25 > 12, and 27 is not a term since 27 > 20.
For omega = 2, we have the subset {6, 10, 12, 14, 15, 18, 20, 22, 24, 26, 28, 34, 36, 38, 40, 44, 48, 50, 54, 72, 96, 108, 144, 162}.
  38 = 2*19 is a term since 38 < 45, 45 = 3^2 * 5, but 46 = 2*23 is not, since 46 > 45.
  15 = 3*5 is a term since 15 < 20, but 21 is not, since 21 > 20 and 35 is not, since 35 > 12.
  Intersection with A033845 = {k : rad(k) = 6} is {6, 12, 18, 24, 36, 48, 54, 72, 96, 108, 144, 162}, since m = 5^2 * 7 = 175.
  Intersection with A033846 = {k : rad(k) = 10} is {10, 20, 40, 50}, since m = 3^2 * 7 = 63.
  Intersection with A033847 = {k : rad(k) = 14} is {14, 28}, since m = 3^2 * 5 = 45, etc.
For omega = 3, we have the subset {30, 42, 60, 66, 70, 78, 84, 90, 102, 114, 120, 126, 132, 138, 150, 156, 168, 174, 180, 240, 252, 270, 300, 360, 450, 480}, of which {30, 42, 66, 70, 78, 102, 114, 138, 174} are squarefree.
  Intersection with A143207 = {k : rad(k) = 30} is {30, 60, 90, .., 480} because m = 7^2 * 11 = 539.
  Intersection with 42*A108319 = {k : rad(k) = 42} is {42, 84, 126, 168}, since m = 5^2 * 11 = 275, etc.
For omega = 4, we have the subset {210, 330, 390, 420, 510, 630, 840, 1050, 1260, 1470}, of which {210, 330, 390, 510} are squarefree.
  Intersection with A147571 = {k : rad(k) = 210} is {210, 420, 630, 840, 1050, 1260, 1470} since m = 11^2 * 13 = 1573, etc.
For omega = 5, we have 2310 = 2*3*5*7*11, a term since 2310 < 13*17 = 2873; 2730 = 2*3*5*7*13 is not a term.
There are no terms larger than 2310, since the intersection with A147572 = {2310}, 2730 is not a term, and k = Product_{i=1..j} prime(i), k > prime(j+1)^2 * prime(j+2) for j > 5. Therefore the sequence is finite like A051250.

Michael De Vlieger, Table of n, a(n) for n = 1..72

Cf. A048597 (k such that k < p^2), A051250 (k such that k < p*q), A053669, A126706, A303554, A380539, A382248, A382960.

Select[Range[30030], Function[n, c = 0; q = 2; n < Times @@ Reap[While[c < 2, While[Divisible[n, q], q = NextPrime[q]]; Sow[q^(2 - c)]; q = NextPrime[q]; c++]][[-1, 1]] ] ]

A382960 Numbers k such that k < A053669(k)^2 * A380539(k)^2, i.e., k < A382767(k).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 56, 57, 58, 60, 62, 63, 64, 66, 68, 69, 70, 72, 74, 75, 76, 78, 80, 81, 82, 84

Offset: 1

Michael De Vlieger, Apr 14 2025

Numbers k whose reduced residue system does not intersect A286708 (i.e., powerful numbers that are not prime powers).
Let p = A053669(k), and let q = A380539(k). Thus, p and q are the smallest and second smallest primes, respectively, that do not divide k. Let m = p^2 * q^2 = A382767(k). Then this sequence is that of k such that k < m.
This sequence is finite following arguments akin to those in A051250 and A382659, with 626 terms.
Sequences A048597, A051250, and A382659 are proper subsets of this sequence.

			Let omega = A001221.
For omega = 0, we have the subset {1}. 1 is in the sequence since 1 < m, m = (2*3)^2 = 36.
For omega = 1, we have the subset {2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 64, 81, 128}.
  31 is in the sequence since 31 < m, m = (2*3)^2 = 36, but 37 is not a term since 37 > 36.
  25 is in the sequence since 25 < m, m = 36.
  49 is not a term since 49 > 36, and 243 is not a term since 243 > 100, 100 = (2*5)^2, etc.
For omega = 2, we have the squarefree numbers {6, 10, 14, 15, 22, 26, 34, 35, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 194, 202, 206, 214, 218}.
  Intersection with A033845 = {k : rad(k) = 6} is {6, 12, 18, .., 1152}, since m = (5*7)^2 = 1225.
  Intersection with A033846 = {k : rad(k) = 10} is {10, 20, 40, ..., 400}, since m = (3*7)^2 = 441.
  Intersection with A033847 = {k : rad(k) = 14} is {14, 28, 56, ..., 224}, since m = (3*5)^2 = 225.
  Intersection with A033848 = {k : rad(k) = 15} is {15, 45, 75, 135}, since m = (2*7)^2 = 196, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..626

Cf. A048597 (k such that k < p^2), A051250 (k such that k < p*q), A053669, A286708, A380539, A382659 (k such that k < p^2*q), A382767.

Select[Range[510510], Function[n, c = 0; q = 2; n < Times @@ Reap[While[c < 2, While[Divisible[n, q], q = NextPrime[q]]; Sow[q^2]; q = NextPrime[q]; c++]][[-1, 1]] ] ]

cp's OEIS Frontend

A139555 a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A051265 Maximal value of prime divisors of numbers in reduced residue system for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A051266 Numbers n such that maximal value of prime divisors of reduced residue system for n is 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A051267 Numbers n such that maximal value of prime divisors of reduced residue system for n is 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A051268 Numbers n such that maximal value of prime divisors of reduced residue system for n is 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A122937 3-Round numbers: numbers n such that every number less than n and relatively prime to n has at most three prime factors (counting multiplicities).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A122936 2-Round numbers: numbers n such that every number less than n and relatively prime to n has at most two prime factors (counting multiplicities).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A381805 Smallest composite squarefree number that is coprime to n.

Views

Author

Keywords