Module 11

Computation and properties of a number-theoretical function

1. Introduction

Let the function for be defined by

(1)

where denotes the greatest common divisor of and . We wish an efficient algorithm to compute for arbitrary (and especially for large) .

	3	4	5	6	8	9	12	13	14	16	22	30	31	33	36	37	40
	5	8	9	15	20	21	40	25	39	48	63	135	61	105	168	73	180

An obvious solution to this problem is the application of the Euclidean algorithm to compute the greatest common divisor of and for to .

Starting from the factorisation of we will develop two algorithms and an explicit formula for (1) which will yield a significant reduction in processing time needed to compute , as can be seen from table 1.

	1000	10000	100000	1000000
Application of the Euclidean algorithm	0.3	32	4039	-
Algorithm described in section 3.1	0.3	0.2	2.1	30.0
Computation according to (18)	0.3	0.1	1.1	19.7

Table 1: Run time of several algorithms for the computation of for in seconds, measured on an AMD K6 166MHz.

2. Definitions

(2)

Then we have (with denoting the number of elements of a finite set)

The divisibility of can be expressed in terms of a partial ordering over . Let and let be the corresponding non-reflexive restriction of .

Then we have hence

Note that with respect to , constitutes an upper bound of .

Let be the frequency of occurrence of in the sum of (1) as a greatest common divisor:

(3)

Clearly,

(4)

so the task of computing (1) efficiently is solved when we find an efficient algorithm to compute for all (assuming that the prime factorisation of is given; see section 5).

The example

(5)

will be used throughout the paper to illustrate concepts and ideas.

We will think of as a rectangular -dimensional lattice, where the -th dimension corresponds to the -th prime factor of . The elements () can be considered as coinciding lattice points.

One divides another if and only if lies ``more to the right'' () or ``in the same place'' as () along each coordinate axis , hence (see fig. 1).

Fig. 1: Lattice of all divisors of , see (5),(2)

3. Solutions

3.1. Dynamic Programming

Applying relation (2) to the definition of (3), we obtain

(6)

from which we can derive a recursive algorithm for the computation of with the initialisation .

An algorithm directly based on (6) would not be very efficient, as is clear for , and (see fig. 2). The sets and are marked with dotted and dashed lines respectively. In the course of the computation of and according to (6) the sum of all elements belonging to the set , marked with solid lines, is computed twice.

The recursive algorithm based on equation (6) can be transformed into a more efficient one by dynamic programming. The basic idea for this is the extensive storage and reuse of temporary results.

Fig. 2: Lattice of for n=180, see (5) and fig. 1; Identical sums during the computation of for different according to (6)

Let be the standard basis in , such that .

For arbitrary -tuples and we denote the sum over elements by ,such that .

The sum in equation (6) is split into partial sums ( ) which constitute the temporary results to be stored and reused:

	(7)
	(8)

Note that (7) is equivalent to

(9)

The initialisation for an algorithm based on (9) and (8) is for every .

With these notations we obtain the sum in (6) as follows:

(10)

Furthermore we have

(11)

and consequently

(12)

Figure 3 shows how the sum in equation (6) is split into partial sums for . All elements forming a partial sum () are connected by dotted, dashed and full lines respectively.

To compute , the lattice is traversed in ``descending order'' starting at (for the example (5) this means an order like (2,2,1), (1,2,1), (0,2,1), (2,1,1), (1,1,1), ). In each step of the iteration first , then and finally are computed using (9), (12) and (8).

Fig. 3: Lattice of for ; Splitting of the sum of equation (6) for into partial sums as defined in (9);

3.2. Explicit formula for

The algorithm developed in 3.1 is still not optimal. In the following section we will develop a different and more promising approach to the computation of . First, some preliminary considerations are necessary.

Define . can be considered the set of all vertices of an -dimensional hypercube.

Let the mapping of onto be defined by with

(13)

Note that we have always .

This mapping yields a partitioning of in classes (). The cardinality of the equivalence class of a given is

(14)

as may be derived per induction.

Fig. 4: Partitioning of for

Applying relation (2) to the definition of (3), we obtain Now we can develop stepwise (starting with and incrementing in each step ): With for arbitrary finite sets we have For we finally obtain

	(15)
	(16)

This explicit formula for is mainly determined by ,meaning that

(17)

3.3. Explicit formula for

Applying relation (15) to (4), we can now derive an explicit formula for : Using the previously introduced partitioning of and (14),(17) we obtain: This sum can be rewritten as a product (compare this to (16) and (15)):

(18)

In addition to the derivation we give a self-contained proof of (18). This proof yields an interesting property of , namely that if .

Proof:

First step. Let ( ...prime, ). Then we have: Therefore

Second step. Let with . Then we have With and follows: Let be fixed. Then any two different numbers belong to different residue classes modulo . Hence

Now we have if are relative prime, so that

4. Relation to other number-theoretical functions

Let us recall the following number-theoretical functions:

• - the Moebius function,
• - the Euler function,
• - the identity function.

From our prior investigations we find that . Applying this to (4), we obtain ( denoting the Dirichlet product) and

5. Concluding remarks

Some interesting properties of this function will be outlined in the following.

1. The points with , prime, approximate a line with a slope of when . Similarly the points with , primes form a line with a slope of for . For the slope of the corresponding line tends to 4 (see fig. 5).

Fig. 5: Graph of for with primes.

Fig. 6: Graph of for with primes.

2. The graph of with , primes, can be approximated by the ray pattern of for with primes: For we have , so the graph can be approximated by an overlay of vertically stretched ray patterns of figure 5 (see fig. 6).

We can proceed in this manner with , , primes. Thus the graph of the function is dominated by a ray pattern that can be generated recursively.

3. One could now expect that grows essentially linearly, meaning that there exists a mean slope with

(19)

Some considerations indicate that no such limit exists.

A rough argument is as follows: The probability of two randomly chosen numbers being relatively prime is (cf. [1]). Hence the probability of the greatest common divisor of two randomly chosen numbers being equals . Now we may approximate where is a constant term. Proceeding we have:

(20)

An asymptotically correct approximation of seems to be difficult to prove (in (20) only should be correct). Nevertheless computer experiments show that (20) is a fair approximation and give . The following observations might serve as starting points to further investigation of the function :

• A better approximation of the asymptotical behaviour might be derived examining the previously described recursive structure of the ray patterns.
• Let With (18) we obtain for all : . Thus the function is a normalisation of : This normalised function might yield an interesting mean value () of ,

  (21)

  Computer calculations up to suggest a value of , but the convergence behaviour of the left-hand term of equation (21) is not clear.

  Besides the mean value, the deviation of might be interesting.

• With (18) we have for all , thus obtaining a second possibility to normalise : For a more efficient computation we rewrite this as follows: As with , we are interested in the mean value of (defined similarly to (21)). Computer calculations up to suggest a value of and show a monotonously decreasing convergence as in the case of .

Literature