Consider the following problem where we are given an n-digit decimal (i.e., base 10) number.Suppose we want to check if this number divides 3. In this problem, we assume that1) the modulo function...

Consider the following problem where we are given an n-digit decimal (i.e., base 10) number.

Suppose we want to check if this number divides 3. In this problem, we assume that

1) the modulo function does not take constant time and

2) addition can be done in constant time.

One can prove that a number divides 3 if and only if the sum of its digits divides 3. For example: 1011 divides 3 because the sum of the digits is 1+0+1+1=3 which is divisible by 3. Another example, 2364358 does not divide 3 because 2+3+6+4+3+5+8 = 31 which does not divide 3 (how do we again tell that 31 does not divide 3?)

Let say we only know the base case that 0, 3, 6, 9 divides 3. Any larger number requires checking.

Design a parallel algorithm running in O





(





log








n











×








log





^∗





n)





time to decide if the input number divides 3. Hint: use recursion.








O(log⁡n×log∗⁡n)" role="presentation" id="MathJax-Element-1-Frame" style="display: inline-block; overflow-wrap: normal; max-width: none; max-height: none; min-width: 0px; min-height: 0px; float: none; word-spacing: normal;">