login
Numbers n that are not sqrt(n-1)-smooth: largest prime factor of n (=A006530(n)) >= sqrt(n).
36

%I #33 Oct 06 2024 09:16:28

%S 2,3,4,5,6,7,9,10,11,13,14,15,17,19,20,21,22,23,25,26,28,29,31,33,34,

%T 35,37,38,39,41,42,43,44,46,47,49,51,52,53,55,57,58,59,61,62,65,66,67,

%U 68,69,71,73,74,76,77,78,79,82,83,85,86,87,88,89,91

%N Numbers n that are not sqrt(n-1)-smooth: largest prime factor of n (=A006530(n)) >= sqrt(n).

%C 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 all numbers with a superior prime divisor, which is unique (A341676) when it exists. For example, 42 is in the sequence because it has a prime divisor 7 which is greater than the quotient 42/7 = 6. - _Gus Wiseman_, Feb 19 2021

%D D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms; see pp. 95-98.

%H Robert Israel, <a href="/A063538/b063538.txt">Table of n, a(n) for n = 1..10000</a>

%H Beeler, M., Gosper, R. W. and Schroeppel, R., <a href="http://www.inwap.com/pdp10/hbaker/hakmem/number.html#item29">HAKMEM, ITEM 29</a>

%F Union of A001248 and A064052. - _Gus Wiseman_, Feb 24 2021

%p N:= 1000: # to get all terms <= N

%p Primes:= select(isprime, [2,seq(2*i+1, i=1..floor((N-1)/2))]):

%p S:= {seq(seq(m*p, m = 1 .. min(p, N/p)),p=Primes)}:

%p sort(convert(S,list)); # _Robert Israel_, Sep 01 2015

%t Select[Range[2, 91], FactorInteger[#][[-1, 1]] >= Sqrt[#] &] (* _Ivan Neretin_, Aug 30 2015 *)

%o (Python)

%o from math import isqrt

%o from sympy import primepi

%o def A063538(n):

%o def f(x): return int(n+x-primepi(x//(y:=isqrt(x)))-sum(primepi(x//i)-primepi(i) for i in range(1,y)))

%o m, k = n, f(n)

%o while m != k: m, k = k, f(k)

%o return m # _Chai Wah Wu_, Oct 05 2024

%Y Cf. A006530, A063762.

%Y Complement of A063539. Supersequence of A001358 (semiprimes).

%Y The strictly superior version is A064052 (complement: A048098), with associated unique prime divisor A341643.

%Y The case of odd instead of prime divisors is A116883 (complement: A116882).

%Y Also nonzeros of A341591 (number of superior prime divisors).

%Y The unique superior prime divisors of the terms are A341676.

%Y A001221 counts prime divisors, with sum A001414.

%Y A033677 selects the smallest superior divisor.

%Y A038548 counts superior (also inferior) divisors.

%Y A161908 lists superior divisors.

%Y - Inferior: A033676, A063962, A066839, A161906, A217581, A333749, A333750.

%Y - Superior: A051283, A059172, A070038, A072500, A341592, A341593, A341675.

%Y - Strictly Inferior: A056924, A060775, A070039, A333805, A333806, A341596, A341674, A341677.

%Y - Strictly Superior: A140271, A238535, A341594, A341595, A341642, A341644, A341645/A341646, A341673.

%Y Cf. A000005, A001055, A001222, A001248, A020639, A056239, A112798.

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_, Aug 14 2001