

A240751


a(n) is the smallest k such that in the prime power factorization of k! there exists at least one exponent n.


24



2, 6, 4, 6, 12, 15, 8, 10, 21, 12, 14, 50, 27, 30, 16, 18, 36, 20, 22, 85, 45, 24, 26, 100, 28, 30, 57, 60, 182, 63, 32, 34, 135, 36, 38, 78, 150, 40, 42, 81, 44, 46, 175, 90, 93, 48, 50, 99, 52, 54, 210, 215, 56, 58, 114, 60, 62, 120, 123, 364, 126, 129, 64
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

For n = 1, 2, 3, etc., a(n)! contains 2^1, 3^2, 2^3, 2^4, 3^5, 3^6, 2^7, etc.
Note that for number N and for sufficiently large k=k(N), in interval (k/(N+1), k/N] there exists a prime, and in case sqrt(k) < k/(N+1), p^N  k!. Therefore the sequence is infinite.
Sum_{i>=1} n*(p1)/p^i} = n and Sum_{i=1..m} floor(n*(p1)/p^i)) < n where m = floor(log(n*(p1)/log(p)). Therefore, we can test exponents of primes in k! to see if the exponent of p is n, where k is the least k > n*(p1) and pk.  David A. Corneth, Mar 21 2017
Record k's are 2, 6, 12, 15, 21, 50, 85, 100, 182, 210, 215, 364, 553, 560, 854, 931, 1120, etc., at indices 1, 2, 5, 6, 9, 12, 20, 24, 29, 51, 52, 60, 91, 92, 141, 154, 185, 186, 342, 403, 441, 447, 635, 765, 1035, 1092, 1378, 1435, 1540, 2015, 2553, 2740, 2808, 2865, 3265, 4922, 5322, 7209, etc.  Robert G. Wilson v, Apr 13 2017


LINKS



FORMULA

a(n) <= n*t, where t is such that t*(11300/log^4(t))/log(t) >= n+1. Cf. Shevelev, Greathouse IV, and Moses link, Proposition 6.


EXAMPLE

a(2)=6, since 6!=2^4*3^2*5, and there is no k<6 such that the factorization of k! contains a power p^2, where p is prime.
To compute a(5) we first see if there is a factorial k! such that 2^5k!. I.e., p = 2. The next multiple of p = 2 and larger than n * (p1) = 5 is 6. The exponent of 2 in 6! Is 3 + 1 = 4 < 5. Therefore, we try the next multiple of p = 2 and larger than 6 which is 8. 8 has three factors 2. Therefore, 8! has 4 + 3 = 7 > 5 factors 2 and no factorial exists that properly divides 2^5.
So we try the next prime larger than 2, which is p = 3. We start with the next multiple of p and larger than n * (p  1) = 10, which is 12. The exponent of 3 in 12! is floor(12/3) + floor(4/3) = 5. Therefore, 12! is properly divisible by 3^5 and 12 is the least k such that k! has 5 as an exponent in the prime factorization. (End)


MATHEMATICA

Table[k = 2; While[! MemberQ[FactorInteger[k!][[All, 1]], n], k++]; k, {n, 63}] (* Michael De Vlieger, Mar 24 2017 *)
f[n_] := Block[{k = 0, p = 2, s}, While[True, While[s = Plus @@ Rest@ NestWhileList[ Floor[#/p] &, (p 1)n +k, # > 0 &]; s < n, k++]; If[s == n, Goto[fini]]; k = 0; p = NextPrime@ p]; Label[fini]; (p 1)n +k]; Array[f, 70] (* Robert G. Wilson v, Apr 15 2017, revised Apr 16 2017 and Apr 19 2017 *)


PROG

(PARI) hasexp(k, n)=f = factor(k!); for (i=1, #f~, if (f[i, 2] == n, return (1)); ); return (0);
a(n) = {k = 2; while (!hasexp(k, n), k++); k; } \\ Michel Marcus, Apr 12 2014
(PARI) a(n)=my(r = 0, m, p = 2, cn, cm); while(1, cn = n * (p1); m = p*(cn\p+1); r = 0; cm = m; while(cm, r+=cm\=p); while(r < n, m += p; r += valuation(m, p)); if(r==n, return(m)); p = nextprime(p + 1)) \\ David A. Corneth, Mar 20 2017
(PARI) valp(n, p)=my(s=n); while(n\=p, s+=n); s
findLower(f, n, lower, upper)=my(lV=f(lower), uV, m, mV); if(lV>=n, return(if(lV==n, lower, oo))); uV=f(upper); if(uV<n, return(oo)); while(upperlower>1, m=(lower+upper)\2; mV=f(m); if(mV<n, lower=m; lV=mV, upper=m; uV=mV)); if(uV==n, upper, oo)
addhelp(findLower, "findLower(f, n, lower, upper): Given a nondecreasing function f on [lower, upper], find the least integer m, lower <= m <= upper, such that f(m) = n, or an infinite value if no such m exists.");
a(n)=my(t); forprime(p=2, , t=(n+1)*(p1)\p; t=findLower(k>valp(k, p), n, t, logint(t, p)+t); if(t!=oo, return(t*p))) \\ Charles R Greathouse IV, Jul 27 2017


CROSSREFS

Cf. A240537, A240606, A240619, A240620, A240668, A240669, A240670, A240672, A240695, A284050, A284051.


KEYWORD

nonn,easy


AUTHOR



EXTENSIONS



STATUS

approved



