A109665 - OEIS

%I #18 Sep 03 2024 15:02:44

%S 11,12,273,714,15015,149226,22309287,60138078,25588752189,8720021310,

%T 55093966638711,197238101872812,92887605454857213,174457101106502214,

%U 25517925977422393515,951603427533949306116,832747507651789493981217

%N Smallest number that has exactly n distinct prime factors and ends with the digits of n.

%e a(2)=12 since 12 has 2 prime factors (2 and 3) and ends with 2 and is the smallest such number

%t f[n_] := Block[{k = n, inc = 10^Floor[ Log[10, n] + 1]}, While[ Length[ FactorInteger[ k]] != n, k += inc]; k]; (* _Robert G. Wilson v_, Aug 08 2005 *)

%o (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;

%o leastCombo(numPrimes, firstPrime, limit, M, r) = lcHelper(numPrimes, firstPrime, limit, prod(i = firstPrime, firstPrime + numPrimes - 1, prime(i)), 1, firstPrime + numPrimes, M, r);

%o lcHelper(left, i, limit, minimum, found, nextP, M, r) = local(p); if (left == 0, return(if (found%M == r, found, limit))); p = prime(i); limit = lcHelper(left - 1, i + 1, limit, minimum, found*p, nextP, M, r); if (minimum*prime(nextP)/p <= limit, limit = lcHelper(left, i + 1, limit, minimum*prime(nextP)/p, found, nextP + 1, M, r)); limit;

%o {

%o \\This function returns 0 if its assumptions fail; otherwise it returns the correct answer. With the defaults 3 and 40, no failures occur in the first 1000 terms.

%o a(n, searchP = 3, searchSize = 40) =

%o local(r, num2, num5, d, M, pLeft, assumedP, fixed, x, rNeeded, y, best, z, zz, j, z3, pLimit);

%o r = n;

%o d = digitcount(n);

%o if (n < 7,

%o while (omega(r) != n, r += 10);

%o return(r)

%o );

%o while (num2 < d && !(r%2),

%o num2++;

%o r = r/2

%o );

%o while (num5 < d && !(r%5),

%o num5++;

%o r = r/5

%o );

%o M = 10^d/2^num2/5^num5;

%o pLeft = n - if (num2, 1, 0) - if (num5, 1, 0);

%o searchP = 3;

%o searchSize = 40;

%o fixed = 2^num2*5^num5;

%o assumedP = pLeft - searchP;

%o x = 3*prod(i = 4, assumedP + 2, prime(i));

%o rNeeded = lift(Mod(r, M)/Mod(x, M));

%o best = prime(n + 40)^searchP;

%o forvec (v = vector(searchP, i, [assumedP + 3, assumedP + searchSize + 2]), y = prod(i = 1, searchP, prime(v[i])); if (y%M == rNeeded, best = min(best, y)), 2);

%o if (best == searchP ^prime(n + 40), return(0));

%o y = fixed*x*best;

%o z = fixed*x*prod(i = assumedP + 3, pLeft + 2, prime(i));

%o if (z >= 2*y, return(0));

%o rNeeded = lift(Mod(r, M)/3);

%o return(fixed*3*leastCombo(pLeft - 1, 4, y/fixed/3, M, rNeeded));

%o } \\ _David Wasserman_, Sep 30 2008

%Y Cf. A109687 [From _David Wasserman_, Sep 30 2008]

%K base,nonn

%O 1,1

%A _Erich Friedman_, Aug 06 2005

%E a(11) - a(17) from _Robert G. Wilson v_, Aug 08 2005

%E Corrected terms. Deleted second program, which appeared to be incorrect. - _David Wasserman_, Sep 30 2008