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
Keywords
Examples
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.
Links
- Jon E. Schoenfield, Table of n, a(n) for n = 1..1000
- Eli Bendersky, Making any integer with four 2s, Blog Post, Feb 22 2025
- Eli Bendersky, Making any integer with four 2s, Blog Post, Feb 22 2025 [Local copy, with the author's permission]
- 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
Programs
-
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
Formula
a(4) = 0, a(n) = min { a(k)+1 ; n^2 <= k < (n+1)^2 or k! = n }
Extensions
a(7)-a(9) from Max Alekseyev, Oct 17, Nov 01 2008
More terms from Jon E. Schoenfield, Nov 10 2008
Comments