Rosetta Code

Largest number divisible by its digits: Difference between revisions

Page Discussion

Largest number divisible by its digits (view source)

Revision as of 09:56, 15 December 2023

17,777 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
m (Reverted edits by Gerard Schildberger (talk) to last revision by Thundergnat)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(22 intermediate revisions by 12 users not shown)
Line 38:
===Base 10===
{{trans|C++}}
<langsyntaxhighlight lang="11l">F check_dec(num)
Set[Int] st
L(c) String(num)
Line 50:
I check_dec(i)
print(i)
L.break</langsyntaxhighlight>
{{out}}
<pre>
Line 60:
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===
<langsyntaxhighlight lang="360asm">* Largest number divisible by its digits - base10 - 05/05/2020
LANUDIDO CSECT
USING LANUDIDO,R13 base register
Line 151:
CK DS C ck
REGEQU
END LANUDIDO </langsyntaxhighlight>
{{out}}
<pre>
Line 157:
</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}}==
Line 163 ⟶ 232:
 
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.
<langsyntaxhighlight AWKlang="awk"># Usage: gawk -f LARGEST_NUMBER_DIVISIBLE_BY_ITS_DIGITS_10.AWK
BEGIN {
base = 10
Line 199 ⟶ 268:
}
return 1
}</langsyntaxhighlight>
{{out}}
<pre>
Line 212 ⟶ 281:
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).
 
<langsyntaxhighlight AWKlang="awk"># Usage: GAWK -f LARGEST_NUMBER_DIVISIBLE_BY_ITS_DIGITS_16.AWK
BEGIN {
base = 16
Line 265 ⟶ 334:
}
}
}</langsyntaxhighlight>
{{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">
<lang C>
#include<stdio.h>
 
Line 301 ⟶ 409:
return 0;
}
</syntaxhighlight>
</lang>
Output:
<pre>
Line 309 ⟶ 417:
===Base 16===
{{trans|Kotlin}}
<langsyntaxhighlight Clang="c">#include<stdio.h>
#include<string.h>
 
Line 361 ⟶ 469:
}
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 369 ⟶ 477:
 
=={{header|C sharp|C#}}==
{{trans|D}}
 
=== Base 10Both ===
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.
<lang csharp>using System;
<syntaxhighlight lang="csharp">using System.Collections.Generic;
 
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 {
namespace LargestNumber {
class Program {
static bool ChkDec(int num) {
HashSet<int> set = new HashSet<int>();
 
static IEnumerable<long> decline(long min, long max, long stp) {
return num.ToString()
long lmt = .Select(cmin =>/ cstp) -* '0')stp;
for (long .All(di => (dmax !=/ 0stp) &&* (numstp; % di =>= 0)lmt; &&i set.Add(d-= stp));
} yield return i;
}
 
static voidbool MainChkDigs(long number) {
var set = new int result = Enumerable.RangeHashSet<char>(0, 98764321);
return .Reverse()number
.WhereToString(ChkDec)
.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();
Consolesw.WriteLineStop(result);
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);
}
}</langsyntaxhighlight>
{{out}}Timing from Tio.run:
<pre>Base 10 = 9867312</pre> in 13.6382 ms
Base 16 = fedcb59726a1348 in 1.0334308 sec</pre>
 
=={{header|C++}}==
Line 402 ⟶ 599:
 
=== Base 10 ===
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <sstream>
#include <set>
Line 436 ⟶ 633:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>9867312</pre>
Line 449 ⟶ 646:
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.
<langsyntaxhighlight lang="clojure">
(require '[clojure.string :as str]) ;'
(def the_base 16)
Line 543 ⟶ 740:
 
(find_largest_lb)
</syntaxhighlight>
</lang>
 
{{out}}
Line 555 ⟶ 752:
===base 10===
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">magic_number = 9*8*7
div = (9876432 // magic_number) * magic_number
candidates = div.step(to: 0, by: -magic_number)
Line 564 ⟶ 761:
end
 
puts "Largest decimal number is #{res}"</langsyntaxhighlight>
{{out}}<pre>Largest decimal number is 9867312</pre>
 
===base 16===
{{trans|Kotlin}}
<langsyntaxhighlight lang="ruby">def divByAll(num, digits)
digits.all? { |digit| num % digit.to_i(16) == 0 }
end
Line 580 ⟶ 777:
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</langsyntaxhighlight>
{{out}}<pre>Largest hex number is fedcb59726a1348</pre>
 
Line 587 ⟶ 784:
 
=== Base 10 ===
<langsyntaxhighlight lang="d">import std.algorithm.iteration : filter, map;
import std.algorithm.searching : all;
import std.conv : to;
Line 612 ⟶ 809:
.front
.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>9867312</pre>
Line 619 ⟶ 816:
{{Trans|Go}}
===base 10===
<syntaxhighlight lang="delphi">
<lang Delphi>
program Largest_number_divisible_by_its_digits;
 
Line 675 ⟶ 872:
end;
readln;
end.</langsyntaxhighlight>
 
===base 16===
<syntaxhighlight lang="delphi">
<lang Delphi>
program Largest_number_divisible_by_its_digits;
 
Line 743 ⟶ 940:
end;
readln;
end.</langsyntaxhighlight>
=={{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.
<langsyntaxhighlight lang="factor">USING: io kernel math math.combinatorics math.parser math.ranges
sequences tools.time ;
IN: rosetta-code.largest-divisible
Line 766 ⟶ 1,002:
[ largest-divisible print ] time ;
 
MAIN: largest-divisible-demo</langsyntaxhighlight>
{{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>
 
Line 779 ⟶ 1,053:
===base 10===
 
<langsyntaxhighlight lang="go">package main
 
import (
Line 823 ⟶ 1,097:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 832 ⟶ 1,106:
===base 16===
 
<langsyntaxhighlight lang="go">package main
 
import (
Line 882 ⟶ 1,156:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 894 ⟶ 1,168:
Using the analysis provided in the Raku (base 10) example:
 
<langsyntaxhighlight lang="haskell">import Data.List (maximumBy, permutations, delete)
import Data.Ord (comparing)
import Data.Bool (bool)
Line 916 ⟶ 1,190:
-- Checking for divisibility by all digits
(comparing (bool 0 <*> (0 ==) . (`rem` lcmDigits)))
(unDigits <$> concat (permutations <$> sevenDigits))</langsyntaxhighlight>
{{Out}}
Test run from inside the Atom editor:
Line 924 ⟶ 1,198:
===base 16===
First member of a descending sequence of multiples of 360360 that uses the full set of 15 digits when expressed in hex.
<langsyntaxhighlight lang="haskell">import Data.Set (fromList)
import Numeric (showHex)
 
Line 939 ⟶ 1,213:
(print . head)
(filter ((15 ==) . length . fromList) $
(`showHex` []) <$> [upperLimit,upperLimit - lcmDigits .. 1])</langsyntaxhighlight>
Test run from inside the Atom editor:
<pre>"fedcb59726a1348"
Line 946 ⟶ 1,220:
=={{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">
<lang J>
Filter =: (#~`)(`:6)
combinations =: <@#"1~ [: #: [: i. 2 ^ #
Line 955 ⟶ 1,229:
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>
</lang>
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">
<lang J>
NB. 16bfedcba987654321 loses precision and so we need to work in extended data type
 
Line 980 ⟶ 1,254:
16bfedcb59726a1348
 
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
Line 987 ⟶ 1,261:
=== Base 10 ===
Using the analysis provided in the Raku (base 10) example:
<langsyntaxhighlight lang="java">public class LynchBell {
static String s = "";
Line 1,042 ⟶ 1,316:
return true;
}
}</langsyntaxhighlight>
 
{{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}}
Line 1,052 ⟶ 1,364:
=== Base 10 ===
{{trans|C}}
<langsyntaxhighlight lang="julia">function main()
num = 9876432
dif = [4, 2, 2, 2]
Line 1,076 ⟶ 1,388:
end
 
println("Number found: ", main())</langsyntaxhighlight>
 
{{out}}
Line 1,084 ⟶ 1,396:
Makes use of the Raku entry's analysis:
===base 10===
<langsyntaxhighlight lang="scala">// version 1.1.4-3
 
fun Int.divByAll(digits: List<Char>) = digits.all { this % (it - '0') == 0 }
Line 1,102 ⟶ 1,414:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,110 ⟶ 1,422:
 
===base 16===
<langsyntaxhighlight lang="scala">// version 1.1.4-3
 
fun Long.divByAll(digits: List<Char>) =
Line 1,129 ⟶ 1,441:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,137 ⟶ 1,449:
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">function isDivisible(n)
local t = n
local a = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Line 1,165 ⟶ 1,477:
end
end
</syntaxhighlight>
</lang>
{{out}}
<pre>9867312</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
 
===base 10===
<langsyntaxhighlight Mathematicalang="mathematica"> Max@Select[FromDigits/@Rest@Flatten[Permutations/@Subsets[Range@9,9],1],And@@IntegerQ/@(#/IntegerDigits@#)&]</langsyntaxhighlight>
 
{{out}}
<pre>9867312</pre>
9867312
</pre>
 
=={{header|Nanoquery}}==
===Base 10===
{{trans|Java}}
<langsyntaxhighlight lang="nanoquery">s = ""
 
def uniqueDigits(i)
Line 1,238 ⟶ 1,548:
end
i -= 1
end</langsyntaxhighlight>
 
=={{header|Nim}}==
Line 1,245 ⟶ 1,555:
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.
 
<langsyntaxhighlight lang="nim">type Digit = range[0..9]
 
iterator digits(n: int64): Digit =
Line 1,269 ⟶ 1,579:
if n.isLynchBell:
echo n
break</langsyntaxhighlight>
 
{{out}}
Line 1,277 ⟶ 1,587:
This is the same algorithm adapted for base 16. The program runs in about 30ms.
 
<langsyntaxhighlight Nimlang="nim">import strformat
 
type Digit = range[0..15]
Line 1,302 ⟶ 1,612:
if n.isLynchBell:
echo &"{n:x}"
break</langsyntaxhighlight>
 
{{out}}
Line 1,312 ⟶ 1,622:
===Base 10===
 
<langsyntaxhighlight lang="perl">my $step = 9 * 8 * 7; # 504, interval between tests
 
my $initial = int(9876432 / $step) * $step; # largest 7 digit multiple of 504 < 9876432
Line 1,329 ⟶ 1,639:
}
last
}</langsyntaxhighlight>
{{out}}
<pre>Found 9867312 after 18 steps
Line 1,341 ⟶ 1,651:
===Base 16===
 
<langsyntaxhighlight lang="perl">use bigint; # Very slow, but consistent results even with 32-bit Perl
 
my $hex = 'FEDCBA987654321'; # largest possible hex number
Line 1,363 ⟶ 1,673:
}
 
print join "\n", @res;</langsyntaxhighlight>
{{out}}
<pre>Found fedcb59726a1348 after 954460 steps
Line 1,386 ⟶ 1,696:
=== base 10 ===
{{trans|Go}}
<!--<langsyntaxhighlight Phixlang="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>
Line 1,409 ⟶ 1,719:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,418 ⟶ 1,728:
{{trans|Haskell}}
{{libheader|Phix/mpfr}}
<!--<langsyntaxhighlight Phixlang="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>
Line 1,439 ⟶ 1,749:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,447 ⟶ 1,757:
=={{header|Prolog}}==
This will work with any radix, including base 10 and base 16.
<langsyntaxhighlight 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
Line 1,513 ⟶ 1,823:
 
largest_decimal(N) :- bignum(10, N), !.
largest_hex(N, H) :- bignum(16, N), !, sformat(H, '~16r', [N]).</langsyntaxhighlight>
<pre>?- time(largest_decimal(S)).
% 20,043,250 inferences, 3.086 CPU in 3.089 seconds (100% CPU, 6493905 Lips)
Line 1,527 ⟶ 1,837:
Using the insights presented in the preamble to the Raku (base 10) example:
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Largest number divisible by its digits'''
 
from itertools import (chain, permutations)
Line 1,605 ⟶ 1,915:
# MAIN ---
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>9867312</pre>
Line 1,613 ⟶ 1,923:
 
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Largest number divisible by its hex digits'''
 
from functools import (reduce)
Line 1,718 ⟶ 2,028:
# MAIN --
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{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}}==
Line 1,737 ⟶ 2,159:
All these optimizations get the run time to well under 1 second.
 
<syntaxhighlight lang="raku" perl6line>my $magic-number = 9 * 8 * 7; # 504
 
my $div = 9876432 div $magic-number * $magic-number; # largest 7 digit multiple of 504 < 9876432
Line 1,750 ⟶ 2,172:
}
last
}</langsyntaxhighlight>
{{out}}
<pre>Found 9867312
Line 1,765 ⟶ 2,187:
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. The combination of <code>.race</code> with <code>.first</code> lets us utilize concurrency and exit early when the single desired solution is found.
 
<syntaxhighlight lang="raku" perl6line>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;
Line 1,782 ⟶ 2,204:
printf "%s / %s = %s | %d / %2d = %19d\n",
$hexnum, $_, ($target / :16($_)).base(16),
$target, :16($_), $target / :16($_);}</langsyntaxhighlight>
{{out}}
<pre>Found FEDCB59726A1348
Line 1,802 ⟶ 2,224:
FEDCB59726A1348 / 8 = 1FDB96B2E4D4269 | 1147797065081426760 / 8 = 143474633135178345</pre>
=={{header|Red}}==
<langsyntaxhighlight Rebollang="rebol">Red []
t0: now/time/precise ;; measure runtime
lbn: 98764321 + 1 ;; because digit 5 is ruled out, this is the highest 8 digit number
Line 1,825 ⟶ 2,247:
halt
]
</syntaxhighlight>
</lang>
{{Out}}(interpreted version:)<pre>9867312
0:01:38.004
Line 1,836 ⟶ 2,258:
 
The inner &nbsp; '''do''' &nbsp; loop is only executed a score of times; &nbsp; the 1<sup>st</sup> &nbsp; '''if''' &nbsp; statement does the bulk of the eliminations.
<langsyntaxhighlight lang="rexx">/*REXX program finds the largest (decimal) integer divisible by all its decimal digits. */
$= 7 * 8 * 9 /*a # that it must divide the found #. */
t= 0 /*the number of divisibility trials. */
Line 1,853 ⟶ 2,275:
end /*#*/
 
say 'found ' # " (in " t ' trials)' /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|:}}
Timing note: &nbsp; execution time is under &nbsp; '''<sup>1</sup>/<sub>2</sub>''' &nbsp; millisecond &nbsp; (essentially not measurable in the granularity of the REXX timer under Microsoft Windows).
Line 1,864 ⟶ 2,286:
 
Note that &nbsp; '''15&times;14&times;13&times;12&times;11''' &nbsp; is the same as &nbsp; '''13&times;11&times;9&times;8&times;7&times;5'''.
<langsyntaxhighlight lang="rexx">/*REXX program finds the largest hexadecimal integer divisible by all its hex digits. */
numeric digits 20 /*be able to handle the large hex nums.*/
bigH= 'fedcba987654321' /*biggest number possible, hexadecimal.*/
Line 1,885 ⟶ 2,307:
end /*#*/
 
say 'found ' h " (in " t ' trials)' /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|:}}
<pre>
Line 1,892 ⟶ 2,314:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Largest number divisible by its digits
 
Line 1,930 ⟶ 2,352:
ok
next
</syntaxhighlight>
</lang>
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.
<langsyntaxhighlight lang="ruby">magic_number = 9*8*7
div = 9876432.div(magic_number) * magic_number
candidates = div.step(0, -magic_number)
Line 1,948 ⟶ 2,395:
end
 
puts "Largest decimal number is #{res}"</langsyntaxhighlight>
{{out}}<pre>Largest decimal number is 9867312</pre>
===base 16===
{{trans|Crystal from Kotlin}}
<langsyntaxhighlight lang="ruby">def divByAll(num, digits)
digits.all? { |digit| num % digit.to_i(16) == 0 }
end
Line 1,965 ⟶ 2,412:
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</langsyntaxhighlight>
{{out}}<pre>Largest hex number is fedcb59726a1348</pre>
 
Line 1,972 ⟶ 2,419:
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.
 
<langsyntaxhighlight lang="scala">import scala.collection.mutable
 
def largestDecimal: Int = Iterator.from(98764321, -1).filter(chkDec).next
Line 1,978 ⟶ 2,425:
val set = mutable.HashSet[Int]()
num.toString.toVector.map(_.asDigit).forall(d => (d != 0) && (num%d == 0) && set.add(d))
}</langsyntaxhighlight>
 
{{out}}
Line 1,987 ⟶ 2,434:
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.
 
<langsyntaxhighlight lang="scala">import spire.math.SafeLong
import spire.implicits._
 
Line 2,016 ⟶ 2,463:
Iterator.from(base.toInt - 1, -1).map(len => chkBlock(baseDigits.combinations(len))).collect{case Some(n) => n}.next
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,024 ⟶ 2,471:
=={{header|Sidef}}==
===base 10===
<langsyntaxhighlight lang="ruby">func largest_number(base) {
 
var digits = @(base ^.. 1)
Line 2,038 ⟶ 2,485:
}
 
say largest_number(10) #=> 9867312</langsyntaxhighlight>
 
=={{header|VBScript}}==
===base 10===
<langsyntaxhighlight lang="vb">' Largest number divisible by its digits - base10 - VBScript
s=7*8*9 'reasonable assumption
m=9876432 'reasonable assumption
Line 2,062 ⟶ 2,509:
end if
next
wscript.echo i </langsyntaxhighlight>
{{out}}
<pre>
Line 2,071 ⟶ 2,518:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
Function ChkDec(num As Integer) As Boolean
Line 2,088 ⟶ 2,535:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>9867312</pre>
Line 2,095 ⟶ 2,542:
===base 10===
{{trans|Kotlin}}
<langsyntaxhighlight ecmascriptlang="wren">var divByAll = Fn.new { |n, digits| digits.all { |d| n%(d-48) == 0 } }
 
var magic = 9 * 8 * 7
Line 2,121 ⟶ 2,568:
}
i = i - magic
}</langsyntaxhighlight>
 
{{out}}
Line 2,131 ⟶ 2,578:
{{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.
<langsyntaxhighlight ecmascriptlang="wren">var digits = "0123456789abcdef"
var base = 16
var size = 15
Line 2,185 ⟶ 2,632:
var startN = List.filled(size + 1, 0)
for (i in 1..size) startN[i] = i
solve.call(startN)</langsyntaxhighlight>
 
{{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>
 
Line 2,195 ⟶ 2,683:
===base 10===
{{trans|Raku}}
<langsyntaxhighlight lang="zkl">const magic_number=9*8*7; # 504
const div=9876432 / magic_number * magic_number; #largest 7 digit multiple of 504 < 9876432
Line 2,209 ⟶ 2,697:
}
break;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,224 ⟶ 2,712:
===base 16===
{{trans|Haskell}}
<langsyntaxhighlight 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
Line 2,233 ⟶ 2,721:
println(text);
break;
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn lcmNs(ns){ ns.reduce(fcn(m,n){ (m*n).abs()/m.gcd(n) }) }</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,479

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/277870...353331"