Re: Puzzle: What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual digits?

As noted by others, if the answer includes a 5 it must end in 5, which would preclude all of 2, 4, 6 and 8.

However you may also spot that the digits 12346789 do not have a sum divisible by 3, so we must lose a 1, 4 or 7 to avoid losing all of 3, 6 and 9. Of those, only 4 leaves us a digit sum divisible by 9, so if a 7-digit solution is possible it must consist of 1236789.

The gcd of those digits is 7*8*9 = 504, so we can start at 504 * int(9876321/504), and work down in steps of 504 until we find a multiple that consists of the right set of digits; as it turns out, just 17 such steps take us to the answer, and we could reasonably do that much by hand (though I didn't :).

Hugo

Comment on Re: Puzzle: What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual digits?

Replies are listed 'Best First'.
Re^2: Puzzle: What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual digits? by QM (Parson) on Oct 27, 2005 at 20:09 UTC
This was my take too. Since we start with an even number, and subtract an even number, we don't have to worry about ending in an odd digit. Since we know that all allowed digits will divide any multiple of 504, we don't even test for that. Here's the code I wrote (somewhat inspired by previous posts): `#!/your/perl/here use strict; use warnings; use Benchmark::Timer; my $t = Benchmark::Timer->new(); $t->start(); my $c = 789; my $x = $c * int(9876321/$c); my $steps = 0; while ($x > 0) { next if $x =~ /[05]/; # no 0 or 5 next if $x =~ /([1-9]).*\1/; # no repeated digits last; } continue { $x -= $c; $steps++; } $t->stop(); print "$x ($steps steps)\n"; print $t->report(); __OUTPUT__ 9867312 (17 steps) 1 trial of _default (64us total)` [download] -QM -- Quantum Mechanics: The dreams stuff is made of	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: Puzzle: What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual digits?
by QM (Parson) on Oct 27, 2005 at 20:09 UTC

Here's the code I wrote (somewhat inspired by previous posts):

#!/your/perl/here

use strict;
use warnings;

use Benchmark::Timer;
my $t = Benchmark::Timer->new();
$t->start();

my $c = 7*8*9;
my $x = $c * int(9876321/$c);
my $steps = 0;

while ($x > 0)
{
    next if $x =~ /[05]/; # no 0 or 5
    next if $x =~ /([1-9]).*\1/; # no repeated digits
    last;
}
continue
{
    $x -= $c;
    $steps++;
}
$t->stop();
print "$x ($steps steps)\n";
print $t->report();

__OUTPUT__
9867312 (17 steps)
1 trial of _default (64us total)
[download]

-QM
--
Quantum Mechanics: The dreams stuff is made of

[reply]
[d/l]