Largest number divisible by its digits

From Rosetta Code
Largest number divisible by its digits is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

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.


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.


Also see



C[edit]

Base 10[edit]

The number can't contain 0 and 5, 0 is obvious, 5 because the number must end in 5 for it to be a multiple of that number and if that happens, all the even digits are ruled out which severely reduces the number's length since the other condition is that all digits must be unique. However, this means the number must be even and thus end only in 2,4,6,8. This speeds up the search by a factor of 2. The same approach when applied to hexadecimals takes a very long, long time.

 
/*Abhishek Ghosh, 8th November 2017*/
 
#include<stdio.h>
 
int main()
{
int num = 9876432,diff[] = {4,2,2,2},i,j,k=0;
char str[10];
 
start:snprintf(str,10,"%d",num);
 
for(i=0;str[i+1]!=00;i++){
if(str[i]=='0'||str[i]=='5'||num%(str[i]-'0')!=0){
num -= diff[k];
k = (k+1)%4;
goto start;
}
for(j=i+1;str[j]!=00;j++)
if(str[i]==str[j]){
num -= diff[k];
k = (k+1)%4;
goto start;
}
}
 
printf("Number found : %d",num);
return 0;
}
 

Output:

Number found : 9867312

Haskell[edit]

base 10[edit]

Using the analysis provided in the Perl 6 (base 10) example:

import Data.List (maximumBy, permutations, delete)
import Data.Ord (comparing)
 
unDigits :: [Int] -> Int
unDigits = foldl ((+) . (10 *)) 0
 
ds :: [Int]
ds = [1, 2, 3, 4, 6, 7, 8, 9] -- 0 (and thus 5) are both unworkable
 
lcmDigits :: Int
lcmDigits = foldr1 lcm ds -- 504
 
sevenDigits :: [[Int]]
sevenDigits = (`delete` ds) <$> [1, 4, 7] -- Dropping any one of these three
 
main :: IO ()
main =
print $
maximumBy
(comparing
(\x ->
if rem x lcmDigits == 0 -- Checking for divisibility by all digits
then x
else 0))
(unDigits <$> concat (permutations <$> sevenDigits))
Output:

Test run from inside the Atom editor:

9867312
[Finished in 0.395s]

base 16[edit]

First member of a descending sequence of multiples of 360360 that uses the full set of 15 digits when expressed in hex.

import Data.Set (fromList)
import Numeric (showHex)
 
lcmDigits :: Int
lcmDigits = foldr1 lcm [1 .. 15] -- 360360
 
upperLimit :: Int
upperLimit =
let allDigits = 0xfedcba987654321
in allDigits - rem allDigits lcmDigits
 
main :: IO ()
main =
print $
head
(filter ((15 ==) . length . fromList) $
(`showHex` []) <$> [upperLimit,upperLimit - lcmDigits .. 1])

Test run from inside the Atom editor:

"fedcb59726a1348"
[Finished in 2.319s]

Kotlin[edit]

Makes use of the Perl 6 entry's analysis:

base 10[edit]

// version 1.1.4-3
 
fun Int.divByAll(digits: List<Char>) = digits.all { this % (it - '0') == 0 }
 
fun main(args: Array<String>) {
val magic = 9 * 8 * 7
val high = 9876432 / magic * magic
for (i in high downTo magic step magic) {
if (i % 10 == 0) continue // can't end in '0'
val s = i.toString()
if ('0' in s || '5' in s) continue // can't contain '0' or '5'
val sd = s.toCharArray().distinct()
if (sd.size != s.length) continue // digits must be unique
if (i.divByAll(sd)) {
println("Largest decimal number is $i")
return
}
}
}
Output:
Largest decimal number is 9867312

base 16[edit]

// version 1.1.4-3
 
fun Long.divByAll(digits: List<Char>) =
digits.all { this % (if (it <= '9') it - '0' else it - 'W') == 0L }
 
fun main(args: Array<String>) {
val magic = 15L * 14 * 13 * 12 * 11
val high = 0xfedcba987654321L / magic * magic
for (i in high downTo magic step magic) {
if (i % 16 == 0L) continue // can't end in '0'
val s = i.toString(16) // always generates lower case a-f
if ('0' in s) continue // can't contain '0'
val sd = s.toCharArray().distinct()
if (sd.size != s.length) continue // digits must be unique
if (i.divByAll(sd)) {
println("Largest hex number is ${i.toString(16)}")
return
}
}
}
Output:
Largest hex number is fedcb59726a1348

Perl 6[edit]

Works with: Rakudo version 2017.08

Base 10[edit]

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. It is extremely unlikely be 1, since EVERY number is divisible by 1. Removing it reduces the number of digits available but doesn't gain anything as far as divisibility. It is unlikely to be 7 since 7 is prime and can't be made up of multiples of other numbers. Practically though, the code to accommodate these observations 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.

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
}
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[edit]

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

my $hex = 'FEDCBA987654321';        # largest possible hex number
my $magic-number = [lcm] 1 .. 15; # find least common multiple
my $div = :16($hex) div $magic-number * $magic-number;
 
for $div, { $_ - $magic-number } ... 0 -> $num { # Only generate multiples of the lcm
my $test = $num.base(16);
 
next if $test ~~ / 0 /; # skip numbers containing 0
next if $test ~~ / (.).*$0 /; # skip numbers with non unique digits
 
say "Found $test"; # Found a solution, display it
say ' ' x 12, 'In base 16', ' ' x 36, 'In base 10';
for $test.comb {
printf "%s / %s = %s |  %d / %2d = %19d\n",
$test, $_, ($num / :16($_)).base(16),
$num, :16($_), $num / :16($_);
}
last
}
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[edit]

base 10[edit]

This REXX version uses mostly 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 1st   if   statement does the bulk of the eliminations.

/*REXX program finds the largest (decimal) integer divisible by all its decimal digits. */
$=7 * 8 * 9 /*a number that it must be divisible by*/
start=9876432 % $ * $ /*the number to start the sieving from.*/
t=0 /*the number of divisibility trials. */
do #=start by -$ /*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? */
t=t+1 /*curiosity's sake, track # of trials. */
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*/
/* [↓] superfluous, but check anyways.*/
do v=1 for length(#) /*verify the # is divisible by all digs*/
if # // substr(#,v,1) \==0 then iterate #
end /*v*/ /* [↑] ¬divisible? Then keep looking.*/
leave /*we found a number, so go display it. */
end /*#*/
 
say 'found ' # " (in " t ' trials)' /*stick a fork in it, we're all done. */
output:

Timing note:   execution time is under   1/2   millisecond   (essentially not measurable in the granularity of the REXX timer under Microsoft Windows).

found  9867312   (in  11  trials)

base 16[edit]

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

Note that   15*14*13*12*11   is the same as   13*11*9*8*7*5.

/*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= 'fedcba987654321' /*biggest hexadecimal number possible. */
bigN=x2d(bigH) /* " " " in decimal*/
$=15 * 14 * 13 * 12 * 11 /*a number that it must be divisible by*/
start=bigN % $ * $ /*the number to start the sieving from.*/
t=0 /*the number of divisibility trials. */
do #=start by -$ /*search from largest poss. # downwards*/
if # // $ \==0 then iterate /*Not divisible? Then keep searching.*/
h=d2x(#) /*convert decimal number to hexadecimal*/
if pos(0, h) \==0 then iterate /*does hexadecimal number contain a 0? */
t=t+1 /*curiosity's sake, track # of trials. */
do j=1 for length(h) - 1 /*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*/
 
do v=1 for length(h) /*verify the # is divisible by all digs*/
if # // x2d(substr(h,v,1)) \==0 then iterate #
end /*v*/ /* [↑] ¬divisible? Then keep looking.*/
leave /*we found a number, so go display it. */
end /*#*/
 
say 'found ' h " (in " t ' trials)' /*stick a fork in it, we're all done. */
output:
found  FEDCB59726A1348   (in  287747  trials)

Ring[edit]

 
# Project : Largest number divisible by its digits
# Date  : 2017/09/22
# Author  : Gal Zsolt (~ CalmoSoft ~)
# Email  : <[email protected]il.com>
 
for n = 9867000 to 9867400
numbers = list(9)
for t=1 to 9
numbers[t] = 0
next
flag = 1
flag2 = 1
flag3 = 1
str=string(n)
for m=1 to len(str)
if number(str[m]) > 0
numbers[number(str[m])] = numbers[number(str[m])] + 1
else
flag2 = 0
ok
next
if flag2 = 1
for p=1 to 9
if numbers[p] = 0 or numbers[p] = 1
else
flag = 0
ok
next
if flag = 1
for x=1 to len(str)
if n%(number(str[x])) != 0
flag3 = 0
ok
next
if flag3 = 1
see n + nl
ok
ok
ok
next
 

Output:

9867312

zkl[edit]

base 10[edit]

Translation of: Perl6
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:=test.toString();
if(text.holds("0","5")) continue; # skip numbers containing 0 or 5
if(text.unique().len()!=text.len()) 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;
}
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[edit]

Translation of: Haskell
const bigN=0xfedcba987654321; // biggest hexadecimal number possible.
lcm:=lcmNs([1..15]); // 360360, smallest # that will divide answer
upperLimit:=bigN - bigN%lcm; // start at a mulitple of whatever the answer is
 
foreach test in ([upperLimit..1,-lcm]){
text:=test.toString(16);
if(15!=text.unique().len()) continue;
println(text);
break;
}
fcn lcmNs(ns){ ns.reduce(fcn(m,n){ (m*n).abs()/m.gcd(n) }) }
Output:
fedcb59726a1348