cp's OEIS Frontend

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

%I A240751 #84 Feb 26 2025 01:54:03
%S A240751 2,6,4,6,12,15,8,10,21,12,14,50,27,30,16,18,36,20,22,85,45,24,26,100,
%T A240751 28,30,57,60,182,63,32,34,135,36,38,78,150,40,42,81,44,46,175,90,93,
%U A240751 48,50,99,52,54,210,215,56,58,114,60,62,120,123,364,126,129,64
%N A240751 a(n) is the smallest k such that in the prime power factorization of k! there exists at least one exponent n.
%C A240751 For n = 1, 2, 3, etc., a(n)! contains 2^1, 3^2, 2^3, 2^4, 3^5, 3^6, 2^7, etc.
%C A240751 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.
%C A240751 Sum_{i>=1} n*(p-1)/p^i = n and Sum_{i=1..m} floor(n*(p-1)/p^i) < n where m = floor(log(n*(p-1))/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*(p-1) and p|k. - _David A. Corneth_, Mar 21 2017
%C A240751 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
%H A240751 David A. Corneth, <a href="/A240751/b240751.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Peter J. C. Moses)
%H A240751 Vladimir Shevelev, Charles R. Greathouse IV, and Peter J. C. Moses, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Moses/moses1.html">On intervals (kn, (k+1)n) containing a prime for all n>1</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.7.3. Also <a href="http://arxiv.org/abs/1212.2785">arXiv preprint</a>, arXiv:1212.2785 [math.NT], 2012.
%H A240751 Robert G. Wilson v, <a href="/A240751/a240751.pdf">Graph of the first 10000 terms</a>
%H A240751 Robert G. Wilson v, <a href="/A240751/a240751_1.pdf">Graph of the first 2500000 terms.</a>
%F A240751 a(n) <= n*t, where t is such that t*(1-1300/log^4(t))/log(t) >= n+1. Cf. Shevelev, Greathouse IV, and Moses link, Proposition 6.
%F A240751 a(n) = A284050(n)*n + A284051(n). - _Robert G. Wilson v_, Apr 15 2017
%e A240751 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.
%e A240751 From _David A. Corneth_, Mar 21 2017: (Start)
%e A240751 To compute a(5) we first see if there is a factorial k! such that 2^5||k!. I.e., p = 2. The next multiple of p = 2 and larger than n * (p-1) = 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.
%e A240751 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)
%t A240751 fi[n_]:=fi[n]=FactorInteger[n!]; A240751={2}; Do[AppendTo[A240751, NestWhile[#+1 &,n+1,!MemberQ[Last[Transpose[fi[#]]],n]&]], {n,2,100}]; A240751 (* _Peter J. C. Moses_, Apr 12 2014 *)
%t A240751 Table[k = 2; While[! MemberQ[FactorInteger[k!][[All, -1]], n], k++]; k, {n, 63}] (* _Michael De Vlieger_, Mar 24 2017 *)
%t A240751 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 *)
%o A240751 (PARI) hasexp(k, n)=f = factor(k!); for (i=1, #f~, if (f[i, 2] == n, return (1));); return (0);
%o A240751 a(n) = {k = 2; while (!hasexp(k, n), k++); k;} \\ _Michel Marcus_, Apr 12 2014
%o A240751 (PARI) a(n)=my(r = 0, m, p = 2, cn, cm); while(1,cn = n * (p-1); 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
%o A240751 (PARI) valp(n,p)=my(s=n); while(n\=p, s+=n); s
%o A240751 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(upper-lower>1, m=(lower+upper)\2; mV=f(m); if(mV<n, lower=m; lV=mV, upper=m; uV=mV)); if(uV==n, upper, oo)
%o A240751 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.");
%o A240751 a(n)=my(t); forprime(p=2,, t=(n+1)*(p-1)\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
%Y A240751 Cf. A240537, A240606, A240619, A240620, A240668, A240669, A240670, A240672, A240695, A284050, A284051.
%K A240751 nonn,easy
%O A240751 1,1
%A A240751 _Vladimir Shevelev_, Apr 12 2014
%E A240751 More terms from _Michel Marcus_, Apr 12 2014