Many good replies above, but figured I'd
try it for myself with the help of CPAN.
Looks like it runs plenty fast enough with
brute force alone. Fun.
#!/usr/bin/perl -w
#
# See http://perlmonks.org/?node_id=503317, Oct 27 2005
# Jim Mahoney (mahoney@marlboro.edu)
#
use strict;
use warnings;
use Algorithm::FastPermute qw(permute);
use Math::Combinatorics qw();
my $debug = 0;
my $largest = 0;
my @solutions;
my $start_time = time();
print "
What is the largest integer whose digits are all different
(and do not include 0) that is divisible by each of its individual di
+gits?
Working...
";
for my $n (reverse 1..9){
my $c = Math::Combinatorics->new( count=>$n, data=>[1..9] );
while (my @array = $c->next_combination){
permute { remember(@array) if is_solution(@array) } @array;
}
}
@solutions = sort @solutions;
print "
Done in " . (time()-$start_time) . " seconds.
Total number of solutions found is " . scalar(@solutions) . ".
Largest is " . $solutions[-1] . ".
";
sub remember {
my @digits = @_;
push @solutions, join('',@digits);
}
sub is_solution {
my @digits = @_;
my $number = 0+join('',@digits);
for my $digit (@digits){
return 0 if $number % $digit != 0;
}
return 1;
}
__END__
$ ./n_digits_divide.pl
What is the largest integer whose digits are all different
(and do not include 0) that is divisible by each of its individual di
+gits?
Working...
Done in 6 seconds.
Total number of solutions found = 548.
Largest found was 9867312.
