 Perl-Sensitive Sunglasses PerlMonks

### Challenge: Chasing Knuth's Conjecture

by kvale (Monsignor)
 on Mar 29, 2005 at 04:56 UTC Need Help??

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*(n-1)*(n-2)*...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
[download]```
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.

-Mark

Replies are listed 'Best First'.
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

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.

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 => ssssssssfsssssssssssfsssssfssssssssssfssssssssssssfsssssssssssss
+fssssfsssssssssfsssssssssssfsssssssfssssssssfssssssssssfssssfsssssssf
+sssssssssssfssssssssfssssssssssfsssssssssssfsssssssfsssssssssfssssssf
+sssssssssfsssssssssfsssssssfssssssfsssfsssssssssfssssssfssssssfssssfs
+sssssssfsfssfssssssfsssssfssfsfssff
[download]```

Hugo

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

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 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]```
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(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 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.

-Mark

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
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.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.
Re: Challenge: Chasing Knuth's Conjecture
by Roy Johnson (Monsignor) on Mar 29, 2005 at 17:29 UTC
Here's a fairly straightforward sieve. It finds solutions by repeatedly applying the basic functions to the already-found solutions, so it finds solutions for some incredibly large numbers, but doesn't get 9 (for example), likely due to the limit I put on factorial (no inputs larger than 150). Output strings are effectively unary RPN. Update: instead of iterating a given number of times, iterates until no new solutions are found.

Caution: Contents may have been coded under pressure.
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.

Cheers - L~R

Note: It is assumed that each operation will result in an implicit floor()
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.
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.
Experimental Mathematics - Re: Challenge: Chasing Knuth's Conjecture
by metadoktor (Hermit) on Apr 03, 2005 at 21:14 UTC
The casual hacker may be interested to know that there is a whole new field called experimental mathematics that makes heavy use of computers to find new equations or to explore mathematical ideas.

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

metadoktor

"The doktor is in."

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://443037]
Approved by blokhead
Front-paged by hsmyers
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (7)
As of 2021-04-20 06:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?