 Problems? Is your data what you think it is? PerlMonks

### comment on

 Need Help??
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:

```use warnings;
use strict;

use Algorithm::Loops qw( NestedLoops );
use Math::BigInt lib => 'GMP';

my \$start_base = shift;
my \$depth = shift;

my @func = qw/i s f/;  # alphabet used
# my @func = qw/s if/;
my @seq;   # Stores shortest sequences associated with each positive i
+nteger [1,200]
\$seq = "";

my @todo;  # Stores base elements yet to be searched.
push @todo, \$start_base; # Start things off

while (@todo) {
my \$base = shift @todo;
print "expanding \$base\n";
expand( \$base, \$depth);
}

for my \$val (1..200) {
print "\$val: \$seq[\$val]\n" if defined \$seq[\$val];
}

### Subroutines

# Create all possible strings up to \$depth long and evaluate each stri
+ng
sub expand
{
my (\$base, \$depth) = @_;

NestedLoops(
[ ( [@func] ) x \$depth ],
{ OnlyWhen => 1 },
sub{ evaluate_bigint( \$base, @_); },
);
}

# Evaluate the result of computing the expression given by a string
# Adds useful strings to @seq and pushes newly found values onto @todo
# queue.
sub evaluate_bigint
{
my \$base = shift;
my \$val = Math::BigInt->new( \$base);  # create a BigInt object

my \$seq_str = join "", @_;
my @sequence = split //, \$seq_str;
my \$prefix = defined \$seq[\$base] ? \$seq[\$base] : "";

foreach my \$f (@sequence) {
if (\$f eq 'i') {    # int
# int is a no-op for a BigInt
}
elsif (\$f eq 's') { # sqrt
\$val->bsqrt();
}
else {              # factorial
return if \$val->length() > 5;  # limit max size
\$val->bfac();
}
}
return if \$val->length() > 3;  # only want small integers
my \$num = \$val->numify();      # convert to ordinary scalar

\$seq_str = \$prefix . \$seq_str;
\$seq_str =~ s/^i+//;
\$seq_str =~ s/i+/i/g;
\$seq_str =~ s/fif/ff/g;

if (! defined(\$seq[\$num])) { # new entry
push @todo, \$num;
\$seq[\$num] = \$seq_str;
print "\$num: \$seq_str\n";
}
elsif (length \$seq_str < length \$seq[\$num]) {
\$seq[\$num] = \$seq_str;
}
}
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:

```use warnings;
use strict;

use Algorithm::Loops qw( NestedLoops );
use Math::BigInt lib => 'GMP';

my \$start_base = shift;
my \$depth = shift;

my @seq;   # Stores shortest sequences associated with each positive i
+nteger [1,200]
\$seq = "";

my @todo;  # Stores base elements yet to be searched.
push @todo, \$start_base; # Start things off

while (@todo) {
my \$base = shift @todo;
print "expanding \$base\n";
expand( \$base, \$depth);
}

for my \$val (1..200) {
print "\$val: \$seq[\$val]\n" if defined \$seq[\$val];
}

### Subroutines

# Create all possible strings up to \$depth long and evaluate each stri
+ng
sub expand
{
my (\$base, \$depth) = @_;

for my \$len (1..\$depth) {
my \$max_f = \$len < 3 ? \$len : 3;
for my \$f (0..\$max_f) {
my \$str = 'f'x\$f . 's'x(\$len-\$f);
evaluate_bigint( \$base, \$str);
}
}
}

# Evaluate the result of computing the expression given by a string
# Adds useful strings to @seq and pushes newly found values onto @todo
# queue.
sub evaluate_bigint
{
my \$base = shift;
my \$val = Math::BigInt->new( \$base);  # create a BigInt object

my \$seq_str = shift;
my \$prefix = defined \$seq[\$base] ? \$seq[\$base] : "";
#    my \$str = \$prefix . \$seq_str;
#    print "base: \$base,  seq_str: \$seq_str,  str: \$str\n";

my @sequence = split //, \$seq_str;

foreach my \$f (@sequence) {
if (\$f eq 'i') {    # int
# int is a no-op for a BigInt
}
elsif (\$f eq 's') { # sqrt
\$val->bsqrt();
}
else {              # factorial
return if \$val->length() > 3;  # limit max size
#  print "length before fac:", \$val->length(), "\n";
\$val->bfac();
}
}
return if \$val->length() > 3;  # only want small integers
my \$num = \$val->numify();       # convert to ordinary scalar

\$seq_str = \$prefix . \$seq_str;

if (! defined(\$seq[\$num])) { # new entry
push @todo, \$num;
\$seq[\$num] = \$seq_str;
print "\$num: \$seq_str\n";
}
elsif (length \$seq_str < length \$seq[\$num]) {
\$seq[\$num] = \$seq_str;
}
}
This runs in 1.4 seconds -- a speedup of 5000!

Update: Corrected a spelling mistake, thanks to gam3.

-Mark

In reply to Re: Challenge: Chasing Knuth's Conjecture by kvale
in thread Challenge: Chasing Knuth's Conjecture by kvale

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (6)
As of 2019-11-18 21:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Strict and warnings: which comes first?

Results (92 votes). Check out past polls.

Notices?