Largest number divisible by its digits: Difference between revisions

Content added Content deleted

Inline

Revision as of 14:22, 2 September 2017

Task

Find the largest base 10 integer whose digits are all different, that is evenly divisible by each of its individual digits.

For example: 135 is evenly divisible by 1, 3 and 5.

Note that the digit zero (0) can not be in the number as integer division by zero is undefined. The digits must all be unique so a base 10 number will have at most 9 digits.

Feel free to use analytics and clever algorithms to reduce the search space your example needs to visit, but it must do an actual search. (Don't just feed it the answer and verify it is correct.)

Stretch goal

Do the same thing for hexadecimal.

Perl 6

Works with: Rakudo version 2017.08

Base 10

The number can not have a zero in it, that implies that it can not have a 5 either since if it has a 5, it must be divisible by 5, but the only numbers divisible by 5 end in 5 or 0. It can't be zero, and if it is odd, it can't be divisible by 2, 4, 6 or 8. So that leaves 98764321 as possible digits the number can contain. The sum of those 8 digits is not divisible by three so the largest possible integer must use no more than 7 of them (since 3, 6 and 9 would be eliminated). Strictly by removing possibilities that cannot possibly work we are down to at most 7 digits.

We can deduce that the digit that won't get used is one of 1, 4, or 7 since those are the only ones where the removal will yield a sum divisible by 3, but practically, the code to accommodate that is longer running and more complex than just brute-forcing it from here.

In order to accommodate the most possible digits, the number must be divisible by 7, 8 and 9. If that is true then it is automatically divisible by 2, 3, 4, & 6 as they can all be made from the combinations of multiples of 2 and 3 which are present in 8 & 9; so we'll only bother to check multiples of 9 * 8 * 7 or 504.

All these optimizations get the run time to well under 1 second.

<lang perl6>my $magic-number = 9 * 8 * 7; # 504

my $div = 9876432 div $magic-number * $magic-number; # largest 7 digit multiple of 504 < 9876432

for $div, { $_ - $magic-number } ... * -> $test { # only generate multiples of 504

   next if $test ~~ / <[05]> /;                     # skip numbers containing 0 or 5
   next if $test ~~ / (.).*$0 /;                    # skip numbers with non unique digits
   next unless all $test.comb.map: $test %% *;      # skip numbers that don't divide evenly by all digits

   say "Found $test";                               # Found a solution, display it
   for $test.comb {
       printf "%s / %s = %s\n", $test, $_, $test / $_;
   }
   last

}</lang>

Output:

Found 9867312
9867312 / 9 = 1096368
9867312 / 8 = 1233414
9867312 / 6 = 1644552
9867312 / 7 = 1409616
9867312 / 3 = 3289104
9867312 / 1 = 9867312
9867312 / 2 = 4933656

Base 16

There are fewer analytical optimizations available for base 16. Other than 0, no digits can be ruled out so a much larger space must be searched. Rather than using a magic number to try to filter the search space and then check for uniqueness, we'll just generate unique permutations and check them for divisibility. In practice this seems to be much faster. We'll start at the largest possible permutation (FEDCBA987654321) and work down so as soon as we find a solution, we know it is the solution.

To verify that a number is divisible by 1 through 15, we only need to check 5, 7, 8, 9, 11, & 13.

<lang perl6>my $hex = 'FEDCBA987654321'; # largest possible hex number

for $hex.comb.permutations -> @test {

   my $test = [~] @test;
   my $num = $test.parse-base(16);

   next unless $num +& 8;                        # extremely cheap pre-check for divisibility by 8
   next unless all (5,7,9,11,13).map: $num %% *; # check divisibility by other factors

   say "Found $test";                            # Found a solution, display it
   say ' ' x 12, 'In base 16', ' ' x 36, 'In base 10';
   for @test {
       printf "%s / %s = %s  |  %d / %2d = %19d\n",
         $test, $_, ($num / :16($_)).base(16),
         $num, :16($_), $num / :16($_);
   }
   last

}</lang>

Output:

Found FEDCB59726A1348
            In base 16                                    In base 10
FEDCB59726A1348 / F = 10FDA5B4BE4F038  |  1147797065081426760 / 15 =   76519804338761784
FEDCB59726A1348 / E = 1234561D150B83C  |  1147797065081426760 / 14 =   81985504648673340
FEDCB59726A1348 / D = 139AD2E43E0C668  |  1147797065081426760 / 13 =   88292081929340520
FEDCB59726A1348 / C = 153D0F21EDE2C46  |  1147797065081426760 / 12 =   95649755423452230
FEDCB59726A1348 / B = 172B56538F25ED8  |  1147797065081426760 / 11 =  104345187734675160
FEDCB59726A1348 / 5 = 32F8F11E3AED0A8  |  1147797065081426760 /  5 =  229559413016285352
FEDCB59726A1348 / 9 = 1C5169829283B08  |  1147797065081426760 /  9 =  127533007231269640
FEDCB59726A1348 / 7 = 2468AC3A2A17078  |  1147797065081426760 /  7 =  163971009297346680
FEDCB59726A1348 / 2 = 7F6E5ACB93509A4  |  1147797065081426760 /  2 =  573898532540713380
FEDCB59726A1348 / 6 = 2A7A1E43DBC588C  |  1147797065081426760 /  6 =  191299510846904460
FEDCB59726A1348 / A = 197C788F1D76854  |  1147797065081426760 / 10 =  114779706508142676
FEDCB59726A1348 / 1 = FEDCB59726A1348  |  1147797065081426760 /  1 = 1147797065081426760
FEDCB59726A1348 / 3 = 54F43C87B78B118  |  1147797065081426760 /  3 =  382599021693808920
FEDCB59726A1348 / 4 = 3FB72D65C9A84D2  |  1147797065081426760 /  4 =  286949266270356690
FEDCB59726A1348 / 8 = 1FDB96B2E4D4269  |  1147797065081426760 /  8 =  143474633135178345

REXX

base 10

This REXX version uses the same logic and deductions that the Perl 6 example does, but it performs the tests in a different order for maximum speed.

The inner do loop is only executed a score of times; the 1^st if statement does the bulk of the eliminations. <lang rexx>/*REXX program finds the largest (decimal) integer divisible by all its decimal digits. */ $=7*8*9 /*a number that it must be divisible by*/

       do #=9876432  by -2                      /*search from largest number downwards.*/
       if #//$\==0                 then iterate /*Not divisible?   Then keep searching.*/
       if verify(50, #, 'M') \==0  then iterate /*does it contain a  five  or a  zero? */
              do j=1  for length(#-1)           /*look for a possible duplicated digit.*/
              if pos( substr(#, j, 1), #, j+1) \== 0  then iterate #
              end  /*j*/                        /* [↑]  Not unique? Then keep searching*/
       leave                                    /*we found a number, so go display it. */
       end   /*#*/

say 'found' # /*stick a fork in it, we're all done. */</lang>

output:

Timing note: execution time is under ¹/₂ millisecond (essentially not measurable in the granularity of the REXX timer).

found 9867312

base 16

The "magic" number was expanded to handle hexadecimal numbers.

The bigH (below) was initially fedcba987654321, but it can't be an odd number,
so the next lower hex number is fedcba987654320, but it can't have a zero digit,
so the next lower hex number is fedcba98765431f, but it can't be an odd number,
so the next lower hex number is fedcba98765431e. <lang rexx>/*REXX program finds the largest hexadecimal integer divisible by all its hex digits. */ numeric digits 20 /*be able to handle the large hex nums.*/ bigH= 'fedcba98765431e' /*biggest hexadecimal number possible. */ bigN=x2d(bigH); L=length(bigN) - 1 /* " " " in decimal*/ $=15*14*13*12*11 /*a number that it must be divisible by*/

                do #=bigN  by -2                /*search from largest number downwards.*/
                if #//$\==0        then iterate /*Not divisible?   Then keep searching.*/
                h=d2x(#)
                if pos(0, h) \==0  then iterate /*does hexadecimal number contain a 0? */
                       do j=1  for L            /*look for a possible duplicated digit.*/
                       if pos( substr(h, j, 1), h, j+1) \== 0   then iterate #
                       end  /*j*/               /* [↑]  Not unique? Then keep searching*/
                leave                           /*we found a number, so go display it. */
                end   /*#*/

say 'found' h /*stick a fork in it, we're all done. */</lang>

zkl

base 10

Translation of: Perl6

<lang zkl>const magic_number=9*8*7; # 504 const div=9876432 / magic_number * magic_number; #largest 7 digit multiple of 504 < 9876432

foreach test in ([div..0,-magic_number]){

  text,sz := test.toString(),text.len();
  if(text.holds("0") or text.holds("5")) continue; # skip numbers containing 0 or 5
  if(text.unique().len()!=sz)            continue; # skip numbers with non unique digits
  if(test.split().filter1('%.fp(test)))  continue; # skip numbers that don't divide evenly by all digits

  println("Found ",test); # Found a solution, display it
  foreach d in (test.split()){
     println("%s / %s = %s".fmt(test,d, test/d));
  }
  break;

}</lang>

Output:

Found 9867312
9867312 / 9 = 1096368
9867312 / 8 = 1233414
9867312 / 6 = 1644552
9867312 / 7 = 1409616
9867312 / 3 = 3289104
9867312 / 1 = 9867312
9867312 / 2 = 4933656