# Quantum.Mechanic

Members

87

## Community Reputation

0

• Rank
Junior Member

## Quantum.Mechanic's Activity

1. Quantum.Mechanic added a post in a topic Half as old as my brother

When in Thailand...
• 0
2. Quantum.Mechanic added a post in a topic Relatively prime

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.
• 0
3. Quantum.Mechanic added a post in a topic dice problem

4. Quantum.Mechanic added a post in a topic dice problem

5. Quantum.Mechanic added a post in a topic Conditionally conflicting

6. Quantum.Mechanic added a post in a topic The army of ants

I saw this puzzle in the same Peter Winkler book I mentioned elsewhere.

• 0

Testing a few targets other than 99,

• 0

I wrote a program to check.

• 0
9. Quantum.Mechanic added a post in a topic optimal game strat

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; }
• 0
10. Quantum.Mechanic added a post in a topic Prisoners sorting cards - this puzzle is not for the faint of heart

I just read an equivalent puzzle in a puzzle book, so I'll sit this one out...
• 0
11. Quantum.Mechanic added a post in a topic List of numbers

12. Quantum.Mechanic added a post in a topic optimal game strat

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.)
• 0
13. Quantum.Mechanic added a post in a topic optimal game strat

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?

• 0
14. Quantum.Mechanic added a post in a topic optimal game strat

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.
• 0
15. Quantum.Mechanic added a post in a topic Lost in the jungle

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/.
• 0