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?

[barrachois]

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 ([e-mail])
#
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.