MU puzzle
en.wikipedia.org
en.wikipedia.org
"Our main finding to report is the fact that a path length of a Mersenne prime is approximately proportional to its index for large n, namely, D(Mn) ≈ 13.45n."
Paper is at https://arxiv.org/pdf/1104.2804.pdf . WARNING: PDF.
For example, https://arxiv.org/abs/1104.2804
In retrospect it may have actually undone some damage done by the school system where the solution space is usually very restricted.
Edit: (1) From what I remember it’s stated as find the sequence and not does such a sequence exist.
But if you're at work and your boss says "I have a puzzle I need you to solve: Given these constraints, find an answer" You need to be able to say "Here is my solution" or "No solution is possible, and here is why."
Or take something simpler: a 500 piece "Puzzle" only there's a manufacturing defect in all copies: one piece is miss shaped. The puzzle can't be completed; there is no "solution". It's still a puzzle.
So no, you don't get to "unfair!" your way out of the MU Puzzle through narrow semantic definitions, especially given the, well, grammatical nature of language, because then you have gone and missed the entire point.
You and the parent comment claim it's not a puzzle, it's a riddle, with the implication that's somehow unfair or deceptive in how the problem was framed.
That is a semantic hair splitting that dodges the problem & its answer. In real life problems you don't get to define away responsibility for problems put in front of you. And if thoroughly stating my case is "overractive", then I'm guilty, but I find it's generally better to over-support my argument than state claims without justification.
All of which is besides the point: "Puzzle" and "Riddle" are pretty much interchangeable. They appear as synonyms for each other in thesauri; "riddle" is given as one of multiple definitions for "puzzle" in wiktionary. Many sources treat "riddle" as a kind of "puzzle". The degree to which riddle might be more appropriate in a given context relies on a few factors, for example riddles often tend towards more verbal basis, spoken or written. A puzzle is the broader category and can include things like physical object such as a 500-piece jigsaw puzzle. But any difference is still only that of broader category and specific type. Either term is valid here.
So stating "It's not a puzzle, it's a riddle" is indeed splitting hairs, or simply not knowing the nuances of the actual definitions of those words. The OP of that comment appeared to be doing so with the implication that the whole problem was somehow unfair as a result. I cry foul on that assertion for the reasons stated.
(Yes, using the traditional definitions of all those symbols.)
It should be noted that if the teacher had had the foresight (often a big ask) to simply tell you they suspected there was no solution, which is often the case with such problems presented as they are, and that you should attempt a proof alone, you would likely not feel so bad about not spotting it immediately.
But that was precisely the point. That given a system with a set of rules, the space of all possible problems may be larger than the space of all solutions, i.e., not all problems have a solution.
To say it's useful to be able to determine if a problem is solvable is a vast understatement.
Now I've had some of the surprise ruined just by reading a HN thread that didn't even appear to be related to the book in the first place. If I had just clicked the Wikipedia link and read the first puzzle, I'd have clipped it to my notes and marked it as something to read afterward. But because this was pushed up to top comment, it caught my eye first.
#!/usr/bin/perl -w
use strict;
my %tried = ();
main();
sub main {
my @rules = (
\&rule_one,
\&rule_two,
\&rule_three,
\&rule_four,
);
my $axiom = 'MI';
my @path;
my @tries;
solve($axiom, \@rules);
}
sub solve {
my @app;
my ($axiom, $rules) = @_;
my $i = 0;
foreach(@$rules){
my $tmp = $_->($axiom);
push(@app, $tmp) if $tmp;
}
foreach(@app){
next if $tried{$_};
next unless (length($_) < 1000);
print $_ . "\n";
$tried{$_} = 1;
if($_ eq 'MU'){
print "YES!\n\n\n";
exit;
}
solve($_, $rules);
}
}
sub rule_one {
# If any string ends in I, you can append U
my $str = shift;
if ($str =~ m/I$/){
return $str . 'U';
}else{
return undef;
}
}
sub rule_two {
# If any string begins with M,
# you can duplicate the string after M,
my $str = shift;
if($str =~ /^M/){
return 'M' . substr($str, 1) . substr($str, 1);
}else{
return undef;
}
}
sub rule_three {
# If any string contains III,
# you can replace the III with U
my $str = shift;
if($str =~ /III/){
$str =~ s/III/U/g;
return $str;
}else{
return undef;
}
}
sub rule_four {
#If any string contains UU,
# you can delete the UU
my $str = shift;
if($str =~ /UU/){
$str =~ s/UU//g;
return $str;
}else{
return undef;
}
}I thoroughly enjoyed it, but I've always had diverse interests and the book sort of caters to that.
If you approach it as an object of art, the book is fun because it embeds into itself many of the techniques and principles it describes (but you'll only notice this if you're paying attention). This is kinda cool on a meta-meta level because the central concept of the book is self-referentiality.
The GEB book doesn't have all the details, but it uses the ASCII representations (actually base 20 but whatever). With the ASCII representation the theorem feels obvious.
It is a lot of fluff and meandering, but the dialogue are just too good, and I still enjoy them.
Some people have recommended reading "I am a strange loop" as a basically more mature and better written version of GEB.
That's actually the Pythagorean theorem. How did you arrive at that by doing the "unsolvable"?
This is basic knowledge (and as someone said, comes from the Pythagorean theorem) and taught on school in a lot of places.