Mark Wieder wrote:
Steve-
Wednesday, October 26, 2005, 11:48:00 PM, you wrote:
"What is the largest integer whose digits are all different (and do
not include 0) that is divisible by each of its individual digits?"
The biggest I get is 864312, have not tested all yet. 12346789
through 98764321 does not yield a result.
Thanks, but I'm actually more interested in the program that finds the
answer than in the result itself. Can you show your work?
Warning - I have both my code and my reasoning below ..... so don't
scroll down and read it unless you don't mind seeing that already ...
Well, I decided to do some more analysis first ...
(As Petzold said :
If the answer contains a 5, then it cannot contain any even digit, so
the max possible value would be <= 97531.
So we can safely assume there is no '5', provided the final result is >
97531.
That leaves us 8 digits, 98764321.
If the final answer includes the digit '9', then the sum of its digits
must also be divisible by 9.
The ones we have add up to 40 - so we'd need to drop the 4 (or drop
multiple digits).
If we dropped the 9, the max value would be <= 8764321
Assume we instead drop the 4 - and provided we get an answer > 8764321
that is an OK assumption.
That's as far as I can go with analysis. Time for some brute force.
We can either construct possible answers (just from the digits left) and
test them against the other criteria, or simply construct numbers and
test them against all criteria, including these one. I decided on the
latter - probably faster to construct numbers in a repeat loop.
The answer is
9867312 is OK
1002 229 208 68
This is large enough to validate the assumptions above; the last number
is the time taken, i.e. 68 milliseconds !!
CP's version (in ANSI C) took "< 1 second"
Who says interpreted langauges are slow ? <LOL>
The other numbers output are explained in the code below:
--> all handlers
on mouseUp
put 0 into tCount1 -- numbers considered
put 0 into tCount2 -- numbers which pass first filter : no 0,5,4
put 0 into tCount3 -- numbers which pass "repeated digit" test
put the millisecs into tStart
repeat with tNum = 9876321 down to 1 step -9
add 1 to tCount1
if "0" is in tNum then next repeat
if "5" is in tNum then next repeat
if "4" is in tNum then next repeat
add 1 to tCount2
put true into possible
repeat with i = 1 to the number of chars in tNum
put char i of tNum into c
if c is in char i+1 to -i of tNum then
put false into possible
exit repeat
end if
add 1 to tCount3
if (tNum / c) is not an integer then
put false into possible
exit repeat
end if
end repeat
-- oh for a "exit repeat <name>" or equivalent !!
if possible then exit repeat
end repeat
put tNum && " is OK" & cr after msg
put tCount1 && tCount2 && tCount3 && the millisecs - tSTart & cr
after msg
end mouseUp
--
Alex Tweedly http://www.tweedly.net
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.361 / Virus Database: 267.12.5/149 - Release Date: 25/10/2005
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
