login
A106429
Smallest number beginning with 9 and having exactly n prime divisors counted with multiplicity.
28
97, 9, 92, 90, 918, 96, 972, 960, 9072, 9600, 90624, 9216, 93312, 90112, 903168, 98304, 995328, 917504, 9043968, 9175040, 90243072, 9437184, 95551488, 92274688, 924844032, 922746880, 9042919424, 905969664, 9172942848, 9059696640
OFFSET
1,1
EXAMPLE
a(2) = 9 = 3^2.
PROG
(PARI) a(n) = {i = 2^n; while ((digits(i)[1] != 9) || (bigomega(i)!=n), i++); i; } \\ Michel Marcus, Sep 14 2013
(Python)
from itertools import count
from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A106429(n):
if n == 1: return 97
def g(x, a, b, c, m): yield from (((d, ) for d in enumerate(primerange(b, isqrt(x//c)+1), a)) if m==2 else (((a2, b2), )+d for a2, b2 in enumerate(primerange(b, integer_nthroot(x//c, m)[0]+1), a) for d in g(x, a2, b2, c*b2, m-1)))
def f(x): return int(sum(primepi(x//prod(c[1] for c in a))-a[-1][0] for a in g(x, 0, 1, 1, n)))
for l in count(len(str(1<<n))-1):
kmin, kmax = 9*10**l-1, 10**(l+1)-1
mmin, mmax = f(kmin), f(kmax)
if mmax>mmin:
while kmax-kmin > 1:
kmid = kmax+kmin>>1
mmid = f(kmid)
if mmid > mmin:
kmax, mmax = kmid, mmid
else:
kmin, mmin = kmid, mmid
return kmax # Chai Wah Wu, Aug 29 2024
KEYWORD
base,nonn
AUTHOR
Ray Chandler, May 02 2005
STATUS
approved