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

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, 13, 51, 41, 36, 6, 30, 41, 44, 33, 16, 33, 31, 64, 35, 50, 25, 43, 12, 18, 41, 18, 42, 55, 39, 23, 71, 65, 45, 43, 52, 39, 49, 44, 51, 60, 57, 59, 24, 66, 26, 36, 46, 51, 46, 26, 48, 76

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.

Links

Jon E. Schoenfield, Table of n, a(n) for n = 1..1000

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

Cf. A139003.

Sequence in context: A013071 A155756 A204432 * A074951 A055633 A105606

Adjacent sequences: A139001 A139002 A139003 * A139005 A139006 A139007

Keyword

nonn

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