A229099 -id:A229099 - cp's OEIS frontend

A100613 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y) > 1}.

0, 1, 2, 5, 6, 13, 14, 21, 26, 37, 38, 53, 54, 69, 82, 97, 98, 121, 122, 145, 162, 185, 186, 217, 226, 253, 270, 301, 302, 345, 346, 377, 402, 437, 458, 505, 506, 545, 574, 621, 622, 681, 682, 729, 770, 817, 818, 881, 894, 953, 990, 1045, 1046, 1117, 1146, 1209

Offset: 1

Douglas Stones (dssto1(AT)student.monash.edu.au), Dec 02 2004

nonn

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

Cf. A018805, A000290, A185670, A063985, A242114, A229099.

a100613 n = length [()| x <- [1..n], y <- [1..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013

f[n_] := Table[ #^2 &[m], {m, 1, n + 1}] - FoldList[Plus, 1, 2 Array[EulerPhi, n, 2]] (* Gregg K. Whisler, Jun 25 2008 *)

a(n) = sum(i=1, n, sum(j=1, n, gcd(i,j)>1)); \\ Michel Marcus, Jan 30 2017

from functools import lru_cache
@lru_cache(maxsize=None)
def A100613(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(k1**2-A100613(k1))
        j, k1 = j2, n//j2
    return n+c-j # Chai Wah Wu, Mar 24 2021

a(n) = A000290(n) - A018805(n) = A185670(n) + A063985(n). - Reinhard Zumkeller, Jan 21 2013
a(n) = Sum_{k = 2..n} A242114(n,k). - Reinhard Zumkeller, May 04 2014
a(n) ~ kn^2, where k = 1 - 6/Pi^2 = 0.39207... (A229099). - Charles R Greathouse IV, Mar 29 2024

A368039 The product of exponents of prime factorization of the nonsquarefree numbers.

Original entry on oeis.org

2, 3, 2, 2, 4, 2, 2, 3, 2, 3, 2, 5, 4, 3, 2, 2, 4, 2, 2, 2, 3, 3, 2, 2, 6, 2, 6, 2, 2, 4, 4, 2, 3, 2, 2, 5, 2, 2, 4, 3, 6, 4, 2, 2, 3, 2, 2, 3, 2, 7, 2, 3, 3, 2, 8, 2, 2, 2, 3, 2, 2, 5, 4, 2, 3, 2, 2, 2, 2, 4, 4, 3, 2, 3, 6, 4, 2, 6, 2, 2, 4, 2, 9, 2, 5, 4, 2

Offset: 1

Amiram Eldar, Dec 09 2023

nonn

The terms of A005361 that are larger than 1, since A005361(k) = 1 if and only if k is squarefree (A005117).

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

Cf. A005117, A005361, A013929.
Cf. A084936, A174961, A275699, A368038, A368040.
Cf. A059956, A082695, A229099.

Select[Table[Times @@ FactorInteger[n][[;;, 2]], {n, 1, 250}], # > 1 &]

lista(kmax) = {my(p); for(k = 1, kmax, p = vecprod(factor(k)[, 2]); if(p > 1, print1(p, ", ")));}

a(n) = A005361(A013929(n)).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = ((zeta(2)*zeta(3)/zeta(6)) - 1/zeta(2))/(1-1/zeta(2)) = (A082695 - A059956)/A229099 = 3.406686208821... .

A250032 a(n) is the numerator of the density of natural numbers m such that gcd(m,floor(m/n))>1.

Original entry on oeis.org

1, 1, 1, 11, 7, 19, 16, 117, 269, 877, 1003, 11243, 4261, 56163, 61883, 199663, 107339, 919889, 2009948, 38444267, 41354174, 43432679, 46078049, 266161243, 379669754, 387106183, 407127338, 1258564159, 1322304979, 19229195413, 40830611677, 634491904301, 2638247862269, 2717256540199, 2823435623209, 2886468920107, 1006725304509

Offset: 1

Stanislav Sykora, Nov 16 2014

Let m be any natural number, and P(m) a relational expression on m (i.e., a property of m) evaluating to either 0 (false) or 1 (true). This defines a subset S of natural numbers N for which P(m)=1. When there exists a limit d=limit(M->infinity, Sum(m=1..M, P(m))/M), d is said to be the limit mean density (or just density) of the subset S in N. Now, choose an integer parameter n and set P(m)=gcd(m,floor(m/n))>1. This makes the property P, the corresponding subset S, and the density d all dependent upon n. The reference proves that for any n>0, the density d(n) exists and is a rational number. The value of a(n) is the numerator of d(n), while A250033(n) is the denominator of d(n).

			When n=1, S includes all natural numbers except 1, so d(1)=1. Hence a(1)=1 and A250033(1)=1.
When n=2, S includes all even numbers greater than 2, so d(2)=1/2. Hence a(2)=1 and A250033(2)=2.
When n=10, the subset S is A248500 and d(10)=877/2100. Hence a(10)=877 and A250033(10)=2100.
When n=16, S is A248502 and d(16)=199663/480480. Hence a(16)=199663 and A250033(16)=480480.

Stanislav Sykora, Table of n, a(n) for n = 1..1000
S. Sykora, On some number densities related to coprimes, Stan's Library, Vol. V, Nov 2014, DOI: 10.3247/SL5Math14.005

Cf. A229099, A248500, A248502, A250031, A250033, A250034.

s_aux(n,p0,inp)={my(t=0/1,tt=0/1,in=inp,pp);while(1,pp=p0*prime(in);tt=n\pp;if(tt==0,break,t+=tt/pp-s_aux(n,pp,in++)));return(t)};
s(n)=1+s_aux(n,1,1);
a=vector(1000,n,numerator(s(n-1)/n))

For n>1, a(n)/A250033(n) = s(n-1)/n, where s(n) = A250034(n)/A072155(n).

lim(n->infinity)a(n)/A250033(n) = 1-1/zeta(2) = A229099.

A368038 The sum of non-unitary divisors of the nonsquarefree numbers.

Original entry on oeis.org

2, 6, 3, 8, 14, 9, 12, 24, 5, 12, 16, 30, 41, 36, 24, 18, 56, 7, 15, 28, 36, 48, 48, 24, 62, 36, 105, 20, 40, 84, 39, 64, 72, 54, 48, 120, 21, 36, 87, 84, 140, 112, 60, 42, 144, 11, 64, 30, 72, 126, 96, 72, 108, 96, 233, 28, 76, 60, 120, 54, 112, 180, 117, 84

Offset: 1

Amiram Eldar, Dec 09 2023

nonn

The positive terms of A048146, since A048146(k) = 0 if and only if k is squarefree (A005117).

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

Cf. A005117, A048146, A013929.
Cf. A084936, A174961, A275699, A368039, A368040.
Cf. A002117, A013661, A072691, A229099.

f[p_, e_] := (p^(e+1)-1)/(p-1); nusigma[n_] := Module[{fct = FactorInteger[n]}, If[n == 1, 0, Times @@ f @@@ fct - Times @@ (1 + Power @@@ fct)]]; Select[Array[nusigma, 200], # > 0 &]

lista(kmax) = {my(f); for(k = 1, kmax, f = factor(k); if(!issquarefree(f), print1(sigma(f) - prod(i=1, #f~, 1+f[i,1]^f[i,2]), ", ")));}

a(n) = A048146(A013929(n)).

Sum_{k=1..n} a(k) ~ c * n^2, where c = (zeta(2)/2)*(1-1/zeta(3))/(1-1/zeta(2))^2 = 0.899359898779... .

A368040 The powerful part of the nonsquarefree numbers.

Original entry on oeis.org

4, 8, 9, 4, 16, 9, 4, 8, 25, 27, 4, 32, 36, 8, 4, 9, 16, 49, 25, 4, 27, 8, 4, 9, 64, 4, 72, 25, 4, 16, 81, 4, 8, 9, 4, 32, 49, 9, 100, 8, 108, 16, 4, 9, 8, 121, 4, 125, 9, 128, 4, 27, 8, 4, 144, 49, 4, 25, 8, 9, 4, 32, 81, 4, 8, 169, 9, 4, 25, 16, 36, 8, 4, 27

Offset: 1

Amiram Eldar, Dec 09 2023

nonn

The terms of A057521 that are larger than 1, since A057521(k) = 1 if and only if k is squarefree (A005117).

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

Cf. A005117, A013929, A057521.
Cf. A084936, A174961, A275699, A368038, A368039.
Cf. A013661, A229099, A328013.

f[p_, e_] := If[e > 1, p^e, 1]; powPart[n_] := Times @@ f @@@ FactorInteger[n]; Select[Array[powPart, 200], # > 1 &]

lista(kmax) = {my(p, f); for(k = 1, kmax, f = factor(k); p = prod(i=1, #f~, if(f[i, 2] > 1, f[i, 1]^f[i, 2], 1)); if(p > 1, print1(p, ", ")));}

a(n) = A057521(A013929(n)).

Sum_{k=1..n} a(k) ~ c * n^(3/2), where c = d/(3*(1-1/zeta(2))^(3/2)) = 4.778771..., and d = A328013.

A063035 Number of integers m <= 10^n that contain a square factor (i.e., belong to A013929).

Original entry on oeis.org

3, 39, 392, 3917, 39206, 392074, 3920709, 39207306, 392072876, 3920729058, 39207289720, 392072897726, 3920728981706, 39207289814053, 392072898145897, 3920728981459595

Offset: 1

Robert G. Wilson v, Aug 02 2001

nonn

Note that "containing a square factor" (A013929) is different from "squareful" (A001694).

Robert G. Wilson v, Table of n, a(n) for n = 1..36

Cf. A001694, A013929, A229099.

For the complementary counts see A053462 and A071172.

f[n_] := Sum[-MoebiusMu[i]Floor[n/i^2], {i, 2, Sqrt@ n}]; Table[ f[10^n], {n, 0, 14}]

{ default(realprecision, 50); for (n=1, 100, t=10^n - 1; a=10^n - sum(k=1, sqrt(t), moebius(k)*floor(t/k^2)); write("b063035.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 16 2009

from math import isqrt
from sympy import mobius
def A063035(n): return (m:=10**n)-sum(mobius(k)*(m//k**2) for k in range(1,isqrt(m)+1)) # Chai Wah Wu, Jul 20 2024

Limit_{n->oo} a(n)/10^n = A229099. - Robert G. Wilson v, Aug 12 2014

a(n) = 10^n - A071172(n). - Amiram Eldar, Mar 10 2024

More terms from Harry J. Smith, Aug 16 2009

Edited (with a more precise definition and a new value for a(1)) by N. J. A. Sloane, Aug 06 2012. As a result of this change, the programs probably now give the wrong value for a(1). The source of the trouble was the ambiguous meaning of squareful - the official definition of squareful is A001694.

A087049 Characteristic sequence for numbers n>=0 that are either squares or have a square > 1 as factor.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1

Offset: 0

Wolfdieter Lang, Sep 08 2003

a(0)=1, a(1)=1, n>=2: a(n)=1 if isquarefree(n)=false else 0.
Except for a(0)=1 and a(1)=1 this is the bit-flipped unsigned Moebius sequence abs(A008683(n)), n>=2.
For n>=2: a(n)=1 iff n is from A013929 (not squarefree).

			a(4) = 1 because 4 is a square; a(8) = 1 because 8 = 2^2 * 2.

Cf. A008683, A008966, A080733, A000290 (squares), A013929 (not squarefree), A229099.

1,1,seq(`if`(numtheory:-issqrfree(n),0,1),n=2..100); # Robert Israel, Nov 17 2017

Array[If[# <= 1, 1, 1 - Abs@ MoebiusMu@ #] &, 105, 0] (* Michael De Vlieger, Nov 17 2017 *)

A087049(n) = if(n<=1,1,1-abs(moebius(n))); \\ Antti Karttunen, Nov 17 2017

a(n) = 1 if n is a perfect square (A000290) or has some square > 1 as a factor, else 0.
a(0) = a(1) = 1; for n > 1, a(n) = 1 - A008966(n). - Antti Karttunen, Nov 17 2017
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=0..m} a(k) = 1 - 6/Pi^2 (A229099). - Amiram Eldar, Jan 19 2024

A212177 Number of exponents >= 2 in the canonical prime factorization of the n-th nonsquarefree number (A013929(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1

Offset: 1

Matthew Vandermast, Jun 03 2012

Length of second signature of A013929(n) (cf. A212172).

			24 = 2^3*3 has 1 exponent of size 2 or greater in its prime factorization. Since 24 = A013929(8), a(8) = 1.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 844.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Primefan, The First 2500 Integers Factored (1st of 5 pages).

Cf. A013929, A212172, A212174.

Cf. A046028, A056170, A085548, A124010, A229099.

a212177 n = a212177_list !! (n-1)
a212177_list = filter (> 0) a056170_list
-- Reinhard Zumkeller, Dec 29 2012

f[n_] := Module[{c = Count[FactorInteger[n][[;; , 2]], ?(# > 1&)]}, If[n > 1 && c > 0, c, Nothing]]; f[1] = 0; Array[f, 300] (* _Amiram Eldar, Oct 01 2023 *)

from math import isqrt
from sympy import mobius, factorint
def A212177(n):
    def f(x): return n+sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return sum(1 for e in factorint(m).values() if e>1) # Chai Wah Wu, Jul 22 2024

a(n) = A056170(A013929(n)).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = (Sum_{p prime} 1/p^2)/(1-1/zeta(2)) = A085548 / A229099 = 1.15347789194214704903... . - Amiram Eldar, Oct 01 2023

A303946 Numbers that are neither squarefree nor perfect powers.

Original entry on oeis.org

12, 18, 20, 24, 28, 40, 44, 45, 48, 50, 52, 54, 56, 60, 63, 68, 72, 75, 76, 80, 84, 88, 90, 92, 96, 98, 99, 104, 108, 112, 116, 117, 120, 124, 126, 132, 135, 136, 140, 147, 148, 150, 152, 153, 156, 160, 162, 164, 168, 171, 172, 175, 176, 180, 184, 188, 189

Offset: 1

Gus Wiseman, May 03 2018

nonn

First differs from A059404 at a(40) = 147, A059404(40) = 144.

First differs from A126706 at a(6) = 40, A126706(6) = 36.

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

Cf. A000009, A000837, A001597, A005117, A007916, A013929, A047966, A052409, A052410, A072774, A073576, A126706, A132350.

filter:= proc(n) local F;
F:= map(t->t[2],ifactors(n)[2]);
max(F)>1 and igcd(op(F))=1
end proc:
select(filter, [$1..1000]); # Robert Israel, May 06 2018

Select[Range[200], !SquareFreeQ[#] && GCD@@FactorInteger[#][[All, 2]] == 1 &]

isok(n) = !issquarefree(n) && !ispower(n); \\ Michel Marcus, May 05 2018

from math import isqrt
from sympy import mobius, integer_nthroot
def A303946(n):
    def f(x): return int(n+sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Aug 19 2024

a(n) ~ n/k, where k = 1 - 1/zeta(2) = 1 - 6/Pi^2 = A229099. - Charles R Greathouse IV, Jun 01 2018

A258614 Numbers m having with the largest square <= m a common divisor > 1.

Original entry on oeis.org

4, 6, 8, 9, 12, 15, 16, 18, 20, 22, 24, 25, 30, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 56, 63, 64, 66, 68, 70, 72, 74, 76, 78, 80, 81, 84, 87, 90, 93, 96, 99, 100, 102, 104, 105, 106, 108, 110, 112, 114, 115, 116, 118, 120, 121, 132, 143, 144, 146, 147

Offset: 1

Reinhard Zumkeller, Jun 05 2015

nonn

The asymptotic density of this sequence is 1-6/Pi^2 (A229099). - Amiram Eldar, Nov 19 2024

			a(11) = 24: GCD(24,A048760(24)) = GCD(24,16) = 4 > 1.
a(12) = 25: GCD(25,A048760(25)) = GCD(25,25) = 25 > 1.
GCD(26,A048760(26)) = GCD(26,25) = 1, therefore 26 is not a term.

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

Cf. A074695, A048760, A229099, A258613 (complement).

a258614 n = a258614_list !! (n-1)
a258614_list = filter ((> 1) . a074695) [1..]

Select[Range[150], !CoprimeQ[#, Floor[Sqrt[#]]^2] &] (* Amiram Eldar, Nov 19 2024 *)

isok(m) = gcd(m, sqr(sqrtint(m))) > 1; \\ Michel Marcus, Jan 23 2022

A074695(a(n)) > 1.

cp's OEIS Frontend

A100613 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y) > 1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A368039 The product of exponents of prime factorization of the nonsquarefree numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A250032 a(n) is the numerator of the density of natural numbers m such that gcd(m,floor(m/n))>1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A368038 The sum of non-unitary divisors of the nonsquarefree numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A368040 The powerful part of the nonsquarefree numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A063035 Number of integers m <= 10^n that contain a square factor (i.e., belong to A013929).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A087049 Characteristic sequence for numbers n>=0 that are either squares or have a square > 1 as factor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple