Largest number divisible by its digits: Difference between revisions
Largest number divisible by its digits (view source)
Revision as of 09:56, 15 December 2023
, 5 months ago→{{header|Wren}}: Changed to Wren S/H
m (→base 10: crunch) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (171 intermediate revisions by 41 users not shown) | |||
Line 1:
[[Category:Puzzles]]
{{task}}
;Task:
Find the largest base 10 integer whose digits are all different,
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.
;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 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.)
;Stretch goal:
Do the same thing for hexadecimal.
;Related tasks:
:* [https://rosettacode.org/wiki/Gapful_numbers gapful numbers].
:* [https://rosettacode.org/wiki/Palindromic_gapful_numbers palindromic gapful numbers].
;Also see:
:* The OEIS sequence: [http://oeis.org/A115569 A115569: Lynch-Bell numbers].
<br><br>
=={{header|
===Base 10===
{{trans|C++}}
<syntaxhighlight lang="11l">F check_dec(num)
Set[Int] st
L(c) String(num)
V d = Int(c)
I d == 0 | num % d != 0 | d C st
R 0B
st.add(d)
R 1B
L(i) (98764321 .< 0).step(-1)
I check_dec(i)
print(i)
L.break</syntaxhighlight>
{{out}}
<pre>
9867312
</pre>
=={{header|360 Assembly}}==
For maximum compatibility, this program uses only the basic instruction set.
The program uses also HLASM structured macros (DO,ENDDO,IF,ELSE,ENDIF) for readability and one ASSIST/360 macros XPRNT) to keep the code as short as possible.
===Base 10===
<syntaxhighlight lang="360asm">* Largest number divisible by its digits - base10 - 05/05/2020
LANUDIDO CSECT
USING LANUDIDO,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
L R6,KM i=km
DO WHILE=(C,R6,GE,=F'1') do i=km to 1 by -ks
CVD R6,DBLI binary to packed decimal
MVC CI,MAK load mask for edit
EDMK CI,DBLI+2 ci=cstr(i)
S R1,=A(CI) number of blanks
LA R2,L'CI length(ci)
SR R2,R1 length of the number
ST R2,LCI lci=length(ci)
MVC CIL,=CL12' ' cil=' '
LA R4,CI @ci
AR R4,R1 @ci[k]
LA R3,CIL @cil
LR R5,R2 length(ci)
BCTR R5,0 ~
EX R5,MVCR3R4 cil=ltrim(ci)
LA R8,CIL @ci
LA R7,1 j=1
DO WHILE=(C,R7,LE,LCI) do j=1 to length(ci)
CLI 0(R8),C'5' if ci[j]='5'
BE ITERI then cycle i ! 5 impossible
CLI 0(R8),C'0' if ci[j]='0'
BE ITERI then cycle i ! 0 impossible
LA R8,1(R8) @ci++
LA R7,1(R7) j++
ENDDO , enddo j
L R2,LCI length(ci)
BCTR R2,0 length(ci)-1
LA R7,1 j=1
DO WHILE=(CR,R7,LE,R2) do j=1 to length(ci)-1
LA R3,CIL-1 @cil
AR R3,R7 @cil[j]
IC R1,0(R3) cil[j]
STC R1,CK ck=substr(cil,j,1)
SR R0,R0 index=0
LR R8,R7 j
LA R8,1(R8) k=j+1
LA R9,CIL @ci
AR R9,R8 +i
BCTR R9,0 -1
DO WHILE=(C,R8,LE,LCI) do k=j+1 to length(ci)
IF CLC,0(0,R9),EQ,CK THEN if substr(ci,k,1)=ck then
LR R0,R8 index=k
B EXITK exit do k
ENDIF , endif
LA R9,1(R9) @ci++
LA R8,1(R8) k++
ENDDO , enddo k
EXITK LTR R0,R0 if index(ci,ck,j+1)<>0
BNZ ITERI then cycle i ! no dup digit
LA R7,1(R7) j++
ENDDO , enddo j
LA R7,1 j=1
DO WHILE=(C,R7,LE,LCI) do j=1 to length(ci)
LA R3,CIL-1 @cil
AR R3,R7 @cil[j]
IC R1,0(R3) cil[j]
SLL R1,28 ~
SRL R1,28 kk=int(substr(ci,j,1))
XR R4,R4 ~
LR R5,R6 i
DR R4,R1 r5=i/kk r4=mod(i,kk)
LTR R4,R4 if mod(i,kk)<>0
BNZ ITERI then cycle i ! div by all digit
LA R7,1(R7) j++
ENDDO , enddo j
B EXITI exit do i ! found
ITERI S R6,KS i-=ks
ENDDO , enddo i
EXITI XPRNT CIL,L'CIL print cil
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
MVCR3R4 MVC 0(0,R3),0(R4) move: %R3 <- %R4
KS DC F'504' ks=504=7*8*9 magic number
KM DC F'9876384' km=9876384 mod(km,ks)=0
DBLI DS PL8 double word 15num
MAK DC X'402020202020202020202020' mask CL12 11num
CI DS CL12 12num - i right justify
CIL DS CL12 12num - i left justify
LCI DS F length(i)
CK DS C ck
REGEQU
END LANUDIDO </syntaxhighlight>
{{out}}
<pre>
9867312
</pre>
=={{header|ALGOL 68}}==
Base 10.
{{Trans|Kotlin}}... largely
<syntaxhighlight lang="algol68">BEGIN # find the largest decimal integer with unique digits, divisible by its digits #
INT magic = 9 * 8 * 7; # see analysis in the Raku sample #
INT high = ( 9876432 OVER magic ) * magic;
BOOL found := FALSE;
FOR i FROM high BY - magic TO magic WHILE NOT found DO
IF INT d1 = i MOD 10;
d1 = 0
THEN SKIP # can't end in '0' #
ELIF [ 0 : 9 ]BOOL digits :=
[]BOOL( FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE )[ @ 0 ];
BOOL unique := TRUE;
INT v := i OVER 10;
digits[ d1 ] := TRUE;
WHILE v > 0 AND unique DO
INT d = v MOD 10;
v OVERAB 10;
unique := NOT digits[ d ];
digits[ d ] := TRUE
OD;
NOT unique
THEN SKIP # digits must be unique #
ELIF digits[ 0 ] OR digits[ 5 ]
THEN SKIP # can't contain 0 or 5 #
ELIF found := TRUE;
FOR d TO UPB digits WHILE found DO
IF digits[ d ] THEN found := i MOD d = 0 FI
OD;
found
THEN
print( ( "Largest decimal number is ", whole( i, 0 ), newline ) )
FI
OD
END</syntaxhighlight>
{{out}}
<pre>
Largest decimal number is 9867312
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">lynchBell?: function [num][
hset: new []
loop digits num 'd [
if d=0 -> return false
if or? [0 <> mod num d]
[contains? hset d] -> return false
'hset ++ d
unique 'hset
]
return true
]
Magic: 9 * 8 * 7
High: ((from.hex "9876432") / Magic) * Magic
loop range High .step: Magic Magic 'n [
if lynchBell? n [
print n
break
]
]</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|AWK}}==
===Base 10===
Ruling out 9- and 8-digit numbers (see first paragraph in the Raku example), we are looking for 7-digit numbers. In order to be a solution such a number has to be divisible by 12 = 2*2*3, because its digits must contain at least 2 of the numbers 2, 4, 6, 8 (leading to a factor of 2*2) and its digits must contain at least one of the numbers 3, 6, 9 (leading to a factor of 3).
The program does a brute force search, starting with the largest possible 7-digit number and iterates over all smaller numbers divisible by 12. It checks for each iteration, if the number in question consists of different digits and is divisible by those digits.
<syntaxhighlight lang="awk"># Usage: gawk -f LARGEST_NUMBER_DIVISIBLE_BY_ITS_DIGITS_10.AWK
BEGIN {
base = 10
comdiv = 12
startn = 9876543
stopn = 1000000
solve(startn, stopn)
}
function solve(startn, stopn, n, d) {
for (n = startn - startn % comdiv; n > stopn; n -= comdiv) {
if (hasuniqedigits(n)) {
# Check divisibility of n by all its digits
for (d = 2; d < base; d++) {
if ((dcount[d]) && (n % d)) {
break
}
}
if (d == base) {
printf("%d\n", n)
return
}
}
}
}
function hasuniqedigits(n, d) {
# Returns 1, if n consists of unique digits in range 1..(base-1)
# The array dcount stores the count (up to 1) of those digits
for (d = 1; d < base; d++)
dcount[d] = 0
while (n) {
d = n % base
if ((d == 0) || (++dcount[d] > 1))
return 0
n = int(n / base)
}
return 1
}</syntaxhighlight>
{{out}}
<pre>
9867312
</pre>
===Base 16===
In the hexadecimal case we cannot rule out 15-digit numbers, thus all digits from 1 to f (hex) are present. The number has to be divisible by all its digits, therefore it has to be divisible by the least common multiple of the numbers 1, 2, 3, ..., 15 (360360).
AWK does not support arbitrary long integers, so we have to use an array of digits for its representation. It makes use of functions hexmod (modulus) and hexsub (subtraction), which act on an array.
The program does a brute force search, starting with the largest possible 15-digit number and iterates over all smaller numbers divisible by 360360. It checks for each iteration, if the number in question consists of different digits (by construction it is then also divisible by its digits).
<syntaxhighlight lang="awk"># Usage: GAWK -f LARGEST_NUMBER_DIVISIBLE_BY_ITS_DIGITS_16.AWK
BEGIN {
base = 16
size = 15
# startn = FEDCB A9876 54321 (hex)
for (i = 1; i <= size; i++) {
startn[i] = i
}
comdiv = 360360 # lcm(1..15)
solve(startn)
}
function solve(n, r, i) {
r = hexmod(n, comdiv)
hexsub(n, r)
while (n[size] > 0) {
if (hasuniqedigits(n)) {
for (i = size; i > 0; i--)
printf("%0x", n[i])
printf("\n")
return
}
hexsub(n, comdiv)
}
}
function hasuniqedigits(n, d, i) {
# Return 1, if n is an array of unique digits in range 1..(base-1)
# The array dcount stores the count (up to 1) of those digits
for (d = 1; d < base; d++)
dcount[d] = 0
for (i = 1; i <= size; i++) {
d = n[i]
if ((d == 0) || (++dcount[d] > 1))
return 0
}
return 1
}
function hexmod(n, k, i, r) {
# Return n mod k, where n is an array and k is a number
for (i = size; i > 0; i--) {
r = (r * base + n[i]) % k
}
return r
}
function hexsub(n, m) {
# Calculate n = n - m, where n is an array and m is a number
for (i = 1; m && (i <= size); i++) {
n[i] -= m % base
m = int(m / base)
if (n[i] < 0) {
n[i] += base
m++
}
}
}</syntaxhighlight>
{{out}}
<pre>
fedcb59726a1348
</pre>
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
===base 10===
<syntaxhighlight lang="basic256">
arraybase 1
for n = 9867000 to 9867400
dim numbers(9) fill 0
flag = true : flag2 = true : flag3 = true
cadena = string(n)
for m = 1 to length(cadena)
if int(mid(cadena,m,1)) > 0 then
numbers[int(mid(cadena,m,1))] += 1
else
flag2 = false
end if
next m
if flag2 = true then
for p = 1 to 9
if not (numbers[p] = 0 or numbers[p] = 1) then flag = false
next p
if flag = true then
for x = 1 to length(cadena)
if n mod (int(mid(cadena,x,1))) <> 0 then flag3 = false
next x
if flag3 = true then print "El mayor número decimal es: "; n
end if
end if
next n
end
</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
=={{header|C}}==
===Base 10===
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.
<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>
Output:
<pre>
Number found : 9867312
</pre>
===Base 16===
{{trans|Kotlin}}
<syntaxhighlight lang="c">#include<stdio.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
typedef char bool;
typedef unsigned long long uint64;
bool div_by_all(uint64 num, char digits[], int len) {
int i, d;
for (i = 0; i < len; ++i) {
d = digits[i];
d = (d <= '9') ? d - '0' : d - 'W';
if (num % d != 0) return FALSE;
}
return TRUE;
}
int main() {
uint64 i, magic = 15 * 14 * 13 * 12 * 11;
uint64 high = 0xfedcba987654321 / magic * magic;
int j, len;
char c, *p, s[17], sd[16], found[16];
for (i = high; i >= magic; i -= magic) {
if (i % 16 == 0) continue; // can't end in '0'
snprintf(s, 17, "%llx", i); // always generates lower case a-f
if (strchr(s, '0') - s >= 0) continue; // can't contain '0'
for (j = 0; j < 16; ++j) found[j] = FALSE;
len = 0;
for (p = s; *p; ++p) {
if (*p <= '9') {
c = *p - '0';
} else {
c = *p - 87;
}
if (!found[c]) {
found[c] = TRUE;
sd[len++] = *p;
}
}
if (len != p - s) {
continue; // digits must be unique
}
if (div_by_all(i, sd, len)) {
printf("Largest hex number is %llx\n", i);
break;
}
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>
Largest hex number is fedcb59726a1348
</pre>
=={{header|C sharp|C#}}==
=== Both ===
Skips unnecessary numbers, sorts the digits of the tested number (which makes it simple to find zeros and repeated digits). Stops as soon as it finds the first (highest) one. Determines the skip amount by finding the least common multiple of the product of the digits utilized. Base 10 uses all digits but digit five and digit zero, base 16 uses all digits but digit zero. Note that digit five is omitted in base 10 because it would eliminate the even numbers. The eight digits remaining cannot be evenly divided by three, so the base 10 result must have seven digits or less.
<syntaxhighlight lang="csharp">using System;
class Program {
static int gcd(int a, int b) { return b > 0 ? gcd(b, a % b) : a; }
// returns least common multiple of digits of x in base b
static int lcmd(long x, int b) {
int r = (int)(x % b), a; x /= b; while (x > 0) {
r = (r * (a = (int)(x % b))) / gcd(r, a); x /= b; } return r; }
static void Main(string[] args) {
var sw = System.Diagnostics.Stopwatch.StartNew();
long mx = 987654321; // all digits except zero
mx = 98764321; // omitting 5 because even numbers are lost
mx /= 10; // 7 digs because 8 digs won't divide by 3
long skip = lcmd(mx, 10), i; bool nDup;
for (i = mx - mx % skip; ; i -= skip) {
var s = i.ToString().ToCharArray(); Array.Sort(s);
if (s[0] == '0') continue; // no zeros
nDup = true; // checking for duplicate digits or digit five
for (int j = 0, k = 1; k < s.Length; j = k++)
if (s[j] == s[k] || s[k] == '5') { nDup = false; break; }
if (nDup) break; } sw.Stop(); // found it
Console.Write("base 10 = {0} in {1} μs\n", i,
1000 * sw.Elapsed.TotalMilliseconds);
sw.Restart();
mx = 0xfedcba987654321; // all 15 digits used, no zero
skip = lcmd(mx >> 4, 16); // digit one implied, so omit it
for (i = mx - mx % skip; ; i -= skip) {
var s = i.ToString("x").ToCharArray(); Array.Sort(s);
if (s[0] == '0') continue; // no zeros
nDup = true; // checking for duplicate digits
for (int j = 0, k = 1; k < s.Length; j = k++)
if (s[j] == s[k]) { nDup = false; break; }
if (nDup) break; } sw.Stop(); // found it
Console.Write("base 16 = {0} in {1} ms", i.ToString("x"),
sw.Elapsed.TotalMilliseconds); } }</syntaxhighlight>
{{out}}Timing from Tio.run:
<pre>base 10 = 9867312 in 349.1 μs
base 16 = fedcb59726a1348 in 291.6791 ms</pre>
=== Both using Linq ===
For both bases, the digit 0 is unsuitable, because when you divide by zero, the result isn't a number.
For base 10, digit five is unsuitable for the following reason. Five can only be the last digit, because the result must be divisible by five. Since five is an odd number, all the even numbers must be removed. This means the maximum number of digits would only be four digits. (9735, 9315, or another combination ending in five, five digit combinations of 97315 are invalid because none of them are divisible by three). If an even number were to be the last digit, it could only be zero (to keep the divisible-by-five), and zero has already been kicked out.
This leaves 98764321. However, when all eight of those digits are in the same number, in any combination, that number cannot be evenly divided by three. Either digit one, digit four, or digit seven must be removed, leaving a seven digit number that is evenly divided by three.
Since digits nine, eight, six, three, and two become the required digits in the number, the following pattern occurs.
9 81 72 63 54
Each of the paired numbers sum to nine. Both six and three are already required. Since there must be an eight, there must also be a one. Since there is a two, there must also be a seven. Since there is not a five, there must not be a four.
So the maximum number possible will be 9876312, the last digit of two, since the result must be even. Likewise, the minimum would be 1236798.
The base 10 step amount is 9 * 8 * 7. By stepping through the numbers by this amount, we avoid numbers that don't have all the factors of the individual digits.
For base 16, to construct the required step factor, we multiply the numbers 11 through 15 together.
<syntaxhighlight lang="csharp">using System;
using System.Linq;
using System.Collections.Generic;
class Program {
static IEnumerable<long> decline(long min, long max, long stp) {
long lmt = (min / stp) * stp;
for (long i = (max / stp) * stp; i >= lmt; i -= stp)
yield return i;
}
static bool ChkDigs(long number) {
var set = new HashSet<char>();
return number
.ToString()
.All(d => d > '0'
&& number % (d - '0') == 0
&& set.Add(d));
}
static bool ChkHDigs(long number) {
const string hDigs = "0123456789abcdef";
var set = new HashSet<char>();
return number
.ToString("x")
.All(d => d > '0'
&& number % hDigs.IndexOf(d) == 0
&& set.Add(d));
}
static void Main() {
var sw = System.Diagnostics.Stopwatch.StartNew();
long min = 1236798, // lowest possible seven digit number
max = 9876312, // high limit
stp = 9 * 8 * 7, // skip numbers without this factor
result = decline(min, max, stp)
.Where(ChkDigs)
.First();
sw.Stop();
Console.Write("Base 10 = {0} in {1} ms", result,
sw.Elapsed.TotalMilliseconds);
sw.Restart();
min = 0x123456789abcdef; // lowest possible 15 digit number
max = 0xfedcba987654321; // high limit
stp = 15*14*13*12*11; // skip numbers without this factor
result = decline(min, max, stp)
.Where(ChkHDigs)
.First();
sw.Stop();
Console.Write("\nBase 16 = {0} in {1} sec",
result.ToString("x"), sw.Elapsed.TotalSeconds);
}
}</syntaxhighlight>
{{out}}Timing from Tio.run:
<pre>Base 10 = 9867312 in 13.6382 ms
Base 16 = fedcb59726a1348 in 1.0334308 sec</pre>
=={{header|C++}}==
{{trans|D}}
=== Base 10 ===
<syntaxhighlight lang="cpp">#include <iostream>
#include <sstream>
#include <set>
bool checkDec(int num) {
std::set<int> set;
std::stringstream ss;
ss << num;
auto str = ss.str();
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
int d = c - '0';
if (d == 0) return false;
if (num % d != 0) return false;
if (set.find(d) != set.end()) {
return false;
}
set.insert(d);
}
return true;
}
int main() {
for (int i = 98764321; i > 0; i--) {
if (checkDec(i)) {
std::cout << i << "\n";
break;
}
}
return 0;
}</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|Clojure}}==
=== Base Agnostic ===
This is a generic solution that works for any number base. Just change the line '''(def the_base 16)'''. The performance may be questionable for large bases which do not have a Lynch-Bell number using all digits.
Rather than searching through all numbers with unique digits, a space whose size verges on N factorial,
this algorithm instead works with the non-empty sets of non-zero digits, a space of size 2^(N-1) - 1.
For a given subset, it finds the least common multiple for that subset and examines each multiple of the LCM which is between
the largest and smallest positive numbers that can be constructed using each digit from that subset exactly once.
<syntaxhighlight lang="clojure">
(require '[clojure.string :as str]) ;'
(def the_base 16)
;A sequence named digits containing the non-zero digits for the current number base.
(def digits (rest (range the_base)))
;A container for the digits which are prime.
(def primes [])
;Populate the primes sequence with the primes less than the current base.
(for [n digits] (if (= 1 (count (filter (fn[m] (and (< m n) (= 0 (mod n m)))) digits)) ) (def primes (conj primes n))))
;Determines the highest power of a given prime p that divides a given integer n.
(defn duplicity [n p partial] (if (= 0 (mod n p)) (duplicity (/ n p) p (conj partial p)) partial))
;Constructs the prime factorization of a given integer.
(defn factorize [n] (let [a (flatten (for [p (filter #(< % n) primes)]
(remove #(= 1 %) (duplicity n p [1]))))] (if (= 0 (count a)) (lazy-seq [n]) a) ))
;Determines the number of times a given number appears in a given sequence of numbers.
(defn multiplicity [s n] (count (filter #(= n %) s)))
;Combines two sequence two create their "union" in the sense that in the resulting sequence
;each element from each sequence is uniquely represented and no smaller sequence would suffice.
;For example if one sequence contains two A's and other contains three A's, then the result will contain three A's.
;This is used to generate representations of prime factorizations and to construct least common multiples from them.
(defn combine [x y] (concat x (flatten (for [w (dedupe y)] (repeat (- (multiplicity y w) (multiplicity x w)) w) ))))
;deterimes the lcm least common multiple for a set of digits.
(defn lcm [s] (reduce * (reduce combine (map factorize s))))
;Retuns x^n.
(defn exp [x n] (reduce * (repeat n x)))
;Generates all non-empty subsequences for a sequence.
(defn non_empty_subsets [s] (for [x (reverse (rest (range (exp 2 (count s)))))]
(remove nil? (for [i (range (count s))] (if (bit-test x i) (nth s i))))))
;Generates from a given sequence of digits in the current base the number that is s[0]s[1]s[2]...s[n].
;More generally, produces s[0]*the_base^n + s[1]*the_base^(n-1) + ... + s[n-1]*the_base^1 + s[n]*the_base^0
;for an arbitrary sequence of numbers.
(defn power_up [s] (reduce + (loop [idx (- (count s) 1) s_next s]
(if (zero? idx) s_next (recur (dec idx) (map-indexed #(if (< %1 idx) (* %2 the_base) %2) s_next))))))
;Here is an alternative version of power_up that could be more efficient as it does not repeatedly recalculate powers of the base.
;Instead it calculates the dot product of s with a pre-populated sequence of powers of the base.
;Calculates the dot product of two vectors/sequences
;(defn dot [xs ys] (reduce + (map * xs ys)))
;(def places (map #(exp the_base %) (range the_base)))
;(defn power_up [s] (dot s (reverse (take (count s) places))))
;Returns the largest integer which contains each item from a given sequence exactly once as a digit.
(defn max_for_digits [s] (power_up (sort #(> %1 %2) s)))
;Returns the smallest non-negative integer which contains each item from a given sequence exactly once as a digit.
(defn min_for_digits [s] (power_up (sort #(< %1 %2) s)))
;calculate the logarithm of the input in the current base.
(defn log_base [x] (/ (Math/log x) (Math/log the_base)))
;Removes the zeros from a sequence
(defn remove_zeros [s] (remove #(= % 0) s))
;Returns the largest integer that is a multiple of a given integer and does not exceed another given integer.
(defn first_multiple_not_after [n ub] (loop [m ub] (if (= 0 (mod m n)) m (recur (dec m)))))
;creates a representation in the current base of a positive integer as a sequence listing the digits for the number in the base.
(defn representation [n] (let [full_power (int (log_base n))]
(loop [power full_power place (exp the_base full_power) rep [] rem n ] (if (= power -1) rep
(recur (dec power) (/ place the_base) (conj rep (int (/ rem place))) (- rem (* place (int (/ rem place)))))))))
;determines if a given number is exactly comprised of a given set of digits.
(defn digit_qualifies [m s] (let [rep_m (representation m)] (= (sort s) (sort rep_m))))
;Returns a sequence containing the largest Lynch-Bell number for the current base and a given sequence of digits
;or an empty sequence if there is none.
(defn find_s_largest_lb [s] (let [lb (min_for_digits s)] (let [m (lcm s)]
(loop [v (first_multiple_not_after m (max_for_digits s))] (if (< v lb) []
(if (digit_qualifies v s) (representation v) (recur (- v m))))))))
;Finds the largest Lynch-Bell number for the current base by looking for the largest for all subsets of a given size
;and picking the largest from those working from the largest size (most digits) to the smallest.
(defn find_largest_lb [] (let [subsets (non_empty_subsets (reverse digits))]
(loop [s_size (- the_base 1)] (let [hits (remove #(= (count %) 0) (map find_s_largest_lb (filter #(= (count %) s_size) subsets)))]
(if (pos? (count hits)) (first (sort #(first (remove_zeros (map - %2 %1))) hits)) (recur (dec s_size)))))))
;Converts small integers to hexidecimal digits.
;This isn't being used but could be leveraged to make output that looks normal for base 16.
(defn hex_digit [v] (case v 15 "F" 14 "E" 13 "D" 12 "C" 11 "B" 10 "A" (str v)))
(find_largest_lb)
</syntaxhighlight>
{{out}}
<pre>
[15 14 13 12 11 5 9 7 2 6 10 1 3 4 8] (base 16)
[10 9 8 7 6 2 4 1 3] (base 11)
[9 8 6 7 3 1 2] (base 10)
</pre>
=={{header|Crystal}}==
===base 10===
{{trans|Ruby}}
<syntaxhighlight lang="ruby">magic_number = 9*8*7
div = (9876432 // magic_number) * magic_number
candidates = div.step(to: 0, by: -magic_number)
res = candidates.find do |c|
digits = c.to_s.chars.map(&.to_i)
(digits & [0,5]).empty? && digits == digits.uniq
end
puts "Largest decimal number is #{res}"</syntaxhighlight>
{{out}}<pre>Largest decimal number is 9867312</pre>
===base 16===
{{trans|Kotlin}}
<syntaxhighlight lang="ruby">def divByAll(num, digits)
digits.all? { |digit| num % digit.to_i(16) == 0 }
end
magic = 15_i64 * 14 * 13 * 12 * 11
high = (0xfedcba987654321_i64 // magic) * magic
high.step(to: magic, by: -magic) do |i|
s = i.to_s(16) # always generates lower case a-f
next if s.includes?('0') || s.chars.uniq.size != s.size # need uniq non-zero digits
(puts "Largest hex number is #{i.to_s(16)}"; break) if divByAll(i, s.chars)
end</syntaxhighlight>
{{out}}<pre>Largest hex number is fedcb59726a1348</pre>
=={{header|D}}==
{{trans|Scala}}
=== Base 10 ===
<syntaxhighlight lang="d">import std.algorithm.iteration : filter, map;
import std.algorithm.searching : all;
import std.conv : to;
import std.range : iota;
import std.stdio : writeln;
bool chkDec(int num) {
int[int] set;
return num
.to!string
.map!(c => c.to!int - '0')
.all!(d => (d != 0) && (num % d == 0) && set[d]++ < 1);
}
auto lcm(R)(R r) {
return r.reduce!((a,b) => a * b / gcd(a,b));
}
void main() {
// base 10
iota(98764321, 0, -1)
.filter!chkDec
.front
.writeln;
}</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|Go}}
===base 10===
<syntaxhighlight lang="delphi">
program Largest_number_divisible_by_its_digits;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
type
TSetAnsiChar = set of AnsiChar;
function DivByAll(num: Integer; digits: TSetAnsiChar): Boolean;
var
offset: byte;
begin
offset := ord('0');
for var d in digits do
begin
if (num mod (ord(d) - offset)) <> 0 then
exit(false);
end;
Result := true;
end;
begin
var magic: Cardinal := 9 * 8 * 7;
var h: Cardinal := 9876432 div magic * magic;
for var i := h downto magic do
begin
if i mod 10 = 0 then
Continue;
var s := i.tostring;
if (s.indexOf('0') > -1) or (s.indexOf('5') > -1) then
Continue;
var digits: TSetAnsiChar := [];
var isUnic := true;
for var b in ansistring(s) do
if not (b in digits) then
Include(digits, b)
else
begin
isUnic := false;
break;
end;
if not isUnic then
Continue;
if DivByAll(i, digits) then
begin
writeln('Largest decimal number is ', i);
Break;
end;
end;
readln;
end.</syntaxhighlight>
===base 16===
<syntaxhighlight lang="delphi">
program Largest_number_divisible_by_its_digits;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
type
TSetAnsiChar = set of AnsiChar;
function DivByAll(num: Uint64; digits: TSetAnsiChar): Boolean;
var
offset_dec, offset_hex: byte;
begin
offset_dec := ord('0');
offset_hex := ord('W');
for var digit in digits do
begin
var d: byte := 0;
if digit <= '9' then
d := ord(digit) - offset_dec
else
d := ord(digit) - offset_hex;
if (num mod d) <> 0 then
exit(false);
end;
Result := true;
end;
begin
var magic: Uint64 := 15 * 14 * 13 * 12 * 11;
var h: Uint64 := $fedcba987654321 div magic * magic;
writeln('Wait while search for');
for var i := h downto magic do
begin
if (i mod 16) = 0 then
Continue;
var s := i.ToHexString(0).ToLower;
if (s.indexOf('0') > -1) then
Continue;
var digits: TSetAnsiChar := [];
var isUnic := true;
for var b in ansistring(s) do
if not (b in digits) then
Include(digits, b)
else
begin
isUnic := false;
break;
end;
if not isUnic then
Continue;
if DivByAll(i, digits) then
begin
writeln('Largest hex number is ', i.ToHexString);
Break;
end;
end;
readln;
end.</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
global found dig[] .
proc test . .
for i to len dig[]
n = n * 10 + dig[i]
.
for i to len dig[]
if n mod dig[i] <> 0
return
.
.
found = 1
print n
.
len use[] 9
proc perm pos . .
if found = 1
return
.
for i = 9 downto 1
dig[pos] = i
if use[i] = 0
use[i] = 1
if pos = len dig[]
test
else
perm pos + 1
.
use[i] = 0
.
.
.
for ndig = 9 downto 1
len dig[] ndig
perm 1
.
</syntaxhighlight>
=={{header|Factor}}==
===Base 10===
This program works by filtering all the 8-digit permutations (of which there are only ~40,000) for all-digit-divisibility, and upon finding none, it will then generate the 7-digit combinations (of which there are 8) of the 8 possible digits, and then filter all permutations of the 8 combinations for all-digit-divisibility. Upon finding many, it will simply select the largest element which is our answer. If there hadn't been any 7-digit solutions, it would have gone down to six and then five, etc.
<syntaxhighlight lang="factor">USING: io kernel math math.combinatorics math.parser math.ranges
sequences tools.time ;
IN: rosetta-code.largest-divisible
: all-div? ( seq -- ? )
[ string>number ] [ string>digits ] bi [ mod ] with map
sum 0 = ;
: n-digit-all-div ( n -- seq )
"12346789" swap <combinations>
[ [ all-div? ] filter-permutations ] map concat ;
: largest-divisible ( -- str )
8 [ dup n-digit-all-div dup empty? ] [ drop 1 - ] while
nip supremum ;
: largest-divisible-demo ( -- )
[ largest-divisible print ] time ;
MAIN: largest-divisible-demo</syntaxhighlight>
{{out}}
<pre>
9867312
Running time: 0.07224931499999999 seconds
</pre>
=={{header|FreeBASIC}}==
{{trans|Ring}}
===base 10===
<syntaxhighlight lang="freebasic">
For n As Integer = 9867000 To 9867400
Dim As Integer numbers(9)
For t As Byte = 1 To 9
numbers(t) = 0
Next t
Dim As Boolean flag = true, flag2 = true, flag3 = true
Dim As String cadena = Str(n)
For m As Byte = 1 To Len(cadena)
If Val(Mid(cadena,m,1)) > 0 Then
numbers(Val(Mid(cadena,m,1))) += 1
Else
flag2 = false
End If
Next m
If flag2 = true Then
For p As Byte = 1 To 9
If Not (numbers(p) = 0 Or numbers(p) = 1) Then flag = false
Next p
If flag = true Then
For x As Byte = 1 To Len(cadena)
If n Mod (Val(Mid(cadena,x,1))) <> 0 Then flag3 = false
Next x
If flag3 = true Then Print "El mayor n£mero decimal es:"; n
End If
End If
Next n
Sleep
</syntaxhighlight>
{{out}}
<pre>
El mayor número decimal es: 9867312
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
===base 10===
<syntaxhighlight lang="go">package main
import (
"fmt"
"strconv"
"strings"
)
func divByAll(num int, digits []byte) bool {
for _, digit := range digits {
if num%int(digit-'0') != 0 {
return false
}
}
return true
}
func main() {
magic := 9 * 8 * 7
high := 9876432 / magic * magic
for i := high; i >= magic; i -= magic {
if i%10 == 0 {
continue // can't end in '0'
}
s := strconv.Itoa(i)
if strings.ContainsAny(s, "05") {
continue // can't contain '0'or '5'
}
var set = make(map[byte]bool)
var sd []byte // distinct digits
for _, b := range []byte(s) {
if !set[b] {
set[b] = true
sd = append(sd, b)
}
}
if len(sd) != len(s) {
continue // digits must be unique
}
if divByAll(i, sd) {
fmt.Println("Largest decimal number is", i)
return
}
}
}</syntaxhighlight>
{{out}}
<pre>
Largest decimal number is 9867312
</pre>
===base 16===
<syntaxhighlight lang="go">package main
import (
"fmt"
"strconv"
"strings"
)
func divByAll(num int64, digits []byte) bool {
for _, digit := range digits {
var d int64
if digit <= '9' {
d = int64(digit - '0')
} else {
d = int64(digit - 'W')
}
if num%d != 0 {
return false
}
}
return true
}
func main() {
var magic int64 = 15 * 14 * 13 * 12 * 11
high := 0xfedcba987654321 / magic * magic
for i := high; i >= magic; i -= magic {
if i%16 == 0 {
continue // can't end in '0'
}
s := strconv.FormatInt(i, 16) // always generates lower case a-f
if strings.IndexByte(s, '0') >= 0 {
continue // can't contain '0'
}
var set = make(map[byte]bool)
var sd []byte // distinct digits
for _, b := range []byte(s) {
if !set[b] {
set[b] = true
sd = append(sd, b)
}
}
if len(sd) != len(s) {
continue // digits must be unique
}
if divByAll(i, sd) {
fmt.Printf("Largest hex number is %x\n", i)
return
}
}
}</syntaxhighlight>
{{out}}
<pre>
Largest hex number is fedcb59726a1348
</pre>
=={{header|Haskell}}==
===base 10===
Using the analysis provided in the Raku (base 10) example:
<syntaxhighlight lang="haskell">import Data.List (maximumBy, permutations, delete)
import Data.Ord (comparing)
import Data.Bool (bool)
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
-- Checking for divisibility by all digits
(comparing (bool 0 <*> (0 ==) . (`rem` lcmDigits)))
(unDigits <$> concat (permutations <$> sevenDigits))</syntaxhighlight>
{{Out}}
Test run from inside the Atom editor:
<pre>9867312
[Finished in 0.395s]</pre>
===base 16===
First member of a descending sequence of multiples of 360360 that uses the full set of 15 digits when expressed in hex.
<syntaxhighlight lang="haskell">import Data.Set (fromList)
import Numeric (showHex)
lcmDigits :: Int
lcmDigits = foldr1 lcm [1 .. 15] -- 360360
upperLimit :: Int
upperLimit = allDigits - rem allDigits lcmDigits
where
allDigits = 0xfedcba987654321
main :: IO ()
main =
(print . head)
(filter ((15 ==) . length . fromList) $
(`showHex` []) <$> [upperLimit,upperLimit - lcmDigits .. 1])</syntaxhighlight>
Test run from inside the Atom editor:
<pre>"fedcb59726a1348"
[Finished in 2.319s]</pre>
=={{header|J}}==
The 536 values found---all base 10 numbers that are divisible by their digits without repetition---are sorted descending, hence 9867312 is the greatest number divisible by its digits in base 10.
<syntaxhighlight lang="j">
Filter =: (#~`)(`:6)
combinations =: <@#"1~ [: #: [: i. 2 ^ #
permutations =: A.&i.~ !
f =: [: \:~ _ ". [: ; [: ({~ permutations@#)L:_1 }.@combinations
test =: 0 = ([: +/ (|~ 10&#.inv))&>
test Filter f '12346789'
9867312 9812376 9782136 9781632 9723168 9718632 9678312 9617832 9617328 9283176 9278136 9237816 9231768 9182376 9176832 9176328 9163728 8973216 8912736 8796312 8731296 8617392 8367912 8312976 8219736 8176392 8163792 8123976 7921368 7916832 7916328 7892136 ...
</syntaxhighlight>
Working in base 16 using the largest possible solution also a multiple of the least common multiple, subtract the LCM until all the digits appear.
<syntaxhighlight lang="j">
NB. 16bfedcba987654321 loses precision and so we need to work in extended data type
[ HEX_DIGITS =: >: i. _15x
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
[ LCM =: *./ HEX_DIGITS
360360
] START =: <.&.(%&LCM)16#.HEX_DIGITS
1147797409030632360
Until =: conjunction def 'u^:(0-:v)^:_'
assert 9 -: >:Until(>&8)1
test=: 0 -.@e. HEX_DIGITS e. 16&#.inv
[ SOLUTION =: -&LCM Until test START
1147797065081426760
'16b' , (16 #.inv SOLUTION) { Num_j_ , 26 }. Alpha_j_
16bfedcb59726a1348
</syntaxhighlight>
=={{header|Java}}==
{{works with|JDK 1.8.0}}
=== Base 10 ===
Using the analysis provided in the Raku (base 10) example:
<syntaxhighlight lang="java">public class LynchBell {
static String s = "";
public static void main(String args[]) {
//Highest number with unique digits (no 0 or 5)
int i = 98764321;
boolean isUnique = true;
boolean canBeDivided = true;
while (i>0) {
s = String.valueOf(i);
isUnique = uniqueDigits(i);
if (isUnique) {
//Number has unique digits
canBeDivided = testNumber(i);
if(canBeDivided) {
System.out.println("Number found: " + i);
i=0;
}
}
i--;
}
}
public static boolean uniqueDigits(int i) {
//returns true, if unique digits, false otherwise
for (int k = 0; k<s.length();k++) {
for(int l=k+1; l<s.length();l++) {
if(s.charAt(l)=='0' || s.charAt(l)=='5') {
//0 or 5 is a digit
return false;
}
if(s.charAt(k) == s.charAt(l)) {
//non-unique digit
return false;
}
}
}
return true;
}
public static boolean testNumber(int i) {
//Tests, if i is divisible by all its digits (0 is not a digit already)
int j = 0;
boolean divisible = true;
// TODO: divisible by all its digits
for (char ch: s.toCharArray()) {
j = Character.getNumericValue(ch);
divisible = ((i%j)==0);
if (!divisible) {
return false;
}
}
return true;
}
}</syntaxhighlight>
{{out}}
<pre>Number found: 9867312</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The following is based on the [[#awk|awk]] entry, for which see the rationale.
<syntaxhighlight lang="jq">
def has_unique_digits:
tostring
| explode
| label $out
| (foreach map([.] | implode)[] as $d ({};
.[$d] += 1;
select(.[$d] > 1) | (0, break $out)))
// true
| . == true;
# exclude numbers with a 0
def is_divisible_by_all_its_digits:
. as $n
| tostring
| explode
| map([.] | implode | tonumber) as $digits
| all($digits[]; . != 0) and
all($digits[]; $n % . == 0);
def task:
def solve($startn; $stopn; $comdiv):
($startn - ($startn % $comdiv))
| while (. >= $stopn; . - $comdiv)
| select(has_unique_digits and is_divisible_by_all_its_digits);
first(solve(9876543; 1000000; 12));
task
</syntaxhighlight>
{{out}}
<pre>
9867312
</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
=== Base 10 ===
{{trans|C}}
<syntaxhighlight lang="julia">function main()
num = 9876432
dif = [4, 2, 2, 2]
local k = 1
@label start
local str = dec(num)
for (i, ch) in enumerate(str)
if ch in ('0', '5') || num % (ch - '0') != 0
num -= dif[k]
k = (k + 1) % 4 + 1
@goto start
end
for j in i+1:endof(str)
if str[i] == str[j]
num -= dif[k]
k = (k + 1) % 4 + 1
@goto start
end
end
end
return num
end
println("Number found: ", main())</syntaxhighlight>
{{out}}
<pre>Number found: 9867312</pre>
=={{header|Kotlin}}==
Makes use of the Raku entry's analysis:
===base 10===
<syntaxhighlight lang="scala">// 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
}
}
}</syntaxhighlight>
{{out}}
<pre>
Largest decimal number is 9867312
</pre>
===base 16===
<syntaxhighlight lang="scala">// 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
}
}
}</syntaxhighlight>
{{out}}
<pre>
Largest hex number is fedcb59726a1348
</pre>
=={{header|Lua}}==
<syntaxhighlight lang="lua">function isDivisible(n)
local t = n
local a = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
while t ~= 0 do
local r = t % 10
if r == 0 then
return false
end
if n % r ~= 0 then
return false
end
if a[r + 1] > 0 then
return false
end
a[r + 1] = 1
t = math.floor(t / 10)
end
return true
end
for i=9999999999,0,-1 do
if isDivisible(i) then
print(i)
break
end
end
</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
===base 10===
<syntaxhighlight lang="mathematica"> Max@Select[FromDigits/@Rest@Flatten[Permutations/@Subsets[Range@9,9],1],And@@IntegerQ/@(#/IntegerDigits@#)&]</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|Nanoquery}}==
===Base 10===
{{trans|Java}}
<syntaxhighlight lang="nanoquery">s = ""
def uniqueDigits(i)
global s
// returns true, if unique digits, false otherwise
for k in range(0, len(s) - 2)
for l in range(k + 1, len(s) - 1)
if (s[l] = "0") || (s[l] = "5")
//0 or 5 digit
return false
end
if s[k] = s[l]
//non-unique digit
return false
end
end
end
return true
end
def testNumber(i)
global s
//Tests, if i is divisible by all its digits (0 is not a digit already)
j = 0
divisible = true
for ch in s
j = int(ch)
divisible = (i % j) = 0
if not divisible
return false
end
end
return true
end
i = 98764321
isUnique = true
canBeDivided = true
while i > 0
s = str(i)
isUnique = uniqueDigits(i)
if isUnique
//Number has unique digits
canBeDivided = testNumber(i)
if canBeDivided
println "Number found: " + i
i = 0
end
end
i -= 1
end</syntaxhighlight>
=={{header|Nim}}==
===Base 10===
This version uses a combination of several algorithms, especially those of the C++ and the Go/Raku versions. But, to get the digits, instead of converting the number to a string it uses an iterator which is significantly faster. And to check digit uniqueness, it uses a very efficient bit set. The programs runs in less than 20ms.
<syntaxhighlight lang="nim">type Digit = range[0..9]
iterator digits(n: int64): Digit =
var n = n
while true:
yield n mod 10
n = n div 10
if n == 0: break
func isLynchBell(num: int64): bool =
var hSet: set[Digit]
for d in num.digits:
if d == 0 or num mod d != 0 or d in hSet:
return false
hSet.incl(d)
return true
const
Magic = 9 * 8 * 7
High = 0x9876432 div Magic * Magic
for n in countdown(High, Magic, Magic):
if n.isLynchBell:
echo n
break</syntaxhighlight>
{{out}}
<pre>9867312</pre>
===Base 16===
This is the same algorithm adapted for base 16. The program runs in about 30ms.
<syntaxhighlight lang="nim">import strformat
type Digit = range[0..15]
iterator digits(n: int64): Digit =
var n = n
while true:
yield n and 15
n = n shr 4
if n == 0: break
func isLynchBell(num: int64): bool =
var hSet: set[Digit]
for d in num.digits:
if d == 0 or num mod d != 0 or d in hSet:
return false
hSet.incl(d)
return true
const Magic = 15 * 14 * 13 * 12 * 11
const High = 0xfedcba987654321 div Magic * Magic
for n in countdown(High, Magic, Magic):
if n.isLynchBell:
echo &"{n:x}"
break</syntaxhighlight>
{{out}}
<pre>fedcb59726a1348</pre>
=={{header|Perl}}==
{{trans|Raku}}
===Base 10===
<syntaxhighlight lang="perl">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
}</syntaxhighlight>
{{out}}
<pre>Found 9867312 after 18 steps
9867312 / 9 = 1096368
9867312 / 8 = 1233414
9867312 / 6 = 1644552
9867312 / 7 = 1409616
9867312 / 3 = 3289104
9867312 / 1 = 9867312
9867312 / 2 = 4933656</pre>
===Base 16===
<syntaxhighlight lang="perl">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;</syntaxhighlight>
{{out}}
<pre>Found fedcb59726a1348 after 954460 steps
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</pre>
=={{header|Phix}}==
=== base 10 ===
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">magic</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">8</span><span style="color: #0000FF;">*</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">high</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9876432</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">high</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">high</span><span style="color: #0000FF;">,</span><span style="color: #000000;">magic</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">seen</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">seen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">magic</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- may as well quickly verify...</span>
<span style="color: #000000;">seen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (skipping 5)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- ( and 0 )</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">seen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d (%d iterations)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">high</span><span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">magic</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
9867312 (18 iterations)
</pre>
=== base 16 ===
{{trans|Haskell}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">lcm15</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">15</span><span style="color: #0000FF;">))),</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"FEDCBA987654321"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lcm15</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- d:= max k*lcm <= "FE..21"</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (no longer used)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)=</span><span style="color: #008000;">"123456789abcdef"</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lcm15</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s (%d iterations, %s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
fedcb59726a1348 (954460 iterations, 12.4s)
</pre>
=={{header|Prolog}}==
This will work with any radix, including base 10 and base 16.
<syntaxhighlight lang="prolog">% Find the largest integer divisible by all it's digits, with no digit repeated.
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
% We go for a generic algorithm here. Test for divisibility is done by
% calculating the least common multiplier for all digits, and testing
% whether a candidate can be divided by the LCM without remainder.
%
% Instead of iterating numbers and checking whether the number has
% repeating digits, it is more efficient to generate permutations of
% digits and then convert to a number. Doing it this way reduces search
% space greatly.
%
% Notes:
% For decimal numbers we could improve times by testing only numbers
% of length 7 (since 5x2=10 and 0 is not one of our digits, and 9x2=18
% which needs 2 digits to store), but that sort of logic does not
% hold for hexadecimal numbers.
% We could also explicitly eliminate odd numbers, but the double validity
% check actually slows us down very slightly instead of speeding us up.
:- dynamic
trial/1. % temporarily store digit combinations here.
gcd(X, X, X). % Calculate greatest common divisor
gcd(M, N, X) :- N > M, B is N-M, gcd(M,B,X).
gcd(M, N, X) :- N < M, A is M-N, gcd(A,N,X).
lcm(A, B, LCM) :- gcd(A,B,GCD), LCM is A * B / GCD.
lcm([H], H). % Calculate least common multiplier
lcm([A|T], LCM) :- lcm(T, B), !, lcm(A,B,LCM).
mkint(_, Val, [], Val). % Result = Val where list is empty
mkint(Radix, Val, [H|T], Int) :- % (((I0*10+I1)*10+I2)*10+In)...
V0 is Val*Radix+H, !, mkint(Radix, V0, T, Int).
% Turn a list of digits into an integer number using Radix.
mkint(Radix, [H|T], Int) :- mkint(Radix, H, T, Int).
domain(0, []). % For example, domain(5) is [1,2,3,4,5]
domain(N, [N|Digits]) :-
succ(N0, N), !, domain(N0, Digits).
trial(0, Digits, Digits). % generates a combination of digits to test
trial(N, D, Digits) :- % remove N digits, and find remaining combinations
append(L0,[_|L1],D), succ(N0, N), trial(N0, L1, Dx),
append(L0, Dx, Digits). % trial(1, [3,2,1], D) -> D=[2,1]; D=[3,1]; D=[3,2].
make_trials(_,_) :- retractall(trial(_)), fail.
make_trials(N,Domain) :- trial(N, Domain, Digits), asserta(trial(Digits)), fail.
make_trials(_,_). % trials are stored highest values to lowest
combinations(Radix, NDigits) :- % Precalculate all possible digit combinations
succ(R0, Radix), domain(R0, Domain), Nskip is R0 - NDigits,
make_trials(Nskip, Domain).
test(Radix, Digits, LCM, Number) :- % Make an integer and check for divisibility
mkint(Radix, Digits, Number), 0 is Number mod LCM.
bignum(Radix, Number) :-
succ(R0, Radix), between(1,R0,N), NDigits is Radix - N, % loop decreasing length
combinations(Radix, NDigits), % precalc digit combos with length=NDigits
trial(Digits), lcm(Digits, LCM), % for a combination, calculate LCM
permutation(Digits, Trial), % generate a permutation
test(Radix, Trial, LCM, Number). % test for divisibility
largest_decimal(N) :- bignum(10, N), !.
largest_hex(N, H) :- bignum(16, N), !, sformat(H, '~16r', [N]).</syntaxhighlight>
<pre>?- time(largest_decimal(S)).
% 20,043,250 inferences, 3.086 CPU in 3.089 seconds (100% CPU, 6493905 Lips)
S = 9867312.
?- time(largest_hex(S,H)).
% 73,332,059 inferences, 11.800 CPU in 11.803 seconds (100% CPU, 6214553 Lips)
S = 1147797065081426760,
H = "fedcb59726a1348".</pre>
=={{header|Python}}==
===base 10===
Using the insights presented in the preamble to the Raku (base 10) example:
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''Largest number divisible by its digits'''
from itertools import (chain, permutations)
from functools import (reduce)
from math import (gcd)
# main :: IO ()
def main():
'''Tests'''
# (Division by zero is not an option, so 0 and 5 are omitted)
digits = [1, 2, 3, 4, 6, 7, 8, 9]
# Least common multiple of the digits above
lcmDigits = reduce(lcm, digits)
# Any 7 items drawn from the digits above,
# including any two of [1, 4, 7]
sevenDigits = ((delete)(digits)(x) for x in [1, 4, 7])
print(
max(
(
intFromDigits(x) for x
in concatMap(permutations)(sevenDigits)
),
key=lambda n: n if 0 == n % lcmDigits else 0
)
)
# intFromDigits :: [Int] -> Int
def intFromDigits(xs):
'''An integer derived from an
ordered list of digits.
'''
return reduce(lambda a, x: a * 10 + x, xs, 0)
# ----------------------- GENERIC ------------------------
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list over which a function has been
mapped. The list monad can be derived by using a
function f which wraps its output in a list,
(using an empty list to represent computational failure).
'''
def go(xs):
return chain.from_iterable(map(f, xs))
return go
# delete :: Eq a => [a] -> a -> [a]
def delete(xs):
'''xs with the first instance of
x removed.
'''
def go(x):
ys = xs.copy()
ys.remove(x)
return ys
return go
# lcm :: Int -> Int -> Int
def lcm(x, y):
'''The smallest positive integer divisible
without remainder by both x and y.
'''
return 0 if (0 == x or 0 == y) else abs(
y * (x // gcd(x, y))
)
# MAIN ---
if __name__ == '__main__':
main()</syntaxhighlight>
{{Out}}
<pre>9867312</pre>
===base 16===
Descending from the upper limit, in steps of 360360 (least common multiple of the fifteen digit values), until the first number that uses all fifteen digits when expressed in hexadecimal.
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''Largest number divisible by its hex digits'''
from functools import (reduce)
from math import (gcd)
# main :: IO ()
def main():
'''First integer evenly divisible by each of its
hex digits, none of which appear more than once.
'''
# Least common multiple of digits [1..15]
# ( -> 360360 )
lcmDigits = foldl1(lcm)(
enumFromTo(1)(15)
)
allDigits = 0xfedcba987654321
# ( -> 1147797409030632360 )
upperLimit = allDigits - (allDigits % lcmDigits)
# Possible numbers
xs = enumFromThenToNext(upperLimit)(
upperLimit - lcmDigits
)(1)
print(
hex(
until(lambda x: 15 == len(set(showHex(x))))(
lambda _: next(xs)
)(next(xs))
)
) # --> 0xfedcb59726a1348
# ------------------ GENERIC FUNCTIONS -------------------
# enumFromThenToNext :: Int -> Int -> Int -> Gen [Int]
def enumFromThenToNext(m):
'''Non-finite series of integer values enumerated
from m to n with a step size defined by nxt-m.
'''
def go(m, nxt):
d = nxt - m
v = m
while True:
yield v
v = d + v
return lambda nxt: lambda n: go(m, nxt)
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: range(m, 1 + n)
# foldl1 :: (a -> a -> a) -> [a] -> a
def foldl1(f):
'''Left to right reduction of the
non-empty list xs, using the binary
operator f, with the head of xs
as the initial acccumulator value.
'''
return lambda xs: reduce(
lambda a, x: f(a)(x), xs[1:], xs[0]
) if xs else None
# lcm :: Int -> Int -> Int
def lcm(x):
'''The smallest positive integer divisible
without remainder by both x and y.
'''
return lambda y: (
0 if (0 == x or 0 == y) else abs(
y * (x // gcd(x, y))
)
)
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.
'''
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)
# showHex :: Int -> String
def showHex(n):
'''Hexadecimal string representation
of an integer value.
'''
return hex(n)[2:]
# MAIN --
if __name__ == '__main__':
main()</syntaxhighlight>
{{Out}}
<pre>0xfedcb59726a1348
[Finished in 1.243s]</pre>
===Both Base 10 & Base 16===
Here is a stripped down version, as compared to the above, this may execute quicker. Note that only digit four need be removed the set of eight (98764321). Removing digit one or digit seven results in no seven digit solutions. Digit four appears in six digit solutions.
Also note that the divisor check can be omitted when stepping by the correct step factor in either base.
Every base 16 solution must end in eight, (in order to have all the divisor factors), so the maximum value can be dropped to 0xfedcba976543218.
<syntaxhighlight lang="python">from time import time
st = time()
stp = 9 * 8 * 7
for n in range((9876312 // stp) * stp, 0, -stp):
s = str(n)
if "0" in s or "5" in s or len(set(s)) < len(s): continue
print("Base 10 =", n, "in %.3f" % (1e6 * (time() - st)), "μs");
break;
st = time()
stp = 15 * 14 * 13 * 12 * 11
for n in range((0xfedcba976543218 // stp) * stp, 0, -stp):
s = hex(n)[2:]
if "0" in s or len(set(s)) < len(s): continue
print("Base 16 =", hex(n), "in %.3f" % (1e3 * (time() - st)), end = "ms")
break;</syntaxhighlight>
{{Out}}Timing from Tio.run, <b>Python 3 (PyPy)</b>
<pre>Base 10 = 9867312 in 71.526 μs
Base 16 = 0xfedcb59726a1348 in 565.161ms</pre>
=={{header|Quackery}}==
Uses the insights in the Raku solution. (Must be divisible by 504, can't include 5 or 0.)
<syntaxhighlight lang="Quackery"> [ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
[ over find swap found ] is has ( [ x --> b )
[ false swap
sort
behead swap
witheach
[ tuck = if
[ dip not
conclude ] ]
drop ] is repeats ( [ --> b )
9876432 504 / 504 *
504 +
[ 504 -
dup digits
dup 5 has iff
drop again
dup 0 has iff
drop again
repeats if again ]
echo</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|R}}==
===Base 10===
Possibility to choose the range of integers to explore.
I read Raku solution too late, so I didn't implement the "magic number" thing.
Although not fully optimized, this solution it's pretty fast and I like how it works doing the task, so I didn't change it.
<syntaxhighlight lang="r">largest_LynchBell_number <- function(from, to){
from = round(from)
to = round(to)
to_chosen = to
if(to > 9876432) to = 9876432 #cap the search space to this number
LynchBell = NULL
range <- to:from #search starting from the end of the range
range <- range[range %% 5 != 0] #reduce search space
for(n in range){
splitted <- strsplit(toString(n), "")[[1]]
if("0" %in% splitted | "5" %in% splitted) next
if (length(splitted) != length(unique(splitted))) next
for (i in splitted) {
if(n %% as.numeric(i) != 0) break
if(which(splitted == i) == length(splitted)) LynchBell = n
}
if(!is.null(LynchBell)) break
}
message(paste0("The largest Lynch-Bell numer between ", from, " and ", to_chosen, " is ", LynchBell))
return(LynchBell)
}
#Verify (in less than 2 seconds)
for(i in 10^(1:8)){
largest_LynchBell_number(1, i)
}</syntaxhighlight>
{{out}}
<pre>
The largest Lynch-Bell numer between 1 and 10 is 9
The largest Lynch-Bell numer between 1 and 100 is 48
The largest Lynch-Bell numer between 1 and 1000 is 936
The largest Lynch-Bell numer between 1 and 10000 is 9864
The largest Lynch-Bell numer between 1 and 100000 is 98136
The largest Lynch-Bell numer between 1 and 1000000 is 984312
The largest Lynch-Bell numer between 1 and 10000000 is 9867312
The largest Lynch-Bell numer between 1 and 100000000 is 9867312</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2017.08}}
Line 22 ⟶ 2,153:
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
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.
Line 28 ⟶ 2,159:
All these optimizations get the run time to well under 1 second.
<syntaxhighlight lang="raku"
my $div = 9876432 div $magic-number * $magic-number; # largest 7 digit multiple of 504 < 9876432
Line 35 ⟶ 2,166:
next if $test ~~ / <[05]> /; # skip numbers containing 0 or 5
next if $test ~~ / (.).*$0 /; # skip numbers with non unique digits
say "Found $test"; # Found a solution, display it
Line 42 ⟶ 2,172:
}
last
}</
{{out}}
<pre>Found 9867312
Line 55 ⟶ 2,185:
===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
<syntaxhighlight lang="raku" line>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;
# hunt for target stepping backwards in multiples of the lcm
my $target = ($div, * - $magic-number ... 0).race.first: -> \test {
my \num= test.base(16);
(num.contains('0') || num.comb.Bag.values.max > 1) ?? False !! True
};
my $hexnum = $target.base(16);
say "Found $hexnum"; # Found a solution, display it
say ' ' x 12, 'In base 16', ' ' x 36, 'In base 10';
for $hexnum.comb {
printf "%s / %s = %s | %d / %2d = %19d\n",
$hexnum, $_, ($target / :16($_)).base(16),
$target, :16($_), $target / :16($_);}</syntaxhighlight>
{{out}}
<pre>Found FEDCB59726A1348
Line 95 ⟶ 2,223:
FEDCB59726A1348 / 4 = 3FB72D65C9A84D2 | 1147797065081426760 / 4 = 286949266270356690
FEDCB59726A1348 / 8 = 1FDB96B2E4D4269 | 1147797065081426760 / 8 = 143474633135178345</pre>
=={{header|Red}}==
<syntaxhighlight lang="rebol">Red []
t0: now/time/precise ;; measure runtime
lbn: 98764321 + 1 ;; because digit 5 is ruled out, this is the highest 8 digit number
;; possible, add 1 because only even numbers are possible
check: func [tos [ string! ]] [ ;; function to check if number is divideable by
foreach ele tos [ ;; all of its digits
div: to-integer ele - #"0" ;; convert asci digit to integer
unless lbn % div = 0 [ return false ] ;; fail at first false condition ( unless = if not...)
]
true ;; true if all digits passed
]
forever [
lbn: lbn - 2 ;; only even numbers could be possible results
if find tos: to-string lbn "0" [continue] ;; no "0" allowed
if find tos "5" [continue] ;; "5" also excluded
unless tos = unique tos [ continue ] ;; only unique digits allowed
unless check tos [continue] ;; passed check ?
print lbn ;; first hit is result
probe now/time/precise - t0 ;; display runtime
halt
]
</syntaxhighlight>
{{Out}}(interpreted version:)<pre>9867312
0:01:38.004
(halted)
</pre>
=={{header|REXX}}==
===base 10===
This REXX version uses mostly the same logic and deductions that the '''
<br>the tests in a different order for maximum speed.
The inner '''do''' loop is only executed a score of times; the 1<sup>st</sup> '''if''' statement does the bulk of the eliminations.
<
$= 7 * 8 * 9
if verify(50, #,
t= t+1
end /*j*/
/* [↓] superfluous, but check anyways.*/
leave
end
say 'found ' # " (in " t ' trials)' /*stick a fork in it, we're all done. */</syntaxhighlight>
{{out|output|:}}
Timing note: execution time is under '''<sup>1</sup>/<sub>2</sub>''' millisecond (essentially not measurable in the granularity of the REXX timer under Microsoft Windows).
<pre>
found 9867312 (in 11 trials)
Line 130 ⟶ 2,285:
The "magic" number was expanded to handle hexadecimal numbers.
Note that '''15
<
numeric digits 20 /*be able to handle the large hex nums.*/
bigH= 'fedcba987654321' /*biggest
bigN= x2d(bigH)
$= 15 * 14 * 13 * 12 * 11
h= d2x(#)
if pos(0, h) \==0 then iterate
t= t+1
do j=1 for
if pos( substr(h, j,
end /*j*/
end /*v*/
leave
end
say 'found ' h " (in " t ' trials)' /*stick a fork in it, we're all done. */</syntaxhighlight>
{{out|output|:}}
<pre>
found FEDCB59726A1348 (in 287747 trials)
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Largest number divisible by its digits
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
</syntaxhighlight>
Output:
<pre>
9867312
</pre>
=={{header|RPL}}==
Based on the rationale developed in the Raku section.
≪ → digits
≪ {10} 0 CON
1 digits SIZE '''FOR''' j
digits j DUP SUB STR→ 1 +
DUP2 GET 1 + PUT
'''NEXT'''
RNRM 1 ==
≫ ≫ '<span style="color:blue">DIFFDIG?</span>' STO
≪ 7 8 9 * * → multiple
≪ 9876432 DUP multiple MOD - 1 '''FOR''' j
j →STR
'''IF''' DUP "0" POS OVER "5" POS OR NOT '''THEN'''
'''IF''' DUP <span style="color:blue">DIFFDIG?</span> '''THEN''' j SWAP O 'j' STO '''END'''
'''END''' DROP
multiple NEG STEP
≫ ≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: 9867312
</pre>
Solution found in 11.5 seconds on an HP-48S.
=={{header|Ruby}}==
===base 10===
Following the reasoning of the Raku sample.
<syntaxhighlight lang="ruby">magic_number = 9*8*7
div = 9876432.div(magic_number) * magic_number
candidates = div.step(0, -magic_number)
res = candidates.find do |c|
digits = c.digits
(digits & [0,5]).empty? && digits == digits.uniq
end
puts "Largest decimal number is #{res}"</syntaxhighlight>
{{out}}<pre>Largest decimal number is 9867312</pre>
===base 16===
{{trans|Crystal from Kotlin}}
<syntaxhighlight lang="ruby">def divByAll(num, digits)
digits.all? { |digit| num % digit.to_i(16) == 0 }
end
magic = 15 * 14 * 13 * 12 * 11
high = (0xfedcba987654321 / magic) * magic
high.step(magic, -magic) do |i|
s = i.to_s(16) # always generates lower case a-f
next if s.include? "0" # can't contain '0'
sd = s.chars.uniq
next if sd.size != s.size # digits must be unique
(puts "Largest hex number is #{i.to_s(16)}"; break) if divByAll(i, sd)
end</syntaxhighlight>
{{out}}<pre>Largest hex number is fedcb59726a1348</pre>
=={{header|Scala}}==
===base 10===
This example starts with a lazily evaluated list of decreasing decimal numbers, starting with 98764321 (5 is eliminated as per the Pearl 6 analysis). It applies a filter to only accept numbers with distinct, nonzero digits that all divide the number itself, and then returns the head of the list.
<syntaxhighlight lang="scala">import scala.collection.mutable
def largestDecimal: Int = Iterator.from(98764321, -1).filter(chkDec).next
def chkDec(num: Int): Boolean = {
val set = mutable.HashSet[Int]()
num.toString.toVector.map(_.asDigit).forall(d => (d != 0) && (num%d == 0) && set.add(d))
}</syntaxhighlight>
{{out}}
<pre>scala> println(s"Base 10: $largestDecimal")
Base 10: 9867312</pre>
===base 16===
While concise, the previous example is relatively slow, taking nearly 30 seconds to complete. So, instead of simply moving on to a base 16 version, this next example is a fast version for arbitrary base. Starting with a list of digits generated from the given base, the program generates a lazily evaluated list of all possible combinations of digits in blocks of decreasing length. Each block is passed to a function that generates a list of numbers for each combination which are divisible by all the digits, then filters it for numbers which are made up of the required digits. The blocks are checked in order until a number is found.
<syntaxhighlight lang="scala">import spire.math.SafeLong
import spire.implicits._
object LargestNumDivisibleByDigits {
def main(args: Array[String]): Unit = {
for(b <- Seq(10, 16)){
val tStart = System.currentTimeMillis
val res = getLargestNum(b).toBigInt.toString(b)
val tDur = System.currentTimeMillis - tStart
println(s"Base $b: $res [${tDur}ms]")
}
}
def getLargestNum(base: SafeLong): SafeLong = {
def chkNum(digits: Vector[SafeLong])(num: SafeLong): Boolean = {
val lst = LazyList.iterate((num%base, num/base)){case (_, src) => (src%base, src/base)}.take(digits.length).map(_._1)
lst.diff(digits).isEmpty
}
def chkChunk(combo: Vector[SafeLong]): Option[SafeLong] = {
val lcm = combo.reduce(_.lcm(_))
val ulim = combo.zipWithIndex.map{case (n, i) => n*(base ** i)}.reduce(_+_)
Iterator.iterate(ulim - (ulim%lcm))(_ - lcm).takeWhile(_ > 0).find(chkNum(combo))
}
val baseDigits: Vector[SafeLong] = Vector.range(1, base.toInt).map(SafeLong(_))
def chkBlock(digits: Iterator[Vector[SafeLong]]): Option[SafeLong] = digits.map(chkChunk).collect{case Some(n) => n}.maxOption
Iterator.from(base.toInt - 1, -1).map(len => chkBlock(baseDigits.combinations(len))).collect{case Some(n) => n}.next
}
}</syntaxhighlight>
{{out}}
<pre>Base 10: 9867312 [1144ms]
Base 16: fedcb59726a1348 [1090ms]</pre>
=={{header|Sidef}}==
===base 10===
<syntaxhighlight lang="ruby">func largest_number(base) {
var digits = @(base ^.. 1)
digits.each {|k|
digits.variations(k, {|*a|
var n = Number(a.join, base)
if (a.all {|d| d.divides(n) }) {
return n
}
})
}
}
say largest_number(10) #=> 9867312</syntaxhighlight>
=={{header|VBScript}}==
===base 10===
<syntaxhighlight lang="vb">' Largest number divisible by its digits - base10 - VBScript
s=7*8*9 'reasonable assumption
m=9876432 'reasonable assumption
for i=(m\s)*s to 1 step -s
if instr(i,"5")=0 and instr(i,"0")=0 then '5 or 0 impossible
b=false: j=1
while j<=len(i)-1 and not b
if instr(j+1,i,mid(i,j,1))<>0 then b=true 'no duplicated digit
j=j+1
wend
if not b then
j=1
while j<=len(i) and not b
if (i mod mid(i,j,1))<>0 then b=true 'divisible by all digits
j=j+1
wend
if not b then exit for
end if
end if
next
wscript.echo i </syntaxhighlight>
{{out}}
<pre>
9867312
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function ChkDec(num As Integer) As Boolean
Dim sett As New HashSet(Of Integer)
Return num.ToString() _
.Select(Function(c) Asc(c) - Asc("0")) _
.All(Function(d) (d <> 0) AndAlso (num Mod d = 0) AndAlso sett.Add(d))
End Function
Sub Main()
Dim result = Enumerable.Range(0, 98764321) _
.Reverse() _
.Where(AddressOf ChkDec) _
.First()
Console.WriteLine(result)
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>9867312</pre>
=={{header|Wren}}==
===base 10===
{{trans|Kotlin}}
<syntaxhighlight lang="wren">var divByAll = Fn.new { |n, digits| digits.all { |d| n%(d-48) == 0 } }
var magic = 9 * 8 * 7
var high = (9876432/magic).floor * magic
var i = high
while (i >= magic) {
if (i%10 != 0) { // can't end in '0'
var s = "%(i)"
if (!s.contains("0") && !s.contains("5")) { // can't contain '0' or '5'
var set = {}
var sd = [] // list of distinct digits
for (b in s.bytes) {
if (set[b] == null) {
set[b] = true
sd.add(b)
}
}
if (sd.count == s.count) { // digits must be unique
if (divByAll.call(i, sd)) {
System.print("Largest decimal number is %(i)")
return
}
}
}
}
i = i - magic
}</syntaxhighlight>
{{out}}
<pre>
Largest decimal number is 9867312
</pre>
===base 16===
{{trans|AWK}}
The integers here are too large (>= 2^53) to be accurately represented by Wren and so we follow the AWK approach of using an array of digits to represent them.
<syntaxhighlight lang="wren">var digits = "0123456789abcdef"
var base = 16
var size = 15
var comDiv = 15 * 14 * 13 * 12 * 11
// Returns n mod k, where n is an array and k is a number
var hexMod = Fn.new { |n, k|
var r = 0
for (i in size..1) r = (r*base + n[i]) % k
return r
}
// Calculates n = n - m, where n is an array and m is a number
var hexSub = Fn.new { |n, m|
var i = 1
while (m != 0 && i <= size) {
n[i] = n[i] - (m%base)
m = (m/base).floor
if (n[i] < 0) {
n[i] = n[i] + base
m = m + 1
}
i = i + 1
}
}
// Returns true if n is an array of unique digits in range 1..(base-1)
var hasUniqueDigits = Fn.new { |n|
var dcount = List.filled(base, 0)
for (i in 1..size) {
var d = n[i]
if (d == 0) return false // can't contain '0'
dcount[d] = dcount[d] + 1
if (dcount[d] > 1) return false // digits must be unique
}
return true
}
var solve = Fn.new { |n|
var r = hexMod.call(n, comDiv)
hexSub.call(n, r)
while (n[size] > 0) {
if (hasUniqueDigits.call(n)) {
System.write("Largest hex number is ")
for (i in size..1) System.write(digits[n[i]])
System.print()
return
}
hexSub.call(n, comDiv)
}
}
var startN = List.filled(size + 1, 0)
for (i in 1..size) startN[i] = i
solve.call(startN)</syntaxhighlight>
{{out}}
<pre>
Largest hex number is fedcb59726a1348
</pre>
=={{header|XPL0}}==
Assumes answer contains either a 2, 4, 6 or 8 and is thus divisible by 2.
Also assumes answer contains either a 3, 6 or 9 and is thus divisible by 3.
Takes 9.7 seconds on Pi4 (with XPL0 ver 3.2).
<syntaxhighlight lang="xpl0">int Digits; \bit array
func AllDiv(N); \Return 'true' if N is divisible by its digits
int N, D;
[for D:= 9 downto 2 do
if 1<<D & Digits then
if rem(N/D) # 0 then return false;
return true;
];
func Unique(N); \Return 'true' if N contains unique digits
int N;
[Digits:= 1; \disallow 0
while N do
[N:= N/10;
if 1<<rem(0) & Digits then return false;
Digits:= 1<<rem(0) ! Digits;
];
return true;
];
int N;
[N:= 987654312; \largest possible number divisible by (2*3)
loop [if Unique(N) then
if AllDiv(N) then
[IntOut(0, N);
quit;
];
N:= N-6;
];
]</syntaxhighlight>
{{out}}
<pre>
9867312
</pre>
=={{header|zkl}}==
===base 10===
{{trans|
<
const div=9876432 / magic_number * magic_number; #largest 7 digit multiple of 504 < 9876432
foreach test in ([div..0,-magic_number]){
text
if(text.holds("0","5")) continue; # skip numbers containing 0 or 5
if(text.unique().len()!=
if(test.split().filter1('%.fp(test))) continue; # skip numbers that don't divide evenly by all digits
Line 176 ⟶ 2,697:
}
break;
}</
{{out}}
<pre>
Line 187 ⟶ 2,708:
9867312 / 1 = 9867312
9867312 / 2 = 4933656
</pre>
===base 16===
{{trans|Haskell}}
<syntaxhighlight lang="zkl">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;
}</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn lcmNs(ns){ ns.reduce(fcn(m,n){ (m*n).abs()/m.gcd(n) }) }</syntaxhighlight>
{{out}}
<pre>
fedcb59726a1348
</pre>
| |||