\documentclass[12pt,reqno]{article} %\setlength{\textheight}{24cm} \setlength{\textwidth}{16cm} %\setlength{\topmargin}{-1cm} \setlength{\oddsidemargin}{-.2cm} \usepackage{amsmath,amssymb} \usepackage{color} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} %\definecolor{webgreen}{rgb}{0,.5,0} %\definecolor{webbrown}{rgb}{.6,0,0} %\usepackage{psfig,epsf,latexsym} \usepackage{epsf} \usepackage{float} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\textheight}{8.9in} \setlength{\topmargin}{-.5in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{ \underline{#1}}} \newtheorem{theorem}{Proposition} \renewcommand{\u}[1]{\underline{#1}} %\font\scr=rsfs10 \newcommand{\D}{\text{\scr D\,}} \newcommand{\D}{\mathcal{D}} \begin{document} \makeatletter \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm {\LARGE\bf Derived Sequences} \vskip 1cm \large G. L. Cohen \\ Department of Mathematical Sciences, Faculty of Science \\ University of Technology, Sydney \\ PO Box 123, Broadway, NSW 2007 \\ Australia \\ \ \\ \vskip -.1in and\\ \ \\ \vskip -.1in D. E. Iannucci \\ Division of Science and Mathematics \\ University of the Virgin Islands \\ St. Thomas, VI 00802 \\ USA\\ \end{center} \begin{center} {\bf Abstract} \end{center} 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\ge1$, we set $D^0(n)=n$ and $D^k(n)=D(D^{k-1}(n))$ when $k\ge1$. We term $\{D^k(n)\}_{k=0}^\infty$ the derived sequence of~$n$. We show that all derived sequences of $n<1.5\cdot10^{10}$ are bounded, and that the density of those $n\in\mathbb 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. \bigskip \section{Introduction} Define a multiplicative arithmetic function $D$ by assigning \begin{equation} D(p^a)=ap^{a-1}, \end{equation} when $p$ is a prime and $a$ is a positive integer. The multiplicativity implies $D(1)=1$ and, for example, $D(p^aq^b)=abp^{a-1}q^{b-1}$, where $q^b$ is another prime power, $q\ne 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 \cite{Apostol}, for example.) Writing $D^0(n)=n$ and $D^k(n)=D(D^{k-1}(n))$ for $k\ge1$ and any positive integer $n$, we call $\{D^k(n)\}_{k=0}^\infty$, or $\{n, D(n), D^2(n), D^3(n), \dotsc\}$, the derived sequence of $n$, and denote this by $\D(n)$. We refer to $D^k(n)$ for $k\ge1$ as the $k$th derivative of $n$ and we refer to $D^j(n)$ for $0\le j1$ and write $n=\prod p_0^{a_0}$, $D(n)=\prod p_1^{a_1}$, $\dots$, $D^{k-1}(n)=\prod p_{k-1}^{a_{k-1}}$. We have $D^k(n)=n$ if and only if $\prod p_0\prod p_1\dotsm\prod p_{k-1}=\prod a_0\prod a_1\dotsm\prod a_{k-1}$. \end{theorem} \noindent \emph{Proof}. Note that \vskip -.4in \begin{alignat*}{2} n&=\prod p_0^{a_0}, & & \\ D(n)&=\prod p_1^{a_1}, & \quad & \text{so} \quad \prod p_1^{a_1}=\prod a_0p_0^{a_0-1}, \\ D^2(n)&=\prod p_2^{a_2}, & \quad & \text{so} \quad \prod p_2^{a_2}=\prod a_1p_1^{a_1-1}, \\ & \vdots && \\ D^{k-1}(n)&=\prod p_{k-1}^{a_{k-1}}, & \quad & \text{so} \quad \prod p_{k-1}^{a_{k-1}}=\prod a_{k-2}p_{k-2}^{a_{k-2}-1}. \end{alignat*} If, further, $D^k(n)=n$ then $\prod p_0^{a_0}=\prod a_{k-1}p_{k-1}^{a_{k-1}-1}$, and we have \begin{align*} \prod p_0\prod p_1\dotsm\prod p_{k-1}&=\frac{\prod p_1^{a_1}}{\prod p_0^{a_0-1}} \frac{\prod p_2^{a_2}}{\prod p_1^{a_1-1}} \dotsm \frac{\prod p_{k-1}^{a_{k-1}}}{\prod p_{k-2}^{a_{k-2}-1}} \frac{\prod p_0^{a_0}}{\prod p_{k-1}^{a_{k-1}-1}} \\ &=\prod a_0\prod a_1\dotsm\prod a_{k-1}. \end{align*} The converse is also clear. \quad $\square$\medskip 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$: \begin{theorem} The integer $n>1$ has \begin{itemize} \item first derivative~$1$ if $n=s$, \item second derivative $1$ if $n=p^2s$ where $p>2$ and $p\nmid s$, \item third derivative $1$ if $n=p^3s$ where $p>3$ and $p\nmid s$, or $n=p^3q^2s$ where $p>3$, $q>3$, $p\ne q$ and $(s,pq)=1$. \end{itemize} There are no other situations in which $n$ has a derivative equal to $1$. \end{theorem} 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. \begin{theorem} For any $p$, \begin{itemize} \item if $p^2+1$ is squarefree, then $\D(p^{p^2+1})=\{\u{p^{p^2+1}},\u{(p^2+1)p^{p^2}},\dotsc\}$, \item if $p^3+2$ and $p^3+1$ are squarefree, then \[ \D(p^{p^3+2})=\{\u{p^{p^3+2}},\u{(p^3+2)p^{p^3+1}},\u{(p^3+1)p^{p^3}},\dotsc\}. \] \end{itemize} \end{theorem} The underlined terms are cycles. Notice that 13, 37, 61, $\dots$, 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: \begin{theorem} Let $s$ be such that $s\equiv2\pmod3$, $4s-1$ is squarefree and $2s-1$ is squarefree. Then $\D(3^{4s})$ results in a $4$-cycle. \end{theorem} \noindent\emph{Proof}. Write $4s-1=s_1$ and $2s-1=3s_2$ (where $3\nmid s_2$). If $s$ is odd, then \[ \D(3^{4s})=\{3^{4s},2^23^{4s-1}s,\u{2^23^{4s-2}s_1},\u{2^33^{4s-2}s_2},\u{2^33^{4s-1}s_2},\u{2^23^{4s-1}s_1}, \dotsc\}, \] while if $s$ is even, then \[ \D(3^{4s})=\{3^{4s},2^33^{4s-1}(s/2),\u{2^23^{4s-1}s_1},\u{2^23^{4s-2}s_1},\u{2^33^{4s-2}s_2},\u{2^33^{4s-1}s_2}, \dotsc\}. \] The underlined terms in each case are 4-cycles (in fact, algebraically, the same 4-cycle). \quad$\square$\medskip 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, \dots. 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},\u{2^{11}3^95^2},\u{2^{11}3^{10}5\cdot11},\u{2^{11}3^95\cdot11}, \u{2^{10}3^{10}\cdot11},\dotsc\}. \] 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.) \begin{theorem} Let $s$ be such that $(s,2\cdot3\cdot5\cdot47)=1$, and suppose $(s_1,5\cdot23\cdot47)=1$, where $s_1=(3s-1)/2$. Put $n=2^{3s}3^{45}5^523s_1$. Then $n$, $D(n)$, $\dots$, $D^4(n)$ is a $5$-cycle. \end{theorem} In this, $s$ may take the values 1, 13, 23, 29, 41, 53, 61, $\dots$. \begin{theorem} {\rm (a)} Let $s$ be such that $(s,2\cdot3\cdot5\cdot7\cdot53)=1$, and suppose $(s_1,5\cdot53\cdot107)=1$, where $s_1=6s+1$. Put $n=2^{6s}3^{105}5^67s_1$. Then $n$, $D(n)$, $\dots$, $D^5(n)$ is a $6$-cycle. {\rm (b)} Let $s$ be such that $(s,2\cdot3\cdot5\cdot13\cdot43)=1$, and suppose $(s_1,7\cdot13\cdot43\cdot131)=1$, where $s_1=30s+1$. Put $n=2^{30s}3^{129}5^67\cdot43s_1$. Then $n$, $D(n)$, $\dots$, $D^5(n)$ is a $6$-cycle. \end{theorem} \noindent\emph{Proof}. As usual, the proofs are a matter of straightforward verification. We will demonstrate this in the case of Proposition 6(a). We have \begin{alignat*}{2} n&=2^{6s}3^{105}5^67s_1, & & \\ D(n)&=2^{6s+1}3^{107}5^67s, & \quad & \text{since } (s_1,2\cdot3\cdot5\cdot7)=1, \\ D^2(n)&=2^{6s+1}3^{107}5^5107s_1, & \quad & \text{since } (s,2\cdot3\cdot5\cdot7)=1, \\ D^3(n)&=2^{6s}3^{106}5^5107s_1, & \quad & \text{since } (s_1,2\cdot3\cdot5\cdot107)=1, \\ D^4(n)&=2^{6s+1}3^{106}5^553s, & \quad & \text{since } (s_1,2\cdot3\cdot5\cdot107)=1, \\ D^5(n)&=2^{6s+1}3^{105}5^553s_1, & \quad & \text{since } (s,2\cdot3\cdot5\cdot53)=1, \\ D^6(n)&=2^{6s}3^{105}5^67s_1, & \quad & \text{since } (s_1,2\cdot3\cdot5\cdot53)=1. \end{alignat*} But $D^6(n)=n$. We have also used the fact that $s$ and $s_1$ are squarefree. \quad$\square$\medskip In Proposition 6(a), we may have $s=11$, 13, 17, 23, 31, 37, 41, $\dots$. In Proposition 6(b), $s$ may take the values 1, 7, 11, 19, 23, 37, 41, \dots. \begin{theorem} Let $s$ be such that $s\equiv 7$ {\rm (mod 10)} and $(s,3\cdot23\cdot31\cdot47\cdot103\cdot311)=1$, and suppose $(s_1,3\cdot5\cdot31\cdot47\cdot103\cdot311)=1$, where $s_1=(2s+1)/5$. Put $n=2^{2s}3^{311}5^{46}103s_1$. Then $n$, $D(n)$, $\dots$, $D^7(n)$ is an $8$-cycle. \end{theorem} In this, $s$ may take the values 17, 107, 167, 197, 227, $\dots$. 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: \begin{alignat*}2 & 2^{159}3^{16725}5^{5}79\cdot8363, & \quad & 2^{158}3^{16726}5^{7}53\cdot223, \\ & 2^{159}3^{16725}5^{6}7\cdot79\cdot8363, & \quad & 2^{159}3^{16727}5^{7}53\cdot223, \\ & 2^{158}3^{16727}5^{6}7\cdot43\cdot53\cdot389, & \quad & 2^{159}3^{16727}5^{5}43\cdot79\cdot389, \\ & 2^{158}3^{16727}5^{5}43\cdot53\cdot389, & \quad & 2^{158}3^{16726}5^{5}43\cdot79\cdot389, \end{alignat*} and \begin{alignat*}2 & 2^{87}3^{149325}5^{5}43\cdot197\cdot379, & \quad & 2^{86}3^{149326}5^{7}11\cdot29\cdot181, \\ & 2^{87}3^{149325}5^{6}7\cdot43\cdot197\cdot379, & \quad & 2^{87}3^{149327}5^{7}11\cdot29\cdot181, \\ & 2^{86}3^{149327}5^{6}7\cdot29\cdot31\cdot4817, & \quad & 2^{87}3^{149327}5^{5}31\cdot43\cdot4817, \\ & 2^{86}3^{149327}5^{5}29\cdot31\cdot4817, & \quad & 2^{86}3^{149326}5^{5}31\cdot43\cdot4817. \end{alignat*} These occur in $\D(3^{16695})$ and $\D(3^{149319})$, respectively. It is not difficult to determine a two-parameter family, containing general exponents on 2 and 3, that includes both of these 8-cycles. %We have also observed the 6-cycle: %\begin{alignat*}{2} %n={}& 2^{1578}3^{345}5^{66}13\cdot23\cdot1579, & \quad & 2^{1579}3^{347}5^{66}11\cdot23\cdot263, \\ % & 2^{1579}3^{347}5^{65}11\cdot347\cdot1579, & \quad & 2^{1578}3^{346}5^{65}13\cdot347\cdot1579, \\ % & 2^{1579}3^{346}5^{65}13\cdot173\cdot263, & \quad & 2^{1579}3^{345}5^{65}13\cdot173\cdot1579; %\end{alignat*} %$\D(2^{81}5^{30})$ arrives in 494 iterations at the 6-cycle beginning with $7^7n$. More impressive is the 8-cycle: %\begin{alignat*}2 %n={}& 2^{1114}3^{311}5^{46}\cdot103\cdot223, & \quad & 2^{1115}3^{310}5^{45}23\cdot311\cdot557, \\ % & 2^{1115}3^{311}5^{47}31\cdot223, & \quad & 2^{1114}3^{310}5^{47}47\cdot223\cdot311, \\ % & 2^{1115}3^{309}5^{47}31\cdot47\cdot557, & \quad & 2^{1114}3^{309}5^{47}47\cdot103\cdot223, \\ % & 2^{1114}3^{309}5^{46}47\cdot103\cdot557, & \quad & 2^{1115}3^{309}5^{45}23\cdot103\cdot557; %\end{alignat*} %$\D(5^{13}29^{54})$ arrives in 428 iterations at the 8-cycle beginning with $29^{29}n$. We have no examples of derived $k$-cycles with $k=7$ or $k>8$. \section{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. \begin{theorem} For all $n<1.5\cdot10^{10}$, the derived sequence $\D(n)$ is bounded. \end{theorem} \noindent\emph{Proof}. The proof involved a direct incremental investigation of all numbers $n=\prod_{i=1}^w p_i^{a_i}<1.5\cdot10^{10}$ for which $\sum_{i=1}^w(a_i-1)\ge8$. (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 $\sum_{i=1}^w(a_i-1)\le7$. For example, suppose $n=p^3q^2s$, where $p\ne q$ and $(s,pq)=1$. If $p$ and $q$ are both greater than 3, then $D(n)=2\cdot3p^2q$, $D^2(n)=2p$ and $D^3(n)=1$ (or use Proposition~2); then the numbers $p^32^2s$ ($p>3$), $p^33^2s$ ($p>3$), $2^3q^2s$ ($q>3$), $3^3q^2s$ ($q>3$), $2^33^2s$ and $3^32^2s$ must be separately and similarly considered. \quad$\square$\medskip 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 $\mathbb N$. 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^3q^2S$ as the set of integers of the form $p^3q^2s$, where $p\ne q$ and $(s,pq)=1$. How the given densities were obtained will be illustrated shortly by the determination of such for the type $p^3q^2S$. The 45 classes of integers were all possible types of the form $p^aq^b\dotsm S$ such that $(a-1)+(b-1)+\cdots\le7$ (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^3q^2S$ is $0.01447$, truncated to five decimal digits. Let $x>0$ be given. In general, the number of positive integers $n\le x$, not divisible by the prime squares $p_1^2$, $p_2^2$, \dots, $p_l^2$ and not divisible by the primes $q_1$, $q_2$, \dots, $q_m$ (all these being different primes) is \[ x\cdot\prod_{i=1}^l\left(1-\frac1{p_i^2}\right)\cdot\prod_{i=1}^m\left(1-\frac1{q_i}\right)+O(1). \] Note that the positive integer $n\le x$ is squarefree if $p^2\nmid n$ for all primes $p\le\sqrt{x}$. Fix distinct primes $p$ and $q$. As above, the number of squarefree positive integers $n\le x/p^3q^2$ which are divisible by neither $p$ nor $q$ is \bigbreak \begin{align*} &\frac x{p^3q^2}\left(1-\frac1p\right)\left(1-\frac1q\right)\prod_{\substack{r\le\sqrt{x/p^3q^2}\\r\ne p,\,q}} \left(1-\frac{1}{r^2}\right)+O(1) \\ &=\frac x{p^3q^2}\left(1-\frac 1p\right)\left(1-\frac1q\right) \left(1-\frac1{p^2}\right)^{-1}\left(1-\frac1{q^2}\right)^{-1} \prod_{r\le\sqrt{x/p^3q^2}}\left(1-\frac1{r^2}\right)+O(1) \\ &=x\cdot\frac1{p^2(p+1)}\cdot\frac{1}{q(q+1)}\prod_{r\le\sqrt{x/p^3q^2}}\left(1-\frac{1}{r^2}\right)+O(1), \end{align*} the products being taken over primes $r$. In general, for $y>0$ we have $\prod_{r\le y}(1-1/r^2)=6/\pi^2+O(1/y)$. Applying this above, the number of squarefree positive integers $n\le x/p^3q^2$ which are divisible by neither $p$ nor $q$ is then \begin{align*} &x\cdot\frac{1}{p^2(p+1)}\cdot\frac{1}{q(q+1)}\left(\frac{6}{\pi^2}+O\left(\sqrt{\frac{p^3q^2}{x}}\right)\right)+O(1)\\ &=\frac{6x}{\pi^2}\cdot\frac{1}{p^2(p+1)}\cdot\frac{1}{q(q+1)}+O\left(\sqrt{\frac{x}{p^3q^2}}\right). \end{align*} To find the number of positive integers $n\le x$ of the form $n=p^3q^2s$, where $p$, $q$ are any two distinct primes and $(s,pq)=1$, we sum our result above over primes $p\le\root 3 \of{x}$ and $q\le\sqrt{x/p^3}$. Therefore the proportion of these integers $p^3q^2s$ which are at most $x$ is given by \begin{align*} &\frac1x\sum_{p\le\root 3\of{x}}\sum_{\substack{q\le\sqrt{x/p^3}\\q\ne p}}\left(\frac{6x}{\pi^2}\cdot \frac{1}{p^2(p+1)}\cdot\frac{1}{q(q+1)}+O\left(\sqrt{\frac{x}{p^3q^2}}\right)\right) \\ &=\sum_{p\le\root 3\of{x}}\sum_{\substack{q\le\sqrt{x/p^3}\\q\ne p}}\frac{6}{\pi^2}\cdot\frac{1}{p^2(p+1)} \cdot\frac{1}{q(q+1)}+O\biggl(\sum_{p\le\root3\of{x}}\sum_{q\le\sqrt{x/p^3}}\frac{1}{\sqrt{xp^3q^2}}\biggr). \end{align*} In general, $\sum_{p\le y}1/p^{3/2}=O(1)$ and $\sum_{q\le y}1/q=O(\log{\log{y}})$, and so \[ O\biggl(\sum_{p\le\root 3\of{x}}\sum_{q\le\sqrt{x/p^3}}\frac{1}{\sqrt{xp^3q^2}}\biggr) =O\biggl(\frac{1}{\sqrt{x}}\sum_{p\le\root 3\of{x}}\frac{1}{\sqrt{p^3}}\sum_{q\le\sqrt{x}}{\frac1q}\biggr) =O\biggl(\frac{\log{\log{x}}}{\sqrt{x}}\biggr). \] Thus the required density is \[ \lim_{x\to\infty}\sum_{p\le\root 3\of{x}}\sum_{\substack{q\le\sqrt{x/p^3}\\q\ne p}}\frac{6}{\pi^2}\cdot \frac1{p^2(p+1)}\cdot\frac{1}{q(q+1)} =\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q\ne p}\frac1{q(q+1)}\ge0.0144. \] The double sum was estimated on a computer. \begin{table} \footnotesize \begin{center} \begin{tabular}{llc} \emph{Type} & \emph{Density} & \emph{Truncated density} \\ \hline \\ [-4\jot] $S$ & $\frac6{\pi^2}$ & 0.60792 \\ [1\jot] $p^2S$ & $\frac6{\pi^2}\sum_p\frac1{p(p+1)}$ & 0.20075 \\ [1\jot] $p^3S$ & $\frac6{\pi^2}\sum_p\frac1{p(p+1)}$ & 0.07417 \\ [1\jot] $p^2q^2S$ & $\frac6{\pi^2}\sum_p\frac1{p(p+1)}\sum_{q>p}\frac1{q(q+1)}$ & 0.02212 \\ [1\jot] $p^4S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}$ & 0.03206 \\ [1\jot] $p^3q^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.01447 \\ [1\jot] $p^2q^2r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p(p+1)}\sum_{q>p}\frac1{q(q+1)}\sum_{r>q}\frac1{r(r+1)}$ & 0.00107 \\ [1\jot] $p^5S$ & $\frac6{\pi^2}\sum_p\frac1{p^4(p+1)}$ & 0.01474 \\ [1\jot] $p^4q^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00586 \\ [1\jot] $p^3q^3S$ & $\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q>p}\frac1{q^2(q+1)}$ & 0.00216 \\ [1\jot] $p^3q^2r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q\ne p}\frac1{q(q+1)}\sum_{r>q,\,r\ne p}\frac1{r(r+1)}$ & 0.00091 \\ [1\jot] $p^2q^2r^2t^2S$ & $\frac6{\pi^2}\sum_p\frac1{p(p+1)}\sum_{q>p}\frac1{q(q+1)}\sum_{r>q}\frac1{r(r+1)}\sum_{t>r}\frac1{t(t+1)}$ & 0.00002 \\ [1\jot] $p^6S$ & $\frac6{\pi^2}\sum_p\frac1{p^5(p+1)}$ & 0.00699 \\ [1\jot] $p^5q^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00259 \\ [1\jot] $p^4q^3S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}$ & 0.00163 \\ [1\jot] $p^4q^2r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q(q+1)}\sum_{r>q,\,r\ne p}\frac1{r(r+1)}$ & 0.00035 \\ [1\jot] $p^3q^3r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q>p}\frac1{q^2(q+1)}\sum_{r\ne q,p}\frac1{r(r+1)}$ & 0.00023 \\ [1\jot] $p^3q^2r^2t^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q\ne p}\frac1{q(q+1)}\sum_{r>q,\,r\ne p}\frac1{r(r+1)}\sum_{t>r,\,t\ne p}\frac1{t(t+1)}$ & 0.00002 \\ [1\jot] $p^7S$ & $\frac6{\pi^2}\sum_p\frac1{p^6(p+1)}$ & 0.00338 \\ [1\jot] $p^6q^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^5(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00120 \\ [1\jot] $p^5q^3S$ & $\frac6{\pi^2}\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}$ & 0.00068 \\ [1\jot] $p^5q^2r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q(q+1)}\sum_{r>q,\,r\ne p}\frac1{r(r+1)}$ & 0.00015 \\ [1\jot] $p^4q^4S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q>p}\frac1{q^3(q+1)}$ & 0.00029 \\ [1\jot] $p^4q^3r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}\sum_{r\ne q,\,r\ne p}\frac1{r(r+1)}$ & 0.00016 \\ [1\jot] $p^3q^3r^3S$ & $\frac6{\pi^2}\sum_p\frac1{p^2(p+1)}\sum_{q>p}\frac1{q^2(q+1)}\sum_{r>q}\frac1{r^2(r+1)}$ & 0.00001 \\ [1\jot] $p^8S$ & $\frac6{\pi^2}\sum_p\frac1{p^7(p+1)}$ & 0.00165 \\ [1\jot] $p^7q^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^6(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00057 \\ [1\jot] $p^6q^3S$ & $\frac6{\pi^2}\sum_p\frac1{p^5(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}$ & 0.00030 \\ [1\jot] $p^6q^2r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^5(p+1)}\sum_{q\ne p}\frac1{q(q+1)}\sum_{r>q,\,r\ne p}\frac1{r(r+1)}$ & 0.00006 \\ [1\jot] $p^5q^4S$ & $\frac6{\pi^2}\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q^3(q+1)}$ & 0.00023 \\ [1\jot] $p^5q^3r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}\sum_{r\ne q,\,r\ne p}\frac1{r(r+1)}$ & 0.00006 \\ [1\jot] $p^4q^4r^2S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q>p}\frac1{q^3(q+1)}\sum_{r\ne q,\,r\ne p}\frac1{r(r+1)}$ & 0.00002 \\ [1\jot] $p^4q^3r^3S$ & $\frac6{\pi^2}\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}\sum_{r>q,\,r\ne p}\frac1{r^2(r+1)}$ & 0.00001 \\ [1\jot] & \hspace{8.5cm} \emph{Total}: & 0.99683 \end{tabular} \end{center} \bigskip \caption{Densities giving a positive lower bound}\label{table1} \end{table} We have therefore shown the following: \begin{theorem} The density in $\mathbb N$ of integers $n$ for which $\D(n)$ is unbounded is less than $0.004$. \end{theorem} Although we cannot exhibit an unbounded derived sequence, we do have the following result. \begin{theorem} 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. \end{theorem} \noindent\emph{Proof}. Let $p$ be a large prime, with ``large'' to be qualified shortly. Take $n=p^{4p}$. Then \[ \D(n)=\{p^{4p},2^2p^{4p},2^4p^{4p},2^7p^{4p},2^87p^{4p},2^{12}p^{4p},2^{15}3p^{4p},\dotsc\}. \] 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 $i$th term of the cycle be $\prod p_i^{a_i}$, $1\le i\le k$, where the notation is as in Proposition 1. It follows that at most $2^k$ divides $\prod p_1\prod p_2\dotsm\prod p_k$, while at least $2^{2k}$ divides $\prod a_1\prod a_2\dotsm\prod 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$. \quad $\square$ \medskip \section{Further work} %(1)~~We may partition the set $\mathbb N$ of positive integers via the equivalence relation $\sim$ defined as %follows: for $m,n\in\mathbb N$, $m\sim n$ if $\D(m)$ and $\D(n)$ are both unbounded, or if $\D(m)$ and $\D(n)$ %result in the same cycle. Write $[n]$ for the equivalence class containing $n$. All equivalence classes are %infinite sets, since $ns\in[n]$ for any squarefree number $s$, relatively prime to $n$. Only the equivalence class %$[1]$ has been fully described, in Proposition~2. % %We observe that $[2^{30}]=[2^{31}]=[2^{33}]=[2^{36}]$, as one of many such examples of four prime powers $p^a$, %with fixed $p$, belonging to the same equivalence class. There is no example known of five such powers in the same %equivalence class. (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$? \medskip\noindent (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^qp})$ ($p\ne 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} \dotsm127^{10414}131^{131}139^{139}149^{141851}\dotsm62763353\cdot348779999$, with all primes up to 131 present. The program was then permanently halted.) \medskip\noindent (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. \bibstyle{plain} \begin{thebibliography}{1} \bibitem{Apostol} \newblock T. M. Apostol. \newblock \emph{Introduction to Analytic Number Theory}, Springer--Verlag, Berlin, 1980. \bibitem{Cohen-teRiele} \newblock G. L. Cohen and H. J. J. te Riele. \newblock Iterating the sum-of-divisors function, \emph{Experiment. Math.}, \textbf{5} (1996), 91--100. \newblock Errata in \emph{Experiment. Math.}, \textbf{6} (1997), 177. \bibitem{Guy} R. K. Guy. \emph{Problems in Number Theory}, second edition, Springer--Verlag, New York, 1994. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11Y55; Secondary 11A25, 11B83.\ \ \noindent \emph{Keywords: Arithmetic functions, density, unbounded sequences, cycles.} \bigskip \hrule \bigskip %\noindent (Concerned with sequence \seqnum{?????}.) \vspace*{+.1in} \noindent Received October 25, 2002; revised version received December 1, 2002. Published in {\it Journal of Integer Sequences} December 23, 2002. Revised, February 10 2004. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo. ca/JIS/}. \end{document}