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

%I #30 Feb 20 2018 02:45:13

%S 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,

%T 13,51,41,36,6,30,41,44,33,16,33,31,64,35,50,25,43,12,18,41,18,42,55,

%U 39,23,71,65,45,43,52,39,49,44,51,60,57,59,24,66,26,36,46,51,46,26,48,76

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

%C Knuth conjectured that any number can be obtained in this way, starting from 4.

%C This sequence gives the minimal number of operations needed to do so.

%C To ensure the sequence is well-defined, define a(n)=-1 if it is not possible to get n in the given way.

%H Jon E. Schoenfield, <a href="/A139004/b139004.txt">Table of n, a(n) for n = 1..1000</a>

%H D. E. Knuth, <a href="http://www.jstor.org/stable/2689238">Representing numbers using only one 4</a>, Mathematics Magazine, Vol. 37, No. 5 (Nov. 1964), pp. 308-310.

%H John E. Maxfield, <a href="http://www.jstor.org/stable/2688966">A Note on N!</a>, Mathematics Magazine, Vol. 43, No. 2 (March 1970), pp. 64-67.

%H Perlmonks.org, <a href="http://www.perlmonks.org/?node_id=443037">Chasing Knuth's Conjecture</a>.

%H Jon E. Schoenfield, <a href="/A139004/a139004.txt">Table of n, a(n), and shortest path for n = 1..1000</a>

%F a(4) = 0, a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }

%e Representing the operation x -> floor(sqrt(x)) by "s" and x -> x! by "f", we have:

%e a(1) = 2 since 1 = ss4 is clearly the shortest way to obtain 1, starting with 4.

%e a(2) = 1 since 2 = s4 is clearly the shortest way to obtain 2, starting with 4.

%e a(4) = 0 since no operation is required to get 4.

%e a(3) = 10 = 3+a(5) since 3 = ssf5 and it cannot be obtained from 4 with fewer operations.

%e a(5) = 7 since 5 = sssssff4.

%e 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.

%o (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!))))))}

%o (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

%Y Cf. A139003.

%K nonn

%O 1,1

%A _M. F. Hasler_, Apr 09 2008

%E a(7)-a(9) from _Max Alekseyev_, Oct 17, Nov 01 2008

%E More terms from _Jon E. Schoenfield_, Nov 10 2008