OFFSET
1,1
COMMENTS
Knuth conjectured that any number can be obtained in this way, starting from 4.
This sequence gives the minimal number of operations needed to do so.
To ensure the sequence is well-defined, define a(n)=-1 if it is not possible to get n in the given way.
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
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
LINKS
Jon E. Schoenfield, Table of n, a(n) for n = 1..1000
Eli Bendersky, Making any integer with four 2s, Blog Post, Feb 22 2025
Eli Bendersky, Making any integer with four 2s, Blog Post, Feb 22 2025 [Local copy, with the author's permission]
D. E. Knuth, Representing numbers using only one 4, Mathematics Magazine, Vol. 37, No. 5 (Nov. 1964), pp. 308-310.
John E. Maxfield, A Note on N!, Mathematics Magazine, Vol. 43, No. 2 (March 1970), pp. 64-67.
Perlmonks.org, Chasing Knuth's Conjecture.
Jon E. Schoenfield, Table of n, a(n), and shortest path for n = 1..1000
FORMULA
a(4) = 0, a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }
EXAMPLE
Representing the operation x -> floor(sqrt(x)) by "s" and x -> x! by "f", we have:
a(1) = 2 since 1 = ss4 is clearly the shortest way to obtain 1, starting with 4.
a(2) = 1 since 2 = s4 is clearly the shortest way to obtain 2, starting with 4.
a(4) = 0 since no operation is required to get 4.
a(3) = 10 = 3+a(5) since 3 = ssf5 and it cannot be obtained from 4 with fewer operations.
a(5) = 7 since 5 = sssssff4.
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.
PROG
(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!))))))}
(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
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
M. F. Hasler, Apr 09 2008
EXTENSIONS
a(7)-a(9) from Max Alekseyev, Oct 17, Nov 01 2008
More terms from Jon E. Schoenfield, Nov 10 2008
STATUS
approved