<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{amsart}

\usepackage[usenames]{color}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\usepackage{latexsym}
\usepackage{enumerate}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{comment}
\usepackage{psfig}
\def\emptyline{\vspace{12pt}}

\newcommand{\lat}[1]{\ensuremath{\mathit{#1}}}
\newcommand{\mat}[1]{\ensuremath{\mathit{#1}}}
\newcommand{\vect}[1]{\ensuremath{\mathbf{#1}}}
\newcommand{\norm}[1]{\ensuremath{\|{#1}\|}}
\newcommand{\Norm}[1]{\ensuremath{\left\|{#1}\right\|}}
\newcommand{\abs}[1]{\ensuremath{\left|{#1}\right|}}
\newcommand{\inner}[2]{\ensuremath{({#1}\cdot{#2})}}
\newcommand{\Inner}[2]{\ensuremath{{#1}\cdot{#2}}}
\newcommand{\proj}[2]{\ensuremath{\mathrm{proj}_{_{#2}}{#1}}}
\newcommand{\prp}[1]{\ensuremath{#1^{\!\perp}}}
%\newcommand{\e}{\mathrm{e}}
\newcommand{\BbQ} {\mathbb Q}
\newcommand{\BbN} {\mathbb N}
\newcommand{\BbR} {\mathbb R}
\newcommand{\BbZ} {\mathbb Z}
\newcommand{\BbC} {\mathbb C}
\newcommand{\f} {\frac}
\newcommand{\p} {{\bar p}}
\renewcommand{\a} {{\bar a}}
\renewcommand{\b} {{\bar b}}
\newcommand{\n} {{\bar a}}
\newcommand{\Erdos} {Erd{\H{o}}s}
\newcommand{\Joo} {Jo{\'o}}
\newtheorem{thm}{\bf{Theorem}}[section]
\newtheorem{defn}{\bf{Definition}}[section]
\newtheorem{lem}{\bf{Lemma}}[section]
\newtheorem{cor}{\bf{Corollary}}[section]
%\newtheorem{note}{\bf{Note}}[section]
\newtheorem{ex}{\bf{Example}}
%%\newenvironment{proof}{{\bf{Proof:}}}
%%         {\begin{flushright} \ensuremath{\square} \end{flushright}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm {\LARGE\bf Further Results on Derived Sequences}
\vskip 1cm
\large
Kevin G. Hare\footnote{Research of K. G. Hare supported,
in part by NSERC of Canada, and by the Department of Mathematics,
University of California, Berkeley.}
and Soroosh Yazdani\footnote{Research of S. Yazdani supported,
in part by NSERC of Canada, and by the Department of Mathematics,
University of California, Berkeley.}\\
Department of Mathematics\\
970 Evans Hall\\
University of California\\
Berkeley, CA  94720-3840\\
USA\\
\href{mailto:kghare@math.berkeley.edu}{kghare@math.berkeley.edu}\\
\href{mailto:syazdani@math.berkeley.edu}{syazdani@math.berkeley.edu}\\
\end{center}

\vskip .2 in
\begin{center}
{\bf Abstract}
\end{center}

In 2003 Cohen and Iannucci introduced a multiplicative arithmetic function 
    $D$ by assigning $D(p^a) = a p^{a-1}$ when $p$ is a prime and $a$ is
    a positive integer.
They defined $D^0(n) = n$ and $D^k(n) = D(D^{k-1}(n))$ 
    and they called $\{D^k(n)\}_{k=0}^\infty$ the derived sequence of $n$.
This paper answers some open questions about the function $D$ and 
    its iterates.
We show how to construct derived sequences of 
    arbitrary cycle size, and we give examples for cycles of lengths up to
    10.
Given $n$, we give a method for computing $m$ such that $D(m)=n$, 
    up to a square free unitary factor.

\vskip .4in


\section{Introduction and Results}
Cohen and Iannucci \cite{CohenIannucci03}
    introduced a multiplicative arithmetic function 
    $D$ by assigning $D(p^a) = a p^{a-1}$ when $p$ is a prime and $a$ is
    a positive integer.
They defined $D^0(n) = n$ and $D^k(n) = D(D^{k-1}(n))$ 
    and they called $\{D^k(n)\}_{k=0}^\infty$ the derived sequence of $n$.
Cohen and Iannucci showed that for all $n &lt; 1.5 \times 10^{10}$ the 
    derived sequences are bounded.
Moreover, they showed that the set of $n$ where the derived sequence of $n$ 
    is bounded has a density of at least $0.996$.
Bounded sequences effectively end in a cycle. 
Although Cohen and Iannucci found only cycles of lengths 1 to 6, and 8, they
    conjectured the existence of cycles of any order. 
This paper gives a constructive proof for the existence of cycles of any order.

Given $n$, an integer $m$ such that $D(m)=n$ is referred to
    as a value of $D^{-1}(n)$, and $m$ is called canonical 
    if it has no square free unitary factor. 
(A factor $d$ of $n$ is unitary if $\gcd(d,n/d)=1$ and square free 
    if $p^2\nmid d$ for any prime $p$.) We give a method for
    computing canonical values of $D^{-1}(n)$ and we give 
    an example where $D^{-1}(n)$ has at least $2^{7101}$
    different canonical values.

\section{Cycles of arbitrary order}

We say that the derived sequence has a cycle of order $r&gt;0$ if 
    for sufficiently large $k$ we have $D^{k+r}(n) = D^{k}(n)$ and $r$ is 
    minimal.

For example, we see that the derived sequence of $n=4$ is 
    \[\{2^2,\ 2^2,\ 2^2,\ \cdots \}\]
and hence this has a cycle of order $1$.
Considering the derived sequence of $n = 16$ gives 
    \[\{2^4,\ 2^5,\ 5\cdot 2^4,\ 2^5,\ 5 \cdot 2^4,\ \cdots \}\]
and hence this has a cycle of order $2$.

First we introduce some notation:
Let $\p = [p_1, p_2, \cdots, p_k]$ and $\a = [a_1, a_2, \cdots, a_k]$.
Then we use the notation 
    \[ \p^\a := p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}.\]

Here we show how to create a cycle of arbitrary order.
First we need a lemma:

\begin{lem}
\label{lem:soroosh}
Let $k$ be odd.
Let $\gcd(a,k)$ and $\gcd(b,k)$ be square free.
Then there exists an $n$ such that $a + k n$ and $b + k n$ are 
    both square free.
\end{lem}

\begin{proof}
We do this by showing that the set of $n$ with the property that $a + k n$
    and $b + k n$ are square free has positive density.
For a subset $U \subset \BbN$, let
\[ \mathrm{Density}(U) = \lim_{n \rightarrow \infty} \frac{\#\{x \in U : x&lt;n\}}
    {n}. \]
For $p$ prime, define: \[ 
R_p := \{n \in \BbN: a + k n \not \equiv 0 \pmod{p^2}\ \mathrm{and}\  
                                 b+k n \not \equiv 0 \pmod{p^2} \} \]
    and $S_p = \mathrm{Density}(R_p)$.

If $p | k$ then $S_p$ either equals $1$, $1-\frac{1}{p}$, or 
    $1-\frac{2}{p}$.
(It is worth remarking here that if $k$ is even, and we took $p = 2$
    then $1 - \frac{2}{p} = 0$, and hence positive density is not 
    necessarily shown.)
If $p\nmid k$ then $S_p$ either equals $1 - \frac{1}{p^2}$ or
    $1-\frac{2}{p^2}$.
Let 
\begin{eqnarray*}
R&amp;=&amp;\{n \in \BbN : a + k n \mbox{ and }b + k n \mbox{ are square free }\} \\
 &amp;=&amp; \bigcap_{p \ \mathrm{prime}} R_p.
\end{eqnarray*}
Then, we get that the density of $R$ is
     \begin{eqnarray*} 
\prod_{p \ \mathrm{prime}} S_p  
    &amp; =  &amp; \prod_{p | k } (S_p)  \prod_{p \nmid k} (S_p)  \\
    &amp; \geq  &amp; \prod_{p | k } \left(1-\frac{2}{p}\right) 
              \prod_{p \nmid k} \left(1-\frac{2}{p^2}\right). \\
\end{eqnarray*}
We see that the first product is positive, as there are only a finite number
    of primes $p$ such that $p |k$.
We see that the second infinite product is positive because $\sum\frac{2}{p^2}$
    converges.
%\marginpar{Do we need a reference here?}

Thus we see that the density of $n$ where $a + nk$ and $b+ nk$ are both 
square free is positive, hence there exists at least one.
\end{proof}

\begin{thm} There exist cycles of every order.
\end{thm}

\begin{proof}
This result is proved by constructing a cycle of order $k$ for arbitrary $k$.
Pick $k &gt; 1$.
Pick $k$ distinct odd primes $p_1, \cdots, p_k$.

For $\a = [a_1, \cdots, a_k]$ let
    $\a_i = [a_1, \cdots, a_{i-1}, a_i + 1, a_{i+1}, \cdots, a_k]$.
The goal is to find an $\n$ such that 
\[ D(\p^{\a_1})  = s_1\cdot \p^{\a_2}\]
and in general
\[ D(\p^{\a_i}) = s_i\cdot \p^{\a_{i+1}} \]
where $i+1$ is taken modulo $k$, and the $s_i$ are square free coprime to 
$p_1 \cdot p_2\cdots p_k$.
Then for any $i$, $\p^{\a_i}$ gives a cycle of order $k$.

Note that if we find $a_i$ such that 
\begin{itemize}
\item $a_i$ is square free,
\item $a_i+1$ is square free,
\item $\gcd(a_i, p_i) = p_i$,
\item $\gcd(a_i+1, p_{i+1}) = p_{i+1}$,
\item $\gcd(a_i, p_j) = 1$ for $j \neq i$,
\item $\gcd(a_i+1, p_j) = 1$ for $j \neq i+1$,
\item $\gcd(a_i+1, a_1 a_2 \cdots a_{i-1}) = 1$ for $i &gt; 1$,
\item $\gcd(a_i, a_1 a_2 \cdots a_{i-1}) = 1$ for $i &gt; 1$,
\item $\gcd(a_i, (a_1+1) (a_2+1) \cdots (a_{i-1}+1)) = 1$ for $i &gt; 1$,
\end{itemize}
then $\a = [a_1, \cdots, a_k]$ has the desired property.
It is worth noting here that the last two conditions require 
   all of the $a_i$ to be odd.
To see that $\bar a$ has the desired property, note that
$$D(s_{i-1}\p^{\a_i})=D(\p^{\a_i}) 
 =a_1a_2\cdots(a_i+1)\cdots a_n \p^{\a_i-1} 
 =s_i \p^{a_{i+1}},
$$ 
where the last equality follows from the properties of $\a$.

We can solve for each $a_i$ in order by the use of the Chinese remainder Theorem
    and Lemma \ref{lem:soroosh}.
\end{proof}

In Table \ref{tab:cycle}, $\n$ is given for cycles of 
    sizes $2$ to $10$ for the first $10$ primes.
It should be noted that this construction does not give the smallest
    $n$ where the derived sequence is of order $k$. 
For example, let $s_1 = 2\cdot 7$ and $s_2 = 2\cdot 23$
    then $s_2 \cdot 3^{70}\cdot 5^{5}$ and $s_1\cdot 3^{69}\cdot 5^{6}$ 
    gives rise to a cycle of order two.
The smallest cycle of order two is $2^5$ and $5 \cdot 2^4$, 
    which is considerably smaller.

\begin{table}[H]
\[
\begin{tabular}{|l|llllllllll|}
\hline
Cycle Size &amp; \multicolumn{10}{c|}{Primes} \\
              &amp; 3&amp;  5&amp;  7&amp; 11&amp; 13&amp; 17&amp; 19&amp; 23&amp; 29&amp; 31 \\
\hline
2 &amp; 69  &amp;  5   &amp; &amp;&amp;&amp;&amp;&amp;&amp;&amp;       \\
3 &amp; 129 &amp;  265 &amp;  77 &amp;&amp;&amp;&amp;&amp;&amp;&amp;       \\
4 &amp; 129 &amp;  265 &amp;  1561 &amp;  1397 &amp;&amp;&amp;&amp;&amp;&amp;      \\
5 &amp; 309 &amp;  265 &amp;  1561 &amp;  12661 &amp;  221 &amp;&amp;&amp;&amp;&amp;     \\
6 &amp; 309 &amp;  265 &amp;  1561 &amp;  12661 &amp;  10777 &amp;  1037 &amp;&amp;&amp;&amp;    \\
7 &amp; 309 &amp;  1945 &amp;  1561 &amp;  12661 &amp;  10777 &amp;  15997 &amp;  437 &amp;&amp;&amp;   \\
8 &amp; 309 &amp;  1945 &amp;  1561 &amp;  12661 &amp;  10777 &amp;  15997 &amp;  20653 &amp;  1541 &amp;&amp;  \\
9 &amp; 309 &amp;  1945 &amp;  1561 &amp;  12661 &amp;  10777 &amp;  15997 &amp;  20653 &amp;  4117 &amp;  2117 &amp; \\
10 &amp; 669 &amp; 1945 &amp; 4333 &amp; 12661 &amp; 10777 &amp; 15997 &amp; 20653 &amp; 4117 &amp; 6757 &amp; 4061 \\
\hline
\end{tabular}
\]
\caption{$\n$ that give rise to an various cycle sizes.}
\label{tab:cycle}
\end{table}

\section{Computing $D^{-1}(n)$.}
\label{sec:Dinverse}

By noticing that $D(s) = 1$ for all square free numbers $s$, we see that if 
    we have $D(m)= n$ then $D(m s) = n$ for all
    square free factors $s$ coprime to $m$.
To eliminate these trivial alternate values to $D^{-1}(n)$, we introduce
    the definition:

\begin{defn}
If $\p^\b$ has no square free components (i.e. $b_i \neq 1$ for all $i$) and
$D(\p^\b)=n$ then we say that $\p^\b$ is a canonical value of $D^{-1}(n)$.
We define $D_{c}(n)$ to be the set of all canonical values of $D^{-1}(n)$.
\end{defn}

To compute $D_c(n)$ we need the following
    lemma.

\begin{lem}
\label{lem:core}
If $n = \p^\a$ and $D_{c}(n) \neq \emptyset$, then for every 
$k \in D_{c}(n)$ we have $k=\p^\b$.
Furthermore $0 \leq b_i \leq a_i + 1$.
\end{lem}
\begin{proof}
 This follows immediately by applying $D$ to $\p^\b$.
\end{proof}

In particular an element of $D_{c}(n)$ cannot have prime
    factors that are not also factors of $n$.

\begin{cor}
\label{cor:prime}
Let $p$ be a prime.  
Then $D_{c}(p^a) \neq \emptyset$ if and only if $a = p^k +k -1$ for some $k$.
Further $D_c(p^{p^k +k -1})=\{p^{p^k}\}$.
\end{cor}

\begin{cor} 
\label{cor:odd squarefree}
If $s$ is an odd square free number, then $D_{c}(s) = \emptyset$.
\end{cor}

Given Lemma \ref{lem:core}, it is an easy matter to determine 
    $D_c(n)$.
Simply compute $D(\p^\b)$ where $0 \leq b_i \leq a_i + 1$ and $b_i \neq 1$, 
    and check which ones work.
For large exponents $\b$ this is not particularly efficient, but 
    it suffices for $n &lt; 10^7$.

We see from Corollary \ref{cor:prime} and \ref{cor:odd squarefree} that
    $D_c(n)$ is empty for some values $n$.    
Table \ref{tab:top100} lists $D_c(n)$, if 
    they are nonempty, for all $n \leq 100$.
It is worth noting that, in the case of the first 100, there is a 
    unique canonical value in $D_c(n)$. 
This is not true in general.
The first example when $D_c(n)$ does not have a unique element is 
    $108 = 2^2 \cdot 3^3$ for which we $D_c(108) = \{2^2\cdot 3^3,\ 3^4\}$.
The first six examples of multiple canonical values, less than 2000 
    are listed in Table \ref{tab:double}.

\begin{table}
\[
\begin{array}{|l|l|l|}
\hline
n		&amp; D_c(n) \\
\hline
1 = 1 &amp; \{1 = 1\}\\ 
4 = 2^2 &amp; \{4 = 2^2\}\\ 
6 = 2\cdot 3 &amp; \{9 = 3^2\}\\ 
10 = 2\cdot 5 &amp; \{25 = 5^2\}\\ 
12 = 2^2 \cdot 3 &amp;\{ 8 = 2^3\}\\ 
14 = 2\cdot 7 &amp;\{ 49 = 7^2\}\\ 
22 = 2\cdot 11 &amp;\{ 121 = 11^2\}\\ 
24 = 2^3 \cdot 3 &amp;\{ 36 = 2^2\cdot 3^2\}\\ 
26 = 2\cdot 13 &amp;\{ 169 = 13^2\}\\ 
27 = 3^3 &amp;\{ 27 = 3^3\}\\ 
32 = 2^5 &amp; \{16 = 2^4\}\\ 
34 = 2\cdot 17 &amp; \{289 = 17^2\}\\ 
38 = 2\cdot 19 &amp;\{ 361 = 19^2\}\\ 
40 = 2^3 \cdot 5 &amp;\{ 100 = 2^2\cdot 5^2\}\\ 
46 = 2\cdot 23 &amp; \{529 = 23^2\}\\ 
56 = 2^3 \cdot 7 &amp;\{ 196 = 2^2 \cdot 7^2\}\\ 
58 = 2\cdot 29 &amp;\{ 841 = 29^2\}\\ 
60 = 2^2 \cdot 3\cdot 5 &amp;\{ 225 = 3^2 \cdot 5^2\}\\ 
62 = 2\cdot 31 &amp; \{961 = 31^2\}\\ 
72 = 2^3 \cdot 3^2 &amp; \{72 = 2^3 \cdot 3^2\}\\ 
74 = 2\cdot 37 &amp; \{1369 = 37^2\}\\ 
75 = 3\cdot 5^2 &amp; \{125 = 5^3\}\\ 
80 = 2^4 \cdot 5 &amp; \{32 = 2^5\}\\ 
82 = 2\cdot 41 &amp; \{1681 = 41^2\}\\ 
84 = 2^2 \cdot 3\cdot 7 &amp; \{441 = 3^2 7^2\}\\ 
86 = 2\cdot 43 &amp; \{1849 = 43^2\}\\ 
88 = 2^3 \cdot 11 &amp; \{484 = 2^2 \cdot 11^2\}\\ 
94 = 2\cdot 47 &amp; \{2209 = 47^2\}\\ 
\hline
\end{array}
\]
\caption{$D_c(n)$ for $n \leq 100$ when $D_c(n)$ is non-empty.}
\label{tab:top100}
\end{table}

\begin{table}
\[
\begin{array}{|l|l|l|}
\hline
n		&amp; D_c(n) \\
\hline
108 = 2^2 \cdot 3^3 &amp; \{81 = 3^4, 108 = 2^2 \cdot 3^3\}\\ 
192 = 2^6 \cdot 3 &amp; \{144 = 2^4 \cdot 3^2 , 64 = 2^6\}\\ 
448 = 2^6 \cdot 7 &amp; \{784 = 2^4 \cdot 7^2 , 128 = 2^7\}\\ 
1080 = 2^3\cdot 3^3 \cdot 5 &amp; \{2025 = 3^4 \cdot 5^2 , 
                                2700 = 2^2 \cdot 3^3 \cdot 5^2\}\\ 
1512 = 2^3 \cdot 3^3 \cdot 7 &amp;\{ 3969 = 3^4 \cdot 7^2, 
                                 5292 = 2^2 \cdot 3^3 \cdot 7^2\}\\ 
1920 = 2^7 \cdot 3 \cdot 5 &amp; \{3600 = 2^4 \cdot 3^2 \cdot 5^2, 
                               1600 = 2^6 \cdot 5^2\}\\ 
\hline
\end{array}
\]
\caption{Examples of two different Canonical values, for $n \leq 2000$}
\label{tab:double}
\end{table}

We have the following results concerning the non-uniqueness of the 
    canonical values in $D_{c}(n)$.

\begin{lem}
\label{lem:p+1}
If $m \in D_{c}(p+1)$, then 
    $D_c((p+1) p^p)$ has at least two elements,
    namely $m\cdot p^p$ and $p^{p+1}$.
\end{lem}
\begin{proof}
One only needs to check that $m$ is coprime to $p$, which follows from
    Lemma \ref{lem:core}.
\end{proof}

\begin{lem}
\label{lem:coprime}
If $D_c(n)$ and $D_c(m)$ have $k$ and $l$ elements in them,
and for every $x \in D_c(n)$ and $y \in D_c(m)$ we have $\gcd(x,y)=1$,
    then $D_c(n m)$ has at least
    $kl$ elements.
\end{lem}
\begin{proof}
 For $x \in D_c(n)$ and $y \in D_c(m)$, 
 note that $D(xy)=D(x)D(y)=mn$, since $x$ and $y$ are coprime.
\end{proof}

\begin{ex}
Notice that: \[D_c(3\cdot 2 \cdot 5^5) =\{ 5^6,\ 5^5 \cdot 3^2\}\]
and \[D_c(2\cdot 7 \cdot 13^{13}) = \{13^{14},\ 7^2 \cdot 13^{13}\}.\]
Combining these together, either by Lemma \ref{lem:coprime}, or by
    direct computation we get
\begin{eqnarray*}
D_c(2^2 \cdot 3 \cdot 5^5\cdot 7 \cdot 13^{13}) &amp; = &amp; 
    \{13^{14} \cdot 5^6,\ 7^2 \cdot 13^{13} \cdot 5^6,\\
         &amp;&amp; 13^{14}\cdot 3^2 \cdot 5^5,\ 7^2 \cdot 13^{13} \cdot 3^2\cdot 5^5\}.
\end{eqnarray*}
It should be noted that Lemma \ref{lem:coprime} only shows that these
    four values are contained in $D_c(2^2 \cdot 3 \cdot 5^5\cdot 7 
    \cdot 13^{13})$.
Equality comes from direct computation.
\end{ex}

In particular if $p$ and $2 p -1$ are both prime, then 
    for $n =2\cdot p \cdot (2p-1)^{2p-1}$ we have $D_c(n)$ has 
    at least $2$ elements, namely 
    $p^2 \cdot (2p-1)^{2p-1}$ and $(2p-1)^{2 p}$.
Primes with this property are similar to Sophie Germain primes,  
    in which $p$ and $2 p + 1$ must both be prime \cite{Dubner96, 
    IndlekoferJarai99}.
It is not known if there are infinitely many Sophie Germain primes,
    and there do not appear to be any results of primes $p$ where
    $2 p -1$ is also prime.  
If anything is learned about primes of this form, then the following
    Theorem can be strengthened.
In particular, if Dickson's Conjecture is true (see for instance page 180 of 
    \cite{Ribenboim91}), then there are an infinite number of 
    primes $p$ such that $2 p -1$ is also prime.
In this case, this Theorem can be strengthen,
    by replacing $2^{7101}$ with $M$ an arbitrarily large number.

\begin{thm}
There exists an $n$ such that $D_{c}(n)$ has at least
    $2^{7101}$ elements.
\end{thm}

\begin{proof}
A quick computation verifies that there are 7101 primes $p$ less
    than a million, where $2 p -1$ is also prime, and all of these
    terms are coprime.
Let $P_i := 2 p_i - 1$.
By Lemma \ref{lem:p+1} we see that $D_c(2\cdot p_i \cdot P_i^{P_i})$
    has (at least) two elements, $P_i^{P_i + 1}$ and
    $P_i^{P_i} \cdot p_i^2$.
By Lemma \ref{lem:coprime} we see that if $n = \prod 2\cdot p_i \cdot P_i^{P_i}$
    then $D_c(n)$ has at least $2^{7101}$ elements.
\end{proof}

\section{Conclusions}

In Section \ref{sec:Dinverse} we considered primes $p$ where $2 p -1$ 
    is also prime. 
An interesting observation is that, empirically, 
    there appears to be the same 
    number of these types of primes as there are of Sophie Germain 
    primes.

In \cite{CohenIannucci03}, Cohen and Iannucci conjectured the existence
    of $n$ such that the derived sequence of $n$ is unbounded. 
It would be interesting to know if this is in fact true or not.

It would also be interesting to explore the properties of the $D$ function
    if it is extended in the natural way to rational numbers.
For example:
\( D \left(\frac{16}{9}\right) = D \left(2^4 \cdot 3^{-2}\right)  
    = 4\cdot 2^3 \cdot (-2)\cdot 3^{-3}
    = -2^6 \cdot 3^{-3} = - \frac{64}{27}\) and $D(-1) = -1$.

\section{Acknowledgment}
We would like to thank the organizers of the West Coast Number Theory 
    conference, where we were first introduced to this problem.
We would also like to thank the referee for a number of very useful 
    comments and suggestions.

\bibliographystyle{plain}

\begin{thebibliography}{1}

\bibitem{CohenIannucci03}
G.~L. Cohen and D.~E. Iannucci.
\newblock Derived sequences.
\newblock {\em J. Integer Seq.}, {\bf 6} (2003), Article 03.1.1.

\bibitem{Dubner96}
Harvey Dubner.
\newblock Large {S}ophie {G}ermain primes.
\newblock {\em Math. Comp.}, {\bf 65} (1996), 393--396.

\bibitem{IndlekoferJarai99}
Karl-Heinz Indlekofer and Antal J{\'a}rai.
\newblock Largest known twin primes and {S}ophie {G}ermain primes.
\newblock {\em Math. Comp.}, {\bf 68} (1999), 1317--1324.

\bibitem{Ribenboim91}
Paulo Ribenboim.
\newblock {\em The Little Book of Big Primes}.
\newblock Springer-Verlag, New York, 1991.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11Y55; Secondary 11A25, 11B83.

\noindent \emph{Keywords: Arithmetic functions, multiplicative functions, cycles.}


\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received April 21, 2003;
revised version received  June 23, 2003.
Published in {\it Journal of Integer Sequences},
July 9, 2003.
\bigskip
\hrule
\bigskip

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


\end{document}


</pre></body></html>