|
| |
|
|
A139003
|
|
Number of operations A000142 (x!) or A000196 [sqrt(x)] needed to get n, starting with 3.
|
|
2
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
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)=0 if it is not possible to get n in the given way.
a(12) >= 35 [From Max Alekseyev (maxale(AT)gmail.com), Nov 03 2008]
See A139004 for references and links
|
|
|
LINKS
| Jon Schoenfield, Table of n, a(n) for n = 1..1000
|
|
|
FORMULA
| a(3) = 0; a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }
|
|
|
EXAMPLE
| Representing the operation x -> [sqrt(x)] by "s" and x -> x! by "f",
we have
a(1) = 1 since 1 = s1 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 4 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 = 35!^(1/2^6), 35=(5!)!^(1/2^7).
a(9) <= 31, since 9 = ssssssssssfsssssssssssfsfsfssff3.
|
|
|
PROG
| (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!))))))}
|
|
|
CROSSREFS
| Cf. A139004.
Sequence in context: A178987 A152154 A009198 * A182661 A189772 A156438
Adjacent sequences: A139000 A139001 A139002 * A139004 A139005 A139006
|
|
|
KEYWORD
| hard,nonn
|
|
|
AUTHOR
| M. F. Hasler (www.univ-ag.fr/~mhasler), Apr 09 2008
|
|
|
EXTENSIONS
| a(9)..a(11) from Max Alekseyev (maxale(AT)gmail.com), Nov 03 2008
Corrected formula, added terms from a(12) onward. - Jon E. Schoenfield (jonscho(AT)hiwaay.net), Nov 17 2008, Nov 19 2008
|
| |
|
|
