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>type Digit = range[0..9] |
|||
⚫ | |||
var n = n |
var n = n |
||
while true: |
while true: |
||
Line 1,122: | Line 1,125: | ||
if n == 0: break |
if n == 0: break |
||
func isLynchBell(num: int64): bool = |
|||
⚫ | |||
for d in num.digits: |
|||
if d == 0 or num mod d != 0 or d in hSet: |
|||
⚫ | |||
hSet.incl(d) |
|||
return true |
|||
const |
|||
⚫ | |||
Magic = 9 * 8 * 7 |
|||
⚫ | |||
High = 0x9876432 div Magic * Magic |
|||
var firstDigit = true |
|||
⚫ | |||
if n.isLynchBell: |
|||
⚫ | |||
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 |
|||
⚫ | |||
var hSet: set[Digit] |
|||
for d in num.digits: |
for d in num.digits: |
||
⚫ | |||
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 |
|||
⚫ | |||
const High = 0xfedcba987654321 div Magic * Magic |
|||
if checkDec(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}}== |