|
| |
|
|
A139004
|
|
Number of operations A000142 (i.e., x!) or A000196 (i.e., floor(sqrt(x))) needed to get n, starting with 4.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
John E. Maxfield, A Note on N!, Mathematics Magazine, Vol. 43, No. 2 (March 1970), pp. 64-67.
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
