How to resolve the algorithm Largest number divisible by its digits step by step in the Perl programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Largest number divisible by its digits step by step in the Perl programming language

Table of Contents

Problem Statement

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

These numbers are also known as   Lynch-Bell numbers,   numbers   n   such that the (base ten) digits are all different (and do not include zero)   and   n   is divisible by each of its individual digits.

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 ten 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.)

Do the same thing for hexadecimal.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Largest number divisible by its digits step by step in the Perl programming language

Source code in the perl programming language

my $step = 9 * 8 * 7;                               # 504, interval between tests

my $initial = int(9876432 / $step) * $step;         # largest 7 digit multiple of 504 < 9876432

for($test = $initial; $test > 0 ; $test -= $step) { # decrement by 504
    next if $test =~ /[05]/;                        # skip numbers containing 0 or 5
    next if $test =~ /(.).*\1/;                     # skip numbers with non unique digits

    for (split '', $test) {                         # skip numbers that don't divide evenly by all digits
        next unless ($test / $_) % 1;
    }

    printf "Found $test after %d steps\n", ($initial-$test)/$step;
    for (split '', $test) {
       printf "%s / %s = %s\n", $test, $_, $test / $_;
    }
    last
}


use bigint;  # Very slow, but consistent results even with 32-bit Perl

my $hex = 'FEDCBA987654321';                      # largest possible hex number
$step = Math::BigInt::blcm(1..15);
$initial = int(hex($hex) / $step) * $step;

for($num = $initial; $num > 0 ; $num -= $step) {  # decrement by lcm

    my $test = sprintf '%x', $num;
    next if $test =~ /0/;                         # skip numbers containing 0
    next if $test =~ /(.).*\1/;                   # skip numbers with non unique digits

    push @res, sprintf "Found $test after %d steps\n", ($initial-$num)/$step;
    push @res, ' 'x12 . 'In base 16' . ' 'x36 . 'In base 10';
    for (split '', $test) {
        push @res, sprintf "%s / %s = %x  |  %d / %2d = %19d",
          $test, $_, $num / hex($_),
          $num, hex($_), $num / hex($_);
    }
    last
}

print join "\n", @res;


  

You may also check:How to resolve the algorithm Multifactorial step by step in the Erlang programming language
You may also check:How to resolve the algorithm Literals/Integer step by step in the jq programming language
You may also check:How to resolve the algorithm Order disjoint list items step by step in the Factor programming language
You may also check:How to resolve the algorithm Display a linear combination step by step in the RPL programming language
You may also check:How to resolve the algorithm Generate lower case ASCII alphabet step by step in the Icon and Unicon programming language