Derived Sequences

G. L. Cohen Department of Mathematical Sciences, Faculty of Science University of Technology, Sydney PO Box 123, Broadway, NSW 2007 Australia

and

D. E. Iannucci Division of Science and Mathematics University of the Virgin Islands St. Thomas, VI 00802 USA

Abstract

We define a multiplicative arithmetic function D by assigning D(p^{a}) = ap^{a−1}, when p is a prime and a is a positive integer, and, for n ≥ 1, we set D^{0}(n) = n and D^{k}(n) = D(D^{k−1}(n)) when k ≥ 1. We term {D^{k}(n)}_{k=0}^{∞} the derived sequence of n. We show that all derived sequences of n < 1.5 · 10^{10} are bounded, and that the density of those n ∈ ℕ with bounded derived sequences exceeds 0.996, but we conjecture nonetheless the existence of unbounded sequences. Known bounded derived sequences end (effectively) in cycles of lengths only 1 to 6, and 8, yet the existence of cycles of arbitrary length is conjectured. We prove the existence of derived sequences of arbitrarily many terms without a cycle.

1 Introduction

Define a multiplicative arithmetic function D by assigning

D(p^{a}) = ap^{a−1},  (1)

when p is a prime and a is a positive integer. The multiplicativity implies D(1) = 1 and, for example, D(p^{a}q^{b}) = abp^{a−1}q^{b−1}, where q^{b} is another prime power, q ≠ p. It is only the shape of the definition (1) that encourages us to use freely terms from calculus. (Our derivatives have no relationship to an earlier use of the term, in Apostol [1], for example.) Writing D^{0}(n) = n and D^{k}(n) = D(D^{k−1}(n)) for k ≥ 1 and any positive integer n, we call {D^{k}(n)}_{k=0}^{∞}, or {n, D(n), D^{2}(n), D^{3}(n), … }, the derived sequence of n, and denote this by D(n). We refer to D^{k}(n) for k ≥ 1 as the kth derivative of n and we refer to D^{j}(n) for 0 ≤ j < k as integrals of D^{k}(n).

If n = ∏_{i=1}^{w} p_{i}^{a_{i}} is the prime decomposition of n then the definition of D(n) may be given differently as

D(n) = \frac{n}{C(n)} τ (\frac{n}{C(n)}) ,

where τ(n) = ∏_{i=1}^{w}(a_{i} + 1) is the number of divisors of n and C(n) = ∏_{i=1}^{w} p_{i} is the core of n.

Our intention is to initiate a study of the ultimate behaviour of derived sequences. Different forms of ultimate behaviour are indicated in the following examples:

D(5^{2}17 · 37) = \{5^{2}17 · 37, 2 · 5, \underline{1}, … \},  (2)
D(2^{25}) = \{2^{25}, 2^{24}5^{2}, 2^{27}3 · 5, 2^{26}3^{3}, \underline{2^{26}3^{3}13}, … \},  (3)
D(13^{16)} = \{13^{16}, 2^{4}13^{15}, 2^{5}3 · 5 · 13^{14}, 2^{5}5 · 7 · 13^{13}, \underline{2^{4}5 · 13^{13}}, \underline{2^{5}13^{13}}, … \},  (4)
D(2^{32}) = \{2^{32}, 2^{36}, \underline{2^{37}3^{2}}, \underline{2^{37}3 · 37}, \underline{2^{36}37}, … \},  (5)
D(3^{8}) = \{3^{8}, \underline{2^{3}3^{7}}, \underline{2^{2}3^{7} · 7}, \underline{2^{2}3^{6} · 7}, \underline{2^{3}3^{6}}, … \}.  (6)

The underlined terms in each case form cycles. Precisely: if

D(n) = {…, D^{j}(n), D^{j+1}(n), …, D^{j+k−1}(n), D^{j+k}(n), … }

and D^{j+k}(n) = D^{j}(n), where j ≥ 0 and k ≥ 1 is the smallest integer with this property, then D^{j}(n), D^{j+1}(n), …, D^{j+k−1}(n) is a derived k-cycle, which, if we need to, we describe as being arrived at in j + k iterations of D. For example, in (3), D(2^{26}3^{3}13) = 2^{26}3^{3}13, and, in (6), D(2^{3}3^{6}) = 2^{3}3^{7}. We have 1-cycles in (2) and (3), and 2-, 3- and 4-cycles in (4), (5) and (6), respectively. The 3-cycle in (5) is arrived at in four iterations of D. We will refer to the element of a 1-cycle as a fixed point of D.

It is not known whether the ultimate behaviour of D(n) is a cycle for all n, or whether, for some n, D^{k}(n) increases without bound as k increases. We will show, however, that cycles result for more than 99.5% of values of n. Many iterations of D may be required before a cycle is reached, if that is to be the case: for example, D(5^{63}) arrives in 531 iterations at the fixed point 2^{1403}3^{329}5^{106}7^{15}23 · 47 · 53 · 61. Our most impressive example is D(17^{35}19^{39}), which, in 443507 iterations of D, arrives at the fixed point

2^{4318267}3^{1370053}5^{525835}7^{159649}11^{33429}13^{20597}17^{1037}19^{1349}23^{299}31^{31}
· 43 · 61 · 71^{2}479 · 1013 · 22807 · 105167 · 1370053 · 4318267.

Other instances of sequences of iterated arithmetic functions are given by Guy [3]. Iteration of the function σ(n) − n, for example, where σ is the sum-of-divisors function, has been studied extensively. The situation is similar: there is an eventual iterate equal to 1, or there is eventually a cycle, or the ultimate behaviour is unknown. Iteration of the function σ itself was studied in Cohen and te Riele [2].

In the following, p, q, r and t, with and without subscripts, denote prime numbers, and s, with and without subscripts, denotes a squarefree number. We include 1 as a squarefree number. Other letters denote positive integers, unless specified otherwise.

2 General results

We are able to give a number of results of a general nature.

First, it is easy to see that n is a fixed point of D if and only if either n = 1 or n = ∏_{i=1}^{w} p_{i}^{a_{i}}, where ∏_{i=1}^{w} p_{i} = ∏_{i=1}^{w} a_{i}. More generally, we have Proposition 1, below. For simplicity of notation, we will write n = ∏ p_{0}^{a_{0}} and D(n) = ∏ p_{1}^{a_{1}} as shorthand for n = ∏_{i=1}^{w_{0}} p_{i0}^{a_{i0}} and D(n) = ∏_{i=1}^{w_{1}} p_{i1}^{a_{i1}}, and so on.

Proposition 1 Suppose n > 1 and write n = ∏ p_{0}^{a_{0}}, D(n) = ∏ p_{1}^{a_{1}}, …, D^{k−1}(n) = ∏ p_{k−1}^{a_{k−1}}. We have D^{k}(n) = n if and only if ∏ p_{0} ∏ p_{1} ⋯ ∏ p_{k−1} = ∏ a_{0} ∏ a_{1} ⋯ ∏ a_{k−1}.

Proof. Note that

n = ∏ p_{0}^{a_{0}},
D(n) = ∏ p_{1}^{a_{1}}, so ∏ p_{1}^{a_{1}} = ∏ a_{0}p_{0}^{a_{0}−1},
D^{2}(n) = ∏ p_{2}^{a_{2}}, so ∏ p_{2}^{a_{2}} = ∏ a_{1}p_{1}^{a_{1}−1},
⋮
D^{k−1}(n) = ∏ p_{k−1}^{a_{k−1}}, so ∏ p_{k−1}^{a_{k−1}} = ∏ a_{k−2}p_{k−2}^{a_{k−2}−1}.

If, further, D^{k}(n) = n then ∏ p_{0}^{a_{0}} = ∏ a_{k−1}p_{k−1}^{a_{k−1}−1}, and we have

∏ p_{0} ∏ p_{1} ⋯ ∏ p_{k−1} = \frac{∏ p_{1}^{a_{1}}}{∏ p_{0}^{a_{0}−1}} \frac{∏ p_{2}^{a_{2}}}{∏ p_{1}^{a_{1}−1}} ⋯ \frac{∏ p_{k−1}^{a_{k−1}}}{∏ p_{k−2}^{a_{k−2}−1}} \frac{∏ p_{0}^{a_{0}}}{∏ p_{k−1}^{a_{k−1}−1}}
= ∏ a_{0} ∏ a_{1} ⋯ ∏ a_{k−1}.

The converse is also clear. □

It does not seem to be easy to use this result to determine cycles, but we can at least identify those numbers which have a derivative equal to the fixed point 1 of D:

Proposition 2 The integer n > 1 has

• first derivative 1 if n = s,

• second derivative 1 if n = p^{2}s where p > 2 and p ∤ s,

• third derivative 1 if n = p^{3}s where p > 3 and p ∤ s, or n = p^{3}q^{2}s where p > 3, q > 3, p ≠ q and (s, pq) = 1.

There are no other situations in which n has a derivative equal to 1.

The proof is a matter of recognising those situations in which 2^{2} or 3^{3} might arise as exact factors of terms in the derived sequence, and avoiding them since these factors will persist in subsequent differentiations.

It is also a matter of checking that 2- and 3-cycles are obtained in the following situations.

Proposition 3 For any p,

• if p^{2} + 1 is squarefree, then D(p^{p^{2}+1}) = \{\underline{p^{p^{2}+1}}, \underline{(p^{2} + 1)p^{p^{2}}}, … \},

• if p^{3} + 2 and p^{3} + 1 are squarefree, then

D(p^{p^{3}+2}) = \{\underline{p^{p^{3}+2}}, \underline{(p^{3} + 2)p^{p^{3}+1}}, \underline{(p^{3} + 1)p^{p^{3}}}, … \}.

The underlined terms are cycles. Notice that 13, 37, 61, …, are primes p such that p^{3} + 2 and p^{3} + 1 are squarefree. Certainly, 2- and 3-cycles may arise in other ways, as in the examples (4) and (5).

We can also give a general instance that leads to a 4-cycle:

Proposition 4 Let s be such that s ≡ 2 (mod 3), 4s−1 is squarefree and 2s−1 is squarefree. Then D(3^{4s}) results in a 4-cycle.

Proof. Write 4s − 1 = s_{1} and 2s − 1 = 3s_{2} (where 3 ∤ s_{2}). If s is odd, then

D(3^{4s}) = \{3^{4s}, 2^{2}3^{4s−1}s, \underline{2^{2}3^{4s−2}s_{1}}, \underline{2^{3}3^{4s−2}s_{2}}, \underline{2^{3}3^{4s−1}s_{2}}, \underline{2^{2}3^{4s−1}s_{1}}, … \},

while if s is even, then

D(3^{4s}) = \{3^{4s}, 2^{3}3^{4s−1}(s/2), \underline{2^{2}3^{4s−1}s_{1}}, \underline{2^{2}3^{4s−2}s_{1}}, \underline{2^{3}3^{4s−2}s_{2}}, \underline{2^{3}3^{4s−1}s_{2}}, … \}.

The underlined terms in each case are 4-cycles (in fact, algebraically, the same 4-cycle). □

The smallest permissible value of s in this proposition is s = 2, as in the example (6); thereafter, s may take the values 11, 17, 26, 29, 35, ….

Other examples of 4-cycles are not difficult to find, and we need not always start at a prime power. For example:

D(2^{10}3^{10}) = \{2^{10}3^{10}, \underline{2^{11}3^{9}5^{2}}, \underline{2^{11}3^{10}5 · 11}, \underline{2^{11}3^{9}5 · 11}, \underline{2^{10}3^{10} · 11}, … \}.

It was initially more difficult to find examples of derived k-cycles for k > 4, but, having found a few, patterns were detected suggesting infinite families of these. Some are described in the following propositions. (We have other, more general, examples.)

Proposition 5 Let s be such that (s, 2 · 3 · 5 · 47) = 1, and suppose (s_{1}, 5 · 23 · 47) = 1, where s_{1} = (3s − 1)/2. Put n = 2^{3s}3^{45}5^{5}23s_{1}. Then n, D(n), …, D^{4}(n) is a 5-cycle.

In this, s may take the values 1, 13, 23, 29, 41, 53, 61, . . ..

Proposition 6 (a) Let s be such that (s, 2·3·5·7·53) = 1, and suppose (s_{1}, 5·53·107) = 1, where s_{1} = 6s + 1. Put n = 2^{6s}3^{105}5^{6}7s_{1}. Then n, D(n), …, D^{5}(n) is a 6-cycle.

(b) Let s be such that (s, 2 · 3 · 5 · 13 · 43) = 1, and suppose (s_{1}, 7 · 13 · 43 · 131) = 1, where s_{1} = 30s + 1. Put n = 2^{30s}3^{129}5^{6}7 · 43s_{1}. Then n, D(n), …, D^{5}(n) is a 6-cycle.

Proof. As usual, the proofs are a matter of straightforward verification. We will demonstrate this in the case of Proposition 6(a). We have

n = 2^{6s}3^{105}5^{6}7s_{1},
D(n) = 2^{6s+1}3^{107}5^{6}7s,  since (s_{1}, 2 · 3 · 5 · 7) = 1,
D^{2}(n) = 2^{6s+1}3^{107}5^{5}107s_{1}, since (s, 2 · 3 · 5 · 7) = 1,
D^{3}(n) = 2^{6s}3^{106}5^{5}107s_{1}, since (s_{1}, 2 · 3 · 5 · 107) = 1,
D^{4}(n) = 2^{6s+1}3^{106}5^{5}53s, since (s_{1}, 2 · 3 · 5 · 107) = 1,
D^{5}(n) = 2^{6s+1}3^{105}5^{5}53s_{1}, since (s, 2 · 3 · 5 · 53) = 1,
D^{6}(n) = 2^{6s}3^{105}5^{6}7s_{1},  since (s_{1}, 2 · 3 · 5 · 53) = 1.

But D^{6}(n) = n. We have also used the fact that s and s_{1} are squarefree. □

In Proposition 6(a), we may have s = 11, 13, 17, 23, 31, 37, 41, . . .. In Proposition 6(b), s may take the values 1, 7, 11, 19, 23, 37, 41, ….

Proposition 7 Let s be such that s ≡ 7 (mod 10) and (s, 3 · 23 · 31 · 47 · 103 · 311) = 1, and suppose (s_{1}, 3 · 5 · 31 · 47 · 103 · 311) = 1, where s_{1} = (2s + 1)/5. Put n = 2^{2s}3^{311}5^{46}103s_{1}. Then n, D(n), …, D^{7}(n) is an 8-cycle.

In this, s may take the values 17, 107, 167, 197, 227, . . .. Proposition 7 was found by observing that D(5^{13}29^{54}) arrives in 428 iterations of D at the 8-cycle beginning with 29^{29}n, with s = 557. Two other examples of 8-cycles turned up in our searches:

2^{159}3^{16725}5^{5}79 · 8363,  2^{158}3^{16726}5^{7}53 · 223,
2^{159}3^{16725}5^{6}7 · 79 · 8363,  2^{159}3^{16727}5^{7}53 · 223,
2^{158}3^{16727}5^{6}7 · 43 · 53 · 389, 2^{159}3^{16727}5^{5}43 · 79 · 389,
2^{158}3^{16727}5^{5}43 · 53 · 389,  2^{158}3^{16726}5^{5}43 · 79 · 389,

and

2^{87}3^{149325}5^{5}43 · 197 · 379,  2^{86}3^{149326}5^{7}11 · 29 · 181,
2^{87}3^{149325}5^{6}7 · 43 · 197 · 379, 2^{87}3^{149327}5^{7}11 · 29 · 181,
2^{86}3^{149327}5^{6}7 · 29 · 31 · 4817, 2^{87}3^{149327}5^{5}31 · 43 · 4817,
2^{86}3^{149327}5^{5}29 · 31 · 4817,  2^{86}3^{149326}5^{5}31 · 43 · 4817.

These occur in D(3^{16695}) and D(3^{149319}), respectively. It is not difficult to determine a twoparameter family, containing general exponents on 2 and 3, that includes both of these 8-cycles.

We have no examples of derived k-cycles with k = 7 or k > 8.

3 Bounded derived sequences

We have two results on the number of bounded derived sequences, the first resulting largely from a direct search, the second of a much more theoretical nature.

Proposition 8 For all n < 1.5 · 10^{10}, the derived sequence D(n) is bounded.

Proof. The proof involved a direct incremental investigation of all numbers n = ∏_{i=1}^{w} p_{i}^{a_{i}} < 1.5 · 10^{10} for which ∑_{i=1}^{w}(a_{i} − 1) ≥ 8. (An initial factorisation of each n determined whether this condition was satisfied.) In all cases, D(n) resulted in a cycle. We showed also that the same is true of all n with ∑_{i=1}^{w}(a_{i} − 1) ≤ 7. For example, suppose n = p^{3}q^{2}s, where p ≠ q and (s, pq) = 1. If p and q are both greater than 3, then D(n) = 2 · 3p^{2}q, D^{2}(n) = 2p and D^{3}(n) = 1 (or use Proposition 2); then the numbers p^{3}2^{2}s (p > 3), p^{3}3^{2}s (p > 3), 2^{3}q^{2}s (q > 3), 3^{3}q^{2}s (q > 3), 2^{3}3^{2}s and 3^{3}2^{2}s must be separately and similarly considered. □

It would seem probable that D(n) is unbounded for some n, and in that case for all numbers ns, where (n, s) = 1, as well. Then the set of such numbers would have positive density in ℕ. We show now that this density is less than 0.004. We have computed lower bounds for the densities of 45 classes of integers, including the known result for the set of squarefree numbers, and have shown that integers in these 45 classes have bounded derived sequences. In each case, the density was computed to within 10^{−6} and then truncated to five decimal digits. Those densities (33 of the 45) which gave a positive lower bound (to that number of digits) are given in Table 1. We refer, for example, to the type p^{3}q^{2}S as the set of integers of the form p^{3}q^{2}s, where p ≠ q and (s, pq) = 1. How the given densities were obtained will be illustrated shortly by the determination of such for the type p^{3}q^{2}S. The 45 classes of integers were all possible types of the form p^{a}q^{b} ⋯ S such that (a − 1) + (b − 1) + ⋯ ≤ 7 (precisely as considered in the proof of Proposition 8), and Table 1 shows that their cumulative density is at least 0.996.

We show now how we obtain that the density of the class p^{3}q^{2}S is 0.01447, truncated to five decimal digits.

Let x > 0 be given. In general, the number of positive integers n ≤ x, not divisible by the prime squares p_{1}^{2}, p_{2}^{2}, …, p_{l}^{2} and not divisible by the primes q_{1}, q_{2}, …, q_{m} (all these being different primes) is

x · ∏_{i=1}^{l} (1 − \frac{1}{p_{i}^{2}} ) · ∏_{i=1}^{m} (1 − \frac{1}{q_{i}} ) + O(1).

Note that the positive integer n ≤ x is squarefree if p^{2} ∤ n for all primes p ≤ \sqrt{x}. Fix distinct primes p and q. As above, the number of squarefree positive integers n ≤ x/p^{3}q^{2} which are divisible by neither p nor q is

\frac{x}{p^{3}q^{2}} (1 − \frac{1}{p}) (1 − \frac{1}{q}) ∏_{\begin{matrix}r≤\sqrt{x/p^{3}q^{2}} \\ r≠p, q \end{matrix}} (1 − \frac{1}{r^{2}} ) + O(1)

= \frac{x}{p^{3}q^{2}} (1 − \frac{1}{p}) (1 − \frac{1}{q}) (1 − \frac{1}{p^{2}} )^{−1} (1 − \frac{1}{q^{2}} )^{−1} ∏_{r≤\sqrt{x/p^{3}q^{2}}} (1 − \frac{1}{r^{2}} ) + O(1)

= x · \frac{1}{p^{2}(p + 1)} · \frac{1}{q(q + 1)} ∏_{r≤\sqrt{x/p^{3}q^{2}}} (1 − \frac{1}{r^{2}} ) + O(1),

the products being taken over primes r.

In general, for y > 0 we have ∏_{r≤y}(1 − 1/r^{2}) = 6/π^{2} + O(1/y). Applying this above, the number of squarefree positive integers n ≤ x/p^{3}q^{2} which are divisible by neither p nor q is then

x · \frac{1}{p^{2}(p + 1)} · \frac{1}{q(q + 1)} (\frac{6}{π^{2}} + O (\sqrt{\frac{p^{3}q^{2}}{x}} )) + O(1)

= \frac{6x}{π^{2}} · \frac{1}{p^{2}(p + 1)} · \frac{1}{q(q + 1)} + O (\sqrt{\frac{x}{p^{3}q^{2}}} ) .

To find the number of positive integers n ≤ x of the form n = p^{3}q^{2}s, where p, q are any two distinct primes and (s, pq) = 1, we sum our result above over primes p ≤ \sqrt[3]{x} and q ≤ \sqrt{x/p^{3}}. Therefore the proportion of these integers p^{3}q^{2}s which are at most x is given by

\frac{1}{x} ∑_{p≤ \sqrt[3]{x}} ∑_{\begin{matrix}q≤\sqrt{x/p^{3}} \\ q≠p \end{matrix}} (\frac{6x}{π^{2}} · \frac{1}{p^{2}(p + 1)} · \frac{1}{q(q + 1)} + O (\sqrt{\frac{x}{p^{3}q^{2}}} ))

= ∑_{p≤ \sqrt[3]{x}} ∑_{\begin{matrix}q≤\sqrt{x/p^{3}} \\ q≠p \end{matrix}} \frac{6}{π^{2}} · \frac{1}{p^{2}(p + 1)} · \frac{1}{q(q + 1)} + O( ∑_{p≤ \sqrt[3]{x}} ∑_{q≤\sqrt{x/p^{3}}} \frac{1}{\sqrt{xp^{3}q^{2}}} ).

In general, ∑_{p≤y} 1/p^{3/2} = O(1) and ∑_{q≤y} 1/q = O(log log y), and so

O( ∑_{p≤ \sqrt[3]{x}} ∑_{q≤\sqrt{x/p^{3}}} \frac{1}{\sqrt{xp^{3}q^{2}}} ) = O(\frac{1}{\sqrt{x}} ∑_{p≤ \sqrt[3]{x}} \frac{1}{\sqrt{p^{3}}} ∑_{q≤\sqrt{x}} \frac{1}{q}) = O(\begin{matrix}log & log x \\ √ & \overline{x} \end{matrix}).

Thus the required density is

lim_{x→∞} ∑_{p≤ \sqrt[3]{x}} ∑_{\begin{matrix}q≤\sqrt{x/p^{3}} \\ q≠p \end{matrix}} \frac{6}{π^{2}} · \frac{1}{p^{2}(p + 1)} · \frac{1}{q(q + 1)} = \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p + 1)} ∑_{q≠p} \frac{1}{q(q + 1)} ≥ 0.0144.

The double sum was estimated on a computer.

We have therefore shown the following:

Type  Density  Truncated density
S  \frac{6}{π^{2}}  0.60792
p^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p(p+1)}  0.20075
p^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p(p+1)}  0.07417
p^{2}q^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p(p+1)} ∑_{q>p} \frac{1}{q(q+1)}  0.02212
p^{4}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)}  0.03206
p^{3}q^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)}  0.01447
p^{2}q^{2}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p(p+1)} ∑_{q>p} \frac{1}{q(q+1)} ∑_{r>q} \frac{1}{r(r+1)}  0.00107
p^{5}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{4}(p+1)}  0.01474
p^{4}q^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)}  0.00586
p^{3}q^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p+1)} ∑_{q>p} \frac{1}{q^{2}(q+1)}  0.00216
p^{3}q^{2}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)} ∑_{r>q, r≠p} \frac{1}{r(r+1)}  0.00091
p^{2}q^{2}r^{2}t^{2}S \frac{6}{π^{2}} ∑_{p} \frac{1}{p(p+1)} ∑_{q>p} \frac{1}{q(q+1)} ∑_{r>q} \frac{1}{r(r+1)} ∑_{t>r} \frac{1}{t(t+1)}  0.00002
p^{6}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{5}(p+1)}  0.00699
p^{5}q^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{4}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)}  0.00259
p^{4}q^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q≠p} \frac{1}{q^{2}(q+1)}  0.00163
p^{4}q^{2}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)} ∑_{r>q, r≠p} \frac{1}{r(r+1)}  0.00035
p^{3}q^{3}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p+1)} ∑_{q>p} \frac{1}{q^{2}(q+1)} ∑_{r≠q,p} \frac{1}{r(r+1)}  0.00023
p^{3}q^{2}r^{2}t^{2}S \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)} ∑_{r>q, r≠p} \frac{1}{r(r+1)} ∑_{t>r, t≠p} \frac{1}{t(t+1)}  0.00002
p^{7}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{6}(p+1)}  0.00338
p^{6}q^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{5}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)}  0.00120
p^{5}q^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{4}(p+1)} ∑_{q≠p} \frac{1}{q^{2}(q+1)}  0.00068
p^{5}q^{2}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{4}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)} ∑_{r>q, r≠p} \frac{1}{r(r+1)}  0.00015
p^{4}q^{4}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q>p} \frac{1}{q^{3}(q+1)}  0.00029
p^{4}q^{3}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q≠p} \frac{1}{q^{2}(q+1)} ∑_{r≠q, r≠p} \frac{1}{r(r+1)}  0.00016
p^{3}q^{3}r^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{2}(p+1)} ∑_{q>p} \frac{1}{q^{2}(q+1)} ∑_{r>q} \frac{1}{r^{2}(r+1)}  0.00001
p^{8}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{7}(p+1)}  0.00165
p^{7}q^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{6}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)}  0.00057
p^{6}q^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{5}(p+1)} ∑_{q≠p} \frac{1}{q^{2}(q+1)}  0.00030
p^{6}q^{2}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{5}(p+1)} ∑_{q≠p} \frac{1}{q(q+1)} ∑_{r>q, r≠p} \frac{1}{r(r+1)}  0.00006
p^{5}q^{4}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{4}(p+1)} ∑_{q≠p} \frac{1}{q^{3}(q+1)}  0.00023
p^{5}q^{3}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{4}(p+1)} ∑_{q≠p} \frac{1}{q^{2}(q+1)} ∑_{r≠q, r≠p} \frac{1}{r(r+1)}  0.00006
p^{4}q^{4}r^{2}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q>p} \frac{1}{q^{3}(q+1)} ∑_{r≠q, r≠p} \frac{1}{r(r+1)}  0.00002
p^{4}q^{3}r^{3}S  \frac{6}{π^{2}} ∑_{p} \frac{1}{p^{3}(p+1)} ∑_{q≠p} \frac{1}{q^{2}(q+1)} ∑_{r>q, r≠p} \frac{1}{r^{2}(r+1)}  0.00001
Total:  0.99683

Table 1: Densities giving a positive lower bound Proposition 9 The density in ℕ of integers n for which D(n) is unbounded is less than 0.004.

Although we cannot exhibit an unbounded derived sequence, we do have the following result.

Proposition 10 For any positive integer M, there exists an integer n such that D(n) requires more than M iterations of D before a cycle is possible.

Proof. Let p be a large prime, with “large” to be qualified shortly. Take n = p^{4p}. Then

D(n) = {p^{4p}, 2^{2}p^{4p}, 2^{4}p^{4p}, 2^{7}p^{4p}, 2^{8}7p^{4p}, 2^{12}p^{4p}, 2^{15}3p^{4p}, … }.

The exact factor p^{4p} will persist in all terms until the exponent on 2 or some other prime (not p) equals p. Until this happens, if it will ever happen, there can be no derived k-cycle in D(n), for any k. For suppose there were such a cycle and let the ith term of the cycle be ∏ p_{i}^{a_{i}}, 1 ≤ i ≤ k, where the notation is as in Proposition 1. It follows that at most 2^{k} divides ∏ p_{1} ∏ p_{2} ⋯ ∏ p_{k}, while at least 2^{2k} divides ∏ a_{1} ∏ a_{2} ⋯ ∏ a_{k}. By Proposition 1, this is a contradiction. The proof is non-constructive, in that we can say only that, whatever the value of M, a prime p exists such that p exceeds all exponents on primes other than p resulting from M iterations of D. □

4 Further work

(1) Find examples of integers n for which D(n) results in a k-cycle for k = 7 or k > 8. Do derived k-cycles exist for all positive integers k?

(2) Can it be shown that D(n) is unbounded for some n, as we have conjectured above? We suspect this to be the case for “most” sequences D(p^{q^{q}p}) (p ≠ q), for reasons suggested in the proof of Proposition 10 (where we considered q = 2). It is not known whether D(7^{4046}), D(11^{1674}) and D(13^{504}) are bounded, but this is the case for all smaller exponents on the respective primes. (It took a few weeks for referee’s comments to be returned. We are grateful for those. In that time we left a program running, checking D(31^{124}) for boundedness. After k = 48218701 iterations, we found no cycle and D^{k}(31^{124}) = 2^{1516268557}3^{780548532}5^{348780008} ⋯ 127^{10414}131^{131}139^{139}149^{141851} ⋯ 62763353·348779999, with all primes up to 131 present. The program was then permanently halted.)

(3) As in the calculus, differentiation is a craft, but integration is an art. Can a technique be developed for finding integrals of a given positive integer or of showing that certain integers, the primes being examples, have no integrals? In Proposition 2, we have given all integrals of 1, but even to identify all integrals of 4 seems to be very difficult.

References

[1] T. M. Apostol. Introduction to Analytic Number Theory, Springer–Verlag, Berlin, 1980.

[2] G. L. Cohen and H. J. J. te Riele. Iterating the sum-of-divisors function, Experiment. Math., 5 (1996), 91–100. Errata in Experiment. Math., 6 (1997), 177.

[3] R. K. Guy. Problems in Number Theory, second edition, Springer–Verlag, New York, 1994.

2000 Mathematics Subject Classification: Primary 11Y55; Secondary 11A25, 11B83. Keywords: Arithmetic functions, density, unbounded sequences, cycles.

Received October 25, 2002; revised version received December 1, 2002. Published in Journal of Integer Sequences December 23, 2002. Revised, February 10 2004.

Return to Journal of Integer Sequences home page.