Digital root/Multiplicative digital root: Difference between revisions
No edit summary |
(Correction to algorithm) |
||
Line 320: | Line 320: | ||
declare (mdr, mp, p) fixed binary (31); |
declare (mdr, mp, p) fixed binary (31); |
||
mdr = n |
mdr = n; |
||
do mp = 1 by 1 until (p <= 9); |
|||
p = 1; |
|||
do until (mdr = 0); /* Form product of the digits in mdr. */ |
|||
p = mod(mdr, 10) * p; |
|||
mdr= mdr/10; |
|||
end; |
|||
mdr = p; |
|||
end; |
end; |
||
put skip |
put skip data (n, mdr, mp); |
||
end find_mdr; |
end find_mdr; |
||
do n = 123321, 7739, |
do n = 123321, 7739, 893, 899998; |
||
call find_mdr; |
call find_mdr; |
||
end; |
end; |
||
Line 336: | Line 338: | ||
end multiple;</lang> |
end multiple;</lang> |
||
Output: |
Output: |
||
⚫ | |||
<pre> |
|||
N= 7739 MDR= 8 MP= 3; |
|||
N= 893 MDR= 2 MP= 3; |
|||
N= 899998 MDR= 0 MP= 2;</pre> |
|||
⚫ | |||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 13:11, 2 May 2014
You are encouraged to solve this task according to the task description, using any language you may know.
The multiplicative digital root (MDR) and multiplicative persistence (MP) of a number, , is calculated rather like the Digital root except digits are multiplied instead of being added:
- Set to and to .
- While has more than one digit:
- Find a replacement as the multiplication of the digits of the current value of .
- Increment .
- Return (= MP) and (= MDR)
- Task
- Tabulate the MP and MDR of the numbers 123321, 7739, 893, 899998
- Tabulate MDR versus the first five numbers having that MDR, something like:
MDR: [n0..n4] === ======== 0: [0, 10, 20, 25, 30] 1: [1, 11, 111, 1111, 11111] 2: [2, 12, 21, 26, 34] 3: [3, 13, 31, 113, 131] 4: [4, 14, 22, 27, 39] 5: [5, 15, 35, 51, 53] 6: [6, 16, 23, 28, 32] 7: [7, 17, 71, 117, 171] 8: [8, 18, 24, 29, 36] 9: [9, 19, 33, 91, 119]
Show all output on this page.
- References
- Multiplicative Digital Root on Wolfram Mathworld.
- Multiplicative digital root on The On-Line Encyclopedia of Integer Sequences.
D
<lang d>import std.stdio, std.algorithm, std.typecons, std.range, std.conv;
/// Multiplicative digital root. auto mdRoot(in int n) pure /*nothrow*/ {
auto mdr = [n]; while (mdr.back > 9) mdr ~= reduce!q{a * b}(1, mdr.back.text.map!(d => d - '0')); //mdr ~= mdr.back.text.map!(d => d - '0').mul; //mdr ~= mdr.back.reverseDigits.mul; return tuple(mdr.length - 1, mdr.back);
}
void main() {
"Number: (MP, MDR)\n====== =========".writeln; foreach (immutable n; [123321, 7739, 893, 899998]) writefln("%6d: (%s, %s)", n, n.mdRoot[]);
auto table = 10.iota.zip((int[]).init.repeat).assocArray; auto n = 0; while (table.byValue.map!walkLength.reduce!min < 5) { table[n.mdRoot[1]] ~= n; n++; } "\nMP: [n0..n4]\n== ========".writeln; foreach (const mp; table.byKey.array.sort()) writefln("%2d: %s", mp, table[mp].take(5));
}</lang>
- Output:
Number: (MP, MDR) ====== ========= 123321: (3, 8) 7739: (3, 8) 893: (3, 2) 899998: (2, 0) MP: [n0..n4] == ======== 0: [0, 10, 20, 25, 30] 1: [1, 11, 111, 1111, 11111] 2: [2, 12, 21, 26, 34] 3: [3, 13, 31, 113, 131] 4: [4, 14, 22, 27, 39] 5: [5, 15, 35, 51, 53] 6: [6, 16, 23, 28, 32] 7: [7, 17, 71, 117, 171] 8: [8, 18, 24, 29, 36] 9: [9, 19, 33, 91, 119]
Alternative Version
<lang d>import std.stdio, std.algorithm, std.typecons, std.range;
uint digitsProduct(uint n) pure nothrow @nogc {
typeof(return) result = !!n; while (n) { result *= n % 10; n /= 10; } return result;
}
/// Multiplicative digital root. Tuple!(size_t, uint) mdRoot(uint m) pure nothrow {
auto mdr = m .recurrence!((a, n) => a[n - 1].digitsProduct) .until!q{ a <= 9 }(OpenRight.no).array; return tuple(mdr.length - 1, mdr.back);
}
void main() {
"Number: (MP, MDR)\n====== =========".writeln; foreach (immutable n; [123321, 7739, 893, 899998]) writefln("%6d: (%s, %s)", n, n.mdRoot[]);
auto table = 10.iota.zip((int[]).init.repeat).assocArray; auto n = 0; while (table.byValue.map!walkLength.reduce!min < 5) { table[n.mdRoot[1]] ~= n; n++; } "\nMP: [n0..n4]\n== ========".writeln; foreach (const mp; table.byKey.array.sort()) writefln("%2d: %s", mp, table[mp].take(5));
}</lang>
More Efficient Version
<lang d>import std.stdio, std.algorithm, std.range;
/// Multiplicative digital root. uint[2] mdRoot(in uint n) pure nothrow /*@nogc*/ {
uint mdr = n; uint count = 0;
while (mdr > 9) { uint m = mdr; uint digitsMul = !!m; while (m) { digitsMul *= m % 10; m /= 10; } mdr = digitsMul; count++; }
return [count, mdr];
}
void main() {
"Number: [MP, MDR]\n====== =========".writeln; foreach (immutable n; [123321, 7739, 893, 899998]) writefln("%6d: %s", n, n.mdRoot);
auto table = 10.iota.zip((uint[]).init.repeat).assocArray; auto n = 0; while (table.byValue.map!walkLength.reduce!min < 5) { table[n.mdRoot[1]] ~= n; n++; } "\nMP: [n0..n4]\n== ========".writeln; foreach (const mp; table.byKey.array.sort()) writefln("%2d: %s", mp, table[mp].take(5));
}</lang> The output is similar.
Haskell
Note that in the function mdrNums
we don't know in advance how many numbers we'll need to examine to find the first 5 associated with all the MDRs. Using a lazy array to accumulate these numbers allows us to keep the function simple.
<lang haskell>import Control.Arrow
import Data.Array
import Data.LazyArray
import Data.List (unfoldr)
import Data.Tuple
import Text.Printf
-- The multiplicative persistence (MP) and multiplicative digital root (MDR) of -- the argument. mpmdr :: Integer -> (Int, Integer) mpmdr = (length *** head) . span (> 9) . iterate (product . digits)
-- Pairs (mdr, ns) where mdr is a multiplicative digital root and ns are the -- first k numbers having that root. mdrNums :: Int -> [(Integer, [Integer])] mdrNums k = assocs $ lArrayMap (take k) (0,9) [(snd $ mpmdr n, n) | n <- [0..]]
digits :: Integral t => t -> [t] digits 0 = [0] digits n = unfoldr step n
where step k = if k == 0 then Nothing else Just (swap $ quotRem k 10)
printMpMdrs :: [Integer] -> IO () printMpMdrs ns = do
putStrLn "Number MP MDR" putStrLn "====== == ===" sequence_ [printf "%6d %2d %2d\n" n p r | n <- ns, let (p,r) = mpmdr n]
printMdrNums:: Int -> IO () printMdrNums k = do
putStrLn "MDR Numbers" putStrLn "=== =======" let showNums = unwords . map show sequence_ [printf "%2d %s\n" mdr $ showNums ns | (mdr,ns) <- mdrNums k]
main :: IO () main = do
printMpMdrs [123321, 7739, 893, 899998] putStrLn "" printMdrNums 5</lang>
- Output:
Note that the values in the first column of the table are MDRs, as shown in the task's sample output, not MP as incorrectly stated in the task statement and column header.
Number MP MDR ====== == === 123321 3 8 7739 3 8 893 3 2 899998 2 0 MDR Numbers === ======= 0 0 10 20 25 30 1 1 11 111 1111 11111 2 2 12 21 26 34 3 3 13 31 113 131 4 4 14 22 27 39 5 5 15 35 51 53 6 6 16 23 28 32 7 7 17 71 117 171 8 8 18 24 29 36 9 9 19 33 91 119
Icon and Unicon
Works in both languages: <lang unicon>procedure main(A)
write(right("n",8)," ",right("MP",8),right("MDR",5)) every r := mdr(n := 123321|7739|893|899998) do write(right(n,8),":",right(r[1],8),right(r[2],5)) write() write(right("MDR",5)," ","[n0..n4]") every m := 0 to 9 do { writes(right(m,5),": [") every writes(right((m = mdr(n := seq(m))[2],.n)\5,6)) write("]") }
end
procedure mdr(m)
i := 0 while (.m > 10, m := multd(m), i+:=1) return [i,m]
end
procedure multd(m)
c := 1 while m > 0 do c *:= 1(m%10, m/:=10) return c
end</lang>
Output:
->drmdr n MP MDR 123321: 3 8 7739: 3 8 893: 3 2 899998: 2 0 MDR [n0..n4] 0: [ 0 20 30 40 45] 1: [ 1 11 111 1111 11111] 2: [ 2 12 21 26 34] 3: [ 3 13 31 113 131] 4: [ 4 14 22 27 39] 5: [ 5 15 35 51 53] 6: [ 6 16 23 28 32] 7: [ 7 17 71 117 171] 8: [ 8 18 24 29 36] 9: [ 9 19 33 91 119] ->
J
First, we need something to split a number into digits:
<lang J> 10&#.inv 123321 1 2 3 3 2 1</lang>
Second, we need to find their product:
<lang J> */@(10&#.inv) 123321 36</lang>
Then we use this inductively until it converges:
<lang J> */@(10&#.inv)^:a: 123321 123321 36 18 8</lang>
MP is one less than the length of this list, and MDR is the last element of this list:
<lang J> (<:@#,{:) */@(10&#.inv)^:a: 123321 3 8
(<:@#,{:) */@(10&#.inv)^:a: 7739
3 8
(<:@#,{:) */@(10&#.inv)^:a: 893
3 2
(<:@#,{:) */@(10&#.inv)^:a: 899998
2 0</lang>
For the table, we don't need that whole list, we only need the final value. Then use these values to classify the original argument (taking the first five from each group):
<lang J> (5&{./.~ (*/@(10&#.inv)^:_)"0) i.20000 0 10 20 25 30 1 11 111 1111 11111 2 12 21 26 34 3 13 31 113 131 4 14 22 27 39 5 15 35 51 53 6 16 23 28 32 7 17 71 117 171 8 18 24 29 36 9 19 33 91 119</lang>
Note that since the first 10 non-negative integers are single digit values, the first column here doubles as a label (representing the corresponding multiplicative digital root).
PL/I
<lang PL/I>multiple: procedure options (main); /* 29 April 2014 */
declare n fixed binary (31);
find_mdr: procedure;
declare (mdr, mp, p) fixed binary (31);
mdr = n; do mp = 1 by 1 until (p <= 9); p = 1; do until (mdr = 0); /* Form product of the digits in mdr. */ p = mod(mdr, 10) * p; mdr= mdr/10; end; mdr = p; end; put skip data (n, mdr, mp);
end find_mdr;
do n = 123321, 7739, 893, 899998; call find_mdr; end;
end multiple;</lang> Output:
N= 123321 MDR= 8 MP= 3; N= 7739 MDR= 8 MP= 3; N= 893 MDR= 2 MP= 3; N= 899998 MDR= 0 MP= 2;
Python
Python: Inspired by the solution to the Digital root task
<lang python>try:
from functools import reduce
except:
pass
def mdroot(n):
'Multiplicative digital root' mdr = [n] while mdr[-1] > 9: mdr.append(reduce(int.__mul__, (int(dig) for dig in str(mdr[-1])), 1)) return len(mdr) - 1, mdr[-1]
if __name__ == '__main__':
print('Number: (MP, MDR)\n====== =========') for n in (123321, 7739, 893, 899998): print('%6i: %r' % (n, mdroot(n))) table, n = {i: [] for i in range(10)}, 0 while min(len(row) for row in table.values()) < 5: mpersistence, mdr = mdroot(n) table[mdr].append(n) n += 1 print('\nMP: [n0..n4]\n== ========') for mp, val in sorted(table.items()): print('%2i: %r' % (mp, val[:5]))</lang>
- Output:
Number: (MP, MDR) ====== ========= 123321: (3, 8) 7739: (3, 8) 893: (3, 2) 899998: (2, 0) MP: [n0..n4] == ======== 0: [0, 10, 20, 25, 30] 1: [1, 11, 111, 1111, 11111] 2: [2, 12, 21, 26, 34] 3: [3, 13, 31, 113, 131] 4: [4, 14, 22, 27, 39] 5: [5, 15, 35, 51, 53] 6: [6, 16, 23, 28, 32] 7: [7, 17, 71, 117, 171] 8: [8, 18, 24, 29, 36] 9: [9, 19, 33, 91, 119]
Python: Inspired by the more efficient version of D.
Substitute the following function to run twice as fast when calculating mdroot(n) with n in range(1000000). <lang python>def mdroot(n):
count, mdr = 0, n while mdr > 9: m, digitsMul = mdr, 1 while m: m, md = divmod(m, 10) digitsMul *= md mdr = digitsMul count += 1 return count, mdr</lang>
- Output:
(Exactly the same as before).
Racket
<lang racket>#lang racket (define (digital-product n)
(define (inr-d-p m rv) (cond [(zero? m) rv] [else (define-values (q r) (quotient/remainder m 10)) (if (zero? r) 0 (inr-d-p q (* rv r)))])) ; lazy on zero (inr-d-p n 1))
(define (mdr/mp n)
(define (inr-mdr/mp m i) (if (< m 10) (values m i) (inr-mdr/mp (digital-product m) (add1 i)))) (inr-mdr/mp n 0))
(printf "Number\tMDR\tmp~%======\t===\t==~%") (for ((n (in-list '(123321 7739 893 899998))))
(define-values (mdr mp) (mdr/mp n)) (printf "~a\t~a\t~a~%" n mdr mp))
(printf "~%MDR\t[n0..n4]~%===\t========~%") (for ((MDR (in-range 10)))
(define (has-mdr? n) (define-values (mdr mp) (mdr/mp n)) (= mdr MDR)) (printf "~a\t~a~%" MDR (for/list ((_ 5) (n (sequence-filter has-mdr? (in-naturals)))) n)))</lang>
- Output:
Number MDR mp ====== === == 123321 8 3 7739 8 3 893 2 3 899998 0 2 MDR [n0..n4] === ======== 0 (0 10 20 25 30) 1 (1 11 111 1111 11111) 2 (2 12 21 26 34) 3 (3 13 31 113 131) 4 (4 14 22 27 39) 5 (5 15 35 51 53) 6 (6 16 23 28 32) 7 (7 17 71 117 171) 8 (8 18 24 29 36) 9 (9 19 33 91 119)
Tcl
<lang tcl>proc mdr {n} {
if {$n < 0 || ![string is integer $n]} {
error "must be an integer"
} for {set i 0} {$n > 9} {incr i} {
set n [tcl::mathop::* {*}[split $n ""]]
} return [list $i $n]
}</lang> Demonstrating: <lang tcl>puts "Number: MP MDR" puts [regsub -all . "Number: MP MDR" -] foreach n {123321 7739 893 899998} {
puts [format "%6d: %2d %3d" $n {*}[mdr $n]]
} puts ""
- The longEnough variable counts how many roots have at least 5 values accumulated for them
for {set i [set longEnough 0]} {$longEnough < 10} {incr i} {
set root [lindex [mdr $i] 1] if {[llength [lappend accum($root) $i]] == 5} {incr longEnough}
} puts "MDR: \[n\u2080\u2026n\u2084\]" puts [regsub -all . "MDR: \[n\u2080\u2026n\u2084\]" -] for {set i 0} {$i < 10} {incr i} {
puts [format "%3d: (%s)" $i [join [lrange $accum($i) 0 4] ", "]]
}</lang>
- Output:
Number: MP MDR -------------- 123321: 3 8 7739: 3 8 893: 3 2 899998: 2 0 MDR: [n₀…n₄] ------------ 0: (0, 10, 20, 25, 30) 1: (1, 11, 111, 1111, 11111) 2: (2, 12, 21, 26, 34) 3: (3, 13, 31, 113, 131) 4: (4, 14, 22, 27, 39) 5: (5, 15, 35, 51, 53) 6: (6, 16, 23, 28, 32) 7: (7, 17, 71, 117, 171) 8: (8, 18, 24, 29, 36) 9: (9, 19, 33, 91, 119)
zkl
<lang zkl>fcn mdroot(n){ // Multiplicative digital root
mdr := List(n); while (mdr[-1] > 9){ mdr.append(mdr[-1].toString().apply("toInt").reduce('*,1)); } return(mdr.len() - 1, mdr[-1]);
}</lang> <lang zkl>fcn mdroot(n){
count:=0; mdr:=n; while(mdr > 9){ m:=mdr; digitsMul:=1; while(m){
reg md; m,md=m.divr(10); digitsMul *= md;
} mdr = digitsMul; count += 1; } return(count, mdr);
}</lang> <lang zkl>println("Number: (MP, MDR)\n======= ========="); foreach n in (T(123321, 7739, 893, 899998))
{ println("%7,d: %s".fmt(n, mdroot(n))) }
table:=D([0..9].zip(fcn{List()}).walk()); // dictionary(0:List, 1:List, ...) n :=0; while(table.values.filter(fcn(r){r.len()<5})){ // until each entry has >=5 values
mpersistence, mdr := mdroot(n); table[mdr].append(n); n += 1;
} println("\nMP: [n0..n4]\n== ========"); foreach mp in (table.keys.sort()){
println("%2d: %s".fmt(mp, table[mp][0,5])); //print first five values
}</lang>
- Output:
Number: (MP, MDR) ======= ========= 123,321: L(3,8) 7,739: L(3,8) 893: L(3,2) 899,998: L(2,0) MP: [n0..n4] == ======== 0: L(0,10,20,25,30) 1: L(1,11,111,1111,11111) 2: L(2,12,21,26,34) 3: L(3,13,31,113,131) 4: L(4,14,22,27,39) 5: L(5,15,35,51,53) 6: L(6,16,23,28,32) 7: L(7,17,71,117,171) 8: L(8,18,24,29,36) 9: L(9,19,33,91,119)