\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\card}{card}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Integers That Are Sums of Uniform\\
Powers of All Their Prime Factors:
\vskip 0.15in
The Sequence \seqnum{A068916}}
\vskip 0.18in
\large
Spencer P. Hurd\\
Professor Emeritus of Mathematics\\
The Citadel \\
Charleston, SC\\
USA\\
and \\
P.O. Box 197\\
Meigs, GA 31765 \\
USA \\
\href{mailto:spencerhurd@yahoo.com}{\tt spencerhurd@yahoo.com} \\
\vskip 0.23in
Judson S. McCranie\\
105 Mackqueen Dr. \\
Brunswick, GA 31525 \\
USA \\
\href{mailto:jud@judmccranie.com}{\tt jud@judmccranie.com}
\end{center}
\vskip 0.15 in
\textit{This paper is dedicated to Richard K. Guy on his $102^{nd}$ birthday, 30 September 2018.}
\begin{abstract}
For integers $s \geq 1$ and $n \geq 2$, we define the function $T_s$
as follows: $T_s(n) = T_s(p^aq^b \cdots r^c) = ap^s + bq^s + \cdots
+ cr^s$. Thus $T_s(n)$ is the sum of the $s^{\rm th}$ powers of the
prime factors of $n$, counted according to multiplicity of the prime
factors. The set $T^*(s)$ is defined as $\{n: T_s(n) = n\}$, and we
let $a(s)$ be the smallest element in $T^*(s)$. We consider several
natural questions. Is the set $T^*(s)$ empty, finite or infinite for
some particular values of $s$? Suppose $y$ is a prime power, say $y
= p^m$. Is it possible that $y = T_s(y)$ for some $s$? What is the
smallest element $a(s)$ in the set $T^*(s)$? The answer for the last
question is documented, but only for certain small values of $s$ in the
title sequence, $a(s)$, for $s = 1, 2, \ldots$, namely sequence
\seqnum{A068916} in the {\it Online Encyclopedia of Integer Sequences}. It
begins $2, 16, 1096744, 3125, \ldots $. Some sets $T^*(s)$ are known to
have one or two elements, and $T^*(1)$ is infinite. Some sets $T^*(s)$
have prime powers. In fact, infinitely often $T^*(s)$ contains $p^y$ for
some power $y$ and prime $p$. For example $T^*(24)$ contains $3^{27}$,
which may be the value of $a(24)$. The set $T^*(3)$ contains six known elements,
and none of these are prime powers. We prove $T^*(3)$ does not contain any
prime powers at all. Curiously, every known member of $T^*(s)$ for any value
of $s$, except $s=3$, is in fact a prime power. We also
briefly discuss algorithms
and functions related to $T_s(n)$.
\end{abstract}
\section{Introduction}
\label{sec:intro}
The decomposition of a number into prime factors is sometimes critical
for understanding the action of a function whose range and domain are
contained in the set of natural numbers. Insight may be obtained from
computer searches related to the function. Here these ideas play a role
in the function of this note whose very definition also depends on this
prime decomposition.
\begin{definition}
Let $n > 1$ be any positive integer whose prime factorization into distinct prime factors is given by $n = p^aq^b \cdots r^c$. We define, for each positive integer $s$, the function $T_s$ on the set $\{n: n \in \mathbb{Z}, n>1\}$ as follows:
$$T_s(n)=T_s(p^aq^b \cdots r^c)=ap^s+bq^s+ \cdots +cr^s.$$
Further, we say that $T_s(n)$ is the \textit{sum} of the $s^{\rm th}$ powers of the prime factors of $n$, counted according to multiplicity of the prime factor. The set $T^*(s)$ is defined as $\{n: T_s(n) = n\}$, and we denote the smallest element in $T^*(s)$ by $a(s)$.
\end{definition}
\begin{example}\label{origEx1}
$T_s(200)=T_s(2^35^2)=2^s+2^s+2^s+5^s+5^s=3(2^s)+2(5^s)$ and for $s=4$, $T_4(200)=3(2^4)+2(5^4)=1298$. Since $2^3 \parallel 200$, $3 \cdot2^4$ occurs in $T_4(200)$. Since $T_4(200) \neq 200$, $200 \not \in T^*(4)$. From Table~\ref{tab:tabA068916}, $a(4) = 3125$, the smallest element in $T^*(4)$.
\end{example}
In this note we consider several natural questions. Is the set $T^*(s)$
empty, finite or infinite for some particular values of $s$? Suppose $y$
is a prime power, say $y = p^m$. Is it possible that $y = T_s(y)$ for
some $s$? What is the smallest element $a(s)$ in the set $T^*(s)$?
The answer for the last question is documented, but only for certain
small $s$, and this brings us to the title sequence, which is $a(s)$,
for $s = 1, 2, \ldots$. It is sequence \seqnum{A068916} in the
{\it Online Encyclopedia of Integer Sequences} \cite{1}. It begins $2,
16, 1096744, 3125, \ldots $. We list what is known of these values in
Table~\ref{tab:tabA068916}. We also list the smallest known values as
upper bounds for $a(s)$ when $a(s)$ is not known. We write ``unknown"
in Table~\ref{tab:tabA068916} to mean not only is $a(s)$ not known but
also that no elements in $T^*(s)$ have even been discovered! For any set
$T$ we use $\card(T)$ to denote its cardinality, and we are especially
interested in $\card\bigl(T^*(s)\bigr)$ for any value of $s$.
For $s=16$, we may calculate $T_{16}(17^{17}) = 17(17^{16}) = 17^{17}$. Thus, ${17^{17} \in T^*(16)}$ and thus $a(16) \leq 17^{17}$. Currently this number $17^{17}$ only provides an upper bound for $a(16)$ because its minimality has not yet been confirmed by a computer search. Indeed, there is no method yet known other than a computer verification for determining the correctness of the entries in the sequence \seqnum{A068916}, except for very small values of $s$.
Two facts about Table~\ref{tab:tabA068916} are immediately clear. First, many of the entries are powers of a prime. So, $a(s) = p^y$ quite often for some power $y$ and prime $p$.
\begin{table}
\centering
\begin{tabular}{| l | l || l | l |}
\hline
$s$ & $a(s)$ & $s$ & $a(s)$ \\
\hline
$1$ & $2$ & $12$ & $65536=2^{16}$\\
\hline
$2$ & $16=2^4$ & $13 \mbox{--} 15$ & unknown\\
\hline
$3$ & $1096744 = 2^3\cdot 11^3\cdot 103$ & $16$ & $\leq 17^{17}$\\
\hline
$4$ & $3125 = 5^5$ & $17$ & unknown\\
\hline
$5$ & $256 = 2^{2^3}$ & $18$ & $\leq 19^{19}$\\
\hline
$6$ & $823543 = 7^7$ & $19 \mbox{--} 21$ & unknown\\
\hline
$7$ & $19683 = 3^{3^2}$ & $22$ & $\leq 23^{23}$\\
\hline
$8,9$ & unknown & $23$ & $\leq 298023223876953125 = 5^{25}$\\
\hline
$10$ & $285311670611 = 11^{11}$ & $24$ & $7625597484987 = 3^{27}$\\
\hline
$11$ & unknown & & \\
\hline
\end{tabular}
\caption{The sequence \seqnum{A068916}, $a(s)$ is the smallest element in $T^*(s)$}
\label{tab:tabA068916}
\end{table}
Secondly, not all of the elements of $T^*(s)$ are prime powers. Note for $s=3$ that $a(3)$ is the product of seven primes, three of which are distinct. Nevertheless, it is further striking that, except for $s=3$, all the entries in Table~\ref{tab:tabA068916} are powers of a prime. It is still more striking that $T^*(3)$ has six known elements, none of which are prime powers, and these six are the only non-prime powers known to be in $T^*(s)$ for any $s$. (See Section~\ref{sec:setsT*3} and Table~\ref{tab:tabKnownT3}.)
\begin{theorem} \label{origThm1}
Suppose the number $y$ is a prime power, say $y=p^m$. Then $y$ is in set $T^*(s)$ if and only if $m=p^k$ for some $k$, and $s=p^k-k$.
\end{theorem}
\begin{proof}
By the hypothesis, $y=p^m$. First suppose $y$ is in set $T^*(s)$. This means $T_s(y)=y=p^m$. But by the definition of $T_s$, $T_s(p^m)=mp^s$, from which $mp^s=p^m$. By division, $m=p^k$ for $k=m-s$. Thus, $s=m-k=p^k-k$.
Conversely, by substitution, $T_s(y) = T_s(p^m) = T_{(m-k)}(p^m) = mp^{m-k} = p^k p^{m-k} = p^m = y$. So, $y$ is in the set $T^*(s)$.
\end{proof}
\begin{corollary} \label{origCor1}
Let $s=p-1$ for some prime $p$. Then $T_s(p^p)=p^p$.
\end{corollary}
\begin{proof}
Take $k=1$ in Theorem~\ref{origThm1}.
\end{proof}
\begin{example} \label{origEx2}
Observe 256 is in set $T^*(5)$ since $T_5(256) = T_5(2^8) = 8\cdot 2^5 = 2^8 = 256$. This illustrates Theorem~\ref{origThm1} as $s = 5 = 2^3 - 3$, and $256 = 2^{2^3}$.
\end{example}
\subsection{Historical remarks}
The sequence \seqnum{A068916} was first
recorded by D. Hickerson in March 2002 in the
{\it Online Encyclopedia of Integer Sequences} \cite{1}.
It was based on the related sequence \seqnum{A067688},
which was recorded a month earlier by J. L. Pe, on February 4 2002.
The earlier sequence lists only composite $m$ for which there is
some $s$ such that $T_s(m) = m$.
Focusing on \seqnum{A068916} allows us to consider the sets $T^*(s)$ more
deeply, as well as the numbers $m$ that satisfy $T_s(m) = m$ for some $s$.
The pattern for prime power elements in $T^*(s)$, that $p^{p^k}$ was in $T^*(s)$ when $s = p^k - k$ was noted in 2003 (JSM). The other half of Theorem~\ref{origThm1}, that all prime powers in $T^*(s)$ for any $s$ must have this form, seems to be new here.
Later contributors D. Hickerson (March 07 2003) and J. S. McCranie (March 16 2003) confirmed earlier entries and extended the list. Donovan Johnson (May 17 2010) noted, in our notation, that $T^*(24)$ contained $3^{27}$ and that $T^*(12)$ contained $13^{13}$. M. Marcus (\seqnum{A068916}) and C. R. Greathouse (\seqnum{A067688}) added programs for testing numbers in January 2016. McCranie (January 18 2016) put upper bounds on $a(23)$ and $a(24)$ in Table~\ref{tab:tabA068916} and reported (on January 30 2016) that $a(24) = 3^{27}$. In between he reported that $a(10) = 11^{11}$. The new sequence \seqnum{A268036} contains material in our Table~\ref{tab:tabKnownT3}.
Table~\ref{tab:tabA268594} contains a new listing of small $s$ such that $T^*(s)$ is known to contain (at least) two elements. We conjecture that there are infinitely many $s$ such that $T^*(s)$ contains two prime powers (see Section~\ref{sec:conclusion}).
Recently we learned of papers \cite{2} and \cite{3}, in which J.-M. De Koninck and F. Luca consider two different functions similar to our $T_s$. In these, an integer $n$ is represented as a sum of equal powers $s$ of some subset (not necessarily all) of its prime factors, and the prime factors are not counted by the multiplicity of the prime factor in the factorization. They list the second through sixth items in our Table~\ref{tab:tabKnownT3} (in Section~\ref{sec:setsT*3}) in their papers. For example they also give $378 = 2 \cdot 3^3 \cdot 7 = 2^3 + 3^3 + 7^3$, as 378 can be written as the sum of the cubes of its prime factors, with multiplicity ignored, and $870 = 2\cdot 3\cdot 5\cdot 29 = 2^2 + 5^2 + 29^2$ equal to squares of a proper subset of its prime factors.
\section{The sets $T^*(s)$ for various $s$}
\label{sec:setsT*various}
It turns out that for many values of $s$, $\card(T^*(s)) \ge 2$, but there are no known values of $s$ such that $\card(T^*(s))$ is exactly 2. The smallest values of $s$ are shown in Table~\ref{tab:tabA268594}.
\begin{table}
\centering
\begin{tabular}{|c|c|c||c|c|c|}
\hline
$s$ & $p^k-k$ & $q-1$ & $s$ & $p^k-k$ & $q-1$\\
\hline
2 & $2^2-2$ & $3-1$ & 65520 & $2^{16}-16$ & $65521-1$\\
\hline
12 & $2^4-4$ & $13-1$ & 161046 & $11^5-5$ & $161047-1$\\
\hline
58 & $2^6-6$ & $59-1$ & 262126 & $2^{18}-18$ & $262127-1$\\
\hline
238 & $3^5-5$ & $239-1$ & 300760 & $67^3-3$ & $300761-1$\\
\hline
3120 & $5^5-5$ & $3121-1$ & 1295026 & $109^3-3$ & $1295027-1$\\
\hline
6856 & $19^3-3$ & $6857-1$ & 3442948 & $151^3-3$ & $3442949-1$\\
\hline
29788 & $31^3-3$ & $29789-1$ & 9393928 & $211^3-3$ & $9393929-1$\\
\hline
50650 & $37^3-3$ & $50651-1$ & & & \\
\hline
\end{tabular}
\caption{ Small $s$ such that $T^*(s)$ has two prime powers, see \seqnum{A268594} }
\label{tab:tabA268594}
\end{table}
$T_1(2) = 2$ and $T_1(4) = T_1(2^2) = 2(2^1) = 4$. So, $T^*(1)$ contains $\{2, 4\}$ and these are the prime powers guaranteed by Theorem~\ref{origThm1}. What other elements are in $T^*(1)$? Is $T^*(1)$ a finite set?
\begin{theorem} \label{origThm2}
We have $T^*(1) = \{4, 2, 3, 5, 7, \ldots \} = \{4, \text{\rm all primes} \}$.
\end{theorem}
\begin{proof}
For any prime $p$, we have $T_1(p^1) = 1(p^1) = p$.
So $T^*(1)$ contains $\{4, \text{\rm all primes}\}$. But for any composite greater than 4, the sum of its prime factors (counted by multiplicity) is less than the product.
\end{proof}
Are there other values of $s$ for which $T^*(s)$ is infinite? None are known, but likewise there is no reason to suppose any is finite. Or is there? We conjecture $T^*(2)$ is a finite set.
We observe that $T_2(16) = T_2(2^4) = 4\cdot 2^2 = 4\cdot 4 = 16$. Also, $T_2(27) = T_2(3^3) = 3\cdot 3^2 = 27$. This shows the set $T^*(2)$ contains \{16, 27\}, both prime powers, and $2 = 2^2 - 2 = 3^1 - 1$. Examination of cases shows $a(2) = 16$. Are other prime powers in $T^*(2)$ besides $2^4$ and $3^3$? No, because it would require, by Theorem~\ref{origThm1}, that $2 = p^k - k$, for some prime $p$ and integer $k$. If $k = 1,2$ then $p = 3, 2$ respectively. Suppose $k > 2$, $p > 3$, and $2 = p^k-k$. Then we claim $p^k = 2+k$ is contradictory. To see this, observe that $2 + k < 5^k$ for any $k > 2$. But $3 < p$ implies $5^k \leq p^k$ as $p$ is an odd prime. Combining inequalities, $2 + k < 5^k \leq p^k = 2 + k$, the desired contradiction. We extend this argument to other cases in Theorem~\ref{origThm3}.
\begin{theorem} \label{origThm3}
Suppose $p$ is a prime, $s > 1$, and $s + 1 < p$. Then no power of $p$ is contained in $T^*(s)$.
\end{theorem}
\begin{proof}
We observe the result is true for $s = 2$, so we may suppose $3 \leq s$ and $5 \leq p$. Suppose on the contrary that $T_s(p^m) = p^m$ for some $m$. Then, by Theorem~\ref{origThm1}, $m = p^k$ for some $k$, and $s = p^k - k$. So, $p^k - k = s < p - 1$. Thus, $p^k < p + k - 1$. Now, for $k = 1$, the last inequality reduces to $p < p$, a contradiction. If $1 < k$, then define $f(p) = p^k - (p + k - 1)$. Note that the derivative of $f$, $f'(p) = kp^{k-1} - 1$, is positive and thus $f(p)$ is a strictly increasing function since $k > 1$. Thus, $p^k > p + k - 1$, a contradiction.
\end{proof}
An obvious consequence of Theorem~\ref{origThm3} is that, for any $s$, the subset of $T^*(s)$ that contains only prime powers is finite, bounded above by the case $s = p-1$.
\begin{example}\label{origEx3}
Using Example~\ref{origEx2}, with $s = 2^6-6$, we get the following: $T_{58}(2^{64}) =T_{58}(2^{2^6}) = (2^6)T_{58}(2) = (2^6)2^{58} = 2^{64}$. Note $T_{58}(59^{59}) = 59^{59}$. We may calculate: $\log_2(59^{59}) = 59\cdot \log_2(59) > 59\cdot \log_2(32) = 59\cdot 5 = 295 > 64 = \log_2(2^{64})$. This shows $a(58)$ may be $2^{64}$, which is smaller than $59^{59}$. We generalize this example in Theorem~\ref{origThm4}.
\end{example}
We have no examples such that $p^k - k = q^j - j$ with neither $j = 1$ nor $k = 1$, and we conjecture that none exist. If $p = 2$ and $j > 1$, our computer
search shows that there are no such $q$ for $2^k - k = q^j - j$ up to $1.84\times10^{19}$. C. R. Greathouse has extended this to $10^{40}$. See \seqnum{A268594} for a partial list of $s = p^k - k = q^j - j$, as in Table~\ref{tab:tabA268594}.
The Catalan conjecture (now Mih\u{a}ilescu's theorem) is that $p^k$ and
$q^j$ never differ by 1 when $\min{(k,j)} \ge 2$, except for $2^3 = 8$
and $3^2 = 9$. We also mention the related Pillai conjecture (unproved)
that, for any fixed positive integer $r$, there are only finitely
many differences of prime powers that equal $r$. More generally, it
is equivalent to the following
claim: for fixed positive integers $A$, $B$, and $C$,
the equation $Ax^n - By^m = C$ has only finitely many solutions $(x, y,
m, n)$ with $(m, n) \not= (2, 2)$.
Assume that every natural number $C$ will occur as a difference of prime powers only finitely often. We are looking for special elements in such a finite set --- those whose prime powers have a difference $C$ and also such that the powers themselves have $C$ as their difference. Such dual differences must be especially scarce.
\begin{conjecture}
Suppose $p, q$ are distinct primes.
Then we conjecture $p^k-q^j \ne k-j$ if $j, k > 1$.
Further, there are infinitely many triples $(p,k,q)$ such that $p^k-k = q-1$.
\end{conjecture}
See Table~\ref{tab:tabA268594} for examples for which this equality holds. See Table~\ref{tab:tabA318606} for examples of $s$ such that $T^*(s)$ is not empty.
For every example in Table~\ref{tab:tabA268594}, the second item is
$s = q-1$. Is this always the case? We conjecture the following.
\begin{conjecture}
Whenever exactly
two elements are contained in $T^*(s)$, both are prime powers and one
of them is $q^q$ for $s = q-1$ and the other is $p^m$ for $m = p^k$
and $s = p^k - k$.
\end{conjecture}
\begin{table}
\centering
\begin{tabular}{| l |}
\hline
1 2 4 5 6 7 10 12 16 18 22 23 24 27 28 30 36 40 42 46 47 52 58 60\\
66 70 72 77 78 82 88 96 100 102 106 108 112 119 121 122 126 130\\
136 138 148 150 156 162 166 167 172 178 180 190 192 196 198\\
210 222 226 228 232 238 240 248 250 256 262 268 270 276 280\\
\hline
\end{tabular}
\caption{Numbers $s$ of the form $s=p^k-k$ for some $k\ge 0$, sequence \seqnum{A318606}}
\label{tab:tabA318606}
\end{table}
\begin{theorem}\label{origThm4}
Suppose $p, q$ are primes with $p < q$ and that $s, k, i$ are natural numbers with $i \ge 1$ such that $p^k - k = q^i - i = s$. Then asymptotically, $a(s) \leq p^{p^k} < q^{q^i}$.
\end{theorem}
\begin{proof} To begin with, $a(s) \leq p^{p^k}$ is a result of Theorem~\ref{origThm1}. Now by hypothesis we have $p < q$ or equivalently $\frac{q}{p} < 1$. Let $J_1$ denote the inequality $p^{p^k} < q^{q^i}$ and let $J_2$ denote the inequality $(\frac{p}{q})^s < 1 - \frac{k-i}{p^k}$. It is easy to show by elementary algebra, the target inequality $J_1$ is true if and only if $J_2$ is true asymptotically. (It is convenient for this algebra to note that $p^k = s + k$ and $q^i = s + i$.) We will argue that $J_2$ is true. First, since $s=p^k-k$, $s$ increases exponentially with $k$ and thus $(\frac{p}{q})^s$ decreases exponentially towards 0. But $\frac{k-i}{p^k}$ converges to 0 as well. It follows that the left-hand side of $J_2$ converges to 0 and the right-hand side converges to 1 as $s$ increases. This shows that $J_2$ is true asymptotically.
\end{proof}
We note that for all known cases for which $T^*(s)$ has two prime powers (see Table~\ref{tab:tabA268594}), $p^k$ and $q^i$ with $p < q$, it is always the case that $i=1$. For an illustration of Theorem~\ref{origThm4}, consider $p = 37$ in Table~\ref{tab:tabA268594}. We have $k = 3$, $q = 50651$ and $i = 1$, and $s = q^1 - 1 = 50650$. Then $J_2$ gives $(\frac{2}{50651})^{50650} < 1 - \frac{2}{37^3}$. The left side is too small to calculate without a few pages of decimal zeroes. The right side is $0.99996\ldots$.
When there are two (or possibly more) prime power elements in $T^*(s)$ for some $s$, the lesser prime always corresponds to the smaller element and gives the lower upper bound for $a(s)$ according to Theorem~\ref{origThm4}.
Theorem~\ref{origThm1} gives an upper bound for a search criterion for $a(s)$ provided there is a prime $p$ such that $s = p^k - k$ for some $k$. We suspect that most searches looked for these special $s$. We listed in Table~\ref{tab:tabA318606} numbers of the form $s = p^k - k$ for some $p, k$, such that $s < 1000$. Of course the corresponding $T$-values are relatively huge, as $T_s(y) = y = p^{p^k}$.
\section{The sets $T^*(3)$ and related questions}
\label{sec:setsT*3}
Table~\ref{tab:tabKnownT3} lists the numbers presently known to be in $T^*(3)$, a case that is strikingly different from all the other known cases.
For example, let $y = 1096744 = 2^3\cdot 11^3\cdot 103$. Then $T_3(y) = 3\cdot 2^3 + 3\cdot 11^3 + 1\cdot 103^3 = 1096744 = y$. Exhaustive computer calculation shows $1096744 = a(3)$, the smallest element of $T^*(3)$.
We classify the examples in Table~\ref{tab:tabKnownT3} as ``irregular". They do not occur with the prime power form suggested in Theorem~\ref{origThm1}. We do not know if the set $T^*(s)$ will often contain a lengthy product of (distinct) primes or other elements with exactly five distinct prime factors. Will any of the sets $T^*(s)$ contain numbers with arbitrarily many distinct prime factors? This is unknown.
\begin{table}
\centering
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{} \\
\hline
$n$ in set $T^*(3)$ & Prime decomposition \\
\hline
1096744 $= a(3)$ & $2^3\cdot 11^3\cdot 103$ \\
\hline
2836295 & $5\cdot 7\cdot 11\cdot 53\cdot 139$ \\
\hline
4473671462 & $2\cdot 13\cdot 179\cdot 593\cdot 1621$ \\
\hline
23040925705 & $5\cdot 7\cdot 167\cdot 1453\cdot 2713$ \\
\hline
13579716377989 & $19\cdot 157\cdot 173\cdot 1103\cdot 23857$ \\
\hline
119429556097859 & $7\cdot 53\cdot 937\cdot 6983\cdot 49199$ \\
\hline
\end{tabular}
\caption{ Known elements in $T^*(3)$, sequence \seqnum{A268036}}
\label{tab:tabKnownT3}
\end{table}
An entry in Table~\ref{tab:tabKnownT3} mentions that $n = 2836295 = 5^3 + 7^3 + 11^3 + 53^3 + 139^3$ is the smallest number that is a product of five distinct prime factors and is also the sum of the cubes of these distinct prime factors. The third entry in Table~\ref{tab:tabKnownT3} is due to McCranie (2003), the fourth to D. Johnson (2010), and the fifth and sixth to McCranie (February 07 2016). But see the comment at the end of Section~\ref{sec:intro}.
\subsection{Remarks on computation} Running our program (by JSM) on 16 CPUs for about 47 hours determined that 13579716377989 is the fifth solution for $T^*(3)$ and that there is no other smaller element in $T^*(4)$. The determination of the sixth element took 27 days.
In Table~\ref{tab:tabA067688} we have factored each value of $m$ so that we are able to see the interplay in the related sequences and the applications of Theorem~\ref{origThm1}. The sixth element 119429556097859 from our Table~\ref{tab:tabKnownT3} is the seventeenth in the sequence \seqnum{A067688} (see the end of Section~\ref{sec:intro}). Forty-eight days of computing by JSM revealed on April 22 2016 that $13^{13}$ was confirmed to be the eighteenth value (in size) of $m$ so that $T_s(13^{13}) = 13^{13}$ for $s =12$, and it became the eighteenth element in \seqnum{A067688}. At present we can say the nineteenth element is conjectured to be $5^{25}$.
\begin{table}
\centering
\begin{tabular}{|c|c|c|}
\multicolumn{3}{c}{} \\
\hline
Index & $s$ & $m$ \\
\hline
1 & 2 & $4=2^2$ \\
\hline
2 & 2 & $16 = 2^4$ \\
\hline
3 & 2 & $27 = 3^3$ \\
\hline
4 & 5 & $256 = 2^8$\\
\hline
5 & 4 & $3125 = 5^5$ \\
\hline
6 & 7 & $19683 = 3^9$ \\
\hline
7 & 12 & $65536 = 2^{16}$ \\
\hline
8 & 6 & $823543 = 7^7$ \\
\hline
9 & 3 & $1096744 = 2^3\cdot 11^3\cdot 103$ \\
\hline
10 & 3 & $2836295 = 5\cdot 7\cdot 11\cdot 53\cdot 139$\\
\hline
11 & 27 & $4294967296 = 2^{32}$ \\
\hline
12 & 3 & $4473671462 = 2\cdot 13\cdot 179\cdot 593\cdot 1621$ \\
\hline
13 & 3 & $23040925705 = 5\cdot 7\cdot 167\cdot 1453\cdot 2713$ \\
\hline
14 & 10 & $2825311670611=11^{11}$ \\
\hline
15 & 24 & $7625597484987= 3^{27}$ \\
\hline
16 & 3 & $13579716377989 = 19\cdot 157\cdot 8173\cdot 1103\cdot 23857$ \\
\hline
17 & 3 & $119429556097859= 7\cdot 53\cdot 937\cdot 6983\cdot 49199$ \\
\hline
18 & 12 & $302875106592253= 13^{13}$ \\
\hline
19? & 23 & $298023223876953125 = 5^{25}$ \\
\hline
20 & ? & unknown \\
\hline
\end{tabular}
\caption{Sequence \seqnum{A067688}, ordered by size of $m$}
\label{tab:tabA067688}
\end{table}
\begin{theorem}\label{origThm5}
If $s \ge 1$, $p, q,\ldots ,r$ are $2u$ distinct primes, and $n = pq \cdots r $, then $n \not \in T^*(s)$.
\end{theorem}
\begin{proof}
First suppose the $2u$ primes are odd. Observe $T_s(n) = p^s + q^s +\cdots + r^s$ is even, being the sum of an even number of odd integers. However, $n$ is odd. Now suppose $p = 2$, and $n = 2q\cdots r$. Here $n$ is even, but $T_s(n)$ sums to $2^s$ plus an odd number of odd integers and is thus odd. In both cases, $n \not \in T_s(n)$.
\end{proof}
\begin{theorem}\label{origThm6}
Suppose $p, q$, and $r$ are three distinct odd primes. (a) If $n = pqr$, then $n \ne T_3(n)$. (b) If $n = 2^kpqr$, then $n \ne T_3(n)$.
\end{theorem}
\begin{proof}
First, for part (a) suppose $p \equiv q \equiv r \equiv 1 \pmod{4}$. Then $n \equiv 1 \pmod{4}$ but $T_3(n) \equiv 1^3+1^3+1^3 \equiv 3 \pmod{4}$. Next suppose $n \equiv (-1)(1)(1) \equiv -1 \pmod{4}$. However, here $T_3(n) \equiv (-1)^3 + 1^3 + 1^3 \equiv 1 \pmod{4}$. Next, if $n \equiv (-1)(-1)(1) \equiv 1 \pmod{4}$, then $T_3(n) \equiv (-1)^3 + (-1)^3 + 1^3 \equiv -1 \pmod{4}$. Finally, if $n \equiv (-1)(-1)(-1) \equiv -1 \equiv 3 \pmod{4}$, then $T_3(n) \equiv (-1)^3 + (-1)^3 + (-1)^3 \equiv -3 \equiv 1 \pmod{4}$. Now for part (b), observe, $n \neq T_3(n)$ because $T_3(n) = k \cdot 2^3 + p^3 + r^3 + q^3$ which is odd; but $n$ is even.
\end{proof}
Theorem~\ref{origThm6} also applies when there are $4k+3$ for $k>0$. This, along with Theorem~\ref{origThm5} means that for members of $T^*(3)$ that are the product of distinct odd primes, the number of primes must be 1 more than a multiple of 4.
According to Theorem~\ref{origThm5} (for $s=3$) and Theorem~\ref{origThm6}, we should begin a search for $n$ in $T^*(3)$ by considering $n = pqrst$, a product of five distinct odd primes or $n = p^aq^br^c$ with each of $p, q, r, a, b, c$ odd (and at least one exponent at least 3), or $n = 2^kq^br^c$ with $b,c$ odd. Happily this is exactly where the elements of $T^*(3)$ have been found.
Are there any prime powers in $T^*(3)$? No, by Theorem~\ref{origThm1}, since 3 is not equal to $p^k - k$ for any $p, k$. This is easily checked. By Theorem~\ref{origThm3}, we need only check primes not greater than 4.
One wonders if there are many other numbers in $T^*(3)$, i.e., is $T^*(3)$ finite or very sparse? It would be curious if a sieve argument, or any argument, could show $T^*(x)$ is finite for some $x$, since $T^*(1)$ is infinite. In fact,
the totality of examples for all known $s$ suggest that integers in $T^*(3)$ abound, compared to $T^*(s)$ for $s = 2$ or $s > 3$.
\section{Eliminating possibilities for $T^*(2)$}
\label{sec:eliminating}
For some prime decomposition forms of the variable $n$ we are able to show $T_2(n)$ is not equal to $n$. The general purpose here is two-fold. Ideally, since $T^*(2)$ contains at least $\{16,27\}$ one would like to prove that $\card(T^*(2)) = 2$, or to be able to use these results to simplify or direct computer
searches.
In what follows we use $p, q, r, s$ to represent odd primes in increasing order. We observe that if $n = pq \cdots s$ for a series of $k$ distinct odd primes, then $n \equiv 1,3 \pmod{4}$, $T_2(n) \equiv k \pmod{4}$.
We further note that, if $p > 3$ is prime, then (a) $p \equiv 1,2 \pmod{3}$, and (b) $p$ is -1 or +1 $\pmod{6}$, and so $p^2 \equiv 1 \pmod{6}$. Similarly, since any odd integer $u$ is $4v+1$ or $4v-1$ for some $v$, it follows that $u^2 \equiv 1 \pmod{8}$.
\begin{lemma}\label{origLemma1}
Suppose $n = p^aq^b$ for two distinct odd primes $p, q$.\\
(a) If $a + b \equiv 0 \pmod{2}$, then $n \neq T_2(n)$.\\
(b) If $a = 2$ and $b = 1$ then $n \neq T_2(n)$.
\end{lemma}
\begin{proof}
For part (a), if $a + b$ is even, then $T_2(n)$ is even but $n$ is odd. For part (b), if $n = T_2(n)$, then $n = p^2q = 2p^2 + q^2 = T_2(n)$, from which $p^2(q-2) = q^2$. This last equation implies $q$ divides either $p$ or $(q-2)$, an impossibility in either case.
\end{proof}
\begin{lemma}\label{origLemma2}
Suppose $n = p^{2a}q^{2b+1}$ where $p, q$ are distinct odd primes. Then
\begin{itemize}
\item[(a)] if $q > 2a$ or if $p > 2b+1$, then $n \neq T_2(n)$.
\item[(b)] if $q^2 \nmid a$ or if $p^2 \nmid 2b+1$, then $n \neq T_2(n)$.
\end{itemize}
\end{lemma}
\begin{proof}
Part (a): Suppose $q > 2a$. If, on the contrary, $n = p^{2a}q^{2b+1} = T_2(n) = 2ap^2 + (2b+1)q^2$, then rearranging terms, $p^{2a}q^{2b+1} - 2ap^2 = (2b+1)q^2$. This implies $p^2[p^{2a-2}q^{2b+1} - 2a] = (2b+1)q^2$. The last equation implies, since $q$ cannot divide $p^2$, that $q$ must divide the term in brackets. This is only possible if $q$ divides $2a$. But $q$ is larger than $2a$. The other case is similar, and in either case, $n \neq T_2(n)$.
Part (b): The equation $p^2(p^{2a-2}q^{2b+1}-2a) = (2b+1)q^2$ implies both that $q^2$ divides the term $(p^{2a-2}q^{2b+1} - 2a)$, and also that $p^2$ divides $2b+1$. But this contradicts the hypothesis, and we conclude $n \neq T_2(n$).
\end{proof}
\begin{lemma} \label{origLemma3}
If $n = 2^kpq$, then $n$ is not equal to $T_2(n)$.
\end{lemma}
\begin{proof}
Supposing otherwise, first let $k = 1$. Now $q = p + a$ for some integer $a$. Then $n = 2p(p+a)$ and $T_2(n) = 4 + p^2 + (p+a)^2$. Thus, equating $n$ and $T_2(n)$, we get $2p^2 +2pa = 4 + p^2 + p^2 + 2pa + a^2$. This simplifies to $0 = 4 + a^2$, a contradiction. If $k > 1$, then $n \equiv 0 \pmod{ 4}$, but $T_2(n)\equiv 4k + p^2 + q^2 \equiv 2 \pmod{4}$.
\end{proof}
\begin{lemma}\label{origLemma4}
\begin{itemize}
\item[(a)] Suppose $n = 2^kpq \cdots r$ and $k > 0$. If $pq \cdots r$ is a product of an odd number of distinct primes, then $n \not \in T^*(2)$.
\item[(b)] Let $n = 2^kp^xq^y \cdots r^z, k > 0$. Suppose the $p, q, \dots ,r$ are distinct odd primes and suppose that $2m+1$ of the exponents $x, y, \ldots, z$ are odd. Then $n \not \in T^*(2)$.
\item[(c)] Suppose $n = 2^kpq \cdots r$ and $k > 1$. If $pq \cdots r$ is a product of $4m+2$ distinct primes, then $n \not \in T^*(2)$.
\end{itemize}
\end{lemma}
\begin{proof}
This follows at once for (a) and (b) since $n$ is even but $T_2(n)$ is odd. Part (c) follows because $n \equiv 0 \pmod{4}$ but $T_2(n) \equiv 2 \pmod{4}$.
\end{proof}
\begin{lemma} \label{origLemma5}
Suppose $n = 2^kpqrs$ and $1 \leq k$.
\begin{itemize}
\item[(a)] If $k = 1$ then $n \neq T_2(n)$.
\item[(b)] If $k = 2$, then $n \neq T_2(n)$.
\item[(c)] Suppose $p = 3$ and $n = 2^k\cdot 3qrs$. If $k = 6m+1$ or $6m+5$, then $n = 2^k\cdot 3qrs\neq T_2(n)$.
\end{itemize}
\end{lemma}
\begin{proof}
For (a), if $k = 1$, then $n \equiv 2 \pmod{4}$. But then $T_2(n) \equiv 2^2 + p^2 + q^2 + r^2 + s^2 \equiv 0 \pmod{4}$.
For part (b) first let $3 < p$. Then $n \equiv 1,2 \pmod{3}$, but then $T_2(n) \equiv 2\cdot 2^2 + p^2 + q^2 + r^2 + s^2 \equiv 8 + 1 + 1 + 1 + 1 \equiv 12 \equiv 0 \pmod{3}$. Now, let $p = 3$. Then $n = 12qrs \equiv 0 \pmod{3}$. Note that $T_2(n) \equiv 2\cdot 2^2 + 9 + q^2 + r^2 + s^2 \equiv 8 + 0 + 1 + 1 + 1 \equiv 2 \pmod{3}$.
For part (c),
$n \equiv 0 \pmod{3}$ since $p = 3$. Say $k = 6m+w$, for $w = 1$ or $5$. Then $T_2(n) \equiv 4(6m+w) + 0 + 1 + 1 + 1 \equiv w \equiv 1,5 \pmod{3}$.
\end{proof}
\begin{theorem}\label{origThm7}
Suppose $n = 2^kpqrs$. If $k = 2m$, then $n \neq T_2(n)$.
\end{theorem}
\begin{proof}
In view of Lemma~\ref{origLemma5}, we assume $4 \leq k = 2m$. Now $n \equiv 0 \pmod{8}$, by hypothesis. We note that every odd integer $u$ satisfies $u = 4U + 1$ or $u = 4U - 1$ for some $U$. In either case, $u^2 \equiv 1 \pmod{8}$. Thus, $T_2(n) = 2m(2^2) + p^2 + q^2 + r^2 + s^2 \equiv 4 \pmod{8}$.
\end{proof}
\begin{theorem}\label{origThm8}
Suppose $n = 2^kpqrs$ for $k = 6m + 5$. Then $n \neq T_2(n)$.
\end{theorem}
\begin{proof}
We assume first, in view of Lemma~\ref{origLemma5}(b), that $3 < p < q < r < s$. Then $n \equiv 1,2 \pmod{3}$ as each odd prime is $\equiv 1,2 \pmod {3}$. However, $T_2(n) \equiv (6m+5)4 + 1 + 1 + 1 + 1 \equiv 0 \pmod{3}$. Now we assume $p = 3$. Then $n \equiv 0 \pmod{3}$, but $T_2(n) \equiv (6m+5)4 + 0 + 1 + 1 + 1 \equiv 2 \pmod{3}$.
\end{proof}
\begin{theorem}\label{origThm9}
Suppose $n = 2^kpqrs$ for $k = 6m + 1$. If $n = T_2(n)$, then $n \equiv 2 \pmod{3}$.
\end{theorem}
\begin{proof}
By Lemma~\ref{origLemma5}(c) we need not consider possibility $p = 3$. Hence, we now suppose $3 < p < q < r < s$. Now, $n=T_2(n) \equiv (6m+1)4 + 1 + 1 + 1 + 1 \equiv 8 \equiv 2 \pmod{3}$.
\end{proof}
\begin{corollary} \label{origCor3}
Suppose $n = 2^kpqrs$ for $k = 6m + 1$. If $n = T_2(n)$, then $pqrs \equiv 1 \pmod{3}$.
\end{corollary}
\begin{proof}
We first note that $2^{6m+1} \equiv \bigl((2^6)^m \bigr)\cdot 2 \equiv 1^m\cdot 2 \equiv 2 \pmod{3}$. If $pqrs \equiv 2 \pmod{3}$, then we have $n \equiv 2^{6t+1}pqrs \equiv 2\cdot 2 \equiv 1 \pmod{3}$, but this contradicts Theorem~\ref{origThm9}.
\end{proof}
\begin{theorem}\label{origThm10}
Suppose $n = 2^kpqrs$ for $k = 6m + 3$. If $n = T_2(n)$, then $n \equiv 1 \pmod{3}$.
\end{theorem}
\begin{proof}
Observe $2^k \equiv (-1)^{6m+3} \equiv -1 \equiv 2 \pmod{3}$. Thus, $n = T_2(n) \equiv (6m+3)4 + 1 + 1 + 1 + 1 \equiv 1 \pmod{3}$.
\end{proof}
\begin{corollary}\label{origCor4}
Suppose $n = 2^kpqrs$ for $k = 6m + 3$. If $n = T_2(n)$, then $pqrs \equiv 2 \pmod{3}$.
\end{corollary}
\begin{proof}
If $pqrs \equiv 1 \pmod{3}$, then $n \equiv 2^{6t+1}pqrs \equiv 2\cdot 1 \equiv 2 \pmod{3}$, contradicting Theorem~\ref{origThm10}.
\end{proof}
\begin{theorem}\label{origThm11}
Suppose that $n$ is a product of $u$ distinct odd primes each greater than 3.
\begin{itemize}
\item[(a)] If $u = 6t+3$, then $n \neq T_2(n)$.
\item[(b)] If $u = 6t+1$ and $n = T_2(n)$, then it is necessary that an even number (possibly zero) of the primes must be congruent to $2 \pmod{3}$.
\item[(c)] If $u = 6t+5$ and $n = T_2(n)$, then it is necessary that an odd number of the primes must be congruent to 2 mod 3.
\end{itemize}
\end{theorem}
\begin{proof}
(a) If $y$ is any odd prime greater than 3, then $y \equiv 1,
-1 \pmod{6}$. Thus, $y^2 \equiv 1 \pmod{6}$. It follows that $y^2
\equiv 1 \pmod{3}$. From this we infer $T_2(n) \equiv 6t + 3 \equiv
0 \pmod{3}$. But $n$ is not a multiple of 3.
For part (b), $T_2(n)
\equiv 6t+1 \equiv 1 \pmod{3}$. Now $n \equiv 1 \pmod{3}$ since $T_2(n)$
is. Thus the quantity of the prime factors which are congruent to $2
\pmod{3}$ must be even --- as, in pairs, they are $(3m+2)(3j+2) \equiv 1
\pmod{3}$.
For (c), $T_2(n) \equiv 6t+5 \pmod{6}$ and thus $T_2(n) \equiv
2 \pmod{3}$. Hence, $n \equiv 2 \pmod{3}$. It follows that an odd number
of the prime factors must be congruent to $2 \pmod{3}$.
\end{proof}
\begin{corollary}\label{origCor5}
Suppose $n$ is a product distinct odd prime factors and $n = 3qrs \cdots t$. Then, if $n = T_2(n)$, $n$ has $6u + 1$ distinct odd factors for some $u > 1$.
\end{corollary}
\begin{proof} Now $n$ must have an odd number $2w+1$ of distinct odd prime factors by Theorem~\ref{origThm5}. We calculate $T_2(n) = 9 + q^2 + r^2 + \cdots + t^2 \equiv 2w \pmod{3}$. Since $T_2(n) = n \equiv 0 \pmod{3}$ we see $w = 3u$ for some $u$. Thus $n$ has $6u+1$ distinct prime factors.
\end{proof}
\begin{theorem}\label{origThm12}
\leavevmode
\begin{itemize}
\item[(a)] If $n = 2^kp^2qrs$, then $n \not \in T^*(2)$.
\item[(b)] If $n = 2^k(pq)^2rs$ and $k > 1$, then $n \not \in T^*(2)$.
\item[(c)] If $n = 2^k(pqr)^2s$ then $n \not \in T^*(2)$.
\item[(d)] If $n = p^2qrst$, then $n \not \in T^*(2)$.
\end{itemize}
\end{theorem}
\begin{proof}
For part (a), $n$ is even and $T_2(n)$ is odd. For part (b), $n \equiv 0 \pmod{4}$ but $T_2(n) \equiv 4k +2p^2 + 2q^2 + r^2 + s^2 \equiv 2 \pmod{4}$. For (c) $T_2(n) = 4k +2p^2 + 2q^2 + 2r^2 + s^2 \equiv 1 \pmod{2}$. But $n$ is even.
For part (d), $n$ is odd but $T_2(n)$ is even.
\end{proof}
\noindent\textbf{Algorithm 1: Application of lemmas.} Set $n = 2^{6m+1}pqrs$ with $pqrs \equiv 1\pmod{3}$.
\medskip
\noindent (a) Select $p = 2 \pmod{3}$. Now exactly 1 or 3 of $q,r,s$ must be $2 \pmod{3}$. Test cases.\\
\noindent (b) Select $p \equiv 1 \pmod{3}$. Now exactly 2 or none of $q,r,s$ is $2 \pmod{3}$. Test cases.\\
Set $n = 2^{6m+3}pqrs$ with $pqrs \equiv 2 \pmod{3}$. \\
\noindent (c) Select $p \equiv 1 \pmod{3}$. Then one or three of $q,r,s$ must be $2 \pmod{3}$. Test cases.\\
\noindent (d) Select $p = 2 \pmod{3}$. Then none or two of $q,r,s$ must be $2 \pmod{3}$. Test cases.
\bigskip
\noindent\textbf{Algorithm 2: Look at the Quadratic.} Consider $n = 2^kpqrs = T_2(n)$. This is quadratic in $s$. It is necessary that the discriminant $\Delta = b^2 - 4ac$ be a perfect square. Evaluate the discriminant $\Delta$ to see if it is a perfect square:
$\sqrt{\Delta} = \sqrt{2^{2k}p^2q^2r^2 - 16k - 4(p^2+q^2+r^2)}$, and this expression is independent of $s$. (We actually factor a 4 before calculating $\Delta$.)
In general, using Algorithm 2, we can say there are no `small' solutions to $n = T_2(n)$, meaning $\Delta$ is not a square number often enough, at least for $b^2 - 4ac < 2^{63}$, for any $3 \leq k < 33$.
With $k$ fixed at 3, our initial computer search was unsuccessful. We determined that our search always stopped because of the discriminant $\Delta$. It was almost never a square. In first week of April 2016, for $k = 3$, we checked $p$ in the first 100 primes, $q$ in the first 5000 primes, and $r$ in the first 10,000 primes. This revealed $\sqrt{\Delta}$ was never an integer, and thus neither was $s$.
We revised the algorithm, improving the search. First setting $k = 3$, the smallest `admissible' value, we let the discriminant go up to $10^{24}$, rather than specifically limiting $p$, $q$, and $r$. At last we finally found a square discriminant with $p, q$ relatively small: $p = 3, q = 23$, and $r = 304151$. The number $r = 304151$ is the $26,335^{th}$ prime. We mention that this discriminant $\Delta$ is given by
$\Delta = 7046784011265625 = 5^6 \cdot 11^2 \cdot 61051^2 = 83945125^2$.
It did not lead to a suitable $s$. The resulting $s = 167890801$ is composite $(13 \cdot 97 \cdot 211 \cdot 631)$. The other root $s = 551 = 19 \cdot 29$ was not a prime either but since $p < s$, it would have been considered and discarded earlier. Thus, the calculated $n$ is
$n = 8\cdot 3\cdot 23\cdot 304151\cdot 167890801 = 28187413568252952$. No other discriminant $\Delta < 10^{24}$ resulted in an integer $s$, with $p < q < r < 2^{34}$.
For this we had $k$ fixed at 3. The next `admissible' values of $k$
are 7, 9, 13, and 15. But $k = 13$ for example will make the numbers
1000 times as large. As Richard K. Guy said, ``There are not enough
small numbers to meet the many demands made of them." See \cite{4, 5}.
If you are looking at numbers on the order of $10^{30}$, only about 1
in $10^{15}$ is a square. When the numbers are under $2^{64}$ (as much
as the hardware does natively) we can check several hundred million per
second on one CPU. When they get larger, we have to go to other methods,
and can check on the order of $10^6$ per second per CPU. And $10^{15}$
divided by $10^6$ is a lot of seconds.
\section{Conclusion}
\label{sec:conclusion}
In searching for two prime power elements in a set $T^*(s)$ one needs to solve $s = p^k - k = q^i - i$, or equivalently solve for a positive integer solution to the equation $p^k - q^i = k - i$, for $p, q$ distinct primes. Such solutions are plentiful for $i = 1$. It is clear that other solutions with $i > 1$ are very rare and may not exist.
C. R. Greathouse reports (private correspondence, February 08 2016) that there are no instances of such $q^i$ with $i > 1$ up to $10^{40}$. But there are about ten thousand less than $10^{40}$ with $i = 1$. For a contrast, when $s = 3$, the most abundant case, the elements in $T^*(3)$ start quite large and get much larger. Nevertheless, searching among larger numbers produced no more solutions.
The absence of ``irregular" values in $T^*(2)$, or for other small $s$, is surprising to us --- so surprising that we conjecture that $\card(T^*(2)) = 2$. Though we did not prove the conjecture, we were able to eliminate many forms for an integer $n$ so that $n \not \in T^*(2)$. In any case, it is clear that infinitely many sets $T^*(s)$ will contain some power of a prime $p$. In fact, whenever $s = p^k - k$ for some $k$, $p^{p^k}$ will be in $T^*(s)$. But whether these values will be the minimum values (or the only values) in $T^*(s)$ is another (difficult) question.
\begin{thebibliography}{9}
\bibitem{4}
Richard K. Guy, The strong law of small numbers.
\textit{Amer. Math. Monthly} \textbf{95} (1988), 697--712.
\bibitem{5}
Richard K. Guy, The second strong law of small numbers.
\textit{Math. Mag.} \textbf{63} (1990), 3--20.
\bibitem{2}
Jean-Marie De Koninck and Florian Luca, Partial sums of powers
of prime factors, \textit{J. Integer Sequences} \textbf{10} (2007)
\href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Koninck/koninck71.html}{Article
07.1.6}.
\bibitem{3}
Jean-Marie De Koninck and Florian Luca, Integers representable as the sum of powers of their prime factors, \textit{Funct. Approx. Comment. Math.} \textbf{33} (2005), 57--72.
\bibitem{1}
N. J. A. Sloane et al.,
The On-Line Encyclopedia of Integer Sequences. Available
at \url{https://oeis.org}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A15; Secondary 11Y50, 11Y55.
\noindent \emph{Keywords: } factorization, sum of powers, integer sequence.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A067688},
\seqnum{A068916},
\seqnum{A268036},
\seqnum{A268594}, and
\seqnum{A318606}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 20 2018;
revised versions received March 20 2019; March 21 2019; May 13 2019.
Published in {\it Journal of Integer Sequences}, May 18 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}