Largest number divisible by its digits: Difference between revisions

Content added Content deleted
m (Modified comment.)
(Changed algorithm for base 10 and added base 16.)
Line 1,114: Line 1,114:


===Base 10===
===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.
Derived from C++ version, with some more optimizations: we check that the first digit (rightmost) is even and we use also an iterator rather than a conversion to string, which speeds up significantly the computation. Result is obtained in about 800 ms.

<lang nim>iterator digits(n: int): int =
<lang nim>type Digit = range[0..9]

iterator digits(n: int64): Digit =
var n = n
var n = n
while true:
while true:
Line 1,122: Line 1,125:
if n == 0: break
if n == 0: break


template isOdd(n: int): bool = (n and 1) != 0
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
func checkDec(num: int): bool =
Magic = 9 * 8 * 7
var hSet: set[range[0..9]]
High = 0x9876432 div Magic * Magic
var firstDigit = true

for n in countdown(High, Magic, Magic):
if n.isLynchBell:
echo n
break</lang>

{{out}}
<pre>9867312</pre>

===Base 16===
This is the same algorithm adapted for base 16. The program runs in about 30ms.

<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:
for d in num.digits:
if firstDigit and d.isOdd: return false
firstDigit = false
if d == 0 or num mod d != 0 or d in hSet:
if d == 0 or num mod d != 0 or d in hSet:
return false
return false
Line 1,135: Line 1,167:
return true
return true


const Magic = 15 * 14 * 13 * 12 * 11
for i in countdown(98764321, 1):
const High = 0xfedcba987654321 div Magic * Magic
if checkDec(i):

echo i
for n in countdown(High, Magic, Magic):
if n.isLynchBell:
echo &"{n:x}"
break</lang>
break</lang>

{{out}}
{{out}}
<pre>fedcb59726a1348</pre>
<pre>
9867312
</pre>


=={{header|Perl}}==
=={{header|Perl}}==