View source for Multiplicative digital root

{{Short description|Mathematical formula}}
{{refimprove|date=October 2019}}

In number theory, the '''multiplicative digital root''' of a [[natural number]] <math>n</math> in a given [[number base]] <math>b</math> is found by [[multiplication|multiplying]] the [[Numerical digit|digits]] of <math>n</math> together, then repeating this operation until only a single-digit remains, which is called the multiplicative digital root of <math>n</math>.<ref name="mathworld1">{{Mathworld|title=Multiplicative Digital Root|urlname=MultiplicativeDigitalRoot}}</ref><ref name="OEIS 31347">{{Cite OEIS|A031347}}</ref> 
The multiplicative digital root for the first few positive integers are:
:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 2, 4, 6, 8, 0, 2, 4, 6, 8, 0, 3, 6, 9, 2, 5, 8, 2, 8, 4, 0. {{OEIS|A031347}} 
Multiplicative digital roots are the multiplicative equivalent of [[digital root]]s.

== Definition ==
Let <math>n</math> be a natural number. We define the '''digit product''' for base <math>b > 1</math> <math>F_{b} : \mathbb{N} \rightarrow \mathbb{N}</math> to be the following:
:<math>F_{b}(n) = \prod_{i=0}^{k - 1} d_i</math>
where <math>k = \lfloor \log_{b}{n} \rfloor + 1</math> is the number of digits in the number in base <math>b</math>, and
:<math>d_i = \frac{n \bmod{b^{i+1}} - n \bmod b^i}{b^i}</math> 
is the value of each digit of the number. A natural number <math>n</math> is a '''multiplicative digital root''' if it is a [[Fixed point (mathematics)|fixed point]] for <math>F_{b}</math>, which occurs if <math>F_{b}(n) = n</math>. 

For example, in base <math>b = 10</math>, 0 is the multiplicative digital root of 9876, as 
: <math>F_{10}(9876) = (9)(8)(7)(6) = 3024</math>
: <math>F_{10}(3024) = (3)(0)(2)(4) = 0</math>
: <math>F_{10}(0) = 0</math>

All natural numbers <math>n</math> are [[periodic point#iterated function|preperiodic points]] for <math>F_{b}</math>, regardless of the base. This is because if <math>n \geq b</math>, then
:<math>n = \sum_{i=0}^{k - 1} d_i b^i</math>
and therefore
:<math>F_{b}(n) = \prod_{i=0}^{k - 1} d_i = d_{k - 1} \prod_{i=0}^{k - 2} d_i < d_{k - 1} b^{k - 1} < \sum_{i=0}^{k - 1} d_i b^i = n</math>
If <math>n < b</math>, then trivially 
:<math>F_{b}(n) = n</math>
Therefore, the only possible multiplicative digital roots are the natural numbers <math>0 \leq n < b</math>, and there are no cycles other than the fixed points of <math>0 \leq n < b</math>. 

==Multiplicative persistence==
The number of iterations <math>i</math> needed for <math>F_{b}^{i}(n)</math> to reach a fixed point is the '''multiplicative [[Persistence of a number|persistence]]''' of <math>n</math>. The multiplicative persistence is undefined if it never reaches a fixed point.

In [[base 10]], it is conjectured that there is no number with a multiplicative persistence <math>i > 11</math>: this is known to be true for numbers <math>n \leq 10^{20585}</math>.<ref name="OEIS 3001" /><ref name="mathworld2">{{Mathworld|title=MultiplicativePersistence|urlname=MultiplicativePersistence}}</ref> The smallest numbers with persistence 0, 1, ... are:
:0, 10, 25, 39, 77, 679, 6788, 68889, 2677889, 26888999, 3778888999, 277777788888899. {{OEIS|A003001}}

The search for these numbers can be sped up by using additional properties of the decimal digits of these record-breaking numbers. These digits must be sorted, and, except for the first two digits, all digits must be 7, 8, or 9. There are also additional restrictions on the first two digits.
Based on these restrictions, the number of candidates for <math>k</math>-digit numbers with record-breaking persistence is only proportional to the square of <math>k</math>, a tiny fraction of all possible <math>k</math>-digit numbers. However, any number that is missing from the sequence above would have multiplicative persistence > 11; such numbers are believed not to exist, and would need to have over 20,000 digits if they do exist.<ref name="OEIS 3001">{{Cite OEIS|A003001}}</ref>

==Extension to negative integers==
The multiplicative digital root can be extended to the negative integers by use of a [[signed-digit representation]] to represent each integer.

==Programming example==
The example below implements the digit product described in the definition above to search for multiplicative digital roots and multiplicative persistences in [[Python (programming language)|Python]].
<syntaxhighlight lang="python">
def digit_product(x: int, b: int) -> int:
    if x == 0:
        return 0
    total = 1
    while x > 1:
        if x % b == 0:
            return 0
        if x % b > 1:
            total = total * (x % b)
        x = x // b
    return total


def multiplicative_digital_root(x: int, b :int) -> int:
    seen = []
    while x not in seen:
        seen.append(x)
        x = digit_product(x, b)
    return x


def multiplicative_persistence(x: int, b: int) -> int:
    seen = []
    while x not in seen:
        seen.append(x)
        x = digit_product(x, b)
    return len(seen) - 1
</syntaxhighlight>

==See also==
* [[Arithmetic dynamics#Other areas in which number theory and dynamics interact|Arithmetic dynamics]]
* [[Digit sum]]
* [[Digital root]]
* [[Sum-product number]]

== References ==
<references/>

== Literature ==
* {{cite book |last=Guy | first=Richard K. | author-link=Richard K. Guy | title=Unsolved problems in number theory | publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 | pages=398–399 }}

== External links ==
* {{youtube|Wim9WJeDTHQ|What's special about 277777788888899? - Numberphile}} (Mar 21, 2019)

{{Classes of natural numbers}}

[[Category:Algebra]]
[[Category:Arithmetic dynamics]]
[[Category:Integer sequences]]
[[Category:Base-dependent integer sequences]]
[[Category:Number theory]]