\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 j<k$ as integrals of $D^k(n)$.

If $n=\prod_{i=1}^wp_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)}\,\tau\left(\frac n{C(n)}\right), \]
where $\tau(n)=\prod_{i=1}^w(a_i+1)$ is the number of divisors of $n$ and $C(n)=\prod_{i=1}^wp_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:
\begin{align}
\D(5^217\cdot37)&=\{5^217\cdot37,2\cdot5,\u{1},\dotsc\}, \\
\D(2^{25})&=\{2^{25},2^{24}5^2,2^{27}3\cdot5,2^{26}3^3,\u{2^{26}3^313},\dotsc\}, \\
\D(13^{16)}&=\{13^{16},2^413^{15},2^53\cdot5\cdot13^{14},2^55\cdot7\cdot13^{13},\u{2^45\cdot13^{13}},\u{2^513^{13}},
\dotsc\}, \\
\D(2^{32})&=\{2^{32},2^{36},\u{2^{37}3^2},\u{2^{37}3\cdot37},\u{2^{36}37},\dotsc\}, \\
\D(3^8)&=\{3^8,\u{2^33^7},\u{2^23^7\cdot7},\u{2^23^6\cdot7},\u{2^33^6},\dotsc\}.
\end{align}
The underlined terms in each case form cycles. Precisely: if
\[ \D(n)=\{\dotsc,D^j(n),D^{j+1}(n),\dots,D^{j+k-1}(n),D^{j+k}(n),\dotsc\} \]
and $D^{j+k}(n)=D^j(n)$, where $j\ge0$ and $k\ge1$ is the smallest integer with this property, then
$D^j(n),D^{j+1}(n),\dots,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^313)=2^{26}3^313$, and, in (6), $D(2^33^6)=2^33^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\cdot47\cdot53\cdot61$. Our most impressive example is $\D(17^{35}19^{39})$, which,
in 443507 iterations of $D$, arrives at the fixed point
\begin{gather*}
2^{4318267}3^{1370053}5^{525835}7^{159649}11^{33429}13^{20597}17^{1037}19^{1349}23^{299}31^{31} \\
  {}\cdot 43\cdot61\cdot71^2479\cdot1013\cdot22807\cdot105167\cdot1370053\cdot4318267.
\end{gather*}

Other instances of sequences of iterated arithmetic functions are given by Guy \cite{Guy}. Iteration of the function
$\sigma(n)-n$, for example, where $\sigma$ 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 $\sigma$ itself was studied in Cohen and te Riele \cite{Cohen-teRiele}.

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.

\section{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=\prod_{i=1}^wp_i^{a_i}$, where $\prod_{i=1}^wp_i=\prod_{i=1}^wa_i$. More generally, we have Proposition 1,
below.  For simplicity of notation, we will write $n=\prod p_0^{a_0}$ and $D(n)=\prod p_1^{a_1}$ as shorthand for
$n=\prod_{i=1}^{w_0} p_{i0}^{a_{i0}}$ and $D(n)=\prod_{i=1}^{w_1} p_{i1}^{a_{i1}}$, and so on.

\begin{theorem}
Suppose $n>1$ 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$ & $\frac{\pi^2}6$ & 0.60792 \\ [1\jot]
$p^2S$ & $\frac{\pi^2}6\sum_p\frac1{p(p+1)}$ & 0.20075 \\ [1\jot]
$p^3S$ & $\frac{\pi^2}6\sum_p\frac1{p(p+1)}$ & 0.07417 \\ [1\jot]
$p^2q^2S$ & $\frac{\pi^2}6\sum_p\frac1{p(p+1)}\sum_{q>p}\frac1{q(q+1)}$ & 0.02212 \\ [1\jot]
$p^4S$ & $\frac{\pi^2}6\sum_p\frac1{p^3(p+1)}$ & 0.03206 \\ [1\jot]
$p^3q^2S$ & $\frac{\pi^2}6\sum_p\frac1{p^2(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.01447 \\ [1\jot]
$p^2q^2r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\sum_p\frac1{p^4(p+1)}$ & 0.01474 \\ [1\jot]
$p^4q^2S$ & $\frac{\pi^2}6\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00586 \\ [1\jot]
$p^3q^3S$ & $\frac{\pi^2}6\sum_p\frac1{p^2(p+1)}\sum_{q>p}\frac1{q^2(q+1)}$ & 0.00216 \\ [1\jot]
$p^3q^2r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\sum_p\frac1{p^5(p+1)}$ & 0.00699 \\ [1\jot]
$p^5q^2S$ & $\frac{\pi^2}6\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00259 \\ [1\jot]
$p^4q^3S$ & $\frac{\pi^2}6\sum_p\frac1{p^3(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}$ & 0.00163 \\ [1\jot]
$p^4q^2r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\sum_p\frac1{p^6(p+1)}$ & 0.00338 \\ [1\jot]
$p^6q^2S$ & $\frac{\pi^2}6\sum_p\frac1{p^5(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00120 \\ [1\jot]
$p^5q^3S$ & $\frac{\pi^2}6\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}$ & 0.00068 \\ [1\jot]
$p^5q^2r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\sum_p\frac1{p^3(p+1)}\sum_{q>p}\frac1{q^3(q+1)}$ & 0.00029 \\ [1\jot]
$p^4q^3r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\sum_p\frac1{p^7(p+1)}$ & 0.00165 \\ [1\jot]
$p^7q^2S$ & $\frac{\pi^2}6\sum_p\frac1{p^6(p+1)}\sum_{q\ne p}\frac1{q(q+1)}$ & 0.00057 \\ [1\jot]
$p^6q^3S$ & $\frac{\pi^2}6\sum_p\frac1{p^5(p+1)}\sum_{q\ne p}\frac1{q^2(q+1)}$ & 0.00030 \\ [1\jot]
$p^6q^2r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\sum_p\frac1{p^4(p+1)}\sum_{q\ne p}\frac1{q^3(q+1)}$ & 0.00023 \\ [1\jot]
$p^5q^3r^2S$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\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$ & $\frac{\pi^2}6\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.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.
ca/JIS/}.




\end{document}

