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

1, 2, 0, 20, 4, 1, 14, 17, 31, 6, 26, 41, 35, 20, 31, 31, 19, 28, 27, 38, 21, 33, 21, 21, 26, 3, 51, 38, 28, 26, 20, 35, 36, 36, 13, 23, 27, 62, 45, 50, 45, 40, 9, 15, 31, 8, 32, 52, 36, 13, 68, 69, 57, 33, 54, 36, 46, 34, 49, 63, 56, 68, 14, 63, 23, 33, 36, 47, 43, 16, 38, 66, 38

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

Cf. A139004.

Sequence in context: A261516 A009198 A209123 * A264881 A280622 A211880

Adjacent sequences: A139000 A139001 A139002 * A139004 A139005 A139006

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