Quantum.Mechanic
-
Posts
96 -
Joined
-
Last visited
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by Quantum.Mechanic
-
-
Spoiler
Assume the radius R = 1. The diagonal of the square will be 2R = 2. The sides of the square will be sqrt(2). The length from the center to the midpoint of the square's side is sqrt(2)/2. The ratio is then (1-sqrt(2)/2) / 1, or just 1 - sqrt(2)/2, or about 0.3.
-
On 09/03/2018 at 5:54 PM, Molly Mae said:
EDIT: For clarity, I use "number" to reference an individual digit. I use "sequence" to reference the string of numbers.
EDIT2: Added spoiler tag.Sorry, I'm pretty bad at explaining things. You're basically building two sequences: n and 2n. I arbitrarily chose 1 as the first number of the first sequence and we don't know the length of the sequence, so it looks like this:
First: 1????...???
Second: ?????...???Since 1 is the first number of the first sequence and the second sequence is double the first sequence, we can update our second sequence.
First: 1????...???
Second: 2????...???From the OP, we are promoting the least significant number of the first sequence to the most prominent position. So we now know that the first sequence ends with a 2. Let's update that.
First: 1????...??2
Second: 2????...???Again, since our second sequence is double the first, we know that the second sequence ends in a 4.
First: 1????...??2
Second: 2????...??4Remember that the second sequence is the first sequence except that the last number is moved to the front. So the second to last number of the first sequence is a 4.
First: 1????...?42
Second: 2????...??4Four doubled is 8.
First: 1????...?42
Second: 2????...?84The 8 moves up to the first sequence:
First: 1????...842
Second: 2????...?84Eight doubled is 16.
First: 1????...842
Second: 2????...684You can keep doing this until your second sequence can begin with a 2 without having to carry over a number. It's a neat puzzle where you build two sequences simultaneously using new information from one sequence to build the next part of the other sequence.
I hope that clears it up.
Yes, thanks very much. I got lost trying to do this myself, but "it's obvious in hindsight", as they say.
-
I must be thick today, I can't follow the given solution. Can someone paste a little bit more hand holding? Like the first 5 values in the sequence?
-
Spoiler
Each person adds a random number to their salary (the random number can be positive or negative).
The first person gives his sum to the second. The second adds the 2 sums together, and gives it to the third. The third adds the 2 sums together, and gives it to the first. Now they each subtract their random number from the sum, passing the new sum to the next person, finally arriving at the true total. Then they can take the average.
-
Spoiler
"He took note of the time on his clock when he left. We'll call this value TS '"
compared to:
"...when he realized that his grandfather clock had stopped..."
Pickett's answer doesn't seem to acknowledge this (perhaps this was an error in the original statement).
-
Since the integer requirement, there haven't been any replies, so I'll go with an obvious, and not-likely-to-be-optimal one.
SpoilerPowers: Buy a single ticket, and randomly choose X >= 1, where P(X) = 2-x. So P(1) = 1/2, P(2) = 1/4, etc.
-
Spoiler
It's odd that given one focus, and two points on the ellipse, is not enough. But three points on the ellipse, with one focus, should be enough to determine the ellipse and the other focus. And four points on the ellipse, and no foci, would also work. But how to do this is beyond me.
-
OK, I thought that would be a good little puzzle program to write. I'm sure there's an easier way to figure this on paper though, waiting for y'all to clue me in. The first few elements led me to the following:
Spoilerhttp://oeis.org/A046090, "a(a-1) = 2b(b-1)". The first element larger than 1e12 is 1070379110497.
-
To put a finer point, if two siblings are two cells (or particles) resulting from splitting of the mother cell into two, then none is older.
Are we assuming a mammalian birth process?
Then splitting is in utero, and age origin is time of birth.
When in Thailand...
Siamese twins are born at the same time.
-
Most of you got it.
BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.
I'm marking her answer, therefore.
Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.
-
you want to throw three 8 sided dice; such that: all three dice are numbered the same, and 120 different totals are possible; and the maximum number is as small as possible.
with 7 sided dice, the best possible is: 1, 2, 8, 51, 60, 79, 83
but your challenge is to go one more side.
Maximum sum, or highest numbered side?
But according to Wolfram Alpha, x^388-1/x-1 isn't a cube (it's rather ugly).
-
At http://www.numericana.com/answer/dice.htm#split I've found an interesting method.
It seems we need to find some M such that 1 + x + x2 + x3 + ... + xM-1 is a cube, and the polynomial cube root must have all nonnegative coefficients. If the largest face is F, then M = 3F+1. (The cube root could itself be composite, though I'm not sure if being composite implies anything about the minimization of F.)
Given that we have a solution for F=130, then F=129 implies M=388.
On that page there is also mention of cyclotomic factors, which I'll have to go read up on.
-
Perl has the if/unless pair:
http://www.cs.cf.ac.uk/Dave/PERL/node45.html -
I saw this puzzle in the same Peter Winkler book I mentioned elsewhere.
His "solution" was unsatisfying, relying on some metric which scores ants above the X-axis, and higher for ants higher above the axis, and closer to the Y-axis. Since it's the infinite half-plane, it should make no difference what the X coordinate is.
I'd suggest yes, it's possible to do any arbitrary height, though I have no solid proof.
But if as in your example, we can get any ant above the X-axis, then it is fairly trivial to fill in below it, and allow a jump to a higher Y value. Sure, the devil is in the details for replacing all the jumped ants, which must come from farther and farther away. So this may end up being extremely tedious in the vein of Towers of Hanoi. Or I may be completely wrong, and it's not possible, due to backfilling all of the missing ants at an exponential rate which is faster than the growth in height above the X-axis.I feel another program coming on...
-
Testing a few targets other than 99,
N(n,n+1) is always true for targets of 2n+1.
-
I wrote a program to check.
49 + 50 = 99, 4950 | N(49,50)
39 + 60 = 99, 3960 | N(39,60)
24 + 75 = 99, 2475 | N(24,75)
23 + 76 = 99, 2376 | N(23,76)
19 + 80 = 99, 1980 | N(19,80)
15 + 84 = 99, 1584 | N(15,84)
14 + 85 = 99, 1485 | N(14,85)
9 + 90 = 99, 990 | N(9,90) -
I was using the code from post #21; is there another version?
Are you sure? Because starting at line 193, it has:
# This result might already exist. Keep the new one if the path is shorter. if (not exists($m->{$result}) or (scalar keys %$new_path < scalar keys %{$m->{$result}})) { # print STDERR "\tAdded $expression = $result\n"; $m->{$result} = $new_path; ++$results_added; } -
I just read an equivalent puzzle in a puzzle book, so I'll sit this one out...
-
-
Here's a concrete example.
I tried modifying the code so it generates a matrix of steps to get from each starting point to each goal, just like the matrix I posted earlier, and runs from 1 to 30 so I could directly compare the matrices they produce. They differ at some spots, one of which is the path going from 11 to 3. For some reason it took four steps and went 11/11=1, 11+11=22, 22/11=2, 2+1=3. Obviously a shorter path would be 11/11=1, 1+1=2, 1+2=3.
Apparently there are two equally short paths from 11 to 2: {11/11=1, 1+1=2} and {11+11=22, 22/11=2}, and the algorithm ended up storing the second path as the most efficient path to get to 2. However, since it didn't store the path to 2 that creates 1 as an intermediate rather than 22, it wasn't able to discover that you could reach 3 from a path going to 2 through 1 that had a useful intermediate already generated.
Yes, that was possible for earlier versions. The current version gives me this:
four_banger.pl 30 11 3 [...snip...] Steps for 11 => 3 (not in order): 11 / 11 = 1 1 + 1 = 2 2 + 1 = 3 [...snip...]because it compares multiple paths to the same goal, and keeps the shortest. (In case of ties, it takes the path with the smallest max operand.)
-
Checking for paths that go above the limit (last number):
Not allowing any intermediate results above 25:
Steps for 14 => 25 (not in order): 13 - 2 = 11 14 + 11 = 25 14 - 1 = 13 1 + 1 = 2 14 / 14 = 1
Allowing intermediate results above 25:
Steps for 14 => 25 (not in order): 14 - 1 = 13 13 + 13 = 26 14 / 14 = 1 26 - 1 = 25
So this is 1 shorter.
On a whim, I ran it with the max intermediate step = last**2, or 625 in this case, and found this path with 4 steps:
Path above 25 for (15,10): 15 + 15 = 30 450 / 45 = 10 30 + 15 = 45 30 * 15 = 450
Limiting search to 25*2 = 50, found this path with 5 steps:
Steps for 15 => 10 (not in order): 1 + 1 = 2 14 - 4 = 10 15 - 1 = 14 2 + 2 = 4 15 / 15 = 1
I wonder how big the search range needs to be in relation to the last number to guarantee the optimal path?
-
Suppose you start from A and need to reach D, which can be reached from B and C.
There's an optimal path from A to B in, say, four moves.
There's an optimal path from A to C in, say, five moves.
So it would look like it would take 4 moves to reach B, 5 to reach C, and therefore a total of 10 to reach D.
I think you've left something out here, or perhaps meant something else. For pedantic clarity, I'll say this anyway:
You didn't say how many moves it was from B to D, or C to D. If it's the same for both, let's say 1, then A->B->D = 4+1 = 5, and A->C->D = 5+1 = 6. So the optimal is A->B->D = 5. Paths don't simply add together -- any duplicate steps only count once.
The rest of your statement is worth consideration. The algorithm I use is greedy -- it only keeps the shortest path to any result. But I think it is provable that if there are 2 paths A->B->D = 5 and A->C->D = 4, it will pick the latter. While it might find A->B->D first, it still checks any other paths to D, and keeps generating paths to all results until no new results are added, and no shorter paths are found.
# This result might already exist. Keep the new one if the path is shorter. if (not exists($m->{$result}) or (scalar keys %$new_path < scalar keys %{$m->{$result}})) { # print STDERR "\tAdded $expression = $result\n"; $m->{$result} = $new_path; ++$results_added;What you are proposing is that there's some way to get to a result E through a non-optimal path to D, that's shorter than the optimal path to D, plus D->E. I'm a little rusty on my proofs, but I think this falls into the "proof by contradiction" class.
Earlier versions of my program didn't do this, but instead stopped when the first path to a result was found. This depended on the generation order, which wasn't necessarily generating shortest path first, instead of the path order. So if a non-optimal path to D was found, it was kept, and no further paths to D were even checked for length.
On the other hand, I don't think it was ever stated explicitly if all paths could only go through numbers less than or equal to the limit value. There might be some edge cases where, say, an abundant number >> limit provides a path to a goal with fewer steps than any path <= limit.
-
If you give us a link, we might be able to visit the site and suggest other sites. I have always liked http://www.ferryhalim.com/orisinal/.
-
After further study, I realized that the first path to a goal generated may not be the shortest path. It needs to keep generating goals until no new or shorter paths are found. It seems this doesn't happen all that often, so it hardly affects the runtime.
Eliminating some of the low level structure, the full matrix including paths can be saved, at least as high as 256. Judging by the memory usage, it could probably go a bit higher.
Here's the results I have for 256. Hopefully they pass all of plasmid's tests this time.
> time four_banger.pl 256 1 187 Best starts have 7 worst case steps: 2 => 87 3 => 139 4 => 107 5 => 183 6 => 165 7 => 234 <...and many more...> Worst starts have 8 worst case steps: 1 => 187 17 => 245 20 => 233 24 => 179 25 => 239 31 => 237 32 => 213 33 => 251 34 => 249 Best starts have 4.68 mean steps: 6, 4.68 mean steps 7, 4.70 mean steps 5, 4.70 mean steps 8, 4.73 mean steps 10, 4.78 mean steps 11, 4.79 mean steps 9, 4.80 mean steps 3, 4.82 mean steps 14, 4.85 mean steps Worst goals have 6.48 mean steps: 247, 6.48 mean steps 233, 6.47 mean steps 251, 6.46 mean steps 253, 6.39 mean steps 235, 6.38 mean steps 137, 6.38 mean steps <...and many more...> Steps for 1 => 187 (not in order): 4 + 1 = 5 192 - 5 = 187 16 * 12 = 192 1 + 1 = 2 2 + 1 = 3 2 + 2 = 4 4 * 4 = 16 4 * 3 = 12 real 7m28.947s user 7m24.456s sys 0m0.260sSo, not too bad at 7.5 minutes.
Here's the latest code.
#!/usr/bin/env perl # # http://brainden.com/forum/index.php/topic/17088-optimal-game-strat/ # # Two players pick 2 numbers each from 1..256. The first number is that # player's starting number, and the second number is the opponent's goal # number. Using +-*/ only, get from start to goal in the least number of # operations. Players may only use numbers previously generated in their # sequence. # # What is the best starting number, and worst goal number, in terms of # number of moves? # # Generate all start=>goal shortest paths. Report the start with the # smallest "longest" path, and the goal with the longest "shortest" # path. # Method: # Use a hash like this to keep track: # $m = {goal1 => { list => { n1 => 1, # n2 => 1, # }, # path => { "n1 op n2" => result1, # "n3 op n4" => result2, # }, # }, # goal2 => {...}, # }; # # As operations are tried, each generated value is added to the hash, until # the goal is generated. The number of steps is the size of the array for # each seen. Any seen value with a size of 1 is an immediate child. # Any generated values larger than $last*2 are not saved. use strict; use warnings; use integer; my $last = (shift // 10); my $upper_limit = $last; my $my_start = (shift // 0); my $my_goal = (shift // 0); my $START = q/start/; my $GOAL = q/goal/; my $STEPS = q/steps/; my $COUNT = q/count/; my $MEAN = q/mean/; my $PLUS = '+'; my $MINUS = '-'; my $TIMES = '*'; my $DIVIDE = '/'; my @ops = ($PLUS, $MINUS, $TIMES, $DIVIDE); my %matrix; # %matrix = ($start1 => {$goal1 => { $path1 => $result1, # $path2 => $result2 }, # {$goal2 => { ... }, # $start2 => {...} ) # For each $start, record the $goal with the longest $path my %start; # %start = {$start => {STEPS => steps, GOAL => goal}; # For each $start or $goal, sum the steps and update count, to compute mean later on my %mean; # %mean = {$START => {$start => {STEPS => steps, COUNT => count}, # $GOAL => {$goal => {STEPS => steps, COUNT => count}}; for my $start (1..$last) { print STDERR "$start "; my $m = {}; $m->{$start} = {}; # Generate results until no new or shorter results are found. # This loop is limited by the value of $upper_limit. 1 while generate($m); # Now walk through all goals, saving highest steps, summing steps and update counts my $steps_max = 0; for my $goal (1..$last) { my $steps = scalar keys %{$m->{$goal}}; $steps_max = $steps if ($steps > $steps_max); if (not exists($start{$start}) or ($steps > $start{$start}{$STEPS})) { $start{$start}{$STEPS} = $steps; $start{$start}{$GOAL} = $goal; } $mean{$START}{$start}{$STEPS} += $steps; $mean{$START}{$start}{$COUNT}++; $mean{$GOAL}{$goal}{$STEPS} += $steps; $mean{$GOAL}{$goal}{$COUNT}++; } $matrix{$start} = $m; } # Find the starts with the lowest and highest max steps my ($start_best,$start_worst) = (sort {$start{$a}{$STEPS} <=> $start{$b}{$STEPS}} keys %start)[0,-1]; # Best starts print "\nBest starts have $start{$start_best}{$STEPS} worst case steps:\n"; for my $s (1..$last) { if ($start{$s}{$STEPS} == $start{$start_best}{$STEPS}) { printf "\t%4d => %4d\n", $s, $start{$s}{$GOAL}; } } # Worst starts print "\nWorst starts have $start{$start_worst}{$STEPS} worst case steps:\n"; for my $s (1..$last) { if ($start{$s}{$STEPS} == $start{$start_worst}{$STEPS}) { printf "\t%4d => %4d\n", $s, $start{$s}{$GOAL}; } } no integer; # Find the start and goal with the highest mean steps for my $ENDPOINT ($START, $GOAL) { for my $n (1..$last) { $mean{$ENDPOINT}{$n}{$MEAN} = $mean{$ENDPOINT}{$n}{$STEPS} / $mean{$ENDPOINT}{$n}{$COUNT}; } } # Report the best start means my @start_best = sort {$mean{$START}{$a}{$MEAN} <=> $mean{$START}{$b}{$MEAN}} keys %{$mean{$START}}; $start_best = $start_best[0]; # Report all mean starts near the best mean printf "\nBest starts have %3.2f mean steps:\n", $mean{$START}{$start_best}{$MEAN}; my $start_best_mean_plus_2tenths = $mean{$START}{$start_best}{$MEAN} + 0.2; for my $s (@start_best) { if ($mean{$START}{$s}{$MEAN} <= $start_best_mean_plus_2tenths) { printf "\t%4d, %3.2f mean steps\n", $s, $mean{$START}{$s}{$MEAN}; } } # Report the worst goal means my @goal_worst = sort {$mean{$GOAL}{$b}{$MEAN} <=> $mean{$GOAL}{$a}{$MEAN}} keys %{$mean{$GOAL}}; my $goal_worst = $goal_worst[0]; # Report all mean goals near the worst mean printf "\nWorst goals have %3.2f mean steps:\n", $mean{$GOAL}{$goal_worst}{$MEAN}; my $goal_worst_mean_less_2tenths = $mean{$GOAL}{$goal_worst}{$MEAN} - 0.2; for my $g (@goal_worst) { if ($mean{$GOAL}{$g}{$MEAN} >= $goal_worst_mean_less_2tenths) { printf "\t%4d, %3.2f mean steps\n", $g, $mean{$GOAL}{$g}{$MEAN}; } } # If you want a specific start/goal path, print it here. # Order is not preserved. if ($my_start and $my_goal) { print "\nSteps for $my_start => $my_goal (not in order):\n"; for my $path (keys %{$matrix{$my_start}{$my_goal}}) { print "\t$path = $matrix{$my_start}{$my_goal}{$path}\n"; } print "\n"; } exit; use integer; # From the given list of results, compute additional results # using all combinations of operands and operators. # Only record the shortest paths of unique results. sub generate { my $m = shift; my $results_added = 0; # The currently known goals, sorted in descending order for compute my @seen = sort {$b <=> $a} keys %$m; # Walk through @seen x @seen, but avoid obvious redundancies for my $i1 (0..$#seen) { my $s1 = $seen[$i1]; for my $i2 ($i1..$#seen) { my $s2 = $seen[$i2]; # Try every operation for my $op (@ops) { my ($result,$expression) = compute($s1,$s2,$op); next unless $result; next unless ($result <= $upper_limit); # speedup, might lose some shorter paths # Add unique paths to get this result my $new_path = {%{$m->{$s1}}, %{$m->{$s2}}, $expression => $result }; # This result might already exist. Keep the new one if the path is shorter. if (not exists($m->{$result}) or (scalar keys %$new_path < scalar keys %{$m->{$result}})) { # print STDERR "\tAdded $expression = $result\n"; $m->{$result} = $new_path; ++$results_added; } } } } return $results_added; } # Take 2 numbers, sorted in descending order, and an operator. # Return the result and the string expression used. # Subtract and divide are managed to avoid negative or non-integer results. sub compute { my $n1 = shift; # larger my $n2 = shift; # smaller or equal to $n1 my $op = shift; my ($result,$expression); if ($op eq $PLUS) { $result = $n1 + $n2; $expression = "$n1 $PLUS $n2"; } elsif ($op eq $MINUS) { $result = $n1 - $n2; $expression = "$n1 $MINUS $n2"; } elsif ($op eq $TIMES) { $result = $n1 * $n2; $expression = "$n1 $TIMES $n2"; } elsif ($op eq $DIVIDE) { $result = $n1 / $n2; # only integer results allowed ("use integer" in effect) return(0,undef) if ($result * $n2 != $n1); $expression = "$n1 $DIVIDE $n2"; } else { die "Error: unknown operand ($op), aborting...\n"; } return($result,$expression); } # compute
4 letters => 6 words
in New Logic/Math Puzzles
Posted
I've previously written a nice word puzzle script, which takes in a huge list of words, and creates a list of anagram "siblings". One of the special functions is to find, for each word length, the largest anagram set of siblings.
Length: Count, Anagram Siblings
2: 2, ba, ab
3: 5, abr, arb, bar, rab, bra
4: 8, abel, albe, blae, bela, blea, beal, able, bale
5: 13, arces, acers, races, scare, cares, acres, caser, scrae, serac, ceras, sacre, carse, escar
6: 6, reshod, shored, horsed, hordes, dehors, shoder
7: 2, egilops, epilogs
8: 2, aegilops, spoilage
For length of 4, there are 8 siblings in the "abel" set. While I trust my word list sources, some of these may not truly count as English. For instance, I can only find a Dutch entry for "abel". "Blae" is nominally Scots, but is found in Northern England, so it must be English!