Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.2

Abstract: The HR (or Hardy-Ramanujan) program invents and analyses definitions in areas of pure mathematics, including finite algebras, graph theory and number theory. While working in number theory, HR recently invented a new integer sequence, the refactorable numbers, which are defined and developed here. A discussion of how HR works, along with details of well known sequences reinvented by HR and other new sequences invented by HR is also given.

Contents

1. Introduction
2. Refactorable Numbers
• Membership Theorems
• Pairs and Triples of Refactorable Numbers
• Distribution
3. HR - Automatic Concept Formation
• HR Working in Number Theory
• Recent Developments
4. Other Sequences
• Re-invented Sequences
• New Sequences Invented by HR
5. Conclusions
6. Acknowledgements
7. References
8. Addenda, April 19, 1999

1. Introduction

The following sequence of integers has recently been accepted into the OnLine Encyclopedia of Integer Sequences, [9]:

• It has a simple definition: those integers n for which the number of divisors of n divides n.
• It was invented by a computer program.

This note gives some results about the refactorables, followed by a discussion of the HR program which invented them and a look at some of the other sequences HR has invented or reinvented.

2. Refactorable Numbers

Notation. Throughout, the number of divisors of an integer, n, is written τ(n), the sum of the divisors of n is written σ(n) and the number of integers less than and coprime to n is written φ(n).

Definition. An integer, n, is a refactorable number if and only if τ(n) divides n.

Lemma 1. (Theorem 273 from [4]) If the prime factorization of n is

Lemma 2. An odd integer k is refactorable if and only if 2k is refactorable.

Proof. Suppose k = p₁^m₁ ... p_k^m_k   By Lemma 1, if k is refactorable, (m₁ + 1) ... (m_k + 1) divides k. Therefore the number of divisors of 2k, namely 2(m₁ + 1)...(m_k + 1), divides 2k, and so 2k is refactorable. The converse follows by reversing the steps of the argument. QED.

Theorem 1. There are infinitely many odd refactorable numbers, and infinitely many even refactorable numbers.

Proof. From Lemma 1, if p is a prime, q = p^{p - 1} has p divisors, and so q is refactorable. The result now follows from Lemma 2. QED.

The set of integers of the form p^{p - 1} forms a subsequence of the refactorable numbers:

A more interesting way to prove Theorem 1 is to take the integers in numerical order, find their prime factorizations and apply the map:

It is easy to see that the integers produced from this map must all be refactorable numbers, as they have p₁^m₁ ... p_k^m_k divisors, and for any prime p and any integer m we have m <= p^m-1, so the number of divisors divides the integer itself. The result of the transformation on a even number is another even number, and the result on an odd number is another odd number. It follows that there are infinitely many even and odd refactorable numbers.

This mapping of the integers onto the refactorables produces another interesting sequence:

2.1 Membership Theorems

Since primes have two divisors, 2 is the only prime refactorable number.

Theorem 2. All odd refactorable numbers are squares.

Proof. Suppose n is as in Lemma 1, and is odd and refactorable. Since each m_i + 1 must divide n, each m_i is even, so n is a square. QED.

Theorem 2 makes it easy to search for odd refactorable numbers, which form this subsequence:

Theorem 3. No perfect number is refactorable.

Proof.
(a) Even perfect numbers. Using Theorem 277 from [4], we know that if k is an even perfect number, it has the form 2^n-1(2ⁿ-1), where 2ⁿ-1 is a prime, p, and using Theorem 18 from [4], we know that if 2ⁿ-1 is prime, then so is n. Using Lemma 1, we know that k = 2^n-1p must have ((n-1)+1)(1+1) = 2n divisors. If 2n divides k then either n = 2 or n = p (as n is a prime). If n = 2 then the perfect number is 6, which is not refactorable. If n = p then n = 2ⁿ-1, which is impossible for a prime n.
(b) Odd perfect numbers. No odd perfect numbers are known. If one were to exist, say q, with divisors d₁ < ... < d_k = q, then each d_i must be odd, and by definition, d₁+ ... + d_k-1 = q. The sum of an even number of odd integers is even, so, as q is odd, we know that k-1 must be odd, so q has an even number of divisors. Therefore q cannot be refactorable as it is odd and cannot be divisible by an even number. QED.

2.2 Pairs and Triples of Refactorable Numbers

Theorem 4. If (a-1, a, a+1) is a triple of refactorable numbers, then a must be of the form:

for some integer n.

Proof. As odd refactorable numbers are square, and as no two square numbers differ by 2, a must be odd and a square, say b². An instance of the Fermat-Euler theorem (Theorem 72 from [4]) states that b² = 1 (mod 4), so b² + 1 = 2 (mod 4). Therefore a + 1 is not divisible by 4 and so must have prime factorization a + 1 = 2 p₁^m₁ ... p_k^m_k, where the p_i's are distinct odd primes. This means that τ(a+1) = 2(m₁+1)...(m_k+1) and that each m_i+1 must be odd as a+1 is refactorable. So each m_i must be even and therefore a+1 is twice an odd square number. Therefore we can write a+1 = 2c², so b² + 1 = 2c². This means that (b,c) must be a solution of the Diophantine equation x² - 2y² = -1. Theorem 244 of [4] states that the positive integer solutions to this equation are given by

for integers n. Expanding the coefficient of x on the right-hand side, we get:

and so a is as in the statement of the theorem. QED.

These numbers quickly become large. For example, if we take n = 10, then a = 2982076586042449. By considering n <= 35, it is easy to show that there are no triples between 1 and 10⁵³, and it would not be difficult to take this number further.

Conjecture 1. There are no triples of refactorable numbers.

There are, however, pairs of refactorable numbers, although these are fairly rare. The only pairs of refactorable numbers between 1 and 1,000,000 are:

It is easy to see that if (a, a+1) is a pair of refactorable numbers, and a is even, then a is a multiple of four (from the Fermat-Euler theorem as in the proof of Theorem 4).

If two refactorables are relatively prime, their product is also refactorable. So the products of pairs of consecutive refactorables produces another (possibly finite) sequence of refactorables:

Conjecture 2. There are infinitely many pairs of refactorable numbers.

2.3 Distribution

We cannot yet give an accurate measure for the number of refactorables less than a given n, but we can say how many there are with a given number of divisors:

Theorem 5. The number of refactorable numbers with n divisors is:

• 1, if n = 1 or 4.
• k!, if n is the product of k distinct primes (ie. it is square-free:[A005117]).
• infinite, otherwise.

Proof. Clearly, 1 is the only refactorable number with one divisor. If an integer s has four divisors, then it must be of the form p³ or pq for distinct primes p, q. Taking the first case, if it is to be refactorable, then p = 2 and the refactorable number is 8. There are no refactorables of the form pq because 4 cannot divide the product of two distinct primes.
If n is the product of k distinct primes, n = p₁ ... p_k, then any integer s with n divisors must be of the form s = a₁^{p₁ - 1} ... a_k^{p_k - 1} for distinct primes a₁, ..., a_k. If it is to be refactorable, then n must divide s, so {a₁, ..., a_k} = {p₁, ..., p_k} and there are k! ways to choose the a_i's from the p_i's, hence k! possibilities for s.
Suppose now that n is not square-free, and n = p₁^m₁ ... p_k^m_k. Firstly, if k = 1, then n = p^m and m > 1 . Then for any prime q which is not p, the integer s = q^{p - 1}p^{pm - 1 - 1} has n divisors. Further, s is refactorable unless

and we have already dealt with the case where n = 4 . Secondly, if k > 1, with say m_i > 1, for any prime q not in {p₁, ..., p_k}, the integer

has n divisors. Now s is also refactorable unless, as above, p_i = m_i = 2. If there is an i > 2 for which m_i > 1, then choosing this i in the construction above works. This leaves only the case where n = 2² p₂ ... p_k. In this case, for any prime q not in {p₁, ..., p_k}, the integer

has 2p₂ 2p₃ ... p_k = n divisors, and is refactorable because p₂ > 2 implies p₂ - 1 >= 2. QED.

Theorem 5 tells us, for instance, that there are precisely two refactorable numbers with 6 divisors, namely 12 and 18, and precisely 6 refactorable numbers with 30 divisors, namely 2¹3²5⁴, 2¹3⁴5², 2²3¹5⁴, 2²3⁴5¹, 2⁴3¹5² and 2⁴3²5¹.

Also, for a given non-square-free integer n = p₁^m₁ ... p_k^m_k , if we can write:

for j > 0, and some t_i > 0, a_i > 1, then for any set of primes, {q₁, ..., q_j}, none of which are in {p₁, ..., p_k}, the number:

will have n divisors and be refactorable.

So, for instance, because 36 = 2² 3²,

36 = (2+1)(2+1)4 implies 36p³ has 36 divisors and is refactorable (for any prime p > 3).
36 = (2+1)(2+1)2*2 implies 36pq has 36 divisors and is refactorable (for any primes p, q > 3).
36 = (2+1)(2+2)3 implies 108p² has 36 divisors and is refactorable (for any prime p > 3).
36 = (2+2)(2+1)3 implies 72p² has 36 divisors and is refactorable (for any prime p > 3).
36 = (2+1)(2+4)2 implies 972p has 36 divisors and is refactorable (for any prime p > 3).
36 = (2+4)(2+1)2 implies 288p has 36 divisors and is refactorable (for any prime p > 3).

Note that the first such formula comes from the first non-square-free integer greater than 4, namely 8, and we find that 8p is refactorable with 8 divisors, for any prime p > 2.

To end the discussion on refactorable numbers, we give a table of the distribution of (i) refactorable numbers, (ii) odd refactorable numbers, (iii) even refactorable numbers, (iv) pairs of refactorable numbers, and we compare these with the distribution of the primes and pairs of primes.

We used UBASIC and GAP to compile this table. Based on this empirical evidence, it appears that the number of refactorables is always at least half the number of primes. Using the prime number theorem, (Theorem 6 of [4]), we can conjecture that the number of refactorables less than x is at least x/(2 log(x)).

3. HR - Automatic Concept Formation

The research of the author includes understanding and automating the processes at work when mathematicians invent new concepts, specifically in finite group theory. This has culminated in the HR system, named after Hardy and Ramanujan, to emphasize both a theory-driven and a data-driven approach to concept formation. HR starts with only the axioms of group theory and ends with definitions and models of concepts it has derived, such Abelian groups, cyclic groups, orders of elements and so on. It does this by:

1. Finding models of groups using the MACE model finder, [5].
2. Storing data from the group tables which details the core concepts in group theory, namely the group operation, the identity element and the inverses of elements.
3. Manipulating this data in one of eight ways to produce a new data-table from one (or two) old ones.
4. Assigning definitions to each new data-table using the information about how they were constructed.

Most of the concepts HR invents are calculations which can be made directly from the group table of a finite group. However, it also makes sequences of groups, for instance, the sequence formed by taking the subgroup generated by the center of the previous group (which produces sequences of length two only). The sequences produced were mostly disappointing. For this reason, we looked towards number theory to see if it was possible to find more interesting sequences using HR's limited set of production rules.

3.1 HR Working in Number Theory

In number theory, HR generated three initial tables for the integers up to 100:

• The set of triples [a, b, c] for which a = b * c.
• The set of triples [a, b, c] for which a = b + c.
• The set of pairs [a, b] for which b is a digit in the decimal expansion of a.

1. By taking the sequence of integers with a given property, e.g. the prime numbers.
2. By taking the output of some function on successive integers, e.g. the τ function.
3. By finding those integers which, for some function, output an integer larger than any output for a smaller integer, i.e. those integers which set a record, such as the highly composite numbers.

The first time HR was tried in number theory, it invented the refactorable numbers. When we first saw this sequence, we did not know how it was found, but it looked interesting - it had a mix of odd and even numbers, sufficiently many terms between one and a hundred, and no obvious pattern. Therefore we looked it up in the Online Encyclopedia, and were surprised to find that it was not listed. Only then did we look at the output from HR to see its definition (expecting an unintuitive, complicated explanation), and were then even more surprised that this sequence was missing from the Encyclopedia.

We must point out that HR did only the easy part - it invented the concept - we have done all the rest of the above work. However, HR does make conjectures about refactorables. For example, it made the following conjecture, which we thought was true until a very large counterexample was found:

Conjecture. Given a refactorable number n, let

Proof of [==>] Suppose n is refactorable, that f(n) does not divide n and that n is not a square. Then f(n) is equal to the number of divisors of n, and so must divide n, a contradiction.
Disproof of [<==] 36360900, 79388100 and 155600676 are the first three square refactorable number which are divisible by f(n).

Since HR only knew the factorizations of the integers up to 100, the conjecture was not implausible.

Note that there can be no odd refactorable numbers n for which f(n) divides n, because if n is odd and refactorable, it must be a square, and if so, f(n) is one less than the number of divisors of n, so, as n is refactorable, f(n) + 1 must divide n, and as n is odd, we cannot have both f(n) and f(n) + 1 dividing n, as one of these must be even.

We note that HR has in effect discovered the concept of square numbers, for which both τ(n) and τ(n)-1 divide n.

The odd or even square refactorable numbers are:

3.2 Recent Developments

3.2.1 Data Mining Using the Encyclopedia

Having down-loaded a copy of the Online Encyclopedia, we have enabled HR to check each sequence it makes against the database and flag those which it has reinvented. After tidying up the data, we were also able to write an add-on program enabling HR to perform some data mining with the encyclopedia. We are still implementing, experimenting and collating results, but it seems that it is certainly possible to find previously unknown results using data mining. For example, we asked HR to identify any sequences for which the refactorables are a subsequence. It first found [A009230], in which the nth term is lcm(n, d(n)), which was not too surprising since for every refactorable number r, lcm(r, τ(r)) = r.

Next, HR spotted that the refactorables are a subsequence of [A047466], the integers congruent to 0, 1, 2 or 4 (mod 8). This was an unknown result, which we subsequently proved:

Theorem 6. Refactorable numbers are congruent to 0, 1, 2 or 4 (mod 8).

Proof. Odd refactorables are squares, and therefore congruent to 1 modulo 8. If a refactorable number were congruent to 6 mod 8 then it would be of the form 2(4n+3), and by Lemma 2, 4n+3 would also be refactorable, a contradiction. QED.

This gives us another insight into triples of refactorables:

Corollary. If (a-1, a, a+1) is a triple of refactorable numbers, then a = b² for some odd number b and b² = 16c + 1 for some c.

Proof. By Theorem 6, odd refactorables are congruent to 1 (mod 8), hence a+1 = 8n + 2 = 2(4n + 1) for some n. Therefore, as a + 1 is refactorable and 4n + 1 is odd, we see by Lemma 2 that 4n + 1 is an odd refactorable number. Hence, by Theorem 6 again, 4n + 1 = 8c+1, so a + 1 = 2(8c+1) and we see that a = 16c+1. As a is an odd refactorable, by Theorem 2 we can write a = b² for some b, and a = b² = 16c+1. QED.

Another data mining investigation using the encyclopedia, this time to find super-sequences of the perfect numbers ["even" being understood here], showed that perfect numbers are a subsequence of [A009242], with nth term equal to lcm(n, σ(n)). Therefore HR had spotted that, for all (even) perfect numbers p, there is an n such that lcm(n, σ(n)) = p. In the same session, HR also spotted that the even perfect numbers are a subsequence of [A007517], in which the nth term is φ(n)(σ(n)-n). We have subsequently proved both of these results:

Theorem 7. For any even perfect number p, there is an integer a for which lcm(a, σ(a)) = p, and an integer b for which φ(b)(σ(b)-b) = p.

Proof. From Theorem 277 of [4], we note that p = 2^{n - 1} (2ⁿ-1) for some n, where 2ⁿ-1 is a prime. If we take a = 2^n-1 then

So HR has highlighted the following appealing parallel between the refactorable numbers and the even perfect numbers:

• Refactorable numbers are of the form lcm(a, τ(a)) for some a.
• Perfect numbers are of the form lcm(a, σ(a)) for some a.

• Refactorable numbers are those n for which lcm(n, τ(n)) = n,
• Perfect numbers are those n for which lcm(n, σ(n)) = 2n.

3.2.2 A Mathematical Cycle

• Invents definitions
• Spots conjectures involving those definitions
• Proves some of the conjectures using OTTER
• Finds counterexamples to some of the conjectures that OTTER fails to prove

[2] gives a more detailed description of the HR system, and the following web page is devoted to HR:

4. Other Sequences

4.1 Re-Invented Sequences

After a preliminary examination, we can claim that HR reinvented the following sequences:

1. Sequences resulting from factorization:
• the square numbers [A000290].
• the non-squares [A000037].
• the prime numbers [A000040].
• the squares of primes [A001248].
• the primes and squares of primes [A000430].
• 1 and the odd primes [A006005].
• 0 if prime, 1 otherwise [A005171].
• the composite numbers [A002808].
• the highly composite numbers [A002182].
• τ(n), the number of divisors of n [A000005].
• the number of proper divisors [A032741].
• integers with 4 [A030513], 5 [A030514], etc. divisors.
• integer square roots or zero [A037213].
• writing out the divisors [A027750].
• writing out the proper divisors [A027751].
• the squarefree integers. [A005117].
• the powers of 2 [A000079].
• integers with at most 2 prime factors [A037143].
• integers not divisible by 3 [A001651].
2. Sequences resulting from addition:
• the even numbers [A005843].
• the odd numbers [A005408].
• writing out the numbers less than n [A005408].
• 1 together with the even numbers [A004277].
• 2 together with the odd numbers [A004280].
• 2,4 and the odd numbers [A004281].
3. Sequences resulting from examination of digits:
• the repunits [A000042].
• integers with only 2's as digits [A002276].
• integers with a 1 [A011531], 2 [A011532], 3 [A011533], etc. as a digit.
• the repdigits [A010785].
• integers divisible by each non-zero digit [A002796].
• each digit is prime [A046034].
• the numbers with two distinct digits [A031955].
• the number of distinct digits in n [A043537].
• number with distinct digits [A010784].
• numbers divisible by every digit [A034838].
• no base 2 digit is a base 10 digit [A037344].
• the natural numbers in base 3 [A007089].

More interesting than the fact that HR reinvented these sequences are the ways in which HR defines them. For example, even numbers are defined as integers n for which there is a natural number m such that m + m = n. The natural numbers in base 3 were defined as integers in base 10 which have no digits which can be written as a + b where a > 0, b > 0 and a =/= b. Powers of two were defined as those integers with no odd divisors.

4.2 New Sequences Invented by HR

HR invented many other sequences which were not found in the encyclopedia. Most did not seem of any great interest. However, we deemed the following seven of sufficient interest to be submitted to the encyclopedia.

1. 1, 2, 14, 23, 29, 34, 46, 63, 68, 74, 76, 78, 88, 94, ... [A036433],
   the number of divisors is a digit in the decimal expansion of n. This sequence contains all primes with a 2 in them, and those primes starting with a 2, [A045708].

2. 1, 4, 9, 11, 14, 19, 41, 44, 49, 91, 94, 99, ... [A036435],
   those integers where all the digits are nonzero squares.

3. 0, 1, 0, 1, 1, 0, 2, 0, 1, 1, 0, 2, 1, 1, 1, 0, 0, ... [A036431],
   f(n) = |{a < n : a + τ(a) = n}|.

4. 1, 3, 6, 8, 11, 16, 17, 20, 22, 23, 27, 29, ... [A036434],
   integers which cannot be written as a + τ(a) for some a (i.e. those n for which f(n) = 0).

5. 1, 2, 7, 38, 122, 2766, 64686, ... [A036432],
   integers that set a record for f(n).

6. 1, 4, 6, 10, 12, 14, 22, 24, 26, 27, ... [A036438],
   integers which can be written as m * τ(m) for some m (which of course include twice the primes, [A001747]).

7. 1, 6, 8, 10, 14, 15, 22, 26, 27, ... [A036436],
   integers for which τ(n) is a square. This sequence contains the multiplicatively perfect numbers [A007422], n such that the product of the divisors of n equals n².

HR has also found some interesting finite sequences of integers. For example, HR invented those integers which have more distinct digits than any smaller number

1, 10, 102, 1023, 10234, 102345, 1023456, 10234567, 102345678, 1023456789 [A038378].

5. Conclusions

Also, we have shown that HR is capable of producing interesting concepts. Automated concept formation programs have some advantages over humans, in that they have no pride (are not ashamed to look at concepts with simple descriptions) and are very thorough. The use of computers with integer sequences has also been explored in [7], where the Seek-Whence program was used to identify definitions of integer sequences. Indeed, the Superseeker server for the Online Encyclopedia of Integer Sequences does a certain amount of concept formation in attempting to find a match between a given sequence and one in the database. A similar program to HR is Graffiti, [3], which makes conjectures in graph theory. Another program, [1], automatically invents theorems in plane geometry.

Machine discovery in mathematics and in science in general is a productive and interesting area which is gaining recognition and attention. HR and refactorable numbers were themselves recently mentioned in the popular press, [8], which reflects the interest that machine discovery is attracting. As more work is done in this area, we hope to make discovery programs as much a part of the mathematician's tool box as computer algebra packages.

6. Acknowledgements

7. References

[2] Bundy, A., Colton, S. and Walsh, T.: HR - Automated concept formation in finite algebras, in Proceedings of the Machine Discovery Workshop, ECAI 98, Brighton. Also Research Report RP920, Division of Informatics, University of Edinburgh.

[3] Fajtlowicz, S.: On conjectures of Graffiti: Discrete Mathematics, Vol. 72, pages 113-118, 1988. (See also Fajtlowicz, S.: On conjectures of Graffiti V. In Proceedings of the 7th International Quadrennial Conference on Graph Theory, Combinatorics and Applications, Vol. 1, pages 367-376, 1995.)

[4] Hardy, G. H. and Wright, E. M.: The Theory of Numbers, Oxford Univ. Press, 1965.

[5] McCune, W.: A Davis-Putnam program and its application to finite first order model search: Quasigroup existence problems. Technical Report ANL/MCS-TM-194, Argonne National Laboratory, 1994.

[6] McCune, W.: The Otter User's Guide. Technical Report ANL/90/9, Argonne National Laboratory, 1994.

[7] Meredith, M. J.: Seek-Whence: A Model of Pattern Perception, Ph.D. dissertation, Department of Computer Science, Indiana University, 1987.

[8] New Scientist, 5th Sept. 1998, p. 17, para. 3.

[9] Sloane, N. J. A.: The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org.

8. Addenda, April 19, 1999

In this paper we tried to make two points: (i) that the HR program we have implemented can invent new and interesting concepts in number theory and (ii) that one concept output by HR, namely the refactorable numbers, had many interesting properties. Because refactorables and associated sequences were missing from the Encyclopedia of Integer Sequences, [9], and after a preliminary search of the relevant literature, we concluded that the refactorable numbers were a genuinely new invention.

However, on 23rd March 1999, we received notification from Robert Kennedy and Curtis Cooper, of Central Missouri State University, that they had read the above paper and that the concept of refactorables had been defined already as `τ numbers' in a 1990 paper, [10], which proved that the natural density of the τ numbers is zero.

This news detracts from our original paper in only one way, namely that the title is inaccurate, refactorables were a machine re-invention. Indeed, the news that they have been developed so recently adds both to the point that HR can invent and re-invent concepts of interest and, of course, to the point that refactorables are interesting.

To add to the argument that HR produces interesting, novel concepts in number theory, we present the following very simple function defined by HR recently:

This has been added to the encyclopedia:

This was interesting because of its similarity to the τ function, [A000005]: (τ(n) = number of divisors of n). HR went on to define the integer sequence of numbers which set a record for f (ie. those integers, a, for which for all b, 0 < b < a, f(a) > f(b)):

It was easy to spot that these are all square numbers, but a little investigating revealed the following result:

Theorem 1. The nth integer setting the record for f as above is the square of the nth highly composite number [A002182] (the highly composite numbers have more divisors than any smaller integer).

To prove this, we need the following lemma:

Lemma 1. f(n) = τ(square root of the largest square dividing n). Note that the square root of the largest square dividing n, which we write as s(n), is integer sequence [A000188].

Proof of Lemma 1.
Writing n=p₁^k₁...p_m^k_m, the largest square dividing n is p₁^2[k₁/2]...p_m^2[k_m/2], the square root of which is: p₁^[k₁/2]...p_m^[k_m/2], where [z] denotes the integer part of fraction z. The pairs of integers dividing n are of the form:

and a|b if for all i, x_i =< k_i - x_i, ie. x_i =< k_i/2. Therefore, each x_i can be 0,1,2,...,[k_i/2], and:

using Theorem 273 from [4]. QED

Proof of Theorem 1.
Suppose that a sets a record for f. Therefore, f(a) > f(1), f(a) > f(2), ..., f(a) > f(a-1), and by lemma 1, this means that τ(s(a)) > τ(s(1)), τ(s(a)) > τ(s(2)), ..., τ(s(a)) > τ(s(a-1)). Suppose now that c² is the largest square less than or equal to a. Then we see that:

If a > c², the largest square dividing a will be less than c² and s(a) < c. But then, s(a) = c - k for some k, and τ(s(a)) = τ(c-k), which is a contradiction. Hence a = c², s(a) = c, and τ(c) > τ(c - i) for all i < c, which makes c a highly composite number, and a the square of a highly composite number.

Suppose now that b is a highly composite number, and a=b². Therefore, s(a) = b, and, as b is highly composite, if, for some k, τ(s(a-k)) > τ(s(a)), then s(a-k) > s(a) = b, which is impossible. Hence, for all k < a, τ(s(a)) > τ(s(a - k)), and by lemma 1, f(a) > f(a - k), thus a sets a record for f. QED

Coincidentally, the previous time there was a similar confusion over a machine invented concept, Douglas Lenat, who wrote the AM program, [11], thought for a while that what he called maximally divisible numbers were a machine invention. These turned out to be the highly composite numbers we've discussed here, which were originally developed by Ramanujan, [12].

This time, we will only claim that it is possible that the function f above was invented by HR, and that it is possible that, while the concept of the squares of highly composite numbers may have been looked at before, HR may have been the first to define them as setting the record for f. It was fortunate that τ numbers had not been added to the encyclopedia, because we may have decided not to develop them. However, the story of refactorable/τ numbers emphasises the need for databases of mathematical knowledge such as the Encyclopedia of Integer Sequences, [9], which can be used by people and computers alike to check the novelty of inventions.

Additional referencess

[10] Kennedy, R.E and Cooper, C.N.: Tau Numbers, Natural Density, and Hardy and Wright's Theorem 437, Internat. J. Math. Math. Sci. 13 (1990), no. 2, 383-386.

[11] Lenat, D.B.: An Artificial Intelligence Approach to Discovery in Mathematics, PhD thesis, Department of Computer Science, Stanford University.

[12] Ramanujan, S.: Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. 87.

(Concerned with sequences A000005, A000021, A000188 A033950, A036431, A036432, A036433, A036435, A036436, A036878, A036879, A036896, A036897, A036898, A036899, A036907, A038378, A038379, A046951, A046952, .)

Received Dec 15, 1998; revised version received Jan 12, 1999. Published in Journal of Integer Sequences Feb. 13, 1999. Addendum April 19, 1999.

Return to Journal of Integer Sequences home page