The noted computer scientist Donald Knuth has conjectured that every
positive integer can be obtained by beginning with a single 3 and
applying some combination of the factorial, square root, and floor
functions.
Recall that the factorial function is n! = n*(n1)*(n2)*...3*2*1, and
for this problem, we insist that n be an integer. floor(x)
gives the greatest integer less than or equal to x. For example, we
can write
floor(sqrt((3!)!))
= floor(sqrt(6!))
= floor(sqrt(720))
= floor(26.83...)
= 26
to obtain a Knuth expression for 26.
One could spend a pleasant afternoon manually creating Knuth expressions for small integers
with a hand calculator. But it is much more fun to write a
perl program to do this for you. The challenge is to write an elegant,
fast, or golfish program that finds Knuth expressions for the integers 1 to 10 inclusive.
I'll post my solution in a day or so.
Re: Challenge: Chasing Knuth's Conjecture
by hv (Parson) on Mar 29, 2005 at 15:07 UTC

The code below finds 1..10 in 2 seconds on this machine, having calculated nothing greater than 201!; 1..37 takes 8s, and calculates 366!. Beyond that we start to find some more difficult, but at 37 mins and 24MB it has so far found all but 8 numbers (59, 64, 72, 86, 87, 92, 97, 99) out of 1..99.
Update: still missing (92, 97, 99) after 274 mins (process size 67MB).
The basic ideas are: a) keep a sorted list (@try) of the numbers we've reached but not yet calculated a factorial for; b) at each iteration, take the smallest untried number and find it's factorial, and repeatedly take the square root of the result until we get to a number we've seen before; c) use a binary chop to insert new pending numbers.
In the output, eg "5 => ssff" means that 5 = int(sqrt(int(sqrt(fact(fact(3)))))).
Hugo
 [reply] [d/l] [select] 

Here is a variation of that one that deals with log factorials, so it needs only regular arithmetic. It uses the gammln recently posted here by ewijaya.
It is extremely fast, solving 1..99 in about 2 seconds. (There may be roundoff error issues. I have not checked all the answers.)
Update: I added an independent confirmation with Math::Pari for every number I insert in the queue. They all come out correct. With checking added, the solution to 1..99 takes a minute and 23 seconds. The hardest to get is 92, which passes through 12985 factorial.
 [reply] [d/l] 

87 => ssssssssfsssssssssssfsssssfssssssssssfssssssssssssfsssssssssssss
+fssssfsssssssssfsssssssssssfsssssssfssssssssfssssssssssfssssfsssssssf
+sssssssssssfssssssssfssssssssssfsssssssssssfsssssssfsssssssssfssssssf
+sssssssssfsssssssssfsssssssfssssssfsssfsssssssssfssssssfssssssfssssfs
+sssssssfsfssfssssssfsssssfssfsfssff
Hugo  [reply] [d/l] 

 [reply] [d/l] 

I computed an answer for 38 with my modified version of hv's program, using logs. The result is:
"sssssssssfsssssssssssfssssssfssssssfssssssfssssssssssfssssssssfssssss
+ssfssssssfssssssfssssfssssssssfsfssfssssssfsssssfssfsfssff"
I confirmed this answer with Math::Pari, and it is correct. The highest factorial required is 1861.  [reply] [d/l] 

Re: Challenge: Chasing Knuth's Conjecture
by Anonymous Monk on Mar 29, 2005 at 11:33 UTC

One thing to realize is that it makes sense to only apply "floor" after applying "sqrt", and that always applying "floor" after doing "sqrt" doesn't eliminate any solutions. This means there are only two operations: taking the faculty of a number, or to take the square root and flooring the number. This also means all intermediate values are integers.
The following algorithm is a breadthfirst search, keeping track of which numbers were already calculated. To keep the intermediate values managable, it won't apply faculty on numbers greater than 200 (this is a tight limit, for at least one of the number 1 .. 10, you need the faculty of 200). After finding solutions for the numbers 1 to 10, it prints them.
#!/usr/bin/perl
use strict;
use warnings;
use Math::BigInt;
use constant FAC_MAX => 200;
sub pretty_print;
my $three = {meth => "init",
value => Math::BigInt>new(3),
old_value => Math::BigInt>new(3)};
my @list = ($three);
my %done = map {$_>{value} => $_} @list;
while (@list) {
my $node = shift @list;
for my $meth (qw /bsqrt bfac/) {
next if $meth eq 'bfac' && $node>{value} > FAC_MAX;
my $new_value = $node>{value}>copy>$meth;
unless ($done{$new_value}) {
my $new = {meth => $meth,
value => $new_value,
old_value => $node>{value}};
push @list, $new;
$done{$new_value} = $new;
}
}
my $c = 0;
$done{$_} && $c++ for 1 .. 10;
if ($c >= 10) {last}
}
for my $n (1 .. 10) {
printf "%2d = ", $n;
pretty_print $done{$n};
print "\n";
}
sub pretty_print {
my $n = shift;
my $m = $n>{meth};
if ($m eq "bsqrt") {
print "sqrt(";
pretty_print($done{$n>{old_value}});
print ")";
}
elsif ($m eq "bfac") {
print "(";
pretty_print($done{$n>{old_value}});
print ")!";
}
elsif ($m eq "init") {
print $n>{value}
}
else {die}
}
__END__
1 = sqrt(3)
2 = sqrt((3)!)
3 = 3
4 = sqrt(sqrt(sqrt(sqrt(sqrt(sqrt((sqrt(sqrt(sqrt(sqrt(sqr
+t(sqrt(sqrt(((sqrt(sqrt(((3)!)!)))!)!))))))))!)))))
+)
5 = sqrt(sqrt(((3)!)!))
6 = (3)!
7 = sqrt(sqrt(sqrt(sqrt(sqrt(sqrt((sqrt(sqrt(sqrt(sqrt((sq
+rt(((3)!)!))!)))))!))))))
8 = sqrt(sqrt((sqrt(sqrt(sqrt(sqrt(sqrt(sqrt((sqrt(sqrt(sq
+rt(sqrt((sqrt(((3)!)!))!)))))!)))))))!))
9 = sqrt(sqrt(sqrt(sqrt(sqrt((sqrt(sqrt(sqrt(sqrt(sqrt(sqr
+t(sqrt(sqrt((sqrt((sqrt(sqrt((sqrt(sqrt(sqrt(sqrt(sqrt(sqr
+t((sqrt(sqrt(sqrt(sqrt((sqrt(((3)!)!))!)))))!)))))))!
+)))!))!)))))))))!)))))
10 = sqrt((sqrt(sqrt(((3)!)!)))!)
 [reply] [d/l] 
Re: Challenge: Chasing Knuth's Conjecture
by kvale (Monsignor) on Mar 29, 2005 at 21:42 UTC

To me, solving this problem is all about finding the right language.
As expressed in the OP, Knuth expressions like floor(sqrt((3!)!)) are
clunky. The eye gets lost in ! and () and it hard to see structure.
But inspiration hits: every Knuth expression is just a highly nested
function of 3, and functions are evaluated from the inside out. So we
could use a reverse Polish notation to simplify things. Set f =
factorial, s = sqrt and i = floor(int). Then 26 = 3ffsi and in
general, Knuth expressions can be represented by strings of the form
3[isf]*. Much simpler!
This representation immediately suggests a solution to the problem:
generate all strings [isf]* up to length n and evaluate to each string
to see if we have a small integer. Simple, but inefficient. The
problem is that the number of strings generated grows as 3**n, and
even for small n this search can take long, long time.
This situation can be helped by thinking about the nature of the
functions used. Obviously, ii == i, so any sequence i+ can be reduced
to a single i. As japhy points out, any sequence of square roots and
floors [si]+i can drop the floors to become s+i without affecting the
result. And so we can reduce our language of Knuth expressions to the
form 3(sif)+. The number of strings in this language grow as x**n
with x somewhat less than 2. This is much better than 3**n and so I
wrote a program that was able solve the problem in about 2 hours on my
poky PIII notebook:
This code evaluates strings using the Math::BigInt GMP
library in order to handle large factorials. It also uses a
memoization technique to reduce the search space. The idea is that
starting with 3 and applying all possible strings up to length n yields
several small integers as Knuth expressions, e.g., 5 = 3ffssi. Then
one can search starting with the small integers, e.g., 5 to yield new
small integers, and so on.
This memoization trick, however, leads to another big insight: each Knuth
sequence that we have the ability to compute can be described by a
sequence of small integers found as we evaluate the string. Between
each pair of numbers is an ascent to larger numbers created by f*,
followed a descent into smaller numbers created by s*, followed by an i.
This yields a further simplification of our language: to map from
small integer to small integer, search strings of the form
f*s*i. There are just n length n strings of the form f*s*i, versus the 2**n
before, so we get a massive speedup.
Here is the same program as before with our newly optimized language:
This runs in 1.4 seconds  a speedup of 5000!
Update: Corrected a spelling mistake, thanks to gam3.
 [reply] [d/l] [select] 
Re: Challenge: Chasing Knuth's Conjecture
by japhy (Canon) on Mar 29, 2005 at 06:44 UTC

It is interesting to note that, for all positive integers X, FLOOR(SQRT(SQRT(X)) = FLOOR(SQRT(FLOOR(SQRT(X)))). Correct me if I'm mistaken, please. You only need to apply floor() at the end of your calculations, and on the argument to factorial().
_____________________________________________________
Jeff japhy Pinyan,
P.L., P.M., P.O.D, X.S.:
Perl,
regex,
and perl
hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
 [reply] 
Re: Challenge: Chasing Knuth's Conjecture
by tall_man (Parson) on Mar 29, 2005 at 21:33 UTC

On this page there is a reference to Knuth's conjecture but it says he starts with 4:
More recently, we have Knuth's Conjecture:
"Representing Numbers Using Only One 4", Donald Knuth,
(Mathematics Magazine, Vol. 37, Nov/Dec 1964, pp.308310).
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.
For example: Knuth shows how to make the number 64 using only one 4:
_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt
_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt
_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt
_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt
_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt
_ sqrt _ sqrt _ sqrt sqrt sqrt sqrt sqrt
(4!)! _ ! _ ! _ ! _ ! _ ! _ ! _ ! _
As to notation in the above example, he means sqrt n! stands for
sqrt (n!), not (sqrt n)!
Knuth further points out that _ sqrt _ X _ _ = _ sqrt X _
so that the floor function's brackets are only needed around the entire
result and before factorials are taken.
He CONJECTURES that all integers may be represented that way:
"It seems plausible that all positive integers possess such a
representation, but this fact (if true) seems to be tied up with very deep
propertis of the integers."
Your Humble Webmaster believes that Knuth is right, for 9 as well as 4,
and will prove that in a forthcoming paper.
Knuth comments: "The referee has suggested a stronger conjecture, that a
representation may be found in which all factorial operations precede all
square root operations; and, moreover, if the greatest integer function
(our floor function) is not used, an arbitrary positive real number can
probably be approximated as closely as desired in this manner."
 [reply] [d/l] 

On this page there is a reference to Knuth's conjecture but it says he starts with 4
But since
3 == _sqrt(sqrt(_sqrt(sqrt(sqrt(sqrt(sqrt(4!!)))))_!))_
and
4 == _sqrt(sqrt(sqrt(sqrt(sqrt(sqrt((_sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(((sqrt(sqrt(3!!))_)!)!)))))))_)!))))))_
both "conjectures" are equivalent.  [reply] 
Re: Challenge: Chasing Knuth's Conjecture
by Roy Johnson (Monsignor) on Mar 29, 2005 at 17:29 UTC

 [reply] [d/l] 
Re: Challenge: Chasing Knuth's Conjecture
by Limbic~Region (Chancellor) on Mar 30, 2005 at 01:01 UTC

Mark,
Your challenge was to write an elegant, fast, or golfish program. As I look at the problem, I can see an elegant solution, but unfortunately all the implementations I have tried so far are slow in comparison.
You can treat the problem as a tree where each node has two children  the sqrt and the factorial. The stack starts out with the root node (3). After each node has its two children, it is removed from the stack and placed in the tree. A branch is terminated if the child node represents its parent (sqrt(1) = 1, fact(2) = 2), the node is already present in the tree, or the number is beyond a user imposed limit.
Finding the path to a particular node is done in reverse (since the tree is represented by a hash). You select the node and traverse backwards to the root. If you would like to see my implementation, let me know and I will post what I came up with tomorrow when I get to work.
Note: It is assumed that each operation will result in an implicit floor()
 [reply] [d/l] 

Limbic,
I've also got what I think is a perlygolfish approach. It's at least somewhat novel, even if implementation turns out to be impractical. I haven't implemented it at all, but I'll describe it here in the hope that it's interesting.
Every number is either a factorial or the integer sqrt of some other number (well, actually, every number is the latter, but some are also the former). So when you look at a number, you check to see if it's a factorial. If so, you replace it with NF, where N is what you apply the factorial function to to get your number (that is, the inversefactorial of your number). Otherwise, you replace it with X..YS, where X and Y are the minimum and maximum values that you can plug into int(sqrt()) to get your number. S and F are literal characters to indicate the operation in your solution string.
If you have already computed the solution for N, or for any number between X and Y, you can substitute that solution string for the number/range in your solution string and continue solving. Otherwise, you have to solve for it. If a factorial falls in your range, you replace your range with the factorial indicator as before. Otherwise, you expand your range using the inverse int(sqrt()) function.
You proceed until the number (or range) at the beginning of your solution string includes your desired base case.
Caution: Contents may have been coded under pressure.
 [reply] 
Re: Challenge: Chasing Knuth's Conjecture
by Anonymous Monk on Mar 29, 2005 at 09:31 UTC

Not wanting to use Math::Bigint, I found even 64bit integers really limiting. 21! needs more than 64bits. I was only able to get the following numbers: 1, 2, 5, 6, 10, 26, 43, 120, 720, 1904, 3628800.  [reply] 
Experimental Mathematics  Re: Challenge: Chasing Knuth's Conjecture
by metadoktor (Hermit) on Apr 03, 2005 at 21:14 UTC

 [reply] 

