Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
We don't bite newbies here... much
 
PerlMonks  

Puzzle Time

by Anonymous Monk
on Dec 23, 2012 at 02:33 UTC ( #1010066=perlquestion: print w/ replies, xml ) 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?

Comment on Puzzle Time
Re: Puzzle Time
by Anonymous Monk on Dec 23, 2012 at 02:57 UTC
    42 -- hope you flunk it
Re: Puzzle Time
by Athanasius (Prior) 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 LanX (Abbot) 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++ :)
      You are a legend, your help is greatly appreciated :)

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

      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;
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

Re: Puzzle Time
by golux (Pilgrim) 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 hdb (Parson) 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 (Parson) on Sep 20, 2013 at 08:02 UTC

Log In?
Username:
Password:

What's my password?
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 scrutinizing the Monastery: (3)
As of 2014-04-20 16:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (485 votes), past polls