(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;
  }
}
[download]

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;
  }
[download]

with

  for my $pos (0..$#digits) {
    push @number, $digits[$pos];
    local @digits = @digits[0..$pos-1, $pos+1..$#digits];
    append_digit();
    pop @number;
  }
[download]

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;
[download]

++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
[download]

(That 1 extra sub call is the first one, when @number is empty.)

:-)

Read more... (1021 Bytes)



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

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;
}
[download]

Hope that helps,

#!/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;
}
[download]

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
[download]

Just seen this related post: 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? which asks for the largest such number.