\documentclass[12pt,reqno]{article}
   \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{amsthm,amsfonts,amssymb,amsmath,epsf}

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

  \def\divides{\ | \ }
  \def\lcm{{\rm lcm}}

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


  % \renewcommand{\baselinestretch}{1.4}
  \def\C{{\mathbb C}}

  \newtheorem{theorem}{Theorem}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{observation}[theorem]{Observation}
  \newtheorem{conjecture}[theorem]{Conjecture}



  \begin{document}

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

\begin{center}
  
  \vskip 1 cm
  {\LARGE\bf   Tau Numbers: A Partial Proof of a
  \\
  \ \\
  \vskip -.2in
  Conjecture and Other Results}
  \vskip 1.5 cm
  \large Joshua Zelinsky\\

  The Hopkins School\\
  New Haven, CT 06515 \\
  USA\\
  \medskip
  
  Email: {\tt Lord\_Bern@hotmail.com}
  \end{center}

  {\bf Abstract.}
   A positive $n$ is called a {\sl tau number} if $\tau(n) \divides n$, where $\tau$
   is the number-of-divisors function.
   Colton conjectured that
   the number of tau numbers $\leq n$
   is at least ${1 \over 2} \pi(n)$.
   In this paper I show that Colton's
   conjecture is true for all sufficiently
   large $n$.
   I also prove various other results about tau numbers and their
   generalizations .


\section{Introduction}

  Kennedy and Cooper \cite{Kennedy} defined a positive integer to be a
  {\sl tau number} if $\tau(n) \ | \ n$, where $\tau$ is the
  number-of-divisors function.  The first few tau numbers are
  $$1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, 72, 80, \ldots;$$
  it is Sloane's sequence \seqnum{A033950}.
  Among other things, Kennedy and Cooper
  showed the tau numbers have density zero.

  The concept of tau number was rediscovered by Colton, who called
  these numbers {\sl refactorable} \cite{Colton}.
  This paper is primarily concerned with two conjectures made
  by Colton. Colton  conjectured that the number of tau numbers less than or
  equal to a given $n$ was at least half the number of primes less than or 
equal
  to $n$.  In this
  paper I show that Colton's conjecture is true for all
  sufficiently large $n$
  by proving a generalized version of the conjecture.  I calculate
  an upper bound for counterexamples of $7.42 \cdot 10 ^{13} $.

  Colton also
  conjectured that there are no three consecutive tau numbers and I show 
this
  to be the case. Other results are also given, including the properties of
  the tau numbers as compared to the primes. Various generalizations of the 
tau
  numbers
  are
  also discussed.

\section{Basic results}

  \bigskip
  \noindent{\bf Definitions.}
  Let $\pi(n)$ be the number of primes less than or equal to $n$.
  Let $T(n)$ be the number of tau numbers
  less than or equal to $n$.

  \bigskip

  Using this notation,
  Colton's conjecture becomes: $T(n) \geq  \pi(n)/2$ for all $n$.

  Before we prove a slightly weaker form of this
  conjecture, we mention some
  following minor properties of the tau numbers.

  Throughout this paper, the following basic result
  \cite[Theorem 273]{Hardy} is used
  extensively:

  \begin{proposition}
  If $n =  p_1^{a_1}  p_2^{a_2}  \cdots  p_k^{a_k}$ then
  $\tau(n) = (a_1+1)(a_2+1)(a_3+1)\cdots(a_k+1)$.
  \label{hw}
  \end{proposition}

  The next five  theorems are all due to Colton.

  \begin{theorem}
  Any odd tau number is a perfect square.
  \label{thm1}
  \end{theorem}
  \begin{proof}
  Assume that $n$ is an odd tau number. Let $n =  p_1^{a_1} p_2^{a_2} \cdots
   p_k^{a_k} $.   By Proposition~\ref{hw} and the definition of tau number
  $(a_1+1)(a_2+1)(a_3+1)\dots(a_k+1) \ |\  n $.
  Therefore for any $0<i<k+1$, $a_i+1$
  is odd, and hence $a_i$ is even. Since every prime in the factorization of 
$n$
  is raised to an even power, $n$ is a perfect square.
  \end{proof}
  \begin{theorem}
  An odd integer $n$ is a tau number iff $2n$ is a tau number.
  \label{thm2}
  \end{theorem}
  \begin{proof}
  If $n =  p_1^{a_1} p_2^{a_2} \cdots  p_k^{a_k}$,
  then $\tau(2n) =
  2(a_1+1)(a_2+1)(a_3+1)\cdots(a_k+1) =2\tau(n)$.
  Since $\tau(n) \ | \ n$ iff $2\tau(n) \ | \ 2n$, the result follows.
  \end{proof}

  \begin{theorem}
  If $\gcd(m,n)=1$ and $m, n$ are both tau numbers, then $mn$ is a tau number.
  \label{thm3}
  \end {theorem}
  \begin{proof}
  This result follows immediately from $\tau(mn) = \tau(m)\tau(n)$ when
  $\gcd(m,n)=1$.
  \end{proof}
  \begin{theorem}
  There are infinitely many tau numbers.
  \label{thm4}
  \end{theorem}
  There are many possible ways to prove this result. However,
  using an elegant mapping Colton proved the following more general theorem
  from which the above follows.
  \begin{theorem}
  For any given finite nonempty set of primes,
  there are infinitely many tau numbers with
  exactly those primes as their distinct prime divisors.
  \label{thm5}
  \end{theorem}
  \begin{proof}
  This result follows from considering the mapping:
  $$f(n)= f(p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}) =
  p_1^{p_1^{a_1}-1}p_2^{p_2^{a_2}-1} 
  \cdots p_k^{p_k^{a_k}-1}.$$
  It is easy to see
  that the mapping produces only tau numbers.
  \end{proof}
  \begin{theorem}
  Every tau number is congruent to 0,1,2 or 4 mod 8.
  \label{thm6}
  \end{theorem}
  \begin{proof}
  This follows  immediately from Theorems~\ref{thm1} and \ref{thm2}.
  \end{proof}

\section{New Results}

       We now turn to the new results of this paper.

  First, we have a minor, elementary result which is similar to Colton's 
above results.

  \begin{theorem}
  Let $n$ be a tau number and let $p$ be the smallest prime factor of $n$. If $q$ is 
prime and
  $q \divides n $ then $q^{p-1} \divides n $.
  \end{theorem}
  \begin{proof}
  Let $n$ be a tau number and let $p$ be the smallest prime factor of $n$. Let $q$ be 
a prime
  which divides $n$ and let $q^k$ be the largest power of $q$ which divides 
$n$. Since $n$
  is a tau number, $k+1 \divides n $. But $p$ is the smallest non-trivial divisor of $n$ so 
$k+1 \geq p $. Hence
  $ k \geq p-1$ and thus $q^{p-1} \divides n $.
  \end{proof}



  To prove that Colton's first conjecture is true for all sufficiently large
  $n$ we
  construct a subset of the tau numbers which is much denser than the 
primes.

  \begin{lemma}
  %Lemma 1:
  For any distinct primes $p, q > 3$, the number
  $36pq$ is a tau number.
  \label{lemma1}
  \end{lemma}

  \begin{proof}
  By the multiplicative property of the tau function,
  $\tau(36pq)= \tau(4) \tau(9) \tau(p) \tau(q) = 3 \cdot 3 \cdot 2 \cdot 2 = 
36$.
  \end{proof}

  \begin{lemma}
  %Lemma 2:
  Let $k$ be an integer $\geq 1$.  Then the number of integers $\leq n$
  of the form $kp$, where $p$ is prime, is
  asymptotic to $n/ (k \log n )$.  Similary, for any fixed integer $a \geq 
1$
  the numbers of integers $\leq n$ of the form $kp^a$
  is asymptotic to $((n/k)^{1/a})/\log(n)$.
  \label{lemma2}
  \end{lemma}
  \begin{proof}
  Both these formulas follow easily from the prime number theorem.
  \end{proof}

  \begin{lemma}
  %Lemma 3:
  Let $k$ be a positive integer.
  Then the number of numbers $\leq n$
  of the form $kpq$, where $p, q$ are distinct primes, is
  asymptotic to $(n \log\log  n)/(k\log n)$.
  \label{lemma3}
  \end{lemma}
  \begin{proof}
  We use a Theorem of Hardy and Wright \cite[Thm.\ 437]{Hardy}, which
  states that the number of
  squarefree numbers
  less than $n$ with $k$ prime factors, $k \geq 2$ is asymptotic to
  $\frac{n (\log\log n)^{k-1}}{(k-1)!\log n}$. Setting $k=2$ and using the 
same
  techniques as in the proof for Lemma~\ref{lemma2} yields the desired 
result.
  \end{proof}

  \begin{lemma}
  % Lemma 4:
  The numbers of tau numbers $\leq n$ of the form $36pq$ with $p, q$
  distinct primes $> 3$ is asymptotic to
  $(n \log\log n)/(36 \log n)$.
  \label{lemma4}
  \end{lemma}
  \begin{proof}
  By Lemma~\ref{lemma3}
  the number of positive integers $\leq n$ of the form $36pq$ is
  asymptotic to
  \begin{equation}\label{eq2}
  \frac{n \log \log n }{36 \log n}
  \end{equation}
  The number of tau numbers of the form $36pq$ with $p, q$ prime numbers
  $> 3$ is the number of numbers
  of the form $36pq$ minus the number of numbers of the
  form $36 \cdot 2 \cdot p$ or
  $36 \cdot 3 \cdot p$.
  Thus, using \ref{eq2}, together with Lemma~\ref{lemma3} the number
  of such numbers is asymptotically
  \begin{equation}\label{eq3}
  \frac{n \log\log n}{36\log n}- \frac{n}{72 \log n } -\frac{n}{108\log n} -
  \end{equation}
  which is asymptotic to the first term.
  \end{proof}

  \begin{lemma}
  %Lemma 5:
  For any fixed real number $r < 1$ we have
  $T(n)>\frac{rn\log\log n}{36\log n}$ for all $n$ sufficiently large.
  \label{lemma5}
  \end{lemma}

  \begin{proof}
  This inequality follows from Lemmas~\ref{lemma4} and \ref{lemma1}.
  \end{proof}
  \begin{theorem}
  For any real number $k$ we have $T(n) > k\pi(n)$ for all $n$
  sufficiently large.
  \label{thm7}
  \end{theorem}
  \begin{proof}
  Clearly for any positive $r < 1$, and any $k$, for all sufficiently large
  $n$,
  \begin{equation}\label{eq5}
  \frac{rn\log \log n}{36\log n} >kn/\log n.
  \end {equation}
  Since $\pi(n) \sim n/\log n$, for all sufficiently large $n$,
  $\frac{rn \log\log n}{36\log n} >k\pi(n)$.
  By applying Lemma~\ref{lemma5}, we conclude that for all
  sufficiently large $n$,
  $T(n) > k\pi(n)$.
  \end{proof}

  \begin{corollary}
  %Corollary 1:
  \end{corollary}
  For any $b>0$ there are at most a finite number of integers $n$ such that
  $T(n)> b\pi(n)$.

  \begin{proof}
  This result follows immediately from Theorem~\ref{thm7}.
  \end{proof}

  \begin{corollary}
  %Corollary 2:
  There are at most a finite number of integers
  $n$ such that $ T(n) < .5\pi(n)$.
  \end{corollary}

  \begin{proof}
  Let $b=.5$ in the above corollary.
  \end{proof}

  \bigskip

  Theorem~\ref{thm7} also implies that $T(n) >\pi(n)$ for all
  sufficiently large $n$.
  Colton gave  a table of $T(n)$ showing
  that $T(10^7) $ is about $.59\pi(n)$. So
  $T(n)$ must not drastically exceed $\pi(n)$ until $n$ becomes very large.
  This is a  good example of the law of small numbers. In fact, we can
  construct an even better example of the law of small numbers.

  \bigskip
  \noindent{\bf Definition.}
  An integer $n$ is {\sl rare} if $\tau(n) \ | \ n $, $\tau(n)\ | \ \phi(n)$ 
and
  $\tau(n)\ | \ \sigma(n)$, where $\phi(n)$ is
  the number of integers less than or
  equal to $n$ and relatively prime to $n$, and $\sigma(n)$ is the sum of 
the
  divisors of $n$.

  \bigskip

  Let $R(n)$ be the number of rare numbers $\leq n$. We can use a 
construction
  similar to the one above to show that if $p, q$ are distinct primes,
  not equal to $2$,$3$ or $7$,  then  $672pq$ is rare. Using similar logic 
to
  that above, we can conclude for any $k$,  for all sufficiently large $n$,
  $R(n) > k\pi(n)$. Thus, although there are only two rare numbers less than
  $100$ (namely, $1$ and $56$) and there are $25$ primes less than $100$, 
for all
  sufficiently large $n$, $R(n) > \pi(n)$ .

  It would be interesting to establish
  a good upper bound beyond which this inequality always holds. In the above 
construction,
  we have "cheated" slightly since $n$ such that $\tau(n)\ | \ \sigma(n)$ 
have density 1.
  Note that we could have proven tau-prime density result result proving
  that all numbers of the form $kpq$ for any $k$ exceeds the density of
  the primes just like those of the form $36pq$ and then looking at the 
subset
  of tau numbers of the form $36pq$. There are other sequences of tau number 
that
  could have been used to the same effect, such as those of the form $80pqr$
  where $p$, $q$ and $r$ and are distinct odd primes not equal to $5$. It is
  not difficult to generalize the above theorem to show that for any $k$,
  \begin{equation}\label{eq6}
  ((n\log\log n)^k)/\log n = o(T(n)).
  \end{equation}

  Finding an actual asymptotic formula for $T(n)$ is more difficult. We can
  address this issue with certain heuristics.  We know that
  $\tau(n)$ is of average order
  $\log n$. Since $n$ is a tau number when $n \bmod \tau(n) = 0$ and $n 
\bmod
  \tau(n)$ can have
  $\tau(n)$ values, we would expect the probability of a random integer to 
be
  a tau number to be $1/\log(n)$.
  However, integrating this yields $n/\log n$ as the
  asymptotic value, which is too low even if we multiply it by a constant.
  However, almost all integers have about ${\log n}^{\log 2}$ divisors
  \cite[p.\ 265]{Hardy}, and a
  few integers with large tau values bring up the average. If we use the 
same
  logic as above and note that almost all tau numbers are divisible by 4, it
  makes sense to take 1/4th of the integral of  $(\log n)^{-\log 2}$.
  Thus we arrive
  at the following conjectured relation:

  \begin{conjecture}
  %Conjecture 1:
  \begin{equation}
  T(x) \sim (1/4) \int_3^x {\log u}^{-\log 2} du.
  \end{equation}
  \end{conjecture}

  This conjecture gives an approximate values  of $42854$ for $T(10^6)$ and
  $381659$ for $T(10^7)$. Colton's table gives $T(10^6) = 44705$ and
  $T(10^7) = 394240$. Our heuristic approximation
  seems to slightly underestimate
  the actual values, being $95.8\%$ and $96.8\%$ of the actual values,
  respectively. This
  underestimate is expected
  since the integral approximation ignores the tau numbers
  congruent to $1$ or $2 \bmod 4$. In fact, we conjecture that for all
  sufficiently large $n$ the integral underestimates $T(n)$. Since the 
relationship between
  $\tau(n)$ and $(\log n)^{\log 2}$ is weak,
  it seems much safer to conjecture the weaker:
  \begin{equation}
  \log T(x) \sim \log \left( {1 \over 4} \int_3^x (\log u)^{-\log 2} du \right).
  \end{equation}


          It is possible, using the known bounds for the various asymptotic
  formulas here to obtain an actual upper bound above which Colton's
  conjecture must be true. It is not difficult, although computationally
  intensive, to use a few different generators along with $36$ to obtain a
  bound of $10^{37}$. However, using a more general method it is possible to
  lower the bound to slightly over $7 \cdot 10^{13}$.

  \begin{lemma}
  %Lemma 6:
  $2 \ | \ n/\tau(n)$ iff for
  any prime $p$ such that  $p$ does not divide $n$, $np$ is a
  tau number.
  \label{lemma6}
  \end{lemma}

  Example: $2 \ | \ 8/\tau(8) = 8/4 = 2$  and $8p$ is a tau number for all 
odd
  primes $p$.
  The proof is left to the reader.

  \bigskip
  \noindent{\bf Definition.} A tau number $n$ such that
  for any prime $p$, if $p$ does not divide $n$ then
  $np$ is a tau number, is called a {\sl $p$-generator}. Any tau number
  of the form $np$ is said to be
  {\sl $p$-generated} by n.


          Thus, in the example above, $8$ is a $p$-generator.
  Thus Lemma~\ref{lemma6} can be
  restated as follows:
  $n$ is a $p$-generator iff $2\ | \ n/\tau(n)$.  In what follows,
  both forms of this
  lemma are used interchangeably.

  \bigskip
  \noindent{\bf Notation.}
  Let $\omega(n)$ denote the number of distinct prime factors of $n$.
  Let $g(n)$ denote the largest prime factor of $n$.
  Let $G(n)= n(n+1)/2$.
  Let $P_n$ denote the $n$th prime, with $P_1 = 2$.

  \begin{lemma}
  %Lemma 7:
  Let $k$ be a $p$-generator. The number of tau numbers $\leq n$
  of the form $kp$
  is at least
  $\pi(n/k) - \omega(n).$
  \label{lemma7}
  \end{lemma}

  \begin{proof}
  Left to the reader.
  \end{proof}

  \begin{lemma}
  %Lemma 8:
  If $a_1,a_2, \dots a_s$ are $p$-generators, then for any $n$ the
  number of tau numbers $\leq n$  $p$-generated by any $a_i$ is at least
  \begin{equation}\label{eq7}
  \sum_{i=1}^s \pi(n/a_i)-\pi(g(a_i)).
  \end{equation}
  \label{lemma8}
  \end{lemma}

  \begin{proof} The proof follows from Lemma~\ref{lemma6}
  when we observe that for any
  $a_i,a_j$ where
  $k=\pi(g(a_i))+1$ and $m=\pi(g(a_j))+1$,
  the sets $\lbrace a_iP_k,a_iP_{k+1}, a_iP_{k+2}, \ldots \rbrace$ and
  $\lbrace a_jP_m, a_jP_{m+1},a_j P_{m+2}, \ldots \rbrace$
  have no common elements.
  \end{proof}

  \begin{lemma}
  %Lemma 9:
  If $a_1,a_2,a_3,\dots$ are $p$-generators then for any $n$ the
  number of tau numbers $\leq n$ $p$-generated by any $a_i$ is at least 
$A\pi(n)
  -B$ where
  $A=\sum_{i=1}^k 1/a_i$ and
  $B=\sum_{i=1}^k  (\pi(g(a_i))+1)$.
  \label{lemma9}
  \end{lemma}

  \begin{proof}
  This proof follows immediately from Lemma~\ref{lemma7} since each summand
  in $A$ introduces
  an error of at most $1$.
  \end{proof}

  \begin{theorem}
  For all $n>7.42 \cdot 10^{13}$ we have $T(n) > \pi(n)/2$.
  \label{thm8}
  \end{theorem}
  \begin{proof}
  It has been shown by Dusart \cite{Dusart} that  for all
  $n>598$, the inequality
  $$(n/\log n ))(1+.992/\log n )  <\pi(n)<(n/\log n)(1+1.2762/\log n)$$
  holds.
  We use all the $p$-generators less than or equal to $28653696$ together
  with Lemma~\ref{lemma9} to
  obtain a lower bound for the number of tau numbers, and then
  demonstrate that for all $n$ greater than $7.42 \cdot 10^{13}$, this 
exceeds 
  $.5(n/\log n )(1+1.2762/\log n)$ and thus exceeds $.5\pi(n)$. Using a 
simple
  computer program, it is not difficult to calculate that there are exactly
  $413980$ $p$-generators less than
  $28653696$. Their $A$ value as in Lemma~\ref{lemma9} is over $.508.$
  It is not difficult
  to see that
  \begin{eqnarray*}
  B &<& G(\pi(413980/36)) +G(\pi(413980/80))+G(\pi(413980/96))
        +(413980-\pi(413980/36)   \\
  &-& \pi(413980/80)-\pi(413980/96))-\pi(413980/128).
  \end{eqnarray*}
  Calculating  the relevant values and evaluating the above expression 
yields
  $B < 8694520815$.
  Thus, for all $n>598 \cdot28653696$, we have $T(n) >
  .508(n/\log n)(1+.992/\log n)-8694520815$.
  For all $n>10^{13.87}, 508(n/\log n)(1+.992/\log n)-8694520815 >
  .5(n/\log n)(1+1.2762/\log n)$.
  Since $10^{13.87}< 7.42 \cdot 10^{13}$ we conclude that for all $n>7.42
  \cdot 10^{13}$, we have
  $T(n)>.5\pi(n)$.
  \end{proof}

  \bigskip
  The high density of the tau numbers
  and their relationship to the primes motivates
  the comparison of the two types of integers.

  \begin{theorem} The sum of the reciprocals of the tau numbers diverges.
  \label{thm9}
  \end{theorem}
  \begin{proof} The result follows immediately by observing that $8$ is a
  $p$-generator  and that the sum of the reciprocals of the primes diverges.
  \end{proof}

  \bigskip

  There is a famous still unsolved conjecture, by Polignac, that for any
  positive even integer $k$, there exist primes $p, q$ such that $k=p-q$
  \cite{Ribenboim}. It seems reasonable to make an identical conjecture 
about
  the tau numbers. Indeed, the existence of infinitely many
  odd tau numbers makes one wonder
  whether every positive integer is the difference of two tau numbers. 
However,
  there
  are some odd integers which are not the difference of two tau numbers 
despite
  the
  fact that the density of the tau numbers is much higher than that of the 
primes.

  \begin{theorem}
  There do not exists tau numbers $a,b$ such that $a-b=5$.
  \label{thm10}
  \end{theorem}
  \begin{proof}
  Suppose, contrary to what we want to prove, that
  there exist tau numbers $a, b$ such that
  $a-b=5$.
  By Theorem~\ref{thm6} we know
  that every tau number is congruent to $0,1,2$ or $4$ (mod 8).
  Thus, we have
  $b \equiv 4$ (mod 8) and $a \equiv 1$ (mod 8).
  Hence $4$ is the highest power of two which
  divides $b$.  Thus $\tau(4) = 3 \ | \ \tau(b)$, and since
  $\tau(b) \ | \ b$ we get $b \equiv 0$ (mod 3).
  Then $a \equiv 2$ (mod 3),
  which is impossible since $a$ is an odd tau number and hence a square.
  \end{proof}

  \bigskip

  Goldbach made two  famous conjectures about the additive properties of the
  primes. Goldbach's strong conjecture is that any even integer greater than
  $4$ is the sum of two primes. Goldbach's weak conjecture is that every odd
  integer greater than $7$ is the sum of the three odd primes. It is easy to
  see that the weak conjecture follows from the strong
  conjecture \cite{Ribenboim}.

  However,
  Colton's congruence results of Theorem~\ref{thm6}
  imply that any $n \equiv 7$ (mod 8) cannot be
  the sum of two tau numbers.

  The following  theorems and the next conjecture are the tau equivalents of
  Goldbach's conjecture.
  \begin{theorem}
  \begin{itemize}
  \item[(a)] If Goldbach's weak conjecture
  is true than any positive integer can be
  expressed as the sum of $6$ or fewer tau numbers.
  \item[(b)] If Goldbach's strong conjecture is true than every positive 
integer
  is
  the sum of $5$ or fewer tau numbers.
  \end{itemize}
  \label{thm11}
  \end{theorem}

  \begin{proof}
  (a) Assume Goldbach's weak conjecture. Let $A$ be the set of
  integers $n$ such that $8n$ is a tau number or $n = 0$. Consider $x = 8k$ 
for
  some
  odd $k > 7$. Since every odd prime is an element of $A,$ $k =a_1 + a_2 
+a_3$
  for some $a_1, a_2, a_3$ element $A$. So $8k = 8a_1+ 8a_2 +8a_3$. Since 
$8k =
  8$ mod 16, we conclude that for any $x \equiv 8$ mod 16, $x$ is the sum of 
at
  most
  three tau numbers. It is easy to see from this result and the fact that
  $1,2,8,9,12$ are all tau, that any integer greater than $56$ can be
  expressed as the sum of $6$ or fewer tau numbers. It is easy to verify 
that
  every
  integer under $56$ can be expressed as the sum of $6$ or fewer tau 
numbers.
  Thus,
  if Goldbach's weak conjecture is true than every integer is the sum of $6$
  or fewer tau numbers.

  Case (b) follows by similar reasoning.
  \end{proof}

  \begin{theorem}
  For all sufficiently large $n$, $n$ can be expressed as the sum of $6$ or
  fewer tau numbers.
  \label{thm12}
  \end{theorem}
  \begin{proof}
  This result follows from applying Vinogradov's famous result that every
  sufficiently large odd integer is expressible as the sum of three or fewer
  primes and using the same techniques as in the previous theorem.
  \end{proof}

  \bigskip
  The techniques in the previous theorems can also be used to prove the
  following corollary.

  \begin{corollary}
  %Corollary 3:
  If Goldbach's weak conjecture is true than any positive integer
  not congruent to $7$ mod 8 can be expressed as the sum of $5$ or fewer tau
  numbers.
  If Goldbach's strong conjecture is true than every positive integer not
  congruent to $7$ mod 8 is the sum of $4$ or fewer tau numbers.
  \end{corollary}

  Note that since the set $A$ introduced in the proof of Theorem~\ref{thm11}
  contains many elements other than the primes, even if
  either the weak or the strong Goldbach conjectures fail to hold,
  it is still very likely that
  all integers can be expressed as the sum of six or fewer tau numbers.

  We make the following

  \begin{conjecture}
  %Conjecture 2:
  Every positive integer is expressible as the sum of $4$ or
  fewer tau numbers.
  \end{conjecture}

  It seems that the above conjecture cannot be proven by
  methods similar to those used in Theorem~\ref{thm11}.

  \bigskip

  For any $n$, Bertrand's postulate states that there is a prime between $n$ 
and
  $2n$. The equivalent for tau numbers is the next theorem:

  \begin{theorem}
  For any integer $n>5$ there is always a tau number between $n$ and $2n$.
  \label{thm13}
  \end{theorem}
  \begin{proof}
  This result follows immediately from the fact that $8$ is a
  $p$-generator.
  \end{proof}

  \bigskip

  Another unsolved problem about primes is whether there is always a prime
  between $n^2$ and $(n+1)^2$.
  The fact
  that the tau numbers have a much higher density than the primes motivates
  the following conjectures:

  \begin{conjecture}
  %Conjecture 3:
  For any sufficiently large integer $n$, there exists a tau number
  $t$ such that
  $n^2 <t<(n+1)^2$.
  \end{conjecture}

  \begin{conjecture}
  %Conjecture 4:
  For any integer $n$, there exist a tau number $t$ such that $n^2\leq t 
\leq
  (n+1)^2$.
  \end{conjecture}

  Dirichlet's Theorem states that when $\gcd(a,b)=1$ then the set $\lbrace
  n \ : \ an+b \ \rm{is\ prime} \rbrace$
  is infinite.  This theorem is equivalent to there being an infinite number 
of
  primes in any arithmetic progression aside from certain trivial cases. For 
tau
  numbers
  the equivalent problem becomes:

  \begin{conjecture}
  %Conjecture 5:
  Any arithmetic progression of positive integers which contains a
  tau number contains infinitely many tau numbers.
  \end{conjecture}

           For many arithmetic progressions that have no terms divisible by 
$4$,  it is
  often easy to see that they do not contain any tau numbers, since the 
sequences
  contain all odd non-quadratic residues mod some $k$, or twice such 
residues.
  Examples include the progressions
  $3,7,11,15\dots$ and $6,14,22,30\dots$  There are many other
  arithmetic progressions which fail to contain tau numbers and the proofs 
require
  a
  little arithmetic. The arithmetic progression
  $4, 28, 52, 76\dots$ is one example.

  \begin{theorem}
  If $n\equiv 4$ (mod $24$), then $n$ is not a tau number.
  \label{thm14}
  \end{theorem}
  \begin{proof}
  Let $n$ be a tau number
  and $n\equiv 4$ (mod $24$).  Then $4$ is the highest power of $2$
  dividing $n$, so $3 \ | \ n$ which is impossible.
  \end{proof}

  \bigskip
  The concept of $p$-generators can be  be generalized.

  \bigskip
  \noindent{\bf Definition.}
  For a list of positive
  integers $a_1,a_2,a_3\dots a_k$, $n$ is an {\sl $(a_1,a_2, \dots
  a_k)$-generator} if for all $k$-tuples of
  distinct primes $(p_1,p_2,\dots,p_k)$ which do not
  divide $n$, $n p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ is a tau number.
  Such tau numbers are
  said to be {\sl generated by $n$}.

  \bigskip
  Note: Whenever convenient, we assume the $a_i$ in the above definition are
  in increasing order. The earlier idea of the $p$-generator now becomes a
  $(1)$-generator. Under this notation Lemma~\ref{lemma1} can be reexpressed 
as
  follows:  $36$ is a $(1,1)$-generator.

  \bigskip
  \noindent{\bf Definition.}
  A tau number $n$ is said to be a {\sl primitive tau number}
  if $n$ is not generated
  by any $k$.

  \bigskip
  \noindent{\bf Definition.}
  $m$ is said to be an {\sl ancestor} of $n$ if $m$ generates $n$ or $m$
  generates an ancestor of $n$.
  It is not difficult to see that this recursive definition is well-defined.

  Example: $9$ is an ancestor of
  $180$ since $180$ is generated by $36$ and
  $36$ is generated by $9$.

  \bigskip
  \noindent{\bf Definition.} Let $h(n)$ be the number distinct sets of 
positive
  integers
  greater than one such that the product of all the elements of the set is
  $n$.

  The following theorem summarizes the basic properties of generators. No 
part
  is difficult to prove and the proofs are left to the reader.

  \begin{theorem}
  \begin{itemize}
  \item[(a)] There exist infinitely many primitive tau numbers.
  \item[(b)] For any $a_1,a_2,a_3\dots a_k > 0$ there exist infinitely many
  $n$ such that $n$
  is a $(a_1,a_2 \dots a_k)$-generator.
  \item[(c)] For any tau number
  $n>2$ there exist $a_1,a_2,a_3 \dots a_k$ such that $n$ is
  an $(a_1,a_2,a_3 \dots a_k)$-generator. In particular, $n$ is a 
$(n/\tau(n)
  -1)$-generator.
  \item[(d)] Apart from the order of the exponents any given tau number
  has $\sum_{d|n/\tau(n)}
  h(d)$ generators.
  \item[(e)] If for some $a_1,a_2,\dots a_k$ $n$ is an
  $(a_1,a_2,\dots, a_k)$-generator
  then  for any $0<j<k$,
  $n$ is a $(a_1,a_2,\dots,a_j)$-generator.
  \item[(f)] If $m,n$ are relatively prime tau numbers where $n$ is a
  $(a_1,a_2,\dots,
  a_k)$-generator then $mn$ is also a
  $(a_1,a_2,\dots, a_k)$-generator.
  \item[(g)] If $m,n$ are relatively prime tau numbers and $n$ is an
  $(a_1,a_2,\dots,
  a_k)$-generator  and $m$ is a
  $(b_1,b_2,\dots, b_j)$-generator then $mn$ is an $(a_1,a_2,\dots, a_k,
  b_1,b_2,\dots, b_j)$-generator.
  \item[(h)] Every tau number $n$ is either a primitive tau number
  or has exactly one ancestor $m$
  which is a primitive tau number,
  which is defined to be the primitive ancestor of
  $n$.
  \end{itemize}
  \label{thm15}
  \end{theorem}


  The consideration of the low density of tau numbers with a given ancestor 
and
  the
  low density of primitive tau numbers motivates the following definitions 
and
  accompanying conjectures.

  \bigskip
  \noindent{\bf Definitions.}
  Let $T_k (n) $ denote
  the number of tau numbers less than or equal to $n$ with
  $k$ as an ancestor.
  Let $PT(n)$ denote  the number of primitive tau numbers less than or equal 
to
  $n$.

  \begin{conjecture}
  %Conjecture 6:
  For any $k, \lim_{n \rightarrow \ \infty} T_k (n)/T(n) =0 $.
  \end{conjecture}

  A proof of the above conjecture
  for even $n$ is not dificult and is left to the
  reader.

  \begin{conjecture}
  %Conjecture 7:
  $\lim_{n \rightarrow \ \infty} PT(n)/ T(n) =0$.
  \end{conjecture}

  Theorem~\ref{thm15} (c) and (d) motivate an investigation into the properties
  of the function $t(n) :=
  n/\tau(n)$. Clearly this function is an integer iff $n$ is a tau number.
  Not every
  positive integer is in the range of $t(n)$.

  To prove that not every integer is in the range of $t$ we need a few 
lemmas.

  \begin{lemma}
  %Lemma 9:
  % note he has two lemma 9's
  $\tau(n)<2n^{1/2}$ for all $n \geq 1$.
  \label{lemma92}
  \end{lemma}

  \begin{proof}
  Clearly, for any divisor $d$ of $n$, if $d \geq n^{1/2}$ then $n/d \ | \ 
n$
  and $n/d \leq n^{1/2}$ Thus we can make pairs of all the divisors of $n$ 
with
  each one number of each pair less than $n^{1/2}$. Since there are at most
  $n^{1/2}$ pairs, we get $\tau(n))<2n^{1/2}$.
  \end{proof}

  \begin{lemma}
  %Lemma 10:
  For all $n, t(n)> .5n^{1/2}$.
  \label{lemma10}
  \end{lemma}

  \begin{proof}
  This follows immediately from Lemma~\ref{lemma92}.
  \end{proof}

  \begin{lemma}
  %Lemma 11:
  For any real number $r$, if $n/\tau(n) \leq r$ then $n\leq 4r^2$.
  \label{lemma11}
  \end{lemma}
  \begin{proof}
  This follows immediately Lemma~\ref{lemma10}.
  \end{proof}

  \bigskip
  The next lemma is easy to prove and the proof is omitted.
  \begin{lemma}
  %Lemma 12:
  For any prime $p$, tau number $n$, and integer $k \geq 1$,
  if
  $p^{p^k -1}\ |\ n/\tau(n)$ then $p^{p^k} \ | \ n$.
  \label{lemma12}
  \end{lemma}

  \begin{theorem}
  There does not exist $n$ such that $t(n) = 18$.
  \label{thm16}
  \end{theorem}
  \begin{proof}
  By Lemma~\ref{lemma11} we merely need to verify the claim for $n \leq 
1296$.
  Using Lemma~\ref{lemma12} we need only to check the multiples of $108$
  which is easy to do.
  \end{proof}

  Kennedy and Cooper's result that the tau numbers have density $0$
  \cite{Kennedy}, along with
  Lemma~\ref{lemma11}, motivates the following conjecture:

  \begin{conjecture}
  %Conjecture 7:
  There exist infinitely many positive integers $k$ such that for all $n$, 
$t(n)
  \not= k$.
  \label{conjecture7}
  \end{conjecture}

  We can prove a much weaker result than the above conjecture. We
  show that there are integers which are not in the range of $t(2n+1)$ .
  First we need two lemmas corresponding to the earlier lemmas.

  \begin{lemma}
  %Lemma 13:
  For any odd integer $n,$ $\tau(n) \leq  \lceil n^{1/2} \rceil$.
  \label{lemma13}
  \end{lemma}
  \begin{proof}
  This follows from a modification of Lemma~\ref{lemma9}.
  \end{proof}

  Lemma~\ref{lemma13} leads directly to Lemma~\ref{lemma14}:

  \begin{lemma}
  %Lemma 14:
  For any odd integer $n$, $ t(n) \geq \lfloor n^{1/2} \rfloor$.
  \label{lemma14}
  \end{lemma}

  \begin{proof}
  This follows from Lemma~\ref{lemma13}.
  \end{proof}

  \begin{theorem} There exist infinitely many odd integers $k$ such that
  $t(n) \not= k$ for
  all odd $n$. Specifically, whenever $k$ is an odd prime greater than $3$,
  $t(n) \not= k$ for all odd $n.$
  \label{thm17}
  \end{theorem}
  \begin{proof}
  Assume  that for some  prime $p > 3$, $t(n) =p$. So by 
Lemma~\ref{lemma14}, $p >
  \lfloor n^{1/2} \rfloor$. So $p+1 > n^{1/2}$ and thus $p^2+ 2p + 1 \geq 
n$. Now
  since
  $n$ is an odd tau, $n$ is a perfect square. So $p^2 \ | \ n$ . But $n \leq 
p^2 +
  2p
  + 1$. Thus $n=p^2$ which is impossible.
  \end{proof}

  Using a similar method as the proof of the last theorem, we get the
  following slightly stronger result:
  \begin{theorem}
  Let $p$ be a prime $> 3$. Let $n$ be a tau number
  such that $t(n) =p$. Then $4|n$.
  \label{thm18}
  \end{theorem}

  Note that since almost all tau numbers are divisible by $4$,
  the above result is a
  far cry from Conjecture~\ref{conjecture7}.
  In fact, for  any odd prime $p$ we have $t(8p)=p$.

  Colton also has made the conjecture that for any $n>2$, the number
  $n!/3$ is always a tau number.
  The following heuristic suggests a related conjecture:

  \begin{conjecture}
  %Conjecture 8 :
  For any positive integers $a, b$ with $a$ odd, there exists an integer
  $k$  such that
  $ (a/b)n!$ is a tau number for all $n > k$.
  \end{conjecture}

       We give a heuristic reason to believe this conjecture.
  Let $a$ and $b$ be integers.  Consider some $n$ much larger than
  $a$ and $b$. Now on average, for some prime $p$, it is easy to see that
  the mean number of times $p$ appears in the factorization of $n$ is
  about $1/(p-1)$.  For
  large $n$, the change made by $a$ and $b$ in the number of factors is
  small. So for any prime $p$ in the factorization of $(a/b)n!$, $p$ is 
raised
  to a power approximately equal to  $n/(p-1)$.
  and there are about $n/\log n$ primes $\leq n$. Hence
  the highest power of $p$ dividing
  $\tau((a/b)n!))$ is about $n/((p-1)\log n)$.
  For all sufficiently large $n$,
  $n/(p-1)$ is much larger than $n/((p-1)\log n)$.
  Since every prime exponent of $\tau((a/b)n!))$ is less than the 
corresponding
  exponent for $(a/b)n!$ we conclude that
  $\tau((a/b)n!)) \ | \ (a/b)n!$.
  \bigskip

  Note: The reason $a$ must  be odd in the above conjecture is subtle. Let 
$n
  = 2^k$. It is not difficult to see that
  $2^{n-1}\ |\  n!$.  Thus if $a$ has some power of $2$ dividing it than one 
can
  force the power of $2$ in
  $an!$ to be slightly over $n$, such as $2^{n+2}$, in which case
  $(2^k)+3|\tau(an!)$ and $2^k+3$ may be prime infinitely often, in which 
case
  $\tau(an!)$ does not divide $an!$ for any such $k$. Examples other than
  $2^k+3$ would also suffice. It is easy to see that this problem only 
arises
  with $2$ and not any other prime factor.

  We can prove a large portion of this conjecture. We first require a few
  definitions.

  \bigskip
  \noindent{\bf Definition.}
  Let $\nu_p(n)$ denote the largest integer $k$ such that $p^k \ | \ n$.

  \begin{lemma}
  %Lemma 15:
  $n$ is a tau number iff for any prime $p,  \nu_p(\tau(n)) \leq \nu_p(n)$.
  \label{lemma15}
  \end{lemma}

  \begin{proof}
  This follows immediately from the definition of $L$.
  \end{proof}

  \begin{lemma}
  %Lemma 16:
  $\lfloor n/p \rfloor \leq \nu_p(n!) \leq \lceil n/(p-1) \rceil$. 
Furthermore,
  $\nu_p(n!) \sim n/(p-1)$.
  \label{lemma16}
  \end{lemma}

  \begin{proof}
  The proof is left to the reader.
  \end{proof}

  \begin{lemma}
  % Lemma 17:
  For any positive integers $a$ and $b$, and prime $p, \nu_p((a/b)n!)
  \sim n/(p-1)$.
  \label{lemma17}
  \end{lemma}

  \begin{proof}
  Let $a$ and $b$ be positive integers and $p$ prime. Without loss of
  generality assume $\gcd(a,b)=1$.
  For all $n$,
  $\nu_p(n!) - \nu_p(b) \leq \nu_p((a/b)n!) \leq \nu_p(n!)+\nu_p(a)$.
  Now
  applying Lemma~\ref{lemma16},
  and noting that  $\nu_p(b)$ and  $\nu_p(a)$ are constant with
  respect to $n$, we  conclude that $\nu_p((a/b)n!) \sim n/(p-1)$.
  \end{proof}

  \begin{theorem}
  Let $a$ and $b$ be positive integers, and $p$ prime. For all sufficiently
  large $n$
  the highest power of $p$ that divides  $\tau((a/b)n!)$ also
  divides $(a/b)n!$.
  That is,
  $\nu_p(\tau((a/b)n!))\leq \nu_p((a/b)n!)$.
  \label{thm19}
  \end{theorem}
  \begin{proof}
  Let $a$ and $b$ be positive integers and let $p$ be a prime.
  Without loss of
  generality assume $\gcd(a,b)=1$.
  We thus need to find, for all sufficiently large $n$,
  an upper bound $U_p (n)$
  for $\nu_p(\tau((a/b)n!))$  and show that there
  is a constant $k<1$ such that for all sufficiently large $n$,
  the inequality $U_p (n)/(n/p) < k$  holds.
  We consider two cases: $p=2$ and $p>2$.

  Case I: $p=2$. Thus we need to find an upper bound $U_2(n)$ for
  $\nu_2(\tau((a/b)n!))$ such that
  $U_2(n)/(n/p) < k$ for all sufficiently large $n$ and some constant 
$0<k<1$.
  For all sufficiently large $n$, every prime less or equal to $n/2$ which
  does not divide $a$ can contribute at most $(\log n)/(\log 2)$ to
  $\nu_2( \tau((a/b)n!))$.
  Every prime between $n/2$ and $n$ contributes $1$ to
  $\nu_2(\tau((a/b)n!))$. Thus
  \begin{equation}\label{eq10}
  \nu_2(\tau(a/b))n! \leq \pi(n/2)(\log_2 n) +\pi(n) - \pi(n/2) +A_1,
  \end{equation}
  where $A_1$ is some constant depending solely on $a$. Now applying the 
prime
  number theorem yields,   for any $\epsilon >0$ and all sufficiently large
  $n$,
  \begin{equation}\label{eq11}
  \nu_2(\tau((a/b)n!)) < \frac{(1+\epsilon)(n\log_2 n)}{2\log n} +
  \frac{(1+\epsilon)n} {2\log n},
  \end{equation}
  which, when all the logarithms are made natural, becomes:
  For any $\epsilon
   >0$ and all sufficiently large $n$,
  \begin{equation}\label{eq12}
  \nu_2(\tau((a/b)n!)) \leq \frac{(1+\epsilon)n}{2\log 2}
  +\frac{(1+\epsilon)n}{2\log n}
  \end{equation}
  Now fix $\epsilon$ as some number less than $2\log2 -1$and let such a
  resulting function be $U_2(n)$. It is easy to see that the function
  satisfies the desired inequality.

  Case II: Let $p> 2$. Using similar logic to that used in the earlier case 
we conclude that for any $\epsilon >0$ and all sufficiently large $n$
  \begin{equation}\label{eq13}
  \nu_2(\tau((a/b)n!)) \leq \frac{(1+\epsilon)(n+p)(\log_p n)}{p 
\log((n+p)/p)}
  \leq \frac{(1+\epsilon)(n+p)}{p\log p}
  \end{equation}
  Fixing $\epsilon$ as some number less than $p\log p -1$ and making the
  rightmost part of (\ref{eq13}) equal to $U_p
  (n)$ gives the desired result.
  \end{proof}

  Note that one could use the earlier cited bounds of Dusart to make the 
above proof
  constructive.

\section{Generalizations}

  It is possible to generalize the concept of tau number. First consider 
that
  the definition of  tau number
  is equivalent to $n \bmod \tau(n) =0$. We now say that $n$ is
  a tau number relative to $k$ if $n \bmod \tau(n) =k$.
  Of course, $k=0$ gives the ordinary tau numbers and it is
  easy to see that every odd prime is a tau number relative
  to $1$.  Also it is easy to see that any
  $n$ is a tau number relative to $k$,
  for some $k$. The main result about integers which are tau numbers 
relative
  to $k$ is  the following theorem:

  \begin{theorem}
  For any odd $k$ there exists an infinitely many
  $n$ such that $n$ is a tau number relative to
  $k$.
  \label{thm20}
  \end{theorem}
  \begin{proof}
  Let $k$ be an odd integer. We claim that there exist arbitrarily large
  distinct primes, $p$, $q$ and $r$ such that $p^{r-1} q \bmod 
\tau(p^{r-1}q) =
  k$. This is equivalent to showing that $p^{r-1}q \equiv k$ (mod $2r$). By
  Fermat's
  Little Theorem, $p^{r-1} \equiv 1$ (mod $r$). Thus we merely need to show 
that
  there
  exist arbitrarily large primes $q$ such that $q \equiv k$ (mod $2r$), 
which
  follows
  immediately from Dirichlet's theorem about primes in
  arithmetic progressions.
  \end{proof}


  I make the following conjecture.

  \begin{conjecture}
  %Conjecture 10:
  For any $k$, there exist infinitely many $n$ such that $n$ is
  a tau number relative to $k$.
  \end{conjecture}

  It is not difficult to prove many special cases of this conjecture $k$ 
where
  some $p$ is assumed not to divide $k$, as in Theorem~\ref{thm19}. In fact 
we shall prove the
  above conjecture by examining a larger generalization:

  Let $Q(n)$ be a polynomial
  with integer coefficients.
  An integer $n$ is said to be a tau number
  relative to $Q(n)$ if $\tau(n) \ | \ Q(n)$.
  In this generalization, tau
  numbers are the case where $Q(n) =n$.

  Clearly the above conjecture follows from the next theorem:
  \begin{theorem} For any $Q(n)$ with integer coefficients, there exist
  infinitely many $n$ such that
  $\tau(n) \ | \ Q(n)$.
  \label{thm21}
  \end{theorem}
  \begin{proof}
  Without loss of generality, assume the leading coefficient of $Q(n)$ is
  positive. If the constant term is $0$ then any tau number is a
  tau number relative to $Q(n)$.
  So assume the constant term is non-zero. Chose some $c$ such that 
$Q(c)\geq 1$ and
  $(Q(c),c)=1$.
  Now by Dirichlet's theorem there exist
  infinitely many
  primes $p$ such that $p \equiv c$ (mod $Q(c)$). For any such $p$,
  $p^{Q(c)-1}$ is a tau number for $Q(n)$ since $\tau(p^{Q(c)-1}) = Q(c)$ and
  $Q(c)  \ | \  Q(p)$.
  \end{proof}


  If $n$ is a tau number, then $\tau(n)$ has a similar as possible a factorization to 
$n$
  in some sense. Tau numbers maximize $\gcd(n,\tau(n))$. This motivates the
  following definition:

  \bigskip
  \noindent{\bf Definition.} The positive integer $n$ is said to be an {\it anti-tau
  number} if $\gcd(n, \tau(n))=1$.

  Note an integer $n$ is a tau number iff $\lcm(n, \tau(n))=n$.
  Thus in some sense, an integer
  $n$ is a tau number if
  $\lcm(n, \tau(n))$ is minimized. Now, if $\gcd(n, \tau(n)) = 1$ then 
$\lcm(n,
  \tau(n))= n \tau(n)$. Thus the anti-tau numbers
  represent the numbers that maximize
  $\lcm(n, \tau(n))$.

  Note that if two tau numbers are relatively prime then their product is a
  tau number. But as
  the pairs (3,4), (3,5) and (13,4) demonstrate, the product of two 
relatively
  prime anti-tau numbers can be a tau number, an anti-tau number, or 
neither.
  The following Theorem summarizes the basic properties of anti-tau numbers.
  \begin{theorem}
  \begin{itemize}
  \item[(a)] The only tau number that is also an anti-tau number is $1$.
  \item[(b)] If $a$ is an even anti-tau number, then $a$ is a perfect 
square.
  \item[(c)] For $a,b>1$, $\gcd(a,b)=1$  $a$ is a tau number
  and $b$ is an anti-tau number then $ab$ is
  neither a tau nor an anti-tau number.
  \item[(d)] Any odd square-free number is an anti-tau number.
  \item[(e)] For any constant integer $C$, where primes $a_1,a_2\dots a_k$ 
are all
  less
  than $C$ and then for some primes distinct $p_1,p_2,\dots...p_k$ all 
greater
  than $C$, then for any positive integers,  $b_1,b_2 \dots b_k$  the number
  $(a_1^{{p_1^{b_1}}-1})(a_2^{{p_2^{b_2}}-1})\cdots(a_k^{{p_k^{b_k}}-1})$ is 
an
  anti-tau number.
  \end{itemize}
  \label{thm22}
  \end{theorem}

  Part (b) of the above theorem shows
  that the anti-tau numbers are unlike the tau numbers
  in more than one way,
  since a corresponding rule exists about the odd tau numbers.
  Part (c) can be considered a cancellation law of sorts. Parts (d) and (e)
  motivates the following conjecture.  Let $AT(n)$ denote the number
  of numbers $\leq n$ that are anti-tau numbers.

  \begin{conjecture}
  %Conjecture 11:
  For all $n>3$, the inequality $T(n) < AT(n)$ holds.
  \label{conj11}
  \end{conjecture}

  The following results indicate the above conjecture is true for all
  sufficiently large $n$.
  \begin{theorem}
  The density of the anti-tau numbers is at least $3/ \pi^2$.
  \label{thm23}
  \end{theorem}
  \begin{proof}
  This follows immediately from Theorem~\ref{thm22} (d) and the
  fact that the
  square free numbers have density
  $6/\pi^2$.
  \end{proof}

  \begin{theorem}
  For all sufficiently large $n$, $T(n) < AT(n)$. In fact $\lim_{n 
\rightarrow
  \infty} T(n)/AT(n) =0$.
  \label{thm24}
  \end{theorem}
  \begin{proof}
  This theorem follows immediately
  from the density of the anti-tau numbers together
  with Kennedy and Cooper's result that the tau numbers have zero density.
  \end{proof}

  Conjecture~\ref{conj11} is intuitive. In order for $n$ to be not tau, all
  $\tau(n)$ needs is to have too high a prime power in its factorization or 
a
  prime that is not a factor of $n$. However, in order for $n$ not to be
  anti-tau, $\tau(n)$ needs a prime factor of $n$, a much stronger 
condition.

  Colton also conjectured the non-existence of
  three consecutive tau numbers. We shall
  prove the slightly stronger result that  if  $a$ is an odd integer such 
that
  $a, a+1$ are both tau numbers then $a=1$.

  A few remarks:
  Colton started by assuming that he had three tau numbers $a-1,a,a+1$
  and then showed using the basic congurence restrictions on the tau numbers 
that
  $a$ was
  an odd perfect square and $a+1$ was twice an odd perfect square. However, 
it
  is easy to see that this restriction applies equally well if we substitute
  the assumption that $a-1$ is a tau number for assuming $a$ is odd. Colton 
then
  examined the resulting Diophantine equation $x^2 +1 = 2y^2$ and was able 
to
  produce other restriction on the necessary properties of the triple based 
on
  this well-known equation.

  \begin{theorem}
  If  $a$ is an odd integer such that $a, a+1$ are tau numbers then $a=1$.
  \label{thm25}
  \end{theorem}

  \begin{proof}
  By the above comments, we really need to look at the Diophantine equation
  $x^2+1=2y^2$. Now it is a well known result that any odd divisor of 
$x^2+1$
  must be congruent to $1$ (mod 4) \cite{Shirali}. So every odd divisor of
  $2y^2$ must be congruent to $1$ (mod 4). But  $2y^2$ is a tau
  number, so every odd prime
  in its factorization must be raised to an exponent divisible by $4$ since
  otherwise $2y^2$ would be divisible some number of the form $3$ mod 4. 
Thus
  $2y^2 = 2w^4$ for some $w$. So we really need to solve $x^2+1=2w^4$.  This
  is a Diophantine equation which has only the
  solutions $(x,w) =(1,1)$ and
  $(x,w)=(239,13)$ \cite{Steiner}.
  The second solution fails to yield a tau number and
  so $x=1$.
  \end{proof}

  The known proofs that these are the only positive solutions of   this 
final
  Diophantine equation are quite lengthy and involved.  It would be
  interesting to find a way of proving the desired result without relying on
  the equation, or possibly, a simple proof that (1,1) is the only tau
  solution of the equation.

  \section{Acknowledgments}

  The author would like to thank the referee for useful comments.

  The author would also like thank Jeffrey Shallit, Stephen David Miller, 
Simon Colton,
  David Speyer, Glenn Stevens, Aaron and Nathaniel Zelinsky, Aaron Margolis,
  Mogs Wright, David McCord, Kevin Hart and the rest of the ever supportive
  math department of the Hopkins School in New Haven, Connecticut.


  \begin{thebibliography}{1}
  \bibitem{Colton}
  Simon Colton, Refactorable numbers --- a machine invention,
  {\it Journal of Integer Sequences} {\bf 2},  Article 99.1.2,
  {\tt http://www.math.uwaterloo.ca/JIS/colton/joisol.html}.

  \bibitem{Hardy}
  G. H. Hardy and E. M. Wright, {\it An Introduction to the Theory
  of Numbers}, Oxford University Press, 1985.

  \bibitem{Kennedy} R. E. Kennedy and C. N. Cooper,  Tau numbers, natural
  density, and Hardy and Wright's Theorem 437, {\it Internat.\
  J. Math.\ Math.\ Sci.} {\bf 13} (1990), 383--386.

  \bibitem{Ribenboim} Paulo Ribenboim,  Catalan's Conjecture, {\it 
Amer.\ Math.\ Monthly} {\bf 103} (1996), 529--538.

  \bibitem{Shirali} Shailesh A. Shirali, A family portrait of the primes
  --- a
  case study in discrimination, {\it Math.\ Mag.} {\bf 70} (1997), 
263--272 .

  \bibitem{Dusart} P. Dusart, The $k$th prime is greater than $k(\ln 
k+\ln\ln
  k-1)$ for $k> 2$,
  {\it Math. Comp.} {\bf 68} (1999), 411--415.

  \bibitem{Steiner} Ray Steiner and Nikos Tzanakis,  Simplifying the
  solution of Ljunggren's equation $x^2 +1 = 2y^4$, {\it
  J. Number Theory} {\bf 37} (1991) 123--132.

  \end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords:  tau number, number-of-divisors function}

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A033950}.)


\vspace*{+.1in}
\noindent
Received August 1, 2002;
revised version received  December 15, 2002.
Published in {\it Journal of Integer Sequences} December 16, 2002.
Corrections, February 17, 2003.
\bigskip
\hrule
\bigskip

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


  \end{document}