Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

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

Log In?
Username:
Password:

What's my password?
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?