http://qs321.pair.com?node_id=1010066

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 (Saint) 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

    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 (Archbishop) 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 (Patriarch) 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

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