I've worked on this puzzle (3, factorial, isqrt) for about 50 years. Sketch of a possible proof plan, with details left as an exercise for the student :-) ... a) It's enough to show that some sequence of integers with bounded ratio, such as one integer in each decade, is reachable. b) Apply log2(log2()) to the reachable integers, and reduce mod 1. There's at least one accumulation point. Suppose that 0 is an accumulation point-- i.e., that we can reach 2^2^N for arbitrarily large N, and therefore for all N. b2) Then we can reach any integer. I thought I had proved this lemma (once upon a time), but can't reconstruct my steps. Probably I got it wrong. The first step is to notice that N sqrts, applied to (2^(2^N))!, gives roughly (2^(2^N))/e, and some more sqrts will give 2^2^J - 2^K for all J and small enough K (the range of K depends on J). Repeating this step with 2^2^J - 2^K (factorial, then some sqrts) will give more numbers near 2^2^H. The gap to be filled here is to show a construction for numbers in each octave, perhaps 2^any. c) An accumulation point at t (mod 1) gives an accumulation point at t + 2^t (mod 1). When t is small, this is ~ (1+.693)t. This just uses the construction in (b2) with one factorial and many sqrts. c2) An empty range (or a range with only a finite number of reached values) (u,v) implies a smaller empty range (i(u),i(v)) where i() is the inverse function of t+ 2^t -1. For small u, i(u) ~ u/1.693. c3) We can go further, and say that an accumulation point at t implies accum points at t + 2^(t+K) (mod 1). For small t, ~ (1+1.386)t etc. [If 2^t is a Normal number, we're done, since 2^(t+K) (mod 1) will cover the unit interval with accumulation points.] d) (Huge gap here.) Try to show that one accumulation point implies coverage of the unit interval, or that any empty range can be extended at either end to cover the whole interval. Maybe there's some topological argument? Perhaps show that an empty interval can be incremented by K and divided by some power of 1.693 to extend the emptiness? But modeling i(x) as x/1.693 is wrong for large x. d2) If we have an accumulation interval (epsilon,1.7epsilon), then (c) multiplying by 1.693 will extend the interval, and eventually wrap around to cover t=0. d3) Covering all of [0,1] with accumulation points makes (b2) superfluous. Rich PS: Four 4s can be solved with three 4s, if we allow subtraction, division, real sqrt, and floor: 4/(4^-(2^K) - 4^-(2^(K+1))) gives a sequence of roughly doubling values, and (a) finishes the work. I saw this solution many years ago, and can't recall where it was. --------- Quoting Joshua Zucker <joshua.zucker@gmail.com>:

I thought this was a theorem of John Conway's but I can't find a reference to convince me that my memory is correct.

--Joshua Zucker

On Mon, Jul 19, 2010 at 1:58 PM, Erich Friedman <efriedma@stetson.edu> wrote:

...

this is actually a variant of an old puzzle, with 4 replaced by 3. they are equivalent problems since 4 can be done from 3 and 3 from 4.

every number up to 196 has such a representation. i'm guessing all numbers do.

erich

On Jul 19, 2010, at 4:12 PM, Marc LeBrun wrote:

...

Can every integer be represented by a composition of integer square root ($) and factorial (!) applied to 3?

Some example representations: 3 = 3 6 = 3! 1 = 3$ 2 = 3!$ 720 = 3!! 26 = 3!!$ 5 = 3!!$$ 120 = 3!!$$! 10 = 3!!$$! ...

If not, what is the smallest counterexample?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

From http://www.magicdragon.com/math.html

"Knuth shows how (using a computer program he wrote) all integers from 1 through 207 may be represented with only one 4, varying numbers of square roots, varying numbers of factorials, and the floor function." So what are the current smallest numbers of which we don't know their Knuth's presentations? Warut On Sat, Sep 18, 2010 at 2:03 PM, Warut Roonguthai <warut822@gmail.com> wrote:

Here is the representation of 197 that I just found:

844 = [(44!!)^(1/2^185)] 197 = [(844!!)^(1/2^7003)].

I used simple Stirling's formula for large factorial approximations. An independent verification is needed here.

Warut

On Tue, Jul 20, 2010 at 3:58 AM, Erich Friedman <efriedma@stetson.edu> wrote:

...

this is actually a variant of an old puzzle, with 4 replaced by 3. they are equivalent problems since 4 can be done from 3 and 3 from 4.

every number up to 196 has such a representation. i'm guessing all numbers do.

erich

On Jul 19, 2010, at 4:12 PM, Marc LeBrun wrote:

...

Can every integer be represented by a composition of integer square root ($) and factorial (!) applied to 3?

Some example representations:  3  =  3  6  =  3!  1  =  3$  2  =  3!$  720  =  3!!  26  =  3!!$  5  =  3!!$$  120  =  3!!$$!  10  =  3!!$$! ...

If not, what is the smallest counterexample?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun