cp's OEIS Frontend

A139004 Number of operations A000142 (i.e., x!) or A000196 (i.e., floor(sqrt(x))) needed to get n, starting with 4.

%I A139004 #56 Feb 28 2025 20:51:18
%S A139004 2,1,10,0,7,11,24,27,29,9,36,40,36,17,37,31,22,31,37,42,19,37,21,1,26,
%T A139004 13,51,41,36,6,30,41,44,33,16,33,31,64,35,50,25,43,12,18,41,18,42,55,
%U A139004 39,23,71,65,45,43,52,39,49,44,51,60,57,59,24,66,26,36,46,51,46,26,48,76
%N A139004 Number of operations A000142 (i.e., x!) or A000196 (i.e., floor(sqrt(x))) needed to get n, starting with 4.
%C A139004 Knuth conjectured that any number can be obtained in this way, starting from 4.
%C A139004 This sequence gives the minimal number of operations needed to do so.
%C A139004 To ensure the sequence is well-defined, define a(n)=-1 if it is not possible to get n in the given way.
%C A139004 If we are allowed to use tan(x) just once, then a single 2 is enough to get any positive integer, if Knuth's conjecture that one 4 is enough is true. From 2, (((-tan(2.))!)!)! = 5.592..., then floor, factorial gets 120, then sqrt, sqrt gives 3.162..., and floor gives 3, or negate, floor, negate gives 4. - _N. J. A. Sloane_, Feb 26 2025
%C A139004 The article by Bendersky is relevant because it gives an explicit formula for n using four 2's (and some logs). Good illustration of techniques. - _N. J. A. Sloane_, Feb 26 2025
%H A139004 Jon E. Schoenfield, <a href="/A139004/b139004.txt">Table of n, a(n) for n = 1..1000</a>
%H A139004 Eli Bendersky, <a href="https://eli.thegreenplace.net/2025/making-any-integer-with-four-2s/">Making any integer with four 2s</a>, Blog Post, Feb 22 2025
%H A139004 Eli Bendersky, <a href="/A139004/a139004.pdf">Making any integer with four 2s</a>, Blog Post, Feb 22 2025 [Local copy, with the author's permission]
%H A139004 D. E. Knuth, <a href="http://www.jstor.org/stable/2689238">Representing numbers using only one 4</a>, Mathematics Magazine, Vol. 37, No. 5 (Nov. 1964), pp. 308-310.
%H A139004 John E. Maxfield, <a href="http://www.jstor.org/stable/2688966">A Note on N!</a>, Mathematics Magazine, Vol. 43, No. 2 (March 1970), pp. 64-67.
%H A139004 Perlmonks.org, <a href="http://www.perlmonks.org/?node_id=443037">Chasing Knuth's Conjecture</a>.
%H A139004 Jon E. Schoenfield, <a href="/A139004/a139004.txt">Table of n, a(n), and shortest path for n = 1..1000</a>
%F A139004 a(4) = 0, a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }
%e A139004 Representing the operation x -> floor(sqrt(x)) by "s" and x -> x! by "f", we have:
%e A139004 a(1) = 2 since 1 = ss4 is clearly the shortest way to obtain 1, starting with 4.
%e A139004 a(2) = 1 since 2 = s4 is clearly the shortest way to obtain 2, starting with 4.
%e A139004 a(4) = 0 since no operation is required to get 4.
%e A139004 a(3) = 10 = 3+a(5) since 3 = ssf5 and it cannot be obtained from 4 with fewer operations.
%e A139004 a(5) = 7 since 5 = sssssff4.
%e A139004 a(6) = 11 = 1+a(3) since 6 = f3. a(10) = 9 since 10 = sfsssssff4 is the shortest way to obtain 9, starting with 4.
%o A139004 (PARI) A139004( n, S=Set(4), LIM=10^4 )={ for( i=0,LIM, setsearch( S, n) & return(i); S=setunion( S, setunion( Set( vector( #S, j, sqrtint(eval(S[j])))), Set( vector( #S, j, if( LIM > j=eval(S[j]), j!))))))}
%o A139004 (PARI) { search(x,r,l=0) = local(ll,xx); ll=l; xx=x; while(ll<L, if(xx==r, L=ll; print(L); return); ll++; if(xx*(log(xx)-1)<2^(L-ll)*log(r), search(xx!,r,ll)); xx=sqrtint(xx)) } \ where L - upper bound, x - starting value, r - final value; e.g., to compute a(4), run: L=32; search(4,8) \\ _Max Alekseyev_, Nov 01 2008
%Y A139004 Cf. A139003, A055226.
%K A139004 nonn
%O A139004 1,1
%A A139004 _M. F. Hasler_, Apr 09 2008
%E A139004 a(7)-a(9) from _Max Alekseyev_, Oct 17, Nov 01 2008
%E A139004 More terms from _Jon E. Schoenfield_, Nov 10 2008