I came across this thread today, where the OP was attempting to solve a problem regarding counting divisors. Here, the use of a multiplicative function provided means to optimize when counting divisors for larger numbers.
First, let's define two terms multiplicative and completely multiplicative. A multiplicative function f is one such that if n = pq, where p and q are relatively prime, then f(n) = f(p)f(q). A completely multiplicative function f does not rely on the factors of n being relatively prime. So if f is completely multiplicative and n = pq, then f(n) = f(p)f(q).
Let's examine the multiplicative function in question the Tau function, also known as the number of divisors function. It is defined as follows: Tau(n) = Sum_{dn} 1. Another definition is if n = p^{a}q^{b}r^{c} ..., then Tau(n) = (a+1)(b+1)(c+1)....
Before showing how the Tau function is useful here, I want to first detour with an argument for why it is a multiplicative, but not completely multiplicative function. This will provide some insight as to how to use it, as well as indulge the inner mathematician in me.
First, consider n = pq, and ap or aq. Thus, it follows that an. So it stands to reason that if a is counted under Tau(p) or Tau(q), it should be counted once under Tau(n). However, if p and q are not relatively prime, then a will be counted twice under Tau(p) and Tau(q). Thus, it would follow that if p and q are not relatively prime, then Tau(n) != Tau(p)Tau(q), so it isn't completely multiplicative.
Consider if ap and !(aq) (a does not divide q), and !(bp) and bq. So a uniquely divides p, and b uniquely divides q. Thus, an and bn. So both must be counted under Tau(n). If p and q are relatively prime, there won't exist a k such that kp and kq, so no factors of n will be double counted. Thus, by a combinatorial argument, Tau(n) = Tau(p)Tau(q) only when p and q are relatively prime, which satisfies the definition of a multiplicative function.
Applying this to the problem at hand, it is easy to calculate Tau(n) for small n. Multiplying together those relatively prime values n_{1} * n_{2} ... * n_{i} and the results of Tau(n_{1}) * Tau(n_{2})... * Tau(n_{i}) = Tau(n_{1} * n_{2} ... * n_{i}). Thus, it should be possible to more quickly determine the number of factors for larger n.
First, let's define two terms multiplicative and completely multiplicative. A multiplicative function f is one such that if n = pq, where p and q are relatively prime, then f(n) = f(p)f(q). A completely multiplicative function f does not rely on the factors of n being relatively prime. So if f is completely multiplicative and n = pq, then f(n) = f(p)f(q).
Let's examine the multiplicative function in question the Tau function, also known as the number of divisors function. It is defined as follows: Tau(n) = Sum_{dn} 1. Another definition is if n = p^{a}q^{b}r^{c} ..., then Tau(n) = (a+1)(b+1)(c+1)....
Before showing how the Tau function is useful here, I want to first detour with an argument for why it is a multiplicative, but not completely multiplicative function. This will provide some insight as to how to use it, as well as indulge the inner mathematician in me.
First, consider n = pq, and ap or aq. Thus, it follows that an. So it stands to reason that if a is counted under Tau(p) or Tau(q), it should be counted once under Tau(n). However, if p and q are not relatively prime, then a will be counted twice under Tau(p) and Tau(q). Thus, it would follow that if p and q are not relatively prime, then Tau(n) != Tau(p)Tau(q), so it isn't completely multiplicative.
Consider if ap and !(aq) (a does not divide q), and !(bp) and bq. So a uniquely divides p, and b uniquely divides q. Thus, an and bn. So both must be counted under Tau(n). If p and q are relatively prime, there won't exist a k such that kp and kq, so no factors of n will be double counted. Thus, by a combinatorial argument, Tau(n) = Tau(p)Tau(q) only when p and q are relatively prime, which satisfies the definition of a multiplicative function.
Applying this to the problem at hand, it is easy to calculate Tau(n) for small n. Multiplying together those relatively prime values n_{1} * n_{2} ... * n_{i} and the results of Tau(n_{1}) * Tau(n_{2})... * Tau(n_{i}) = Tau(n_{1} * n_{2} ... * n_{i}). Thus, it should be possible to more quickly determine the number of factors for larger n.
0 Comments On This Entry
← November 2015 →
S  M  T  W  T  F  S 

1  2  3  4  5  6  7 
8  9  10  11  12  13  14 
15  16  17  18  19  20  21 
22  23  24  25  26  27  28 
29  30 
My Blog Links
Recent Entries

The Importance of Multiplicative Functions
on Jul 03 2013 08:07 PM
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
