Your skill will accomplishwhat the force of many cannot PerlMonks

### Puzzle Time

 on Dec 23, 2012 at 02:33 UTC Need Help??

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?

Replies are listed 'Best First'.
Re: Puzzle Time
by LanX (Cardinal) on Dec 23, 2012 at 03:47 UTC

(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

Cheers Rolf

¹) and of course their substrings from the start, thx Athanasius++ :)
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..\$pos-1, \$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..\$pos-1, \$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;

++LanX for an excellent answer (way faster than my brute force approach).

Allow me one nit-pick:

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

:-)

 Athanasius <°(((>< contra mundum Iustus alius egestas vitae, eros Piratica,

> Allow me one nit-pick:

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:

1. Evidently 0 is excluded!

2. Any number this long includes even ciphers. So 5 is excluded! But any number divisible by 5 and 2 must end with a 0

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

Cheers Rolf

¹) and therefor a 7 digit number excludes 4 to be divisible by 9.

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

First, some assumptions:

1. Numbers means natural numbers
2. Digits means digits in the decimal representation
3. Divisible by a digit means divisible without remainder
4. 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,

 Athanasius <°(((>< contra mundum Iustus alius egestas vitae, eros Piratica,

Re: Puzzle Time
by golux (Chaplain) 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
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.
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
Re: Puzzle Time
by hdb (Monsignor) on Sep 20, 2013 at 08:02 UTC
Re: Puzzle Time
by Anonymous Monk on Dec 23, 2012 at 02:57 UTC
42 -- hope you flunk it

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1010066]
Approved by McDarren
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2021-01-16 18:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (162 votes). Check out past polls.

Notices?