O'Reilly logo

Elementary Number Theory with Programming by Jeanine Meyer, Marty Lewinter

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

6 NUMBER THEORETIC FUNCTIONS

We examine a class of interesting functions used in number theory.

THE TAU FUNCTION

The function τ(n) counts how many divisors n has. This count includes 1 and n. (τ is a Greek letter and is called “tau.”) The first few values are τ(1) = 1, τ(2) = 2, τ(3) = 2, τ(4) = 3, τ(5) = 2, τ(6) = 4, τ(7) = 2, τ(8) = 4, τ(9) = 3, and τ(10) = 4.

Let n have the prime decomposition images . It is easy to see that m is a divisor of n if and only if images where 0 ≤ c 1 ≤ e 1, 0 ≤ c 2 ≤ e 2, 0 ≤ c 3 ≤ e 3, …, 0 ≤ cr  ≤ er . (This can be stated more tersely as “0 ≤ ci  ≤ ei for i = 1, 2, …, r.”) As an example, the divisors of 233271 = 8 × 9 × 7 = 504 have the form 2 a 3 b 7 c , where a = 0, 1, 2, or 3; b = 0, 1, or 2; and c = 0 or 1. In general, there are e 1 + 1 values ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required