Tau Numbers: A Partial Proof of a Conjecture and Other Results

Joshua Zelinsky The Hopkins School New Haven, CT 06515 USA

                  Email: Lord Bern@hotmail.com

Abstract. A positive n is called a tau number if τ(n) | n, where τ is the number-of-divisors function. Colton conjectured that the number of tau numbers ≤ n is at least \frac{1}{2}π(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 .

1 Introduction

Kennedy and Cooper [3] defined a positive integer to be a tau number if τ(n) | n, where τ 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, …;

it is Sloane’s sequence \underline{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 refactorable [1]. 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 · 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.

2 Basic results

Definitions. Let π(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.

Using this notation, Colton’s conjecture becomes: T (n) ≥ π(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 [2, Theorem 273] is used extensively: Proposition 1. If n = p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}} then τ(n) = (a_{1} + 1)(a_{2} + 1)(a_{3} + 1) ⋯ (a_{k} + 1).

The next five theorems are all due to Colton. Theorem 2. Any odd tau number is a perfect square. Proof. Assume that n is an odd tau number. Let n = p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}}. By Proposition 1 and the definition of tau number (a_{1} + 1)(a_{2} + 1)(a_{3} + 1) … (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. Theorem 3. An odd integer n is a tau number iff 2n is a tau number. Proof. If n = p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}}, then τ(2n) = 2(a_{1} + 1)(a_{2} + 1)(a_{3} + 1) ⋯ (a_{k} + 1) = 2τ(n). Since τ(n) | n iff 2τ(n) | 2n, the result follows. Theorem 4. If gcd(m, n) = 1 and m, n are both tau numbers, then mn is a tau number. Proof. This result follows immediately from τ(mn) = τ(m)τ(n) when gcd(m, n) = 1. Theorem 5. There are infinitely many tau numbers.

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. Theorem 6. For any given finite nonempty set of primes, there are infinitely many tau numbers with exactly those primes as their distinct prime divisors. Proof. This result follows from considering the mapping:

f(n) = f(p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}}) = p_{1}^{p_{1}^{a_{1}}−1}p_{2}^{p_{2}^{a_{2}}−1} ⋯ p_{k}^{p_{k}^{a_{k}} −1}.

It is easy to see that the mapping produces only tau numbers. Theorem 7. Every tau number is congruent to 0,1,2 or 4 mod 8. Proof. This follows immediately from Theorems 2 and 3.

3 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.

Theorem 8. Let n be a tau number and let p be the smallest prime factor of n. If q is prime and q | n then q^{p−1} | n.

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 | n. But p is the smallest non-trivial divisor of n so k + 1 ≥ p. Hence k ≥ p − 1 and thus q^{p−1} | n.

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.

Lemma 9. For any distinct primes p, q > 3, the number 36pq is a tau number.

Proof. By the multiplicative property of the tau function, τ(36pq) = τ(4)τ(9)τ(p)τ(q) = 3 · 3 · 2 · 2 = 36.

Lemma 10. Let k be an integer ≥ 1. Then the number of integers ≤ n of the form kp, where p is prime, is asymptotic to n/(k log n). Similary, for any fixed integer a ≥ 1 the numbers of integers ≤ n of the form kp^{a} is asymptotic to ((n/k)^{1/a})/ log(n).

Proof. Both these formulas follow easily from the prime number theorem.

Lemma 11. Let k be a positive integer. Then the number of numbers ≤ n of the form kpq, where p, q are distinct primes, is asymptotic to (n log log n)/(k log n).

Proof. We use a Theorem of Hardy and Wright [2, Thm. 437], which states that the number of squarefree numbers less than n with k prime factors, k ≥ 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 10 yields the desired result.

Lemma 12. The numbers of tau numbers ≤ n of the form 36pq with p, q distinct primes > 3 is asymptotic to (n log log n)/(36 log n).

Proof. By Lemma 11 the number of positive integers ≤ n of the form 36pq is asymptotic to

\frac{n log log n}{36 log n}  (1)

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 · 2 · p or 36 · 3 · p. Thus, using 1, together with Lemma 11 the number of such numbers is asymptotically

\frac{n log log n}{36 log n} − \frac{n}{72 log n} − \frac{n}{108 log n}−  (2)

which is asymptotic to the first term.

Lemma 13. For any fixed real number r < 1 we have T (n) > \frac{rn log log n}{36 log n} for all n sufficiently large.

Proof. This inequality follows from Lemmas 12 and 9.

Theorem 14. For any real number k we have T (n) > kπ(n) for all n sufficiently large.

Proof. Clearly for any positive r < 1, and any k, for all sufficiently large n,

\frac{rn log log n}{36 log n} > kn/ log n.  (3)

Since π(n) ∼ n/ log n, for all sufficiently large n, \frac{rn log log n}{36 log n} > kπ(n). By applying Lemma 13, we conclude that for all sufficiently large n, T (n) > kπ(n).

Corollary 15.

For any b > 0 there are at most a finite number of integers n such that T (n) > bπ(n).

Proof. This result follows immediately from Theorem 14.

Corollary 16. There are at most a finite number of integers n such that T (n) < .5π(n).

Proof. Let b = .5 in the above corollary.

Theorem 14 also implies that T (n) > π(n) for all sufficiently large n. Colton gave a table of T (n) showing that T (10^{7}) is about .59π(n). So T (n) must not drastically exceed π(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.

Definition. An integer n is rare if τ(n) | n, τ(n) | ϕ(n) and τ(n) | σ(n), where ϕ(n) is the number of integers less than or equal to n and relatively prime to n, and σ(n) is the sum of the divisors of n.

Let R(n) be the number of rare numbers ≤ 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π(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) > π(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 τ(n) | σ(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,

((n log log n)^{k})/ log n = o(T (n)).  (4)

Finding an actual asymptotic formula for T (n) is more difficult. We can address this issue with certain heuristics. We know that τ(n) is of average order log n. Since n is a tau number when n mod τ(n) = 0 and n mod τ(n) can have τ(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 [2, p. 265], 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:

Conjecture 17.

T (x) ∼ (1/4) ∫_{3}^{x} log u^{− log 2}du.  (5)

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 mod 4. In fact, we conjecture that for all sufficiently large n the integral underestimates T (n). Since the relationship between τ(n) and (log n)^{log 2} is weak, it seems much safer to conjecture the weaker:

log T (x) ∼ log (\frac{1}{4} ∫_{3}^{x}(log u)^{− log 2}du) .  (6)

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 · 10^{13}.

Lemma 18. 2 | n/τ(n) iff for any prime p such that p does not divide n, np is a tau number.

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

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 p-generator. Any tau number of the form np is said to be p-generated by n.

Thus, in the example above, 8 is a p-generator. Thus Lemma 18 can be restated as follows: n is a p-generator iff 2 | n/τ(n). In what follows, both forms of this lemma are used interchangeably.

Notation. Let ω(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 nth prime, with P_{1} = 2.

Lemma 19. Let k be a p-generator. The number of tau numbers ≤ n of the form kp is at least π(n/k) − ω(n).

Proof. Left to the reader.

Lemma 20. If a_{1}, a_{2}, … a_{s} are p-generators, then for any n the number of tau numbers ≤ n p-generated by any a_{i} is at least

∑_{i=1}^{s} π(n/a_{i}) − π(g(a_{i})).  (7)

Proof. The proof follows from Lemma 18 when we observe that for any a_{i}, a_{j} where k = π(g(a_{i}))+1 and m = π(g(a_{j}))+1, the sets {a_{i}P_{k}, a_{i}P_{k+1}, a_{i}P_{k+2}, …} and {a_{j}P_{m}, a_{j}P_{m+1}, a_{j}P_{m+2}, …} have no common elements.

Lemma 21. If a_{1}, a_{2}, a_{3}, … are p-generators then for any n the number of tau numbers ≤ n p-generated by any a_{i} is at least Aπ(n)−B where A = ∑_{i=1}^{k} 1/a_{i} and B = ∑_{i=1}^{k}(π(g(a_{i}))+1).

Proof. This proof follows immediately from Lemma 19 since each summand in A introduces an error of at most 1.

Theorem 22. For all n > 7.42 · 10^{13} we have T (n) > π(n)/2.

Proof. It has been shown by Dusart [6] that for all n > 598, the inequality

(n/ log n))(1 + .992/ log n) < π(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 21 to obtain a lower bound for the number of tau numbers, and then demonstrate that for all n greater than 7.42 · 10^{13}, this exceeds .5(n/ log n)(1 + 1.2762/ log n) and thus exceeds .5π(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 21 is over .508. It is not difficult to see that

B < G(π(413980/36)) + G(π(413980/80)) + G(π(413980/96)) + (413980 − π(413980/36)
− π(413980/80) − π(413980/96)) − π(413980/128).

Calculating the relevant values and evaluating the above expression yields B < 8694520815. Thus, for all n > 598·28653696, 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 · 10^{13} we conclude that for all n > 7.42 · 10^{13}, we have T (n) > .5π(n).

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

Theorem 23. The sum of the reciprocals of the tau numbers diverges.

Proof. The result follows immediately by observing that 8 is a p-generator and that the sum of the reciprocals of the primes diverges.

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 [4]. 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.

Theorem 24. There do not exists tau numbers a, b such that a − b = 5.

Proof. Suppose, contrary to what we want to prove, that there exist tau numbers a, b such that a − b = 5. By Theorem 7 we know that every tau number is congruent to 0, 1, 2 or 4 (mod 8). Thus, we have b ≡ 4 (mod 8) and a ≡ 1 (mod 8). Hence 4 is the highest power of two which divides b. Thus τ(4) = 3 | τ(b), and since τ(b) | b we get b ≡ 0 (mod 3). Then a ≡ 2 (mod 3), which is impossible since a is an odd tau number and hence a square.

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 [4].

However, Colton’s congruence results of Theorem 7 imply that any n ≡ 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.

Theorem 25. (a) If Goldbach’s weak conjecture is true than any positive integer can be expressed as the sum of 6 or fewer tau numbers.

(b) If Goldbach’s strong conjecture is true than every positive integer is the sum of 5 or fewer tau numbers.

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 ≡ 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.

Theorem 26. For all sufficiently large n, n can be expressed as the sum of 6 or fewer tau numbers.

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.

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

Corollary 27. 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.

Note that since the set A introduced in the proof of Theorem 25 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

Conjecture 28. Every positive integer is expressible as the sum of 4 or fewer tau numbers.

It seems that the above conjecture cannot be proven by methods similar to those used in Theorem 25.

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:

Theorem 29. For any integer n > 5 there is always a tau number between n and 2n.

Proof. This result follows immediately from the fact that 8 is a p-generator.

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:

Conjecture 30. For any sufficiently large integer n, there exists a tau number t such that n^{2} < t < (n + 1)^{2}.

Conjecture 31. For any integer n, there exist a tau number t such that n^{2} ≤ t ≤ (n + 1)^{2}.

Dirichlet’s Theorem states that when gcd(a, b) = 1 then the set {n : an + b is prime} 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:

Conjecture 32. Any arithmetic progression of positive integers which contains a tau number contains infinitely many tau numbers.

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 nonquadratic residues mod some k, or twice such residues. Examples include the progressions 3, 7, 11, 15 … and 6, 14, 22, 30 … 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 … is one example.

Theorem 33. If n ≡ 4 (mod 24), then n is not a tau number.

Proof. Let n be a tau number and n ≡ 4 (mod 24). Then 4 is the highest power of 2 dividing n, so 3 | n which is impossible.

The concept of p-generators can be be generalized.

Definition. For a list of positive integers a_{1}, a_{2}, a_{3} … a_{k}, n is an (a_{1}, a_{2}, … a_{k})-generator if for all k-tuples of distinct primes (p_{1}, p_{2}, …, p_{k}) which do not divide n, np_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{k}^{a_{k}} is a tau number. Such tau numbers are said to be generated by n.

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 9 can be reexpressed as follows: 36 is a (1, 1)-generator.

Definition. A tau number n is said to be a primitive tau number if n is not generated by any k.

Definition. m is said to be an 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.

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.

Theorem 34. (a) There exist infinitely many primitive tau numbers.

(b) For any a_{1}, a_{2}, a_{3} … a_{k} > 0 there exist infinitely many n such that n is a (a_{1}, a_{2} … a_{k})- generator.

(c) For any tau number n > 2 there exist a_{1}, a_{2}, a_{3} … a_{k} such that n is an (a_{1}, a_{2}, a_{3} … a_{k})- generator. In particular, n is a (n/τ(n) − 1)-generator.

(d) Apart from the order of the exponents any given tau number has ∑_{d|n/τ(n)} h(d) generators.

(e) If for some a_{1}, a_{2}, … a_{k} n is an (a_{1}, a_{2}, …, a_{k})-generator then for any 0 < j < k, n is a (a_{1}, a_{2}, …, a_{j})-generator.

(f) If m, n are relatively prime tau numbers where n is a (a_{1}, a_{2}, …, a_{k})-generator then mn is also a (a_{1}, a_{2}, …, a_{k})-generator.

(g) If m, n are relatively prime tau numbers and n is an (a_{1}, a_{2}, …, a_{k})-generator and m is a (b_{1}, b_{2}, …, b_{j})-generator then mn is an (a_{1}, a_{2}, …, a_{k}, b_{1}, b_{2}, …, b_{j})-generator.

(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. 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. Definitions. Let T_{k}(n) denote the number of tau numbers less than or equal to n with k as an ancestor. Let P T (n) denote the number of primitive tau numbers less than or equal to n. Conjecture 35. For any k, lim_{n→ ∞} T_{k}(n)/T (n) = 0.

A proof of the above conjecture for even n is not dificult and is left to the reader. Conjecture 36. lim_{n→ ∞} P T (n)/T (n) = 0.

Theorem 34 (c) and (d) motivate an investigation into the properties of the function t(n) := n/τ(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. Lemma 37. τ(n) < 2n^{1/2} for all n ≥ 1. Proof. Clearly, for any divisor d of n, if d ≥ n^{1/2} then n/d | n and n/d ≤ 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 τ(n)) < 2n^{1/2}. Lemma 38. For all n, t(n) > .5n^{1/2}. Proof. This follows immediately from Lemma 37. Lemma 39. For any real number r, if n/τ(n) ≤ r then n ≤ 4r^{2}.

Proof. This follows immediately Lemma 38.

The next lemma is easy to prove and the proof is omitted. Lemma 40. For any prime p, tau number n, and integer k ≥ 1, if p^{p^{k}−1} | n/τ(n) then p^{p^{k}} | n. Theorem 41. There does not exist n such that t(n) = 18. Proof. By Lemma 39 we merely need to verify the claim for n ≤ 1296. Using Lemma 40 we need only to check the multiples of 108 which is easy to do.

Kennedy and Cooper’s result that the tau numbers have density 0 [3], along with Lemma 39, motivates the following conjecture: Conjecture 42. There exist infinitely many positive integers k such that for all n, t(n) ≠ k.

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. Lemma 43. For any odd integer n, τ(n) ≤ ⌈n^{1/2}⌉. Proof. This follows from a modification of Lemma 21.

Lemma 43 leads directly to Lemma 44: Lemma 44. For any odd integer n, t(n) ≥ ⌊n^{1/2}⌋. Proof. This follows from Lemma 43. Theorem 45. There exist infinitely many odd integers k such that t(n) ≠ k for all odd n. Specifically, whenever k is an odd prime greater than 3, t(n) ≠ k for all odd n. Proof. Assume that for some prime p > 3, t(n) = p. So by Lemma 44, p > ⌊n^{1/2}⌋. So p + 1 > n^{1/2} and thus p^{2} + 2p + 1 ≥ n. Now since n is an odd tau, n is a perfect square. So p^{2} | n . But n ≤ p^{2} + 2p + 1. Thus n = p^{2} which is impossible.

Using a similar method as the proof of the last theorem, we get the following slightly stronger result: Theorem 46. Let p be a prime > 3. Let n be a tau number such that t(n) = p. Then 4|n.

Note that since almost all tau numbers are divisible by 4, the above result is a far cry from Conjecture 42. 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:

Conjecture 47. 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.

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 ≤ n. Hence the highest power of p dividing τ((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 τ((a/b)n!)) is less than the corresponding exponent for (a/b)n! we conclude that τ((a/b)n!)) | (a/b)n!.

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|τ(an!) and 2^{k} + 3 may be prime infinitely often, in which case τ(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.

Definition. Let ν_{p}(n) denote the largest integer k such that p^{k} | n.

Lemma 48. n is a tau number iff for any prime p, ν_{p}(τ(n)) ≤ ν_{p}(n).

Proof. This follows immediately from the definition of L.

Lemma 49. ⌊n/p⌋ ≤ ν_{p}(n!) ≤ ⌈n/(p − 1)⌉. Furthermore, ν_{p}(n!) ∼ n/(p − 1).

Proof. The proof is left to the reader.

Lemma 50. For any positive integers a and b, and prime p, ν_{p}((a/b)n!) ∼ n/(p − 1).

Proof. Let a and b be positive integers and p prime. Without loss of generality assume gcd(a, b) = 1. For all n, ν_{p}(n!) − ν_{p}(b) ≤ ν_{p}((a/b)n!) ≤ ν_{p}(n!) + ν_{p}(a). Now applying Lemma 49, and noting that ν_{p}(b) and ν_{p}(a) are constant with respect to n, we conclude that ν_{p}((a/b)n!) ∼ n/(p − 1).

Theorem 51. Let a and b be positive integers, and p prime. For all sufficiently large n the highest power of p that divides τ((a/b)n!) also divides (a/b)n!. That is, ν_{p}(τ((a/b)n!)) ≤ ν_{p}((a/b)n!).

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 ν_{p}(τ((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 ν_{2}(τ((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 ν_{2}(τ((a/b)n!)). Every prime between n/2 and n contributes 1 to ν_{2}(τ((a/b)n!)). Thus

ν_{2}(τ(a/b))n! ≤ π(n/2)(log_{2} n) + π(n) − π(n/2) + A_{1},  (8)

where A_{1} is some constant depending solely on a. Now applying the prime number theorem yields, for any ϵ > 0 and all sufficiently large n,

ν_{2}(τ((a/b)n!)) < \frac{(1 + ϵ)(n log_{2} n)}{2 log n} + \frac{(1 + ϵ)n}{2 log n},  (9)

which, when all the logarithms are made natural, becomes: For any ϵ > 0 and all sufficiently large n,

ν_{2}(τ((a/b)n!)) ≤ \frac{(1 + ϵ)n}{2 log 2} + \frac{(1 + ϵ)n}{2 log n}  (10)

Now fix ϵ as some number less than 2 log 2 − 1and 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 ϵ > 0 and all sufficiently large n

ν_{2}(τ((a/b)n!)) ≤ \frac{(1 + ϵ)(n + p)(log_{p} n)}{p log((n + p)/p)} ≤ \frac{(1 + ϵ)(n + p)}{p log p}  (11)

Fixing ϵ as some number less than p log p − 1 and making the rightmost part of (11) equal to U_{p}(n) gives the desired result.

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

4 Generalizations

It is possible to generalize the concept of tau number. First consider that the definition of tau number is equivalent to n mod τ(n) = 0. We now say that n is a tau number relative to k if n mod τ(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:

Theorem 52. For any odd k there exists an infinitely many n such that n is a tau number relative to k.

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 mod τ(p^{r−1}q) = k. This is equivalent to showing that p^{r−1}q ≡ k (mod 2r). By Fermat’s Little Theorem, p^{r−1} ≡ 1 (mod r). Thus we merely need to show that there exist arbitrarily large primes q such that q ≡ k (mod 2r), which follows immediately from Dirichlet’s theorem about primes in arithmetic progressions.

I make the following conjecture.

Conjecture 53. For any k, there exist infinitely many n such that n is a tau number relative to k.

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 51. 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 τ(n) | Q(n). In this generalization, tau numbers are the case where Q(n) = n.

Clearly the above conjecture follows from the next theorem:

Theorem 54. For any Q(n) with integer coefficients, there exist infinitely many n such that τ(n) | Q(n).

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) ≥ 1 and (Q(c), c) = 1. Now by Dirichlet’s theorem there exist infinitely many primes p such that p ≡ c (mod Q(c)). For any such p, p^{Q(c)−1} is a tau number for Q(n) since τ(p^{Q(c)−1}) = Q(c) and Q(c) | Q(p).

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

Definition. The positive integer n is said to be an anti-tau number if gcd(n, τ(n)) = 1.

Note an integer n is a tau number iff lcm(n, τ(n)) = n. Thus in some sense, an integer n is a tau number if lcm(n, τ(n)) is minimized. Now, if gcd(n, τ(n)) = 1 then lcm(n, τ(n)) = nτ(n). Thus the anti-tau numbers represent the numbers that maximize lcm(n, τ(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 antitau numbers can be a tau number, an anti-tau number, or neither. The following Theorem summarizes the basic properties of anti-tau numbers.

Theorem 55. (a) The only tau number that is also an anti-tau number is 1.

(b) If a is an even anti-tau number, then a is a perfect square.

(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.

(d) Any odd square-free number is an anti-tau number.

(e) For any constant integer C, where primes a_{1}, a_{2} … a_{k} are all less than C and then for some primes distinct p_{1}, p_{2}, . . . ...p_{k} all greater than C, then for any positive integers,

b_{1}, b_{2} … b_{k} the number (a_{1}^{p_{1}^{b_{1}}−1})(a_{2}^{p_{2}^{b_{2}}−1}) ⋯ (a_{k}^{p_{k}^{b_{k}} −1}) is an anti-tau number.

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 ≤ n that are anti-tau numbers.

Conjecture 56. For all n > 3, the inequality T (n) < AT (n) holds.

The following results indicate the above conjecture is true for all sufficiently large n.

Theorem 57. The density of the anti-tau numbers is at least 3/π^{2}.

Proof. This follows immediately from Theorem 55 (d) and the fact that the square free numbers have density 6/π^{2}.

Theorem 58. For all sufficiently large n, T (n) < AT (n). In fact lim_{n→∞} T (n)/AT (n) = 0.

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.

Conjecture 56 is intuitive. In order for n to be not tau, all τ(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, τ(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.

Theorem 59. If a is an odd integer such that a, a + 1 are tau numbers then a = 1.

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) [5]. 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) [7]. The second solution fails to yield a tau number and so x = 1.

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.

5 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.

References

[1] Simon Colton, Refactorable numbers — a machine invention, Journal of Integer Se-

   quences 2, Article 99.1.2, http://www.math.uwaterloo.ca/JIS/colton/joisol.html.

[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1985.

[3] R. E. Kennedy and C. N. Cooper, Tau numbers, natural density, and Hardy and Wright’s Theorem 437, Internat. J. Math. Math. Sci. 13 (1990), 383–386.

[4] Paulo Ribenboim, Catalan’s Conjecture, Amer. Math. Monthly 103 (1996), 529–538.

[5] Shailesh A. Shirali, A family portrait of the primes — a case study in discrimination, Math. Mag. 70 (1997), 263–272 .

[6] P. Dusart, The kth prime is greater than k(ln k + ln ln k − 1) for k > 2, Math. Comp. 68 (1999), 411–415.

[7] Ray Steiner and Nikos Tzanakis, Simplifying the solution of Ljunggren’s equation x^{2}+1 = 2y^{4}, J. Number Theory 37 (1991) 123–132.

2000 Mathematics Subject Classification: Primary 11B05; Secondary 11A25. Keywords: tau number, number-of-divisors function (Concerned with sequence \underline{A033950}.) Received August 1, 2002; revised version received December 15, 2002. Published in Journal of Integer Sequences December 16, 2002. Corrections, February 17, 2003.

Return to Journal of Integer Sequences home page.