Anonymous Monk has asked for the
wisdom of the Perl Monks concerning the following question:
how many numbers exist, such that no two digits are the same and such that the number is divisble by each of its digits?
Re: Puzzle Time
by LanX (Bishop) on Dec 23, 2012 at 03:47 UTC

And the answer is: 548
(I suppose only positive numbers otherwise multiply it with 2)
The following is just a variation of the code I recently used:
(I love branch and bound! :)
9! = 362880 possible combinations¹ are checked in a recursive function.
#!perl
use strict;
use warnings;
my @digits = 1..9;
my @number;
my $maxlevel=10;
my %count_hash;
my $count=0;
append_digit();
print "count: $count\n";
print join "\n", sort { $a <=>$b } keys %count_hash;
sub append_digit {
my $level = scalar @number;
my $number= join "", @number;
if ( $level and
! grep {$number % $_} @number
) {
$count++;
print "$count: $number\n" unless $count %100;
$count_hash{$number} = undef;
}
for my $digit (@digits) {
return if $level > $maxlevel; # for testing only
next if $digit ~~ @number;
push @number, $digit;
append_digit();
pop @number;
}
}
output
¹) and of course their substrings from the start, thx Athanasius++ :)  [reply] [d/l] [select] 

Your method of getting the next digit is expensive! Replace
for my $digit (@digits) {
next if $digit ~~ @number;
push @number, $digit;
append_digit();
pop @number;
}
with
for my $pos (0..$#digits) {
push @number, $digits[$pos];
local @digits = @digits[0..$pos1, $pos+1..$#digits];
append_digit();
pop @number;
}
to cut down the time taken to 2/3 (6s from 9s).
Also, there's reason to use a hash (outside of testing).
Full code:
#!perl
use strict;
use warnings;
use 5.010;
our @digits = 1..9;
my @number;
my @results;
sub append_digit {
my $number = join "", @number;
push @results, $number
if @number && !grep $number % $_, @number;
for my $pos (0..$#digits) {
push @number, $digits[$pos];
local @digits = @digits[0..$pos1, $pos+1..$#digits];
append_digit();
pop @number;
}
}
my $stime = time;
append_digit();
my $etime = time;
say $etime$stime;
say "count: " . (0+@results);
#say for sort { $a <=> $b } @results;
 [reply] [d/l] [select] 

++LanX for an excellent answer (way faster than my brute force approach).
Allow me one nitpick:
9! = 362880 possible combinations are checked in a recursive function.
Throwing in a counter shows that sub append_digit is actually called 986,410 times. Took me a while to work out why...
9! is the number of combinations if every number has exactly 9 digits. But we also allow numbers with 1, 2, ..., 8 digits. So the total number of combinations is:
my $p = 9 + # 1 digit
(9 * 8) + # 2 digits
(9 * 8 * 7) + # 3 digits
(9 * 8 * 7 * 6) + # 4 digits
(9 * 8 * 7 * 6 * 5) + # 5 digits
(9 * 8 * 7 * 6 * 5 * 4) + # 6 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3) + # 7 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2) + # 8 digits
(9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1); # 9 digits
say $p; # = 986,409
(That 1 extra sub call is the first one, when @number is empty.)
:)
 [reply] [d/l] [select] 

> Allow me one nitpick:
Yeah I noticed this, but was too tired to correct it. =)
Anyway my guess was wrong (9!+8!+7!+...) you got it right.
> (way faster than my brute force approach).
If it's about speed you can limit the $maxlevel, because the longest number can't have more than 7 digits:
 Evidently 0 is excluded!
 Any number this long includes even ciphers. So 5 is excluded!
But any number divisible by 5 and 2 must end with a 0
 An number from the remaining 8 digits would include 9 and 3, but the digit sum would be 40, which is impossible.¹
Even your approach with a brute force loop could compete when only considering 7 digits, cause you don't have the overhead of 1 million function calls.
¹) and therefor a 7 digit number excludes 4 to be divisible by 9.
 [reply] 

You are a legend, your help is greatly appreciated :)
 [reply] 
Re: Puzzle Time
by Athanasius (Chancellor) on Dec 23, 2012 at 03:39 UTC

First, some assumptions:
 Numbers means natural numbers
 Digits means digits in the decimal representation
 Divisible by a digit means divisible without remainder
 The digit 0 is excluded, since division by 0 is undefined
There are 9 different digits allowed, and any number having more than 9 digits will necessarily have some digits repeated. So, the upper bound is 987,654,321.
#! perl
use Modern::Perl;
my $count = 0;
OUTER:
for my $n (1 .. 987_654_321)
{
my %digits;
++$digits{$_} for split //, $n;
for (keys %digits)
{
next OUTER if ($_ == 0)  ($digits{$_} > 1)  ($n % $_);
}
printf "#%d is %d\n", ++$count, $n;
}
Hope that helps,
 [reply] [d/l] 
Re: Puzzle Time
by golux (Hermit) on Dec 23, 2012 at 05:03 UTC

The solution by Athanasius is already very nice and succinct; it can find all 548 solutions twice as fast (31 seconds instead of 65) if the tests are performed for each digit rather than after all digits have been hashed:
#!/usr/bin/perl w
use strict;
use warnings;
my $count = 0;
my $start = time;
OUTER:
for my $n (1 .. 987_654_321) {
my %digits;
map { next OUTER if !$_ or $digits{$_}++ or $n % $_ } split //, $n;
printf "#%d is %d\n", ++$count, $n;
($count == 548) and printf "Time: %d sec\n", time  $start;
}
say
substr+lc crypt(qw $i3 SI$),4,5
 [reply] [d/l] 
Re: Puzzle Time
by BrowserUk (Pope) on Dec 23, 2012 at 03:59 UTC

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
RIP Neil Armstrong
 [reply] [d/l] 
Re: Puzzle Time
by Anonymous Monk on Dec 23, 2012 at 02:57 UTC

 [reply] 
Re: Puzzle Time
by hdb (Monsignor) on Jun 25, 2013 at 14:58 UTC

Here are the answers for the number representations with bases 2 to 9 using brute force and Math::BaseCalc.
Base 2: 1
Base 3: 2
Base 4: 6
Base 5: 10
Base 6: 10
Base 7: 75
Base 8: 144
Base 9: 487
 [reply] [d/l] 
Re: Puzzle Time
by hdb (Monsignor) on Sep 20, 2013 at 08:02 UTC

 [reply] 

