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

Author

M. F. Hasler, Apr 09 2008

Keywords

• nonn

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.

In fact 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

Examples

			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)).
		

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

Crossrefs

Cf. A139004.

Programs

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!))))))}

Formula

a(3) = 0; a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }

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