login
Smallest 7-smooth number beginning with n.
4

%I #36 Sep 19 2024 02:11:32

%S 1,2,3,4,5,6,7,8,9,10,112,12,135,14,15,16,175,18,192,20,21,224,2304,

%T 24,25,2625,27,28,294,30,315,32,336,343,35,36,375,384,392,40,4116,42,

%U 432,441,45,4608,4704,48,49,50,512,525,5376,54,55125,56,576,588,59049,60

%N Smallest 7-smooth number beginning with n.

%H Chai Wah Wu, <a href="/A085908/b085908.txt">Table of n, a(n) for n = 1..10000</a>

%e a(23) = 2304 = 2^8*3^2 is the smallest 7-smooth number beginning with 23. (23, 230, 231, 232, ..., 239, 2301, 2302, 2303 etc. have a divisor > 10.)

%p N:= 300: # for a(1) .. a(N)

%p V:= Vector(N): count:= 0:with(priqueue):

%p initialize(pq);

%p insert([-1,0,0,0,0],pq);

%p while count < N do

%p t:= extract(pq);

%p x:= -t[1];

%p for d from ilog10(x) to 0 by -1 do

%p xd:= floor(x/10^d);

%p if xd > N then break fi;

%p if V[xd] = 0 then V[xd]:= x; count:= count+1; fi;

%p od;

%p insert([-7*x,t[2],t[3],t[4],t[5]+1],pq);

%p if t[5]=0 then

%p insert([-5*x,t[2],t[3],t[4]+1,0],pq);

%p if t[4] = 0 then

%p insert([-3*x,t[2],t[3]+1,0,0],pq);

%p if t[3] = 0 then

%p insert([-2*x,t[2]+1,0,0,0],pq);

%p fi fi fi;

%p od:

%p convert(V,list); # _Robert Israel_, Sep 18 2024

%t a[n_] := Module[{d = IntegerDigits[n], k = 1}, While[Max[FactorInteger[k][[;; , 1]]] > 7 || Length[IntegerDigits[k]] < Length[d] || IntegerDigits[k][[1 ;; Length[d]]] != d, k++]; k]; Array[a, 60] (* _Amiram Eldar_, Apr 30 2022 *)

%o (PARI) hc(n) = local(f); f = factor(n); f[matsize(f)[1], 1] < 10;

%o a(n) = local(d, x); if (hc(n), return(n)); d = 1; while (d, for (i = 1, 10^d - 1, x = n*10^d + i; if (hc(x), return(x))); d++); \\ _David Wasserman_, Feb 11 2005

%o (Python)

%o from itertools import count

%o from sympy import integer_log

%o def A085908(n):

%o if n<2: return n

%o def f(x):

%o c = 0

%o for i in range(integer_log(x,7)[0]+1):

%o for j in range(integer_log(m:=x//7**i,5)[0]+1):

%o for k in range(integer_log(r:=m//5**j,3)[0]+1):

%o c += (r//3**k).bit_length()

%o return c

%o for l in count(0):

%o kmin, kmax = n*10**l-1, (n+1)*10**l-1

%o mmin, mmax = f(kmin), f(kmax)

%o if mmax>mmin:

%o while kmax-kmin > 1:

%o kmid = kmax+kmin>>1

%o mmid = f(kmid)

%o if mmid > mmin:

%o kmax, mmax = kmid, mmid

%o else:

%o kmin, mmin = kmid, mmid

%o return kmax # _Chai Wah Wu_, Sep 17 2024

%Y Cf. A002473.

%K base,nonn,look

%O 1,2

%A _Amarnath Murthy_, Jul 09 2003

%E Corrected and extended by _David Wasserman_, Feb 11 2005

%E Name corrected by _J. Lowell_, Apr 30 2022