From: "A. Bijanki" <bijanki@uiuc.edu>
Subject: 3, Floor[Sqrts] and Factorials
Date: Mon, 8 May 2000 19:00:35 -0500
Newsgroups: sci.math
Summary: [missing]

Ok, someone posted a problem a while ago wondering if every natural number
can be created by using "Integer Sqrts" and Factorials starting with the
number 3.  I took his "Integer Sqrts" to mean Floor[Sqrt[x]].  Someone
suggested calling it "?".  Factorial is of course "!".

Clive Tooth figured out that:

1 = 3?
2 = 3!?
3 = 3
4 = 3!!?!????!?????!???????
5 = 3!!??
6 = 3!
7 = 3!!??!?!??!?????!??????
8 = 3!!??!?!??!?????!??????!??
9 = 3!!??!?!?!????????????!????!??!?????????????!??????
10= 3!!??!?


It sure looks like the statement is true, but who can prove it?  Here's what
I and others have come up with:

IF     n^2 <= x < (n+1)^2, THEN           x? = n  .....  I guess that is
pretty obvious.


Call RF[x,a] = x!!!!!!...!!! <--------'a' factorial signs following x.  RF =
recursive factorial.  I dunno if there is already a mathematical term for
this...


Anyway it looks to me like the easiest way to prove the statement is to
prove that for a natural number N, there exists natural numbers M,K,A such
that:

(1) N^(2^K) <= RF[M,A] < (N+1)^(2^K)         AND       M<N

Then you can use infinite descent to prove the statement, I think, by
assuming N is the least uncomputable number, and then showing that M must
also be uncomputable since M can produce N.  Then the facts that "M<N" and
"1 is computable" prove the statement.

So does this seem correct? Does _anyone_ know how to go about this?  Could
you gimme hints?  This is intriguing me.  I'd like to write some code to
"try" out equation (1), but I use mathematica and the numbers get WAY too
big too fast.  I suppose I could take the LOG of the equation; but I do not
know how to generate LOG[x!] given LOG[x] where LOG[x] is so large that
calculating x would be unfeasible.  Obviously LOG[x!] where x is calculable
is LOG[x]+LOG[x-1]+....

Well any help appreciated!  This is really interesitng.