Programming tools philosophy.

[Alex Tweedly]

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