Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

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 ( [id://503322]=note: print w/replies, xml ) Need Help??


in reply to 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?

The answer looks to be 1687392. Took my P4 1.7 w/384M about 3 seconds to run it.
use strict; use warnings; use Algorithm::Permute qw( permute ); use Math::Combinatorics qw( combine ); my @arr = reverse 1 .. 9; foreach my $n ( @arr ) { my $last = 0; foreach my $arr ( combine( $n, @arr ) ) { my @v = @$arr; permute { my $v = 1; $v *= $_ for @v; if ( (my $w = join('',@v)) % $v == 0 ) { print "$w\n"; $last = 1; } } @v; } last if $last; }

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?

Replies are listed 'Best First'.
Re^2: Puzzle: What is the largest integer ... (not "a longest")
by tye (Sage) on Oct 27, 2005 at 13:58 UTC

    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        

      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@/

        You can make it even faster by just dropping 5 from the list, since including a 5 excludes all even digits and restricts the solution length to 5 digits (which we quickly prove is too short). You can also make it faster by more efficiently skipping the redundant permutations. That's the nature of quick hacks. (:

        - 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
Re^2: 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 Tanktalus (Canon) on Oct 27, 2005 at 14:05 UTC

    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?
Re^2: 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 14:02 UTC

    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!
Re^2: 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 inman (Curate) on Oct 27, 2005 at 16:08 UTC
    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^2: 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 14:02 UTC
    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://503322]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2024-03-28 17:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found