A388302 - OEIS

%I #61 Sep 24 2025 00:44:36

%S 1,1,2,2,2,2,4,6,7,6,9,9,9,12,14,12,15,16,17,18,19,19,20,21,22,24,24,

%T 24,27,27,29,30,30,32,34,33,34,34,37,37,38,38,39,41,41,41,44,45,46,46,

%U 48,48,50,50,52,53,53,53,56,56,56,58,62,62,64,64,64,64,66,66,68,68,68,70,71,72,73,72

%N a(n) = is the smallest m >= 1 such that n! = b_1*...*b_t with b_1 < ... < b_t and m = b_t - b_1.

%C Empirical observation: while generating this sequence, it seems like searching for factors around a window of (n!)^(1/k), where 2 <= k <= n will find likely matches. This is due to the geometric mean of k factors being near (n!)^(1/k). No proof if this heuristic method guarantees finding valid factors, or a numerical lower bound on the window width.

%C From _David A. Corneth_, Sep 17 2025: (Start)

%C When m = 0 is allowed we would have a(n) = 0 for all n and we could define a(1).

%C As m >= 1, t > 1 and so b_1*b_t <= n! and so b_1 < sqrt(n!) (< as for n >= 2 we have n! is never a square).

%C More generally b_1 < (n!)^(1/t).

%C a(n) <= min(A061057(n), n-2) for n>=3 where upper bound n-2 comes from t = n-1, b_1 = 2, b_t = n. (End)

%D P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique (1980), p. 76.

%H Thomas Bloom, <a href="https://www.erdosproblems.com/393">Problem 393</a>, Erdős Problems.

%H David A. Corneth, <a href="/A388302/a388302.gp.txt">PARI program</a>

%H David A. Corneth, <a href="/A388302/a388302_1.gp.txt">List of tuples multiplying to n! and giving a(n) for n = 2..79</a>

%H Charlie Liou, <a href="https://github.com/swrlly/erdos393/blob/main/geometric_mean_heuristic.py">Python program using geometric mean heuristic</a>

%H Erdős problems database contributors, <a href="https://github.com/teorth/erdosproblems/issues/92">Issue 92</a> linking Erdős problems to the OEIS.

%e For n = 3, a(3) = 1 because 3! = 2*3 and 3 - 2 = 1.

%e For n = 8, a(8) = 4 with two solutions:

%e   8! = 32*35*36, 36-32 = 4

%e   8! = 12*14*15*16, 16-12 = 4.

%t gens[m_,x_]:=Join[{x},#,{x+m}]&/@Subsets[x+Range[1,m-1]]

%t decode[s_,t_]:=If[Length[t]==0,t,s/.t]

%t process[nf_,s_,x_]:=decode[s,Solve[Times@@s==nf,x,Integers]]

%t do[n_,m_]:=Flatten[process[n!,#,x]&/@gens[m,x],1]

%t do[n_]:=Module[{m,d},For[m=1,True,m++,d=do[n,m];If[Length[d]>0,Return[d]]]]

%t (* From Boris Alexeev (Erdős problems database contributor to Issue 92) who computed a(21)-a(22) *)

%o (Python)

%o from math import prod, factorial

%o from sympy.ntheory import factorint

%o from sympy.utilities.iterables import multiset_partitions

%o def a(n):

%o     prime_factors = [factors for prime in [[i for _ in range(j)] for i, j in factorint(factorial(n)).items()] for factors in prime]

%o     best_m = float('inf')

%o     for partition in multiset_partitions(prime_factors):

%o         factors = sorted([prod(group) for group in partition])

%o         if len(factors) != len(set(factors)): continue

%o         test_m = factors[-1] - factors[0]

%o         if test_m < best_m and len(factors) >= 2: best_m = test_m

%o     return best_m

%o print([a(n) for n in range(3, 13)])

%o (PARI) \\ See also David A. Corneth link

%o R(r,m,u)={my(t=r, e=logint(r,m+1)); if(e>1 && sqrtnint(r,e)<u, fordiv(r, d, my(d2=r/d); if(d>d2 && d2>m && u>d2, t=min(t,self()(d,d2,u))))); t}

%o a(n)={my(r=n!, t=r-1); fordiv(r, d, my(d2=r/d); if(d>d2, t=min(t,R(d,d2,d2+t)-d2))); t} \\ _Andrew Howroyd_, Sep 16 2025

%Y Cf. A061057, A082119.

%K nonn

%O 2,3

%A _Charlie Liou_, Sep 16 2025

%E a(23)-a(40) from _Andrew Howroyd_, Sep 16 2025

%E a(41)-a(79) from _David A. Corneth_, Sep 19 2025