cp's OEIS Frontend

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

%I A139003 #30 Feb 26 2025 08:45:11
%S A139003 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,
%T A139003 3,51,38,28,26,20,35,36,36,13,23,27,62,45,50,45,40,9,15,31,8,32,52,36,
%U A139003 13,68,69,57,33,54,36,46,34,49,63,56,68,14,63,23,33,36,47,43,16,38,66,38
%N A139003 Number of operations A000142 (i.e., x!) or A000196 (i.e., floor(sqrt(x))) needed to get n, starting with 3.
%C A139003 Knuth conjectured that any number can be obtained in that way, starting from 4.
%C A139003 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.
%C A139003 To ensure the sequence is well-defined, define a(n)=-1 if it is not possible to get n in the given way.
%C A139003 See A139004 for references and links.
%C A139003 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
%H A139003 Jon E. Schoenfield, <a href="/A139003/b139003.txt">Table of n, a(n) for n = 1..1000</a>
%H A139003 Jon E. Schoenfield, <a href="/A139003/a139003.txt">Table of n, a(n), and shortest path for n = 1..1000</a>
%F A139003 a(3) = 0; a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }
%e A139003 Representing the operation x -> floor(sqrt(x)) by "s" and x -> x! by "f",
%e A139003 we have:
%e A139003 a(1) = 1 since 1 = s3 is clearly the shortest way to obtain 1 from 3.
%e A139003 a(2) = 2 since 2 = sf3 is clearly the shortest way to obtain 2 from 3.
%e A139003 a(3) = 0 since no operation is required to get 3 which is there at the beginning.
%e A139003 a(5) = 4 since 5 = ssff3 is the shortest way to obtain 5 from 3.
%e A139003 a(6) = 1 since 6 = f3 is certainly the shortest way to get 6 from 3.
%e A139003 a(4) = 20 = 7+9+a(5) since 4 = ssssssfsssssssffssff3 = floor(35!^(1/2^6)), 35 = floor((5!)!^(1/2^7)).
%o A139003 (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!))))))}
%Y A139003 Cf. A139004.
%K A139003 nonn
%O A139003 1,2
%A A139003 _M. F. Hasler_, Apr 09 2008
%E A139003 a(9)-a(11) from _Max Alekseyev_, Nov 03 2008
%E A139003 Corrected formula, added terms from a(12) onward. - _Jon E. Schoenfield_, Nov 17 2008, Nov 19 2008
%E A139003 Comments and example edited by _Jon E. Schoenfield_, Sep 15 2013