Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.2 |
The following sequence of integers has recently been accepted into the
OnLine
Encyclopedia of Integer Sequences, [9]:
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.
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_{1}^{m1} ... p_{k}^{mk}
By Lemma 1, if k is
refactorable, (m_{1} + 1) ... (m_{k} + 1) divides k.
Therefore the number of divisors of
2k, namely 2(m_{1} + 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_{1}^{m1} ... p_{k}^{mk} 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:
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^{n}-1),
where 2^{n}-1
is a prime, p, and using Theorem 18 from [4],
we know that if 2^{n}-1 is prime, then so is n.
Using Lemma 1, we know that k = 2^{n-1}p 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^{n}-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_{1} < ... < d_{k} = q, then each
d_{i} must be odd, and by definition, d_{1}+
... + 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.
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^{2}. An instance of the Fermat-Euler theorem (Theorem 72 from [4]) states that b^{2} = 1 (mod 4), so b^{2} + 1 = 2 (mod 4). Therefore a + 1 is not divisible by 4 and so must have prime factorization a + 1 = 2 p_{1}^{m1} ... p_{k}^{mk}, where the p_{i}'s are distinct odd primes. This means that τ(a+1) = 2(m_{1}+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^{2}, so b^{2} + 1 = 2c^{2}. This means that (b,c) must be a solution of the Diophantine equation x^{2} - 2y^{2} = -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^{53}, 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.
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:
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^{3} 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_{1} ... p_{k},
then any integer s with
n divisors must be of the form
s = a_{1}^{p1 - 1} ...
a_{k}^{pk - 1}
for distinct primes a_{1}, ..., a_{k}. If it is
to be refactorable, then n must divide s, so
{a_{1}, ..., a_{k}} = {p_{1},
..., 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_{1}^{m1} ...
p_{k}^{mk}.
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_{1}, ..., 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^{2} p_{2} ... p_{k}. In this case, for any prime q not in {p_{1}, ..., p_{k}}, the integer
has 2p_{2} 2p_{3} ... p_{k} = n divisors, and is refactorable because p_{2} > 2 implies p_{2} - 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^{1}3^{2}5^{4}, 2^{1}3^{4}5^{2}, 2^{2}3^{1}5^{4}, 2^{2}3^{4}5^{1}, 2^{4}3^{1}5^{2} and 2^{4}3^{2}5^{1}.
Also, for a given non-square-free integer n = p_{1}^{m1} ... p_{k}^{mk} , if we can write:
for j > 0, and some t_{i} > 0, a_{i} > 1, then for any set of primes, {q_{1}, ..., q_{j}}, none of which are in {p_{1}, ..., p_{k}}, the number:
will have n divisors and be refactorable.
So, for instance, because 36 = 2^{2} 3^{2},
36 = (2+1)(2+1)4 implies 36p^{3} 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^{2} has 36 divisors and is
refactorable (for any prime p > 3).
36 = (2+2)(2+1)3 implies 72p^{2} 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.
n at most | primes | refactorables | odd refactorables | even refactorables | prime pairs | refactorable pairs |
10 | 4 | 4 | 2 | 2 | 2 | 2 |
10^{2} | 25 | 16 | 2 | 14 | 8 | 2 |
10^{3} | 168 | 92 | 5 | 87 | 35 | 2 |
10^{4} | 1229 | 665 | 15 | 650 | 205 | 3 |
10^{5} | 9592 | 5257 | 34 | 5223 | 1224 | 5 |
10^{6} | 78498 | 44705 | 87 | 44618 | 8169 | 13 |
10^{7} | 664579 | 394240 | 237 | 394003 | 58980 | 27 |
10^{8} | 5761455 | ? | 650 | ? | 440312 | 75 |
10^{9} | 50847534 | ? | 1813 | ? | 3424506 | 187 |
10^{10} | 455052511 | ? | 5152 | ? | 27412679 | 468 |
10^{11} | 4118054813 | ? | 14889 | ? | 224376048 | 1219 |
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)).
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:
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.
In number theory, HR generated three initial tables for the integers up to 100:
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:
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^{2} for some odd number b and b^{2} = 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^{2} for some b, and a = b^{2} = 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^{n}-1) for some n, where 2^{n}-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:
[2] gives a more detailed description of the HR system, and the following web page is devoted to HR:
After a preliminary examination, we can claim that HR reinvented the following sequences:
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.
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.
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].
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.
[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.
[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.
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_{1}^{k1}...p_{m}^{km},
the largest square dividing n is
p_{1}^{2[k1/2]}...p_{m}^{2[km/2]},
the square root of which is:
p_{1}^{[k1/2]}...p_{m}^{[km/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^{2} is the largest
square less than or equal to a. Then we see that:
If a > c^{2}, the largest square dividing a will be less than c^{2} 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^{2}, 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^{2}. 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.
[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.
(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