\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Kaprekar Triples
}
\vskip 1cm
\large
Douglas E. Iannucci and Bertrum Foster\\
University of the Virgin Islands\\
2 John Brewers Bay\\
St. Thomas, VI 00802 \\
USA \\
\href{mailto:diannuc@uvi.edu}{\tt diannuc@uvi.edu} \\
\href{mailto:bfosterk@yahoo.com}{\tt bfosterk@yahoo.com} \\
\end{center}

\vskip .2 in
\begin{abstract} 
We say that 45 is a Kaprekar triple because $45^3=91125$ and
$9+11+25=45$. We find a necessary condition for the existence of
Kaprekar triples which makes it quite easy to search for them. We also
investigate some Kaprekar triples of special forms.
\end{abstract}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\documentclass{article}

%\usepackage{amssymb}
%\usepackage{amsmath}
%\usepackage{latexsym}

\newtheorem{thm}{Theorem}

%\begin{document}


\section{Introduction}

Kaprekar triples (sequence A006887, Sloan~\cite{5}) are numbers with a 
property which is easily demonstrated by example.
Observe that

\begin{alignat*}{2}
8^3&=512, & \qquad 5+1+2&=8,\\
45^3&=91125, & \qquad 9+11+25&=45,\\
297^3&=26198073, & \qquad 26+198+073&=297,\\
4949^3&=121213882349, & \qquad 1212+1388+2349&=4949,\\
44443^3&=87782935806307, & \qquad 8778+29358+06307&=44443,\\
565137^3&=180493358291026353, & \qquad 180493+358291+026353&=565137. 
\end{alignat*}

Therefore 8, 45, 297, 4949, 44443, and 565137 are all examples of
Kaprekar triples. Kaprekar triples generalize the Kaprekar numbers
(sequence A006886, Sloan~\cite{5}), which were introduced by
Kaprekar~\cite{4}, discussed by Charosh\cite{2}, and completely
characterized by Iannucci~\cite{3}. Kaprekar triples are mentioned in
Wells's {\it Dictionary of Curious and Interesting
Numbers\/}~\cite{6}.

Formally, an $n$-Kaprekar triple $k$ (where $n$ is a natural number)
satisfies the pair of equations
\begin{align*}
k^3&=p\cdot10^{2n}+q\cdot10^n+r\,,\\
k&=p+q+r\,,
\end{align*}
where $0\le r<10^n$, $0\le q<10^n$, and $p>0$ are integers.
As the 3-Kaprekar triple 297 shows, $p$ may have fewer than $n$ digits,
and so may $q$ or $r$ (note the leading zero in $r=073$).
The stipulation that $p>0$ precludes many otherwise trivial examples such as
\begin{align*}
100^3&=0\cdot10^8+100\cdot10^4+0\,,\\
100&=0+100+0\,,
\end{align*}
i.e., 100 as a 4-Kaprekar triple. Having $p>0$ also precludes~1 as a 
Kaprekar triple, in spite of its inclusion in sequence 
A006887 by Sloan~\cite{5}. 

\section{The Set ${\mathcal K}(N)$}
Let $N$ be a natural number such that $N\not\equiv1\pmod4$.
We define the set ${\mathcal K}(N)$ of positive integers as follows:
We say $k\in{\mathcal K}(N)$ if there exist nonnegative integers
$r<N$, $q<N$, and a positive integer $p$, such that
%%%%%%%%%%%%%%%%%%%%%%%%%% 1
\begin{equation}
k^3=pN^2+qN+r
\end{equation}
and such that
%%%%%%%%%%%%%%%%%%%%%%%%%  2
\begin{equation}
k=p+q+r\,.
\end{equation}
Although $N$ satisfies~(1) and~(2) (with $p=N$, $q=r=0$),
we nonetheless disallow $N$ as an element of ${\mathcal K}(N)$.
Therefore, it follows that $k<N$ if $k\in{\mathcal K}(N)$.
For, subtracting~(2) from~(1) yields
%%%%%%%%%%%%%%%%%%%%%%%%   3
\begin{equation}
k(k-1)(k+1)=(N-1)(p(N+1)+q)\,,
\end{equation}
so that $k>N$ implies
$$k<p+\frac{q}{k+1}\,.$$
Since $q/(k+1)<1$, we have $k\le p$.
Since $k<p$ contradicts~(2),
we have $k=p$, but this implies $q=r=0$ and hence $k=N$ by~(1).
Contradiction. Therefore $k<N$ if $k\in{\mathcal K}(N)$.

Suppose $k\in{\mathcal K}(N)$. Then~(3) implies $N-1\mid k(k-1)(k+1)$.
Because $N\not\equiv1\pmod4$,
there exist pairwise relatively prime integers $d$, $d_1$, and $d_2$ such that
%%%%%%%%%%%%%%%%%%%%%%%%%   4
\begin{equation}
N-1=dd_1d_2\,,\qquad d\mid k\,,\qquad d_1\mid k-1\,,\qquad d_2\mid k+1\,.
\end{equation}
Since $d\mid k$ we write 
$$k=dm$$
for a positive integer $m$.
Then $d_1\mid dm-1$ and $d_2\mid dm+1$ and so we have
\begin{equation}
dm\equiv1\pmod{d_1}\,,\qquad dm\equiv-1\pmod{d_2}\,.
\end{equation}
Let
\begin{alignat*}{2}
\xi_1&\equiv d^{-1}\pmod{d_1}\,,&\qquad\xi_2&\equiv d^{-1}\pmod{d_2}\,,\\
\mu_1&\equiv d_1^{-1}\pmod{d_2}\,,&\qquad\mu_2&\equiv d_2^{-1}\pmod{d_1}\,.
\end{alignat*}
Then we have 
$$m\equiv\xi_1\pmod{d_1}\,,\qquad m\equiv-\xi_2\pmod{d_2}\,,$$
so that by the Chinese remainder theorem we have
%%%%%%%%%%%%%%%%%%%%%%%%%%%%   5
\begin{equation}
m\equiv\xi_1\mu_2d_2-\xi_2\mu_1d_1\pmod{d_1d_2}\,.
\end{equation}
Moreover, $m$ is the least positive residue such that~(6) is satisfied;
this is because $dm=k<N=dd_1d_2+1$ and thus $m\le d_1d_2$. 

For a positive integer $n$, we call $d$ a {\it unitary divisor\/} of
$n$ if $d\mid n$ and $(d,\frac{n}{d})=1$.
In this case we write $d\|n$. We have shown
\begin{thm}
If $N\not\equiv1\pmod4$, then every element $k\in{\mathcal K}(N)$ is
divisible by a unitary divisor $d$ of $N-1$. 
If we write $k=dm$, then $m$ satisfies~(4) for some pair $d_1$,
$d_2$, of unitary divisors of $N-1$ such that $d_1d_2=(N-1)/d$.
\end{thm}

If $N\not\equiv1\pmod4$, then Theorem~1 gives a necessary condition 
for finding elements $k$ of ${\mathcal K}(N)$,
and hence it may be applied to find an upper bound 
for $|{\mathcal K}(N)|$,
the number of elements in ${\mathcal K}(N)$.
For, if $N-1$ has the unique prime factorization 
given by $N-1=\prod_{i=1}^tp_i^{a_i}$,
then we call the prime powers $p_i^{a_i}$ the {\it components\/} of $N-1$.
Then $d\|N-1$ if and only if $d$ is a product of components of
$N-1$ (including the empty product~1).
We refer to $t$, the number of components of $N-1$,
as $\omega(N-1)$. Thus by Theorem~1, if $N\not\equiv1\pmod4$ then
\begin{equation}
|{\mathcal K}(N)|\le3^{\omega(N-1)}\,.
\end{equation}

It is possible to define ${\mathcal K}(N)$ when $N\equiv1\pmod4$. In
this case, the factors $d$, $d_1$, and $d_2$ in~(4) will be pairwise
relatively prime if and only if $d$ is even. If this is so, we may
proceed exactly as above, so that~(7) is still true.

Otherwise $d$ is odd. Since $2^{\nu}\|N-1$ for some $\nu\ge2$, we have
either $2\| d_1$, $2^{\nu-1}\|d_2$, or, $2^{\nu-1}\| d_1$, $2\|d_2$.
Note that these two cases are identical when $2^2\|N-1$. In either
case, the equations~(5) still hold, and since $(d,d_1)=(d,d_2)=1$, we
see that $m$ may be determined uniquely modulo~$[d_1,d_2]$. Here,
$d\|N-1$, and $d_1$ and $d_2$ are each some power of~2 multiplied by an
odd unitary divisor of $N-1$. Thus~(7) still holds in the case when
$N\equiv1\pmod4$.  


\section{Kaprekar Triples}

In the notation of the previous section,we refer to the set
$\cup_{n=1}^{\infty}{\mathcal K}(10^n)$ as the set of Kaprekar triples.
If we prefer, we may refer to the set ${\mathcal K}(10^n)$, for fixed
$n$, as the set of $n$-Kaprekar triples. To illustrate Theorem~1,
consider the set of $6$-Kaprekar triples, and note the factorization
$$10^6-1=3^3\cdot7\cdot11\cdot13\cdot37\,.$$
We may take $d=27$, $d_1=259$, and $d_2=143$. Then
$$\xi_1=48\,,\qquad \xi_2=53\,, \qquad \mu_1=90\,,  \qquad \mu_2=96\,, $$
giving
$$m\equiv143\cdot96\cdot48-259\cdot90\cdot53\equiv20931\pmod{37037}\,.$$
Therefore
$$m=20931\,,\qquad d=27\,,\qquad k=20931\cdot27=565137\,.$$
Since
\begin{align*}
565137^3&=180493358291026353\,,\\
565137&=180493+358291+026353\,,
\end{align*}
we have $565137\in{\mathcal K}(10^6)$. To show that the conditions in Theorem~1 are not sufficient, consider $d=297$, $d_1=37$, and $d_2=91$. Here,
$$\xi_1=1\,,\qquad \xi_2=19\,, \qquad \mu_1=32\,,  \qquad \mu_2=24\,, $$
giving
$$m\equiv3257\,,\qquad d=297\,,\qquad k=967329\,.$$
However,
$$967329^3=905154309885752289\,,$$
but
$$905154+309885+752289=1967328\,,$$
and so $967329\notin{\mathcal K}(10^6)$. Note that
$1967328=967329+(10^6-1)$. Experimentally, we have seen that roughly
one fourth of the $3^{\omega(N-1)}$ possible triples $(d,d_1,d_2)$ of
unitary divisors of $N-1$ produce an element $k\in{\mathcal K}(N)$ when
Theorem~1 is applied. The other three fourths produce $k$ such that
when $p$, $q$, and $r$ in~(1) are obtained we get $$p+q+r=k+(N-1)$$
instead of~(2). Generally, the larger the value of $\omega(N-1)$, the
closer to 1:3 the ratio of elements of ${\mathcal K}(N)$ to non-elements
becomes.


We provide some data for $N=10^n$, for various values of $n$, where ``ratio'' refers to the ratio $|{\mathcal K}(10^n-1)|/3^{\omega(10^n-1)}$:

\begin{center}
\begin{tabular}{llll}
${n}$&${3^{\omega(10^n-1)}}$&${|{\mathcal K}(10^n)|}$&${\text{ratio}}$\\ \hline
5&27&5&0.185185\\
6&243&37&0.152263\\
7&27&8&0.296296\\
10&243&64&0.263374\\
12&2187&527&0.240969\\
15&729&195&0.267490\\
19&9&1&0.111111\\
20&6561&1649&0.251334\\
21&2187&538&0.245999\\
23&9&$1$&0.111111\\
24&59049&14702&0.248980\\
30&1594323&398838&0.250161\\
42&4782969&1196902&0.250242\\
%60&3486784401&$N$&0.xxxxxx\\
64&43046721&10759839&0.249957\\
80&14348907&3587901&0.250047\end{tabular}
\end{center}

%
%
%
%   Section 4   
%
%
%
\section{Applications}
It is a simple matter to search for Kaprekar triples by applying
Theorem~1. To do so, one only needs the factorizations of $10^n-1$ for
$n\ge1$, which are easily available (for example see Brillhart et
al.~[1]).

In this section we will discuss Kaprekar triples of certain forms. For
example, consider the set ${\mathcal K}(64M^2)$ for some positive
integer $M$. Since $$64M^2-1=(8M-1)(8M+1)\,,$$ and since $8M-1$ and
$8M+1$ are relatively prime, we can apply Theorem~1 by choosing $d$,
$d_1$, and $d_2$ from among the unitary divisors $8M\pm1$ and~1 of
$64M^2-1$. If we let $d_2=1$, there are at least two ways to do this,
one of which is to let $d=8M-1$ and $d_1=8M+1$. In this case we have
$\xi_1=4M$ and $\xi_2=\mu_1=\mu_2=1$, and thus
$$m=d_2\mu_2\xi_1-d_1\mu_1\xi_2=-4M-1\equiv4M\pmod{8M+1}\,,$$ taking
the least positive residue modulo $8M+1$. This gives $k=dm=4M(8M-1)$.
Similarly, taking $d=8M+1$ and $d_1=8M-1$ gives $k=4M(8M+1)$.

Thus it is possible that $4M(8M\pm1)$ are both elements of
${\mathcal K}(64M^2)$. Indeed they are, for
\begin{align*}
k^3&=64M^3(8M\pm1)^3\\
&=4096M^4(8M^2\pm3M)+64M^2(24M^2\pm M)\,,
\end{align*}
and,
$$(8M^2\pm3M)+(24M^2\pm M)=32M^2\pm4M=k\,.$$
Note that if $n\ge3$ then $10^{2n}$ is of the form $64M^2$ with $M=5^3\cdot10^{n-3}$. We have
\begin{thm}
For $n\ge3$, the integers $5\cdot10^{n-1}(10^n\pm1)$ are $2n$-Kaprekar triples.
\end{thm}
For example, $499500$ and $500500$ are both 6-Kaprekar triples,
$49995000$ and $50005000$ are both 8-Kaprekar triples, and so forth.

For positive integers $r>1$ and $n\ge1$, we refer to an element of
${\mathcal K}(r^n)$ as a {\it base-$r$ Kaprekar triple\/}. Note that if
$p\ge3$ then $2^{2p}$ has the form $64M^2$ where $M=2^{p-3}$. Hence
$2^{p-1}(2^p\pm1)$ are binary (or base-2) Kaprekar triples. Since every
even perfect number has the form $2^{p-1}(2^p-1)$ where $2^p-1$ is
prime (a fact first proved by Euler), we have
\begin{thm}
Every even perfect number is a binary Kaprekar triple.
\end{thm}
As examples, we see that
\begin{alignat*}{2}
28^3&=5\cdot64^2+23\cdot64,&\qquad5+23&=28;\\
496^3&=116\cdot1024^2+380\cdot1024,&\qquad116+380&=496;\\
8128^3&=2000\cdot16384^2+6128\cdot16384,&\qquad2000+6128&=8128.\end{alignat*}

We can also consider the set ${\mathcal K}(4096M^4)$ for some 
positive integer $M$. Similarly as we did above,
we can show that $256M^3+4M$ belongs to this set.
Letting $M=5^3\cdot10^{n-3}$ for $n\ge3$ gives us
\begin{thm}
If $n\ge3$ then $5\cdot10^{3n-1}+5\cdot10^{n-1}$ is a $4n$-Kaprekar triple.
\end{thm}
Hence $500000500$ is a 12-Kaprekar triple:
\begin{align*}
500000500^3&=1250003750003750001250000000\,,\\
125+000375000375+000125000000&=500000500\,.
\end{align*}
Also, $500000005000$ is a 16-Kaprekar triple, $500000000050000$ is a 20-Kaprekar triple, and so forth.
%
%
%
%   Section 5   
%
%
%
\section{Concluding Remarks}
Theorem~2 shows that there always exists an $n$-Kaprekar triple when
$n\ge6$ is even. What about odd $n$? By~(7), there are fewer such
triples when $\omega(10^n-1)$ is small. In fact, $\omega(10^n-1)=2$
when $n=19$, 23, and 317 (see Brillhart et. al.~[1]), although it is
not known how long this list may be extended. The table following
section~3 shows that an $n$-Kaprekar exists when $n=19$ or~23. However,
a simple computer search reveals that no 317-Kaprekar triples exist;
thus there do not exist $n$-Kaprekar triples for every $n$.

A more general question is, are there certain forms of $N$ for which
$\mathcal{K}(N)$ is empty? For example, we can show
$\mathcal{K}(N)=\emptyset$ whenever $N>8$ is of the form $p^{\alpha}+1$
for odd prime $p$ and $\alpha\ge1$; note that $\mathcal{K}(8)$ consists
of the perfect number~6 by Theorem~3. Indeed, since $N-1=p^{\alpha}$,
if $k\in\mathcal{K}(N)$ then by~(4) one of three cases occur:
{\it(i)\/} $p^{\alpha}\mid k$; {\it(ii)\/} $p^{\alpha}\mid k-1$;
{\it(iii)\/} $p^{\alpha}\mid k+1$.

In case~{\it(i)\/}, as $k<N$ we must have $k=p^{\alpha}$. But here,
\begin{align*}
k^3&=(N-3)N^2+2N+(N-1),\\ 
(N-3)+2+(N-1)&=k+(N-1)\ne k.\end{align*}

In case~{\it(ii)\/} we have $k\equiv1\pmod{p^{\alpha}}$ by~(6).

In case~{\it(iii)\/}, $k\equiv-1\pmod{p^{\alpha}}$ by~(6), which implies $k=p^{\alpha}-1$. But
\begin{align*}
k^3&=(N-6)N^2+11N+(N-8),\\ 
(N-6)+11+(N-8)&=k+(N-1)\ne k.\end{align*}
All three cases lead to contradiction (case~{\it(ii)\/} contradicts $1<k<N$).

On the other hand, there are forms of $N$ for which
$\mathcal{K}(N)\ne\emptyset$ (as we've already seen when $N=10^{2n}$).
For example, it is straightforward to check that when $N=2^n+1$,
$n\ge2$, we have $k=2^{n-1}-1\in\mathcal{K}(N)$.



\begin{thebibliography}{99}

\bibitem{1} J. Brillhart, D. Lehmer, J. Selfridge, B. Tuckerman,
and S.  Wagstaff
{\it Factorizations of $b^n\pm1$, $b=$2, 3, 5, 6, 7, 10, 11, 12 Up to
High Powers (3rd Ed.)}, {\it Contemporary Mathematics\/} {\bf 22},
2001.

\bibitem{2} M. Charosh, Some Applications of Casting Out 999\dots's {\it J.Recreational Math.} {\bf13} (1980), 111--118.

\bibitem{3} D. Iannucci, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL3/iann2a.html}{The Kaprekar Numbers},
{\it J. Integer Seq.} {\bf3} (2000), article~00.1.2.

\bibitem{4} D. Kaprekar, On Kaprekar Numbers {\it J. Recreational Math.}
{\bf13} (1980), 81--82.

\bibitem{5} N. Sloane, \href{http://www.research.att.com/~njas/sequences/index.html}{The On-Line Encyclopedia of Integer Sequences}.

\bibitem{6} D. Wells, {\it The Penguin Dictionary
of Curious and Interesting Numbers\/}, Penguin Books, New York, 1986.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:}
Kaprekar triples, division algorithm, Chinese remainder theorem,
components, perfect numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A006886} and \seqnum{A006887}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 30 2004;
revised version received October 7 2005.  
Published in {\it Journal of Integer Sequences},
October 20 2005.

\bigskip
\hrule
\bigskip

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


\end{document}