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

13,339 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Added Algol 68)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(15 intermediate revisions by 8 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 159:
 
=={{header|ALGOL 68}}==
Base 10, {{Trans|Kotlin}}.
{{Trans|Kotlin}}... largely
<lang algol68>BEGIN # find the largest decimal integer with unique digits, divisible by its digits #
<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 iINT MOD 10d1 = 0i THENMOD SKIP # can't end in '0' #10;
ELIF STRING s = whole( i,d1 0= );0
char in string( "0", NIL, s ) THEN SKIP # can't containend in '0' #
ELIF char[ in0 string(: "5",9 NIL,]BOOL sdigits ) THEN SKIP # can't contain 5 #:=
ELIF [ 1 : 9 ]BOOL digits := []BOOL( FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE )[ @ 0 ];
BOOL unique := TRUE;
FORINT c posv FROM LWB s TO UPB s := i OVER 10;
WHILE INT c = ABS sdigits[ c posd1 ] - ABS:= "0"TRUE;
WHILE v > 0 AND unique := NOT digits[ c ]DO
DO INT d = v MOD 10;
digits[v cOVERAB ] := TRUE10;
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
Line 188 ⟶ 193:
FI
OD
END</langsyntaxhighlight>
{{out}}
<pre>
Line 196 ⟶ 201:
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">lynchBell?: function [num][
hset: new []
loop digits num 'd [
Line 216 ⟶ 221:
break
]
]</langsyntaxhighlight>
 
{{out}}
Line 227 ⟶ 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 263 ⟶ 268:
}
return 1
}</langsyntaxhighlight>
{{out}}
<pre>
Line 276 ⟶ 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 329 ⟶ 334:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 338 ⟶ 343:
{{trans|FreeBASIC}}
===base 10===
<syntaxhighlight lang="basic256">
<lang BASIC256>
arraybase 1
for n = 9867000 to 9867400
Line 367 ⟶ 372:
next n
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 377 ⟶ 382:
===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 404 ⟶ 409:
return 0;
}
</syntaxhighlight>
</lang>
Output:
<pre>
Line 412 ⟶ 417:
===Base 16===
{{trans|Kotlin}}
<langsyntaxhighlight Clang="c">#include<stdio.h>
#include<string.h>
 
Line 464 ⟶ 469:
}
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 472 ⟶ 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 505 ⟶ 599:
 
=== Base 10 ===
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <sstream>
#include <set>
Line 539 ⟶ 633:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>9867312</pre>
Line 552 ⟶ 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 646 ⟶ 740:
 
(find_largest_lb)
</syntaxhighlight>
</lang>
 
{{out}}
Line 658 ⟶ 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 667 ⟶ 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 683 ⟶ 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 690 ⟶ 784:
 
=== Base 10 ===
<langsyntaxhighlight lang="d">import std.algorithm.iteration : filter, map;
import std.algorithm.searching : all;
import std.conv : to;
Line 715 ⟶ 809:
.front
.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>9867312</pre>
Line 722 ⟶ 816:
{{Trans|Go}}
===base 10===
<syntaxhighlight lang="delphi">
<lang Delphi>
program Largest_number_divisible_by_its_digits;
 
Line 778 ⟶ 872:
end;
readln;
end.</langsyntaxhighlight>
 
===base 16===
<syntaxhighlight lang="delphi">
<lang Delphi>
program Largest_number_divisible_by_its_digits;
 
Line 846 ⟶ 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 869 ⟶ 1,002:
[ largest-divisible print ] time ;
 
MAIN: largest-divisible-demo</langsyntaxhighlight>
{{out}}
<pre>
Line 875 ⟶ 1,008:
Running time: 0.07224931499999999 seconds
</pre>
 
 
=={{header|FreeBASIC}}==
{{trans|Ring}}
===base 10===
<langsyntaxhighlight lang="freebasic">
For n As Integer = 9867000 To 9867400
Dim As Integer numbers(9)
Line 909 ⟶ 1,041:
Next n
Sleep
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 921 ⟶ 1,053:
===base 10===
 
<langsyntaxhighlight lang="go">package main
 
import (
Line 965 ⟶ 1,097:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 974 ⟶ 1,106:
===base 16===
 
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,024 ⟶ 1,156:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,036 ⟶ 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 1,058 ⟶ 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 1,066 ⟶ 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 1,081 ⟶ 1,213:
(print . head)
(filter ((15 ==) . length . fromList) $
(`showHex` []) <$> [upperLimit,upperLimit - lcmDigits .. 1])</langsyntaxhighlight>
Test run from inside the Atom editor:
<pre>"fedcb59726a1348"
Line 1,088 ⟶ 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 1,097 ⟶ 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 1,122 ⟶ 1,254:
16bfedcb59726a1348
 
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
Line 1,129 ⟶ 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,184 ⟶ 1,316:
return true;
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,194 ⟶ 1,326:
 
The following is based on the [[#awk|awk]] entry, for which see the rationale.
<syntaxhighlight lang="jq">
<lang jq>
def has_unique_digits:
tostring
Line 1,222 ⟶ 1,354:
 
task
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,232 ⟶ 1,364:
=== Base 10 ===
{{trans|C}}
<langsyntaxhighlight lang="julia">function main()
num = 9876432
dif = [4, 2, 2, 2]
Line 1,256 ⟶ 1,388:
end
 
println("Number found: ", main())</langsyntaxhighlight>
 
{{out}}
Line 1,264 ⟶ 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,282 ⟶ 1,414:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,290 ⟶ 1,422:
 
===base 16===
<langsyntaxhighlight lang="scala">// version 1.1.4-3
 
fun Long.divByAll(digits: List<Char>) =
Line 1,309 ⟶ 1,441:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,317 ⟶ 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,345 ⟶ 1,477:
end
end
</syntaxhighlight>
</lang>
{{out}}
<pre>9867312</pre>
Line 1,352 ⟶ 1,484:
 
===base 10===
<langsyntaxhighlight Mathematicalang="mathematica"> Max@Select[FromDigits/@Rest@Flatten[Permutations/@Subsets[Range@9,9],1],And@@IntegerQ/@(#/IntegerDigits@#)&]</langsyntaxhighlight>
 
{{out}}
Line 1,360 ⟶ 1,492:
===Base 10===
{{trans|Java}}
<langsyntaxhighlight lang="nanoquery">s = ""
 
def uniqueDigits(i)
Line 1,416 ⟶ 1,548:
end
i -= 1
end</langsyntaxhighlight>
 
=={{header|Nim}}==
Line 1,423 ⟶ 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,447 ⟶ 1,579:
if n.isLynchBell:
echo n
break</langsyntaxhighlight>
 
{{out}}
Line 1,455 ⟶ 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,480 ⟶ 1,612:
if n.isLynchBell:
echo &"{n:x}"
break</langsyntaxhighlight>
 
{{out}}
Line 1,490 ⟶ 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,507 ⟶ 1,639:
}
last
}</langsyntaxhighlight>
{{out}}
<pre>Found 9867312 after 18 steps
Line 1,519 ⟶ 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,541 ⟶ 1,673:
}
 
print join "\n", @res;</langsyntaxhighlight>
{{out}}
<pre>Found fedcb59726a1348 after 954460 steps
Line 1,564 ⟶ 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,587 ⟶ 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,596 ⟶ 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,617 ⟶ 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,625 ⟶ 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,691 ⟶ 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,705 ⟶ 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,783 ⟶ 1,915:
# MAIN ---
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>9867312</pre>
Line 1,791 ⟶ 1,923:
 
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Largest number divisible by its hex digits'''
 
from functools import (reduce)
Line 1,896 ⟶ 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,915 ⟶ 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,928 ⟶ 2,172:
}
last
}</langsyntaxhighlight>
{{out}}
<pre>Found 9867312
Line 1,943 ⟶ 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,960 ⟶ 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,980 ⟶ 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 2,003 ⟶ 2,247:
halt
]
</syntaxhighlight>
</lang>
{{Out}}(interpreted version:)<pre>9867312
0:01:38.004
Line 2,014 ⟶ 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 2,031 ⟶ 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 2,042 ⟶ 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 2,063 ⟶ 2,307:
end /*#*/
 
say 'found ' h " (in " t ' trials)' /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|:}}
<pre>
Line 2,070 ⟶ 2,314:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Largest number divisible by its digits
 
Line 2,108 ⟶ 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 2,126 ⟶ 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 2,143 ⟶ 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 2,150 ⟶ 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 2,156 ⟶ 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 2,165 ⟶ 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,194 ⟶ 2,463:
Iterator.from(base.toInt - 1, -1).map(len => chkBlock(baseDigits.combinations(len))).collect{case Some(n) => n}.next
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,202 ⟶ 2,471:
=={{header|Sidef}}==
===base 10===
<langsyntaxhighlight lang="ruby">func largest_number(base) {
 
var digits = @(base ^.. 1)
Line 2,216 ⟶ 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,240 ⟶ 2,509:
end if
next
wscript.echo i </langsyntaxhighlight>
{{out}}
<pre>
Line 2,249 ⟶ 2,518:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
Function ChkDec(num As Integer) As Boolean
Line 2,266 ⟶ 2,535:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>9867312</pre>
Line 2,273 ⟶ 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,299 ⟶ 2,568:
}
i = i - magic
}</langsyntaxhighlight>
 
{{out}}
Line 2,309 ⟶ 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,363 ⟶ 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,373 ⟶ 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,387 ⟶ 2,697:
}
break;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,402 ⟶ 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,411 ⟶ 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/277877...353331"