Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

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?

by tphyahoo (Vicar)
on Oct 27, 2005 at 12:53 UTC ( #503317=perlquestion: print w/ replies, xml ) Need Help??
tphyahoo has asked for the wisdom of the Perl Monks concerning the following question:

Hi, I saw this puzzle mentioned at Does Visual studio Rot the Brain (linked to from slashdot today). The author solved it with c and I thought I'd give it a whack with perl. I didn't google around for solutions, on purpose, cause I wanted to do it myself.

My solution is below. It's been running for a bit, and still hasn't spit out an answer. I'm wondering if anybody out there has a faster way to do it, or if anyone would care to comment on my code.

One thought I had was, I don't really know threads but I wonder... could threads speed this up (obviously at the cost of using more computer resources).

I suspect there are other number theory tricks that could be applied here as well, but I don't know them either.

Well, Over and out monks :)

#What is the largest integer whose digits are all different (and do no +t include 0) that is divisible by each of its individual digits? #Requirements: # -- Integer # -- Digits all different (largest possible would be 987654321) # -- Divisible by each of individual digits # note: # this integer cannot contain the digit 5 if it also contains any e +ven digit, # because then the number would be divisible by 10, and the last di +git would be 0 # similarly, if the last digit is odd, it can't contain any other e +ven digit. use strict; use warnings; my $max_number = 987654321; #my $max_number = 10000; foreach ( 0 .. $max_number - 1 ) { my $test_number = $max_number - $_; print "number / 100000: " . $test_number/100000 . "\n" if $test_nu +mber % 100000 == 0; if ( passes($test_number) ) { print "$test_number passes!\n"; die; } } sub passes { my $test_number = shift() || die "no test number"; my @digits = split("", $test_number); my %seen; my $last_digit; #fail if see the same digit twice. foreach ( @digits ) { return 0 if $_ == 0; #fail if contains 0 return 0 if $seen{$_}; $seen{$_} = 1; } #set the last digit $last_digit = $digits[$#digits]; #fail if contains 5, and any other digit is even #or the last digit is 1, and any other digit is even if ( $seen{5} || $last_digit % 2 == 1 ) { for ( qw(2 4 6 8) ) { return 0 if $seen{$_}; } } for ( keys %seen ) { return 0 unless $test_number % $_ == 0 ; } return 1; }
UPDATE: Re the answers I've gotten so far, let me just say, I'm awed. Back to work...

Comment on 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?
Download Code
Re: 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?
by dragonchild (Archbishop) on Oct 27, 2005 at 13:34 UTC
    The answer looks to be 1687392. Took my P4 1.7 w/384M about 3 seconds to run it.

    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

      I'd be very surprised if that is the largest. I'm sure it is among the longest. But I'd bet money that the largest starts with a 9, and I'd bet a lot of money that it doesn't start with a 1. Update: I didn't notice it was only 7 digits until I wrote a short script that showed that there is no 9-digit answer, which surprised me -- but it's too early for clear thinking ATM :). I should have noted that I looked at the code and it doesn't appear to look for the largest answer, just the first answer that it finds (and it doesn't look at the possible answers from largest to smallest).

      Update2: And here is the quick hack showing the first block that failed to find any 9-digit answer and then an added block to find the answer. Note that this code searches the potential solutions in order from largest to smallest so it can stop as soon as one answer is found. It isn't particularly fast to run (taking 14 seconds), but it was very fast to write. (:

      use Algorithm::Loops qw( NextPermuteNum ); my @digs= (1..9); my @map; @map[1..9]= reverse 1..9; do { my $num= join '', @map[ @digs ]; for( 9, 8, 7, 5, 0 ) { die "$num\n" if ! $_; last if 0 != $num % $_; } } while( NextPermuteNum(@digs) ); my $prev= 0; for my $len ( reverse 1..8 ) { do { my $num= substr( join( '', @map[ @digs ] ), 0, $len ); if( $num != $prev ) { for( $num =~ /./g, 0 ) { die "$num\n" if ! $_; last if 0 != $num % $_; } } $prev= $num; } while( NextPermuteNum(@digs) ); }

      - tye        

        If it's the longest it's also the largest given the fact that (leading) zeroes are not allowed.

        OTOH: It's neither ;-)


        s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%
        +.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e
        tye,
        I borrowed Algorithm::Loops for the following brute-force approach:
        #!/usr/bin/perl use strict; use warnings; use Algorithm::Loops qw/NestedLoops NextPermute/; my $max = 1; my $next = GenPowerSet(9); while ( my @list = $next->() ) { PERMUTE: while ( NextPermute(@list) ) { my $num = join '', @list; next PERMUTE if $num < $max; for ( @list ) { next PERMUTE if $num % $_; } $max = $num if $num > $max; } } print $max; sub GenPowerSet { my $end = shift; return NestedLoops( [ [ 1..$end ], ( sub { [ $_+1 .. $end ] } ) x $end, ], { OnlyWhen => 1, }, ); }
        It came up with 9_867_312 in about 30 seconds.

        Cheers - L~R

        Note that you can cut the time in half or there abouts by adding just two simple checks; this version of your program runs in 6.1 seconds on my machine - the original without the initial 9-digit loop takes 13 seconds on my machine:

        use Algorithm::Loops qw( NextPermuteNum ); my @digs= (1..9); my @map; @map[1..9]= reverse 1..9; my $prev= 0; for my $len ( reverse 1..8 ) { do { my $num= substr( join( '', @map[ @digs ] ), 0, $len ); if( $num != $prev and $num !~ /[2468].*[13579]$/ and $num !~ / +5./) { for( $num =~ /./g, 0 ) { die "$num\n" if ! $_; last if 0 != $num % $_; } } $prev= $num; } while( NextPermuteNum(@digs) ); }

        Note that all I've done is add two regex tests - that you don't have any even digits if the last digit is odd, and that you never have a 5 in any but the last position.

        Reducing the search space is almost always a good idea.

        --
        @/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/; map{y/X_/\n /;print}map{pop@$_}@/for@/
      Hmm, I'm impressed by the code, and will be poring over those cool modules you used to try to understand what you did, but I finally gave in and googled around, and the answer appears to be more along the lines of what tye said.

      No it's not. Try my program. (which spits out all the answers in under 1.5 seconds)

      As proof that yours isn't the largest, consider 9231768 (also not the largest):

      $ bc -l bc 1.06 Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc. This is free software with ABSOLUTELY NO WARRANTY. For details type `warranty'. 9231768 / 8 1153971.00000000000000000000 9231768 / 9 1025752.00000000000000000000 9231768 / 7 1318824.00000000000000000000

      (The other digits follow as a consequence, or you can check them yourself)

      --
      @/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/; map{y/X_/\n /;print}map{pop@$_}@/for@/
        Clever simplification. If the number is divisible by 9,8,7, and 5, then it must also be divisible by 4,3,2, and 1. At first I thought you forgot about the divide by 5 test, but the I saw that your number doesn't contain 5. Clever!

      Some minor changes to your code results in 9867312. Took my P4 3.2 w/4GB about 9.3 seconds to run it.

        Ahh! I see the error. If I had both 4 and 2, but not 8, I was requiring the divisor to be a multiple of 8. Good catch!

        My criteria for good software:
        1. Does it work?
        2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
      I used Math::Combinatorics for both parts and a slight modification of the original test to get the answer (9867312) in less time than it takes to make a coffee...
      use strict; use warnings; use Math::Combinatorics; my @n = qw(1 2 3 4 6 7 8 9); my $found; foreach my $count (reverse (1..@n)) { my $combinat = Math::Combinatorics->new(count => $count, data => [ +@n],); my @comb; while (@comb = $combinat->next_combination()) { my @permu; my $permute = Math::Combinatorics->new(data => [@comb]); while (@permu = $permute->next_permutation()) { if (passes(@permu)) { print "@permu\n"; $found++; } } } exit if $found; } sub passes { my $test_number = join '', @_; for ( @_ ) { return 0 unless $test_number % $_ == 0 ; } return 1; }
      update I have modified my original code taking the 5 out of the possible numbers and paring down the test as much as possible. This now runs much faster.
Re: 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?
by fizbin (Chaplain) on Oct 27, 2005 at 13:57 UTC

    You appear to be making some of the mistakes the author said you needed to avoid - namely, you aren't really cutting down your search space.

    You're still performing all these checks on every single number; it would be better to only form the numbers that pass the checks mentioned in comments at the top, rather than to form all numbers and then reject those that fail. Not only that, but you're doing some stuff that doesn't make sense - you could replace your check code with this routine and it would still accept/reject the same numbers but would be tons faster:

    sub passes { my $test_number = shift() || die "no test number"; return 0 if ($test_number =~ /0/); # no zero return 0 if ($test_number =~ /(.).*\1/); # no dups for ( split(//,$test_number) ) { return 0 unless $test_number % $_ == 0 ; } return 1; }

    The check about 5 and even numbers is redundant by the point you do it, since if it has 5 and an even number then it either has a 0 or will be rejected by the divisibility test.

    So what you need to do is cut down on the number of possibilities to begin with. Say, something like this:

    use strict; sub pass_divcheck { # dups and 0s are assumed already handled my ($test_number) = @_; for ( split(//,$test_number) ) { return 0 unless $test_number % $_ == 0 ; } return 1; } sub form_number { my ($num, @remaining_digits) = @_; print "$num\n" if pass_divcheck($num); # When dealing with the three low-order digits, we can eliminate som +e # possibilities. E.g. Any number divisible by 4 must end in a 2-dig +it # number divisible by 4. my $ndig = length($num); if ($ndig == 1) { if ($num % 2 != 0) { @remaining_digits = grep($_ % 2, @remaining_digits); } # After we have one digit, either 5 is already used or we # can't use 5 later anyway @remaining_digits = grep($_ % 5, @remaining_digits); } elsif ($ndig == 2) { if ($num % 4 != 0) { @remaining_digits = grep($_ % 4, @remaining_digits); return if ($num =~ /[48]/); } } elsif ($ndig == 3) { if ($num % 8 != 0) { @remaining_digits = grep($_ % 8, @remaining_digits); } } my $maxp = $#remaining_digits; foreach my $p (0..$maxp) { form_number($remaining_digits[$p] . $num, @remaining_digits[0..$p-1], @remaining_digits[$p+1..$m +axp]); } } form_number('', (1..9));

    Note that this code won't print the answers out in numerical order. You'll have to sort them with something else.

    Update: Got rid of some extraneous code that doesn't add much since the answers don't get generated in numerical order anyway.

    --
    @/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/; map{y/X_/\n /;print}map{pop@$_}@/for@/

      I must say, I'm a bit surprised by the times other people are getting - as written above, my program takes about 1 second on my relatively underpowered laptop. (1.3 Ghz Pentium something, 512 MB ram)

      Even if you simplify my program down by removing both "elsif" blocks you're only up to about 2.5 seconds. Removing the "if ($ndig == 1)" block does bring you up to 34 seconds.

      --
      @/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/; map{y/X_/\n /;print}map{pop@$_}@/for@/
Re: 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?
by halley (Prior) on Oct 27, 2005 at 13:59 UTC
    I don't really know threads but I wonder... could threads speed this up?

    Threads don't magically enhance the power of a processor. If you only have one processor, and it's not sleeping while some device is slow to respond, then it can't suddenly get any more effective by spinning off multiple threads.

    Threads are useful for performance only when various parts of the process must sleep to await further data, but other parts of the process can continue to produce those data.

    Threads are useful for design because they let you segment out the problem into loosely-coupled components, and you don't have to design a time-slicing pump to accomplish it.

    --
    [ e d @ h a l l e y . c c ]

Re: 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?
by Skeeve (Vicar) on Oct 27, 2005 at 13:59 UTC
    My attempt:
    #!/usr/bin/perl use strict; use warnings; my @digits= qw(9 8 7 6 5 4 3 2 1); my $max= 0; permut('', @digits); print "Solution: $max\n"; sub permut { my ($s, @digits)= @_; my $i= scalar @digits; DIV: { { no warnings; last DIV if $s<$max; } foreach my $i (split //m,$s) { last DIV if $s % $i; } print "$s\n"; $max=$s; } if ($i) { while ($i--) { my $f= shift @digits; permut($s.$f, @digits); push(@digits, $f); } } }

    My solution and the time needed on a 900MHz Power PC G3 with 640MB and lot's of Java running in the background ;-) is:

    9867312
    real 2m14.144s
    user 0m32.100s
    sys 0m0.730s


    s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%
    +.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e
Re: 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?
by McDarren (Abbot) on Oct 27, 2005 at 14:07 UTC
    This looks like fun, so I've had a go :)
    Update:Well, I'd now like to stake my claim as having come up with the slowest solution that gets the correct answer, and here is my evidence:
    Trying 9867312...Success!! 9867312 / 9 = 1096368 9867312 / 8 = 1233414 9867312 / 6 = 1644552 9867312 / 7 = 1409616 9867312 / 3 = 3289104 9867312 / 1 = 9867312 9867312 / 2 = 4933656 real 384m53.120s user 382m59.960s sys 0m14.600s
    Almost 6.5 hours, I imagine that would have been quite impressive in the late 50's :D
Re: Puzzle: What is the largest integer yadda yadda yadda
by Roy Johnson (Monsignor) on Oct 27, 2005 at 15:11 UTC
    This is reasonably fast. It pre-generates the whole list of candidates, so it's surely not the best. The optimization of making 5 and even numbers mutually exclusive makes a huge difference.
    sub perms { return () unless @_; my ($car, @cdr) = @_; # All permutations that do not include car my @cdr_perm = perms(@cdr); # All permutations that include car my @car_perm = map { my $this_perm = $_; map { substr($this_perm, 0, $_) . $car . substr($this_perm, $_) } 0..length($this_perm) } (@cdr_perm); (@car_perm, @cdr_perm, $car); } my $max = 0; OUTER: for my $num (perms(reverse(1..4,6..9)), perms(9,7,5,3,1)) { next unless $num > $max; my @digits = split //, $num; $num % $_ > 0 and next OUTER for @digits; print "$num is divisible by all of @digits\n"; $max = $num; } print "Biggest found is $max\n";

    Caution: Contents may have been coded under pressure.
Re: Puzzle2: What is the largest /hex/ integer ...
by tye (Cardinal) on Oct 27, 2005 at 15:28 UTC

    Now solve it again in hex instead of base 10...

    Update2: And, in CODE tags inside of HTML comments is the output. The prior silly code that didn't realize that 5*2 isn't "10" in hex can also be grabbed via "select code-to-download".

    - tye        

Re: 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?
by hv (Parson) on Oct 27, 2005 at 15:57 UTC

    As noted by others, if the answer includes a 5 it must end in 5, which would preclude all of 2, 4, 6 and 8.

    However you may also spot that the digits 12346789 do not have a sum divisible by 3, so we must lose a 1, 4 or 7 to avoid losing all of 3, 6 and 9. Of those, only 4 leaves us a digit sum divisible by 9, so if a 7-digit solution is possible it must consist of 1236789.

    The gcd of those digits is 7*8*9 = 504, so we can start at 504 * int(9876321/504), and work down in steps of 504 until we find a multiple that consists of the right set of digits; as it turns out, just 17 such steps take us to the answer, and we could reasonably do that much by hand (though I didn't :).

    Hugo

      This was my take too. Since we start with an even number, and subtract an even number, we don't have to worry about ending in an odd digit. Since we know that all allowed digits will divide any multiple of 504, we don't even test for that.

      Here's the code I wrote (somewhat inspired by previous posts):

      #!/your/perl/here use strict; use warnings; use Benchmark::Timer; my $t = Benchmark::Timer->new(); $t->start(); my $c = 7*8*9; my $x = $c * int(9876321/$c); my $steps = 0; while ($x > 0) { next if $x =~ /[05]/; # no 0 or 5 next if $x =~ /([1-9]).*\1/; # no repeated digits last; } continue { $x -= $c; $steps++; } $t->stop(); print "$x ($steps steps)\n"; print $t->report(); __OUTPUT__ 9867312 (17 steps) 1 trial of _default (64us total)

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

Re: 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?
by thundergnat (Deacon) on Oct 27, 2005 at 19:48 UTC

    Arggh, I went to fix a bug and accidentally deleted the whole post.

    No need for modules

    use strict; use warnings; my $limit = 987654321; my $magic_num = 9 * 8 * 7; my $max = int ($limit / $magic_num); my $start = $max * $magic_num; for (0..$max - 1){ my $num = $start - $magic_num * $_; next if $num =~ /[05]/; next if $num =~ /(.).*\1/; die "$num\n" }
Re: 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?
by barrachois (Pilgrim) on Oct 28, 2005 at 19:47 UTC
    Many good replies above, but figured I'd try it for myself with the help of CPAN. Looks like it runs plenty fast enough with brute force alone. Fun.
    #!/usr/bin/perl -w # # See http://perlmonks.org/?node_id=503317, Oct 27 2005 # Jim Mahoney (mahoney@marlboro.edu) # use strict; use warnings; use Algorithm::FastPermute qw(permute); use Math::Combinatorics qw(); my $debug = 0; my $largest = 0; my @solutions; my $start_time = time(); print " What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual di +gits? Working... "; for my $n (reverse 1..9){ my $c = Math::Combinatorics->new( count=>$n, data=>[1..9] ); while (my @array = $c->next_combination){ permute { remember(@array) if is_solution(@array) } @array; } } @solutions = sort @solutions; print " Done in " . (time()-$start_time) . " seconds. Total number of solutions found is " . scalar(@solutions) . ". Largest is " . $solutions[-1] . ". "; sub remember { my @digits = @_; push @solutions, join('',@digits); } sub is_solution { my @digits = @_; my $number = 0+join('',@digits); for my $digit (@digits){ return 0 if $number % $digit != 0; } return 1; } __END__ $ ./n_digits_divide.pl What is the largest integer whose digits are all different (and do not include 0) that is divisible by each of its individual di +gits? Working... Done in 6 seconds. Total number of solutions found = 548. Largest found was 9867312.
Re: 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?
by Zed_Lopez (Chaplain) on Oct 28, 2005 at 20:02 UTC

    Mine is very slow, but short. I wrote it before reading the rest of the thread. I figured that we knew the answer had at most 8 characters, as it couldn't have both 2 and 5, so I counted down from the largest 8-different-digit number, guessing the answer would be closer to the top than the bottom. I realized that checking both 9, 8, 6 and their divisors was a waste, but guessed that the logic to exclude those would outweigh the extra modulos.

    LOOP: for (my $i = 98765432; $i > 0; $i--) { next if $i =~ /0/ or $i =~ /(\d)\d*\1/; $i % $_ and next LOOP for split '', $i; print "$i\n"; exit; }

    Updated: Re-worded the last sentence to correct a word-processing-o.

      This is based on what you did, except it prints out a status bar for "time remaining." Well, actually not a status bar. Just something along the lines of
      On 22000000. Minutes required: 0.718182 On 21000000. Minutes required: 0.683761 On 20000000. Minutes required: 0.645359 On 19000000. Minutes required: 0.611250 ........
      I think I liked yours the best because it was the closest in spirit to my, even slower, initial attempt. Cheers :)
      use strict; use warnings; my $start = 98765432; my $start_time = time; my $div = 1000000; my $max_tries = ( ( $start - ( $start % $div) ) / $div ); my $tries; LOOP: for (my $i = $start; $i > 0; $i--) { if ( $i % $div == 0 ) { $tries++; my $tries_remaining = $max_tries - $tries; #print "tries re +maining: $tries_remaining\n"; my $seconds_per_tries = ( time() - $start_time ) / $tries; my $estimated_minutes_to_completion = $seconds_per_tries * $tr +ies_remaining / 60; $estimated_minutes_to_completion = sprintf ( "%2f", $estimated +_minutes_to_completion ); print "On $i. Minutes required: $estimated_minutes_to_completi +on\n"; } next if $i =~ /0/ or $i =~ /(\d)\d*\1/; $i % $_ and next LOOP for split '', $i; print "$i\n"; exit; }
Re: 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?
by Anonymous Monk on Aug 23, 2008 at 13:40 UTC
    I got the 9867312 answer in about 10 minutes, using just thinking and a calculator. Sure, the brain is slower than the PC but probably the overall time to write the program and run it is more than 10 minutes :) Heuristics: - the number must have at most 9 digits - 5,2 mutually exclusive (0 in the end) - 5,4 mutually exclusive (0 in the end) - 5,8 mutually exclusive (0 in the end) => 5 probably not in - the remaining are 1 2 3 4 6 7 8 9 - 9 divides a number iff the sum of its digits is divisible by 9, same goes for 3 and 6 - the sum of these digits is 40, so if you take 4 out, it is 36, so we can have a number with 1 2 3 6 7 8 9 divisible by 1 3 6 9 independently of the digits' order - place 2 last so that the resulting number is divisible by 2 - you want it to be the largest, so first try 9876312 - it won't work, and after a few trials and some luck you get the right answer which is 9867312
Re: 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?
by Anonymous Monk on Sep 20, 2013 at 05:56 UTC
    The largest is 9867312. http://pastebin.com/print.php?i=zHraSQPF here is a pastebin with all the 7 digit ones

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://503317]
Approved by xorl
Front-paged by kwaping
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (10)
As of 2014-08-22 01:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (145 votes), past polls