### Re: Coming soon: Algorithm::Loops

by tall_man (Parson)
 on Apr 11, 2003 at 23:15 UTC ( #249996=note: print w/replies, xml ) Need Help??

in reply to Coming soon: Algorithm::Loops

A couple of observations from number theory to reduce the search space. The number 2003 is congruent to 5 mod 9, and taking sums of base-ten digits reduces them mod 9. If three permutations of digits \$x, \$y, and \$z could solve the puzzle, then:
```(3*(\$x+\$y+\$z) % 9) == 5
But 3 has no inverse mod 9 because of the common factor, so it's impossible with 3 permutations.
```if (4*(\$x+\$y+\$z) % 9) == 5  then (\$x+\$y+\$z) % 9 = 8
if (5*(\$x+\$y+\$z) % 9) == 5  then  (\$x+\$y+\$z) % 9 = 1
if (7*(\$x+\$y+\$z) % 9) == 5  then  (\$x+\$y+\$z) % 9 = 2
6 is impossible because of the common factor. For any given \$x, \$y you can calculate what \$z would have to be (or eliminate it if it's a duplicate of the others). That should cut down your search space by a lot.

Replies are listed 'Best First'.
Re^2: Coming soon: Algorithm::Loops (analysis)
by tye (Sage) on Apr 12, 2003 at 06:50 UTC

I just wanted to mention that the code ran so fast (I didn't even notice how long it took, probably a couple of seconds) that I didn't get around to thinking at all about about analysis of the problem since I had no need to cut down the search space (and I got into the loop rewriting).

And I also wanted to thank you for the analysis. Nicely done. (:

- tye

Create A New User
Node Status?
node history
Node Type: note [id://249996]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (8)
As of 2021-04-13 18:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?