OFFSET
1,2
COMMENTS
Knuth conjectured that any number can be obtained in that way, starting from 4.
This seems also to be true using 3 as the starting value. Since 3 is the minimal possible choice, this variant could be considered to be more natural.
To ensure the sequence is well-defined, define a(n)=-1 if it is not possible to get n in the given way.
See A139004 for references and links.
LINKS
Jon E. Schoenfield, Table of n, a(n) for n = 1..1000
Jon E. Schoenfield, Table of n, a(n), and shortest path for n = 1..1000
FORMULA
a(3) = 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) = 1 since 1 = s3 is clearly the shortest way to obtain 1 from 3.
a(2) = 2 since 2 = sf3 is clearly the shortest way to obtain 2 from 3.
a(3) = 0 since no operation is required to get 3 which is there at the beginning.
a(5) = 4 since 5 = ssff3 is the shortest way to obtain 5 from 3.
a(6) = 1 since 6 = f3 is certainly the shortest way to get 6 from 3.
a(4) = 20 = 7+9+a(5) since 4 = ssssssfsssssssffssff3 = floor(35!^(1/2^6)), 35 = floor((5!)!^(1/2^7)).
PROG
(PARI) A139003( n, S=Set(3), LIM=10^5 )={ 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!))))))}
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Apr 09 2008
EXTENSIONS
a(9)-a(11) from Max Alekseyev, Nov 03 2008
Corrected formula, added terms from a(12) onward. - Jon E. Schoenfield, Nov 17 2008, Nov 19 2008
Comments and example edited by Jon E. Schoenfield, Sep 15 2013
STATUS
approved