A064775 -id:A064775 - cp's OEIS frontend

A048098 Numbers k that are sqrt(k)-smooth: if p | k then p^2 <= k when p is prime.

1, 4, 8, 9, 12, 16, 18, 24, 25, 27, 30, 32, 36, 40, 45, 48, 49, 50, 54, 56, 60, 63, 64, 70, 72, 75, 80, 81, 84, 90, 96, 98, 100, 105, 108, 112, 120, 121, 125, 126, 128, 132, 135, 140, 144, 147, 150, 154, 160, 162, 165, 168, 169, 175, 176, 180, 182, 189, 192, 195

Offset: 1

J. Lowell

A006530(a(n))^2 <= a(n). - Reinhard Zumkeller, Oct 12 2011

This set (say S) has density d(S) = 1-log(2) and multiplicative density m(S) = 1-exp(-Gamma). Multiplicative density: let A be a set of numbers, A(x) = { k in A | gpf(k) <=x } where gpf(k) denotes the greatest prime factor of k and let m(x)(A) = Product_{p<=x} (1 - 1/p)*Sum_{k in A(x)} 1/k. If lim_{x->infinity} m(x)(A) exists = m(A), this limit is called "multiplicative density" of A (Erdős and Davenport, 1951). - Benoit Cloitre, Jun 12 2002

T. D. Noe and William A. Tedeschi, Table of n, a(n) for n = 1..10000 (first 1000 terms computed by T. D. Noe)
H. Davenport and P. Erdős, On sequences of positive integers, J. Indian Math. Soc. 15 (1951), pp. 19-24.
Eric Weisstein's World of Mathematics, Greatest Prime Factor
Eric Weisstein's World of Mathematics, Round Number

Set union of A063539 and A001248.
Cf. A006530, A063538, A063762, A063763, A064052.
The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.

a048098 n = a048098_list !! (n-1)
a048098_list = [x | x <- [1..], a006530 x ^ 2 <= x]
-- Reinhard Zumkeller, Oct 12 2011

gpf[n_] := FactorInteger[n][[-1, 1]]; A048098 = {}; For[n = 1, n <= 200, n++, If[ gpf[n] <= Sqrt[n], AppendTo[ A048098, n] ] ]; A048098 (* Jean-François Alcover, Jan 26 2012 *)

print1(1, ", ");for(n=2, 1000, if(vecmax(factor(n)[, 1])<=sqrt(n), print1(n, ", ")))

from sympy import factorint
def ok(n):
    return n == 1 if n < 2 else max(factorint(n))**2 <= n
print([k for k in range(196) if ok(k)]) # Michael S. Branicky, Dec 22 2021

from math import isqrt
from sympy import primepi
def A048098(n):
    def f(x): return int(n+sum(primepi(x//i)-primepi(i) for i in range(1,isqrt(x)+1)))
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    return bisection(f) # Chai Wah Wu, Sep 01 2024

More terms from James Sellers, Apr 22 2000

Edited by Charles R Greathouse IV, Nov 08 2010

A063539 Numbers n that are sqrt(n-1)-smooth: largest prime factor of n (=A006530(n)) < sqrt(n).

Original entry on oeis.org

1, 8, 12, 16, 18, 24, 27, 30, 32, 36, 40, 45, 48, 50, 54, 56, 60, 63, 64, 70, 72, 75, 80, 81, 84, 90, 96, 98, 100, 105, 108, 112, 120, 125, 126, 128, 132, 135, 140, 144, 147, 150, 154, 160, 162, 165, 168, 175, 176, 180, 182, 189, 192, 195, 196

Offset: 1

N. J. A. Sloane, Aug 14 2001

nonn

Sometimes (Weisstein) called the "usual numbers" as opposed to what Greene and Knuth define as "unusual numbers" (A063538), which turn out to not be so unusual after all (Greene and Knuth 1990, Finch 2001). - Jonathan Vos Post, Sep 11 2010
If we define a divisor d|n to be superior if d >= n/d, then superior divisors are counted by A038548 and listed by A161908. This sequence lists numbers without a superior prime divisor, which is unique (A341676) when it exists. For example, the set of superior prime divisors of each n starts: {},{2},{3},{2},{5},{3},{7},{},{3},{5},{11},{},{13},{7}. The positions of empty sets give the sequence. - Gus Wiseman, Feb 24 2021
As Jonathan Vos Post's comment suggests, the sqrt(n-1)-smooth numbers are asymptotically less dense than their "unusual" complement. This is part of a larger picture of "typical" relative sizes of a number's prime factors: see, for example, the medians of the n-th smallest prime factors of the positive integers in A281889. - Peter Munn, Mar 03 2021

			a(100) = 360; a(1000) = 3744; a(10000) = 37665; a(100000)=375084;
a(10^6) = 3697669; a(10^7) = 36519633; a(10^8) = 360856296;
a(10^9) = 3571942311; a(10^10) = 35410325861; a(10^11) = 351498917129. - _Giovanni Resta_, Apr 12 2020

Greene, D. H. and Knuth, D. E., Mathematics for the Analysis of Algorithms, 3rd ed. Boston, MA: Birkhäuser, pp. 95-98, 1990.

N. J. A. Sloane, Table of a(n) for n = 1..10622 [Extending and correcting earlier b-files from T. D. Noe and Marius A. Burtea]
M. Beeler, R. W. Gosper and R. Schroeppel, HAKMEM, ITEM 29
Steven Finch, "RE: Unusual Numbers.", Aug 27 2001.
Hugo Pfoertner, Illustration of deviation from linear fit 3.7642*n, (2020).
Hugo Pfoertner, Illustration of relative error of asymptotic approximation, (2020).
Project Euler, Problem 668: Square root smooth numbers
V. Ramaswami, On the number of positive integers less than x and free of prime divisors greater than x^c, Bull. Amer. Math. Soc. 55 (1949), 1122-1127.
Eric W. Weisstein, Rough Number. [From _Jonathan Vos Post_, Sep 11 2010]
Wikipedia, Dickman function

Set difference of A048098 and A001248.
Complement of A063538.
Cf. A006530.
The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.
Positions of zeros in A341591.
A001221 counts prime divisors, with sum A001414.
A001222 counts prime-power divisors.
A033677 selects the smallest superior divisor.
A038548 counts superior (or inferior) divisors.
A051283 lists numbers without a superior prime-power divisor.
A056924 counts strictly superior (or strictly inferior) divisors.
A059172 lists numbers without a superior squarefree divisor.
A063962 counts inferior prime divisors.
A116882/A116883 list numbers with/without a superior odd divisor.
A161908 lists superior divisors.
A207375 lists central divisors.
A217581 selects the greatest inferior prime divisor.
A341642 counts strictly superior prime divisors.
A341676 gives unique superior prime divisors, with strict case A341643.
- Inferior: A033676, A066839, A069288, A161906, A333749, A333750.
- Superior: A070038, A072500, A341592, A341593, A341675.
- Strictly inferior: A060775, A070039, A333805, A333806, A341596, A341674.
- Strictly superior: A064052, A140271, A238535, A341594, A341595, A341644, A341645, A341646, A341673.
Cf. A000005, A000203, A020639, A112798, A281889.

[1] cat [m:m in [2..200]| Max(PrimeFactors(m)) lt Sqrt(m) ]; // Marius A. Burtea, May 08 2019

N:= 1000: # to get all terms <= N
Primes:= select(isprime, [2, seq(2*i+1, i=1..floor((N-1)/2))]):
S:= {$1..N} minus {seq(seq(m*p, m = 1 .. min(p, N/p)), p=Primes)}:
sort(convert(S, list)); # Robert Israel, Sep 02 2015

Prepend[Select[Range[192], FactorInteger[#][[-1, 1]] < Sqrt[#] &], 1] (* Ivan Neretin, Sep 02 2015 *)

from math import isqrt
from sympy import primepi
def A063539(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: 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+primepi(x//(y:=isqrt(x)))+sum(primepi(x//i)-primepi(i) for i in range(1,y)))
    return bisection(f,n,n) # Chai Wah Wu, Oct 05 2024

From Hugo Pfoertner, Apr 02 - Apr 12 2020: (Start)
For small n (e.g. n < 10000) a(n) can apparently be approximated by 3.7642*n.
Asymptotically, the number of sqrt(n)-smooth numbers < x is known to be (1-log(2))*x + O(x/log(x)), see Ramaswami (1949).
n = (1-log(2))*a(n) - 0.59436*a(n)/log(a(n)) is a fitted approximation. (End)
However, it is known that this fit only leads to an increase of accuracy in the range up to a(10^11). The improvement in accuracy suggested by the plot of the relative error for even larger n does not occur. For larger n the behavior of the error term O(x/log(x)) is not known. - Hugo Pfoertner, Nov 12 2023

A295084 Number of sqrt(n)-smooth numbers <= n.

Original entry on oeis.org

1, 1, 1, 3, 3, 3, 3, 4, 7, 7, 7, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 11, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 23, 30, 31, 31, 31, 31, 32, 32, 33, 33, 33, 33, 34, 34, 34, 35, 36, 36, 36, 36, 36, 36, 37, 37, 38, 38, 38, 39, 39, 39, 39, 39, 40

Offset: 1

Max Alekseyev, Nov 13 2017

a(n) = number of positive integers m<=n such that A006530(m) <= sqrt(n).

Wikipedia, Smooth number

Cf. A048098 (indices of records), A063539, A241419.

The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.

N:= 100: # to get a(1)..a(N)
G:= [0,seq(max(numtheory:-factorset(n)),n=2..N)]:
seq(nops(select(t -> t^2 <= n, G[1..n])),n=1..N); # Robert Israel, Nov 14 2017
a:=[];
for n from 1 to 100 do
   c:=0;
   for m from 1 to n do
      if A006530(m)^2 <= n then c:=c+1; fi; od:
a:=[op(a),c];
od:
a; # (Included because variants of it will apply to related sequences) - N. J. A. Sloane, Apr 10 2020

A295084(n) = my(r=n); forprime(p=sqrtint(n)+1,n, r-=n\p); r;

from math import isqrt
from sympy import primerange
def A295084(n): return int(n-sum(n//p for p in primerange(isqrt(n)+1,n+1))) # Chai Wah Wu, Oct 06 2024

a(n) = n - A241419(n).
If n is in A063539, then a(n)=a(n-1)+1; if n is in A001248, i.e., n=p^2 for prime p, then a(n)=a(n-1)+p; otherwise a(n)=a(n-1).
a(n) = (1 - log(2))*n + O(n/log(n)) as n -> infinity. - Robert Israel, Nov 14 2017

A333535 Card{ k<=n, k such that all prime divisors of k are < sqrt(k) }.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Apr 10 2020

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..65536

The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.

a:=[];
for n from 1 to 100 do
   c:=0;
   for m from 1 to n do
      if A006530(m)^2 < m then c:=c+1; fi; od:
a:=[op(a),c];
od:
a;
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 0, a(n-1)+
      `if`(max(map(i-> i[1], ifactors(n)[2]))^2Alois P. Heinz, Apr 10 2020

a[1] = 0;
a[n_] := a[n] = a[n-1] + Boole[Max[FactorInteger[n][[All, 1]]]^2 < n];
Array[a, 100] (* Jean-François Alcover, Nov 01 2020 *)

from math import isqrt
from sympy import primepi
def A333535(n): return int(n-1-primepi(n//(m:=isqrt(n)))+sum(primepi(i)-primepi(n//i) for i in range(1,m))) # Chai Wah Wu, Oct 06 2024

A333536 Number of sqrt(n-1)-smooth numbers <= n.

Original entry on oeis.org

0, 1, 1, 1, 3, 3, 3, 4, 4, 7, 7, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 16, 17, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 23, 23, 31, 31, 31, 31, 32, 32, 33, 33, 33, 33, 34, 34, 34, 35, 36, 36, 36, 36, 36, 36, 37, 37, 38, 38, 38, 39, 39, 39, 39, 39, 40, 41, 41, 41, 42

Offset: 1

N. J. A. Sloane, Apr 10 2020

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..20000

The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.

a:=[];
for n from 1 to 100 do
   c:=0;
   for m from 1 to n do
      if A006530(m)^2 < n then c:=c+1; fi; od:
a:=[op(a),c];
od:
a;

A242493 a(n) is the number of not-sqrt-smooth numbers ("jagged" numbers) not exceeding n. This is the counting function of A064052.

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 11, 12, 13, 14, 15, 16, 16, 16, 17, 17, 18, 19, 19, 20, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 28, 29, 30, 30, 31, 32, 32, 32, 32, 33, 34, 35, 35, 36, 36, 37, 38, 39, 39, 40, 41, 41, 41, 42, 43, 44, 45

Offset: 1

Jean-François Alcover, May 16 2014

nonn

This sequence is different from shifted A072490, after 22 terms.

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, chapter 2.21, p. 166.
Daniel H. Greene and Donald E. Knuth, Mathematics for the Analysis of Algorithms, 3rd ed., Birkhäuser, 1990, pp. 95-98.

Cf. A064052, A064775, A072490, A153810, A242610.

jaggedQ[n_] := jaggedQ[n] = (f = FactorInteger[n][[All, 1]]; s = Sqrt[n]; Count[f, p_ /; p > s] > 0); a[n_] := ( For[ cnt = 0; j = 2, j <= n, j++, If[jaggedQ[j], cnt++]]; cnt); Table[a[n], {n, 1, 100}]

from math import isqrt
from sympy import primepi
def A242493(n): return sum(primepi(n//i)-primepi(i) for i in range(1,isqrt(n)+1)) # Chai Wah Wu, Sep 01 2024

From Ridouane Oudra, Nov 07 2019: (Start)
a(n) = Sum_{i=1..floor(sqrt(n))} (pi(floor(n/i)) - pi(i)).
a(n) = Sum_{p<=sqrt(n)} (p-1) + Sum_{sqrt(n)a(n) = n - A064775(n). (End)
a(n) ~ log(2)*n - A153810 * n/log(n) - A242610 * n/log(n)^2 + O(n/log(n)^3) (Greene and Knuth, 1990). - Amiram Eldar, Apr 15 2021

Showing 1-6 of 6 results.

cp's OEIS Frontend

A048098 Numbers k that are sqrt(k)-smooth: if p | k then p^2 <= k when p is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Extensions

A063539 Numbers n that are sqrt(n-1)-smooth: largest prime factor of n (=A006530(n)) < sqrt(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Formula

A295084 Number of sqrt(n)-smooth numbers <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A333535 Card{ k<=n, k such that all prime divisors of k are < sqrt(k) }.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

A333536 Number of sqrt(n-1)-smooth numbers <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A242493 a(n) is the number of not-sqrt-smooth numbers ("jagged" numbers) not exceeding n. This is the counting function of A064052.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

Python

Formula