cp's OEIS Frontend

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

%I A063539 #101 Feb 16 2025 08:32:45
%S A063539 1,8,12,16,18,24,27,30,32,36,40,45,48,50,54,56,60,63,64,70,72,75,80,
%T A063539 81,84,90,96,98,100,105,108,112,120,125,126,128,132,135,140,144,147,
%U A063539 150,154,160,162,165,168,175,176,180,182,189,192,195,196
%N A063539 Numbers n that are sqrt(n-1)-smooth: largest prime factor of n (=A006530(n)) < sqrt(n).
%C A063539 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
%C A063539 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
%C A063539 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
%D A063539 Greene, D. H. and Knuth, D. E., Mathematics for the Analysis of Algorithms, 3rd ed. Boston, MA: Birkhäuser, pp. 95-98, 1990.
%H A063539 N. J. A. Sloane, <a href="/A063539/b063539.txt">Table of a(n) for n = 1..10622</a> [Extending and correcting earlier b-files from T. D. Noe and Marius A. Burtea]
%H A063539 M. Beeler, R. W. Gosper and R. Schroeppel, <a href="http://www.inwap.com/pdp10/hbaker/hakmem/number.html#item29">HAKMEM, ITEM 29</a>
%H A063539 Steven Finch, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;1bd7a1c2.0108">"RE: Unusual Numbers."</a>, Aug 27 2001.
%H A063539 Hugo Pfoertner, <a href="/A063539/a063539.png">Illustration of deviation from linear fit 3.7642*n</a>, (2020).
%H A063539 Hugo Pfoertner, <a href="/A063539/a063539_1.png">Illustration of relative error of asymptotic approximation</a>, (2020).
%H A063539 Project Euler, <a href="https://projecteuler.net/problem=668">Problem 668: Square root smooth numbers</a>
%H A063539 V. Ramaswami, <a href="https://doi.org/10.1090/S0002-9904-1949-09337-0">On the number of positive integers less than x and free of prime divisors greater than x^c</a>, Bull. Amer. Math. Soc. 55 (1949), 1122-1127.
%H A063539 Eric W. Weisstein, <a href="https://mathworld.wolfram.com/RoughNumber.html">Rough Number.</a> [From _Jonathan Vos Post_, Sep 11 2010]
%H A063539 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dickman_function">Dickman function</a>
%F A063539 From _Hugo Pfoertner_, Apr 02 - Apr 12 2020: (Start)
%F A063539 For small n (e.g. n < 10000) a(n) can apparently be approximated by 3.7642*n.
%F A063539 Asymptotically, the number of sqrt(n)-smooth numbers < x is known to be (1-log(2))*x + O(x/log(x)), see Ramaswami (1949).
%F A063539 n = (1-log(2))*a(n) - 0.59436*a(n)/log(a(n)) is a fitted approximation. (End)
%F A063539 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
%e A063539 a(100) = 360; a(1000) = 3744; a(10000) = 37665; a(100000)=375084;
%e A063539 a(10^6) = 3697669; a(10^7) = 36519633; a(10^8) = 360856296;
%e A063539 a(10^9) = 3571942311; a(10^10) = 35410325861; a(10^11) = 351498917129. - _Giovanni Resta_, Apr 12 2020
%p A063539 N:= 1000: # to get all terms <= N
%p A063539 Primes:= select(isprime, [2, seq(2*i+1, i=1..floor((N-1)/2))]):
%p A063539 S:= {$1..N} minus {seq(seq(m*p, m = 1 .. min(p, N/p)), p=Primes)}:
%p A063539 sort(convert(S, list)); # _Robert Israel_, Sep 02 2015
%t A063539 Prepend[Select[Range[192], FactorInteger[#][[-1, 1]] < Sqrt[#] &], 1] (* _Ivan Neretin_, Sep 02 2015 *)
%o A063539 (Magma) [1] cat [m:m in [2..200]| Max(PrimeFactors(m)) lt Sqrt(m) ]; // _Marius A. Burtea_, May 08 2019
%o A063539 (Python)
%o A063539 from math import isqrt
%o A063539 from sympy import primepi
%o A063539 def A063539(n):
%o A063539     def bisection(f,kmin=0,kmax=1):
%o A063539         while f(kmax) > kmax: kmax <<= 1
%o A063539         while kmax-kmin > 1:
%o A063539             kmid = kmax+kmin>>1
%o A063539             if f(kmid) <= kmid:
%o A063539                 kmax = kmid
%o A063539             else:
%o A063539                 kmin = kmid
%o A063539         return kmax
%o A063539     def f(x): return int(n+primepi(x//(y:=isqrt(x)))+sum(primepi(x//i)-primepi(i) for i in range(1,y)))
%o A063539     return bisection(f,n,n) # _Chai Wah Wu_, Oct 05 2024
%Y A063539 Set difference of A048098 and A001248.
%Y A063539 Complement of A063538.
%Y A063539 Cf. A006530.
%Y A063539 The following are all different versions of sqrt(n)-smooth numbers: A048098, A063539, A064775, A295084, A333535, A333536.
%Y A063539 Positions of zeros in A341591.
%Y A063539 A001221 counts prime divisors, with sum A001414.
%Y A063539 A001222 counts prime-power divisors.
%Y A063539 A033677 selects the smallest superior divisor.
%Y A063539 A038548 counts superior (or inferior) divisors.
%Y A063539 A051283 lists numbers without a superior prime-power divisor.
%Y A063539 A056924 counts strictly superior (or strictly inferior) divisors.
%Y A063539 A059172 lists numbers without a superior squarefree divisor.
%Y A063539 A063962 counts inferior prime divisors.
%Y A063539 A116882/A116883 list numbers with/without a superior odd divisor.
%Y A063539 A161908 lists superior divisors.
%Y A063539 A207375 lists central divisors.
%Y A063539 A217581 selects the greatest inferior prime divisor.
%Y A063539 A341642 counts strictly superior prime divisors.
%Y A063539 A341676 gives unique superior prime divisors, with strict case A341643.
%Y A063539 - Inferior: A033676, A066839, A069288, A161906, A333749, A333750.
%Y A063539 - Superior: A070038, A072500, A341592, A341593, A341675.
%Y A063539 - Strictly inferior: A060775, A070039, A333805, A333806, A341596, A341674.
%Y A063539 - Strictly superior: A064052, A140271, A238535, A341594, A341595, A341644, A341645, A341646, A341673.
%Y A063539 Cf. A000005, A000203, A020639, A112798, A281889.
%K A063539 nonn
%O A063539 1,2
%A A063539 _N. J. A. Sloane_, Aug 14 2001