Alex Tweedly wrote:
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 ...
That warning still applies .....
I took the dogs for a walk, so had more time to think about this.
(Part of my regular problem-solving technique :-)
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.
More analysis.
The code shown before used a loop
repeat with tNum = 9876321 down to 1 step -9
making use of the fact that we know the initial value is divisible by 9,
so need only try those values which differ from it by multiples of 9.
We can extend that to directly calculate how to make it divisible by 8 -
and then try numbers which differ from *that* by multiples of 72. (In
fact, I didn't do this calculation - simply reduced it by 9 repeatedly
until it became a multiple of 8)
We can extend that to calculate how to make it a multiple of 7 - and
then decrease by steps of 504 (9*8*7)
(again, just decrease by 72 until it becomes a multiple of 7)
etc.
Old answer was
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>
New answer is
9867312 is OK
18 4 0
i.e. less than 1 millisec !
and the code is
--> 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
put 9876321 into tFirst
put 9876321 into tNum
put 1 into tMultiple
repeat with i = 1 to the number of chars in tNum
put char i of tFirst into c
-- I'm sure it should be possible to calculate this, but we
cannot loop
-- more than a single-digit number of time, so not worth the
effort
-- to figure out the calculation
repeat while tNum mod c <> 0
subtract tMultiple from tNum
end repeat
-- Now that we are a multiple of all digits so far, must remain so
-- step down by LCM of tMultiple and this new char
-- (no need to calculate LCM : just use the new digit if not
already a divisor
-- digits in decreasing order satisfy this automatically)
if tMultiple mod c <> 0 then multiply tMultiple by c
end repeat
repeat with tNum = tNUm down to 1 step -tMultiple
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
-- no need for divisibilty check - tMultiple ensures this
is always true
-- -- -- 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 && 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
