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

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.

Read more... (3 kB)

Interesting, I would have expected rounding errors large enough to skew the results, but your results agree with mine as far as the final value I've discerned so far in 1..99:

87 => 
ssssssssfsssssssssssfsssssfssssssssssfss
ssssssssssfsssssssssssssfssssfsssssssssf
sssssssssssfsssssssfssssssssfssssssssssf
ssssfsssssssfsssssssssssfssssssssfssssss
ssssfsssssssssssfsssssssfsssssssssfsssss
sfsssssssssfsssssssssfsssssssfssssssfsss
fsssssssssfssssssfssssssfssssfssssssssfs
fssfssssssfsssssfssfsfssff
[download]

Hugo

Update 2023-11-27: broke long line

I took your ideas for avoiding re-testing things and revamped my sieve. This generates all the answers that don't require factorial on anything higher than whatever you set (350 gets me all solutions for 1..30). It runs in about 5 seconds on my 1 GHz PC with that setting.
Read more... (1484 Bytes)
Update: pregenerated factorials to save time; also put in a limit on how high to print, so the huge numbers don't show up. Even taking factorials as high as 999 (takes 30-40 seconds), there's no solution for 38.

---

Caution: Contents may have been coded under pressure.

I computed an answer for 38 with my modified version of hv's program, using logs. The result is:

"sssssssssfsssssssssssfssssssfssssssfssssssfssssssssssfssssssssfssssss
+ssfssssssfssssssfssssfssssssssfsfssfssssssfsssssfssfsfssff"
[download]

I confirmed this answer with Math::Pari, and it is correct. The highest factorial required is 1861.

The following algorithm is a breadth-first 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)!)!)|)|)!)|
[download]

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(s|if)+. 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 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:

Update: Corrected a spelling mistake, thanks to gam3.

More recently, we have Knuth's Conjecture:

"Representing Numbers Using Only One 4", Donald Knuth, (Mathematics Magazine, Vol. 37, Nov/Dec 1964, pp.308-310). 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!)! _| ! _| ! _| ! _| ! _| ! _| ! _| ! _|
[download]

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."

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.

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.

Limbic,
I've also got what I think is a perly-golfish 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 inverse-factorial 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.

http://crd.lbl.gov/~dhbailey/expmath/