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_{d|n} 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 a|p or a|q. Thus, it follows that a|n. 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 a|p and !(a|q) (a does not divide q), and !(b|p) and b|q. So a uniquely divides p, and b uniquely divides q. Thus, a|n and b|n. So both must be counted under Tau(n). If p and q are relatively prime, there won't exist a k such that k|p and k|q, 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 n1 * n2 ... * ni and the results of Tau(n1) * Tau(n2)... * Tau(ni) = Tau(n1 * n2 ... * ni). 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_{d|n} 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 a|p or a|q. Thus, it follows that a|n. 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 a|p and !(a|q) (a does not divide q), and !(b|p) and b|q. So a uniquely divides p, and b uniquely divides q. Thus, a|n and b|n. So both must be counted under Tau(n). If p and q are relatively prime, there won't exist a k such that k|p and k|q, 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 n1 * n2 ... * ni and the results of Tau(n1) * Tau(n2)... * Tau(ni) = Tau(n1 * n2 ... * ni). Thus, it should be possible to more quickly determine the number of factors for larger n.
0 Comments On This Entry
← April 2021 →
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
2 user(s) viewing
2 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)