Joined: 3/25/2004
Posts: 459
I decided to make this a thread of its own, as I *imagine* the discussion will be long enough to derail the other thread. The object of the game is to find the smallest positive whole number that cannot be represented with nine 9's using only the operations of addition, subtraction, multiplication, division, and parantheses. Sticking the numbers together, like 99 or 999,999 is not allowed. Also, the program should be as efficient as possible. Between two 9's there are four operator combinations. 9+9, 9-9, 9*9, 9/9. This is 4^1. Between three 9's would be 4*4 which is 4^2. Between nine 9's there would be 4^8. The total number of results is 65,536, and not all of them are whole numbers. Here's my idea: 1) generate all possible numbers from any legal combination of operations, 2) sort the elements, 3) check that the value of any element n is 1 greater than the previous element. If the value is greater than 1, then we have found the smallest positive whole number that cannot be represented with nine 9's. If anyone has found any mistakes I made, please correct me. If anyone can think of a more efficient (in terms of how computers work) way to do this, please tell me. If anyone is really good at math and can find a way to detect repeats based on some mathematical principle that I'm unaware of, rendering doing many calculations unnecessary, please please tell me.
Joined: 4/16/2005
Posts: 251
138. And I'm really ashamed to admit that the program I used to come up with that number is only a fraction of your initial post:
#!perl
$max = 1000000000;
@bc = (
  sub { return $_[0] + $_[1]; },
  sub { return $_[0] - $_[1]; },
  sub { return $_[0] * $_[1]; },
  sub { return (!$_[1]||$_[0]%$_[1])?-1:$_[0]/$_[1]; },
);

@bp = (
  sub { return "(".$_[0]." + ".$_[1].")"; },
  sub { return "(".$_[0]." - ".$_[1].")"; },
  sub { return "(".$_[0]." * ".$_[1].")"; },
  sub { return "(".$_[0]." / ".$_[1].")"; },
);

sub combine {
  ($in1, $in2, $out) = @_;
  foreach $v1 (sort { $a <=> $b } keys %$in1) {
    foreach $v2 (sort { $a <=> $b } keys %$in2) {
      foreach $o (0..$#bc) {
        $n = &{$bc[$o]}($v1, $v2);
        if ($n > -1 && $n < $max && $out->{$n} eq '') {
          $out->{$n} = &{$bp[$o]}($in1->{$v1}, $in2->{$v2});
        }
      }
    }
  }
}

sub iteration {
  &combine($v->[$_[0]-$_], $v->[$_], $v->[$_[0]]) for (1..$_[0]-1);
}

$v->[$_] = {} for (0..9);
$v->[1]{9} = "9";
&iteration($_)for(2..9);
foreach (0..200) { print "$_ => $v->[9]{$_}\n"; }
In case you're wondering about comments, the whole thing is only a variation of the script I used for the four 4's challenge, so I removed them for this post, if you want there's also the commented version. (Also: did I mention I love perl?)
Player (201)
Joined: 7/6/2004
Posts: 511
138 = ((((9 - (9 / ((9 + 9) + 9))) * (9 + 9)) - 9) - 9) The smallest positive integer there is no 9 9s for is 195 according to my program. Gorash, your program is impressively short, but I think your error is that you do not allow for fractions, 138 was not found because it needs to do something like 18 * (9 - 1/3) - 18. I made this same mistake too, but in my case I forgot about them completely so I was basically allowing the floor to be done all the time, but then I fixed it to store everything as floats and then at the end see if the final result is an integer. Kind of a messy way to do it, a better way would be to keep track of things as a fraction, but that would be more work =P.
g,o,p,i=1e4,a[10001];main(x){for(;p?g=g/x*p+a[p]*i+2*!o: 53^(printf("%.4d",o+g/i),p=i,o=g%i);a[p--]=g%x)x=p*2-1;}
Joined: 4/16/2005
Posts: 251
You're right, I don't allow fractions... Hmm, I'll see how to hack them into it. EDIT: Yep, you're right. I fixed it:
#!perl
$max = 1000000000;
@bc = (
  sub { return $_[0] + $_[1]; },
  sub { return $_[0] - $_[1]; },
  sub { return $_[0] * $_[1]; },
  sub { return (!$_[1])?-1:$_[0]/$_[1]; },    #  changed
);

@bp = (
  sub { return "(".$_[0]." + ".$_[1].")"; },
  sub { return "(".$_[0]." - ".$_[1].")"; },
  sub { return "(".$_[0]." * ".$_[1].")"; },
  sub { return "(".$_[0]." / ".$_[1].")"; },
);

sub combine {
  ($in1, $in2, $out) = @_;
  foreach $v1 (sort { $a <=> $b } keys %$in1) {
    foreach $v2 (sort { $a <=> $b } keys %$in2) {
      foreach $o (0..$#bc) {
        $n = &{$bc[$o]}($v1, $v2);
        if ($n > -1 && $n < $max && $out->{$n} eq '') {
          $out->{$n} = &{$bp[$o]}($in1->{$v1}, $in2->{$v2});
        }
      }
    }
  }
}

sub iteration {
  &combine($v->[$_[0]-$_], $v->[$_], $v->[$_[0]]) for (1..$_[0]-1);
}

$v->[$_] = {} for (0..9);
$v->[1]{9} = "9";
&iteration($_)for(2..9);
foreach (0..200) { print "$_ => $v->[9]{$_}\n" if ($_ == int($_)); }   # changed
(Computing all and not displaying the fractions in the end takes a wee bit longer though, about 3 seconds)
Joined: 7/5/2004
Posts: 551
Location: Karlstad, Sweden
Gorash wrote:
138.
A magical number! If u are a Misfits geek as me ^^ http://www.onethirtyeight.com/138.html
Joined: 3/25/2004
Posts: 459
Can you please explain to me what the method your code uses and how you know it is correct? Are you sure that all parantheses were considered also? Unary? (I know that I didn't say unary operators were allowed in the first post because I thought they wouldn't make a difference. Now I think they may.)
Player (201)
Joined: 7/6/2004
Posts: 511
I tried it with and without unary minus, and 195 was still the smallest un9able. Since both Gorash's and my programs got 195 independently, I don't think our answer is wrong.
g,o,p,i=1e4,a[10001];main(x){for(;p?g=g/x*p+a[p]*i+2*!o: 53^(printf("%.4d",o+g/i),p=i,o=g%i);a[p--]=g%x)x=p*2-1;}
Joined: 3/25/2004
Posts: 459
I editted out the majority of my first post so as not to confuse any people reading the thread for the first time.
Joined: 4/16/2005
Posts: 251
It works much like the program you proposed I think. (At least like the portion I did understand). Basically, it computes all expressions of two 9s, then out of thos all of three 9s, and so on. The array @bc stands for binary_compute and stores anonymous functions that return the two input values added, substracted, multiplied, or divided. @bp contains the corresponding string expressions (binary print). (there was also unary compute/print in the four4 version...) To get all of the expressions consisting of 2 nines, the program takes the expressions made of one nine (which is only "9"), and combines them using all the functions found in @bc. Result is a hash, that stores all the results and hashes them to their generation expression: 0 => '9-9' 1 => '9/9' 18 => '9+9' 81 => '9*9'. That's what the function combine does. It takes all of the values in the first argument, and all of the values in the second argument, and stores their combination in the third argument. (Arguments have to be references to hashes.) Now you can make up the four 9s expressions from either combining two two 9s expressions or one three 9s expression and one one 9 expression. That's what the function iteration is for. It counts through all combinations that make up the requested iteration, and combines them into the desired hash. The main program only consists of initializing the hashes, setting the initial hash ('9' => '9'), and then iterating through the higher hashes until nine 9s is reached. The last line them filteres non integer values and displays their generating expression. There always is the possibility that I overlooked some weird thing, like I already did with the fractions. Don't trust any result of a computer that you can't check by hand. :)