A109687 Smallest number ending with the digits of n that has exactly n prime factors (counted with multiplicity).

11, 22, 63, 24, 405, 96, 2187, 1408, 124659, 65610, 4271211, 38912, 37614213, 40507614, 326836215, 802816, 10010754117, 2496709818, 23202182619, 14417920, 886805499321, 76709256822, 1474909801623, 25165824, 3922632451125

Offset

1,1

Links

Robert Israel, Table of n, a(n) for n = 1..2078

Example

a(5)=405 since 405=3*3*3*3*5 (5 factors) and ends with 5 and is the smallest such number

Maple

f:= proc(n) uses priqueue;
  local pq, d, td, t, v, p, i, w2, w5, more2, more5;
  initialize(pq);
  d:=1 + ilog10(n); td:= 10^d;
  w2:= padic:-ordp(n, 2);
  more2:= (w2 >= d);
  w2:= min(w2, d);
  w5:= padic:-ordp(n, 5);
  more5:= (w5 >= d);
  w5:= min(w5, d);
  if more2 then insert([-5^w5 * 2^(n-w5), 2, n-w5-w2], pq)
  else insert([-2^w2 * 5^w5 * 3^(n-w5-w2), 3, n-w5-w2], pq)
  fi;
  do
    t:= extract(pq);
    v:= -t[1];
    if v mod td = n then return v fi;
    p:= nextprime(t[2]);
    if p = 5 and not more5 then p:= 7 fi;
    for i from 1 to t[3] do
        insert([t[1]*(p/t[2])^i, p, i], pq);
    od;
  od;
end proc:
map(f, [$1..30]); # Robert Israel, Jul 23 2024

Prog

Program from David Wasserman, Sep 19 2008: (Start)
(PARI) digitcount(n, base = 10) = local(d); if (n == 0, return(1)); d = 1 + floor(log(n)/log(base)); while (n >= base^d, d++); while (n < base^(d - 1), d--); d;
{
a(n) =
local(r, num2, num5, d, M, pLeft, mainP, searchP, fixed, x, rNeeded, y, nextP);
r = n;
d = digitcount(n);
while (num2 < d && !(r%2),
num2++;
r = r/2
);
while (num5 < d && !(r%5),
num5++;
r = r/5
);
M = 10^d/2^num2/5^num5;
pLeft = n - num2 - num5;
mainP = if (num2 == d, 2, 3);
searchP = min(4, pLeft);
fixed = 2^num2*5^num5;
x = mainP^(pLeft - searchP);
rNeeded = lift(Mod(r, M)/Mod(x, M));
while (bigomega(rNeeded) != searchP,
rNeeded += M
);
y = fixed*x*rNeeded;
if (mainP == 2,
nextP = 3,
nextP = if (num5 == d, 5, 7)
);
while (searchP < pLeft && fixed*x*nextP^(1 + searchP)/mainP < y,
searchP++;
x /= mainP
);
rNeeded = lift(Mod(r, M)/Mod(x, M));
while (bigomega(rNeeded) != searchP,
rNeeded += M
);
return(fixed*x*rNeeded);
} (End)

Crossrefs

Cf. A109665 [From David Wasserman, Sep 30 2008]

Sequence in context: A070069 A178664 A292926 * A225361 A111696 A047902

Adjacent sequences: A109684 A109685 A109686 * A109688 A109689 A109690

Keyword

base,nonn,look

Author

Erich Friedman, Aug 07 2005

Extensions

More terms from David Wasserman, Sep 18 2008

Status

approved