Programming tools philosophy.

Alex Tweedly alex at tweedly.net
Thu Oct 27 16:02:12 CDT 2005

```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
>
>
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.

> 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
>         if "0" is in tNum then next repeat
>         if "5" is in tNum then next repeat
>         if "4" is in tNum then next repeat
>         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
>             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

-------------- next part --------------
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
```