Problems with A000028/A000379.
David Wilson
davidwwilson at comcast.net
Thu Dec 20 07:03:29 CET 2007
I may have found the oldest error in the OEIS to date.
A000028 is defined as the sequence that begins with 2, with subsequent
elements being the next larger number that is not a product of two distinct
smaller elements. My computations indicate that the description, %STU
elements, and b-file elements of A000028 are correct.
A comment on A000028 claims that A = A000028 and B = A000379 represent the
only possible sequences such that A and B patition N and any n in N has an
equal number of representations as a product of distinct elements of A or of
B. For the duration of this message, I will call this the "amazing" property
of A and B.
A000028 is not clear about how many numbers are involved in the product
representations, although A000379 says that the products involve two
numbers. There seem to be four reasonable possibilities to investigate:
1. The products involve any number of distinct elements < n.
2. The products involve any number of distinct elements <= n.
3. The products involve pairs of distinct elements < n.
4. The products involve pairs of distinct elements <= n.
For any of these choices, we find that A and B are not amazing.
1. n = 6 has 1 representation as a product of elements of A (2*3) and 0
representations as a product of elements of B.
2. n = 1 has 0 representations as a product of elements of A and 1
representation as a product of elements of B (1). If you permit the empty
set with product 1, the numbers of representations remain unequal.
3. n = 6 has 1 representation as a product of elements of A (2*3) and 0
representations as a product of elements of B.
4. n = 60 has 1 representation as a product of elements of A (2*30) and 2
representations as a product of elements of B (1*60, 6*10).
So, under any reasonable interpretation of "product of distinct elements",
the A000028/A000379 comments are false.
---------------------------------------------
So now let us try constructing an amazing A and B. We will start with empty
A and B, then, for n = 1, 2, 3, ..., we will try adding n to B, checking if
A and B have the same number of products for n. If not, we will move n from
B to A, then check again. If the number of products is still not equal, the
algorithm fails, and an amazing A and B do not exist.
We run this algorithm for each of the four above interpretations of "product
of distinct elements". When we do so, we find:
1. The algorithm fails at n = 6.
2. The algorithm fails at n = 1.
3. The algorithm fails at n = 6.
4. The algorithm does not fail for n <= 10000.
So, if these amazing A and B exist, the definition of "amazing" involves
representations of n as a product of two distinct elements <= n.
We can show that once we have placed n = 1 in either A or B, the placement
of every n >= 2 is determined. This means that {A, B} is unique, there is
only one possible pair of amazing sequences.
For this amazing A and B, we find that A(29) = 60 whereas A000028(29) = 61.
This means that A000028 and A000379 are not the amazing A and B, and their
comments to that effect are false.
When we look for our amazing A and B in the OEIS, we find A064175 and
A064176. I cannot at this juncture prove that A064175 and A064176 are indeed
the amazing A and B, however, initial investigations seem promising. I would
not be surprised if the proof can be found in the reference mentioned on
both A000028 and A000379, to wit:
J. Lambek and L. Moser, On some two way classifications of integers,
Canad. Math. Bull. 2 (1959), 85-89.
I suspect that either this reference mistakenly suggested A000028 = A064175
(the two sequences share many initial terms), or mistakenly attributed the
amazing property to A000028, or maybe someone misinterpreted the reference.
At any rate:
- A000028 and A000379 do not have the "amazing" property described in their
comments. These comments should be removed, and possibly replaced with
pointers to A064175 and A064176.
- A131180 should be killed. It is a recent duplicate of A026416, and makes
reference to the discredited "amazing" property of A000028 and A000379.
- Tentatively, A064175 and A064176 do have the "amazing" property. The proof
may (or may not) lie in the above reference.
- We can either mention the amazing property on
I may have found the oldest error in the OEIS to date.
A000028 is defined as the sequence that begins with 2, with subsequent
elements being the next larger number that is not a product of two distinct
smaller elements. My computations indicate that the description, %STU
elements, and b-file elements of A000028 are correct.
A comment on A000028 claims that A = A000028 and B = A000379 represent the
only possible sequences such that A and B patition N and any n in N has an
equal number of representations as a product of distinct elements of A or of
B. For the purpose of this note, let's call A and B with this property
"amazing".
A000028 is not clear on how many numbers are involved in these products,
although A000379 says that the products involve two numbers. There seem to
be four reasonable possibilities to investigate:
1. The products involve any number of distinct elements < n.
2. The products involve any number of distinct elements <= n.
3. The products involve pairs of distinct elements < n.
4. The products involve pairs of distinct elements <= n.
For any of these choices, we find that A and B are not amazing.
1. n = 6 has 1 representation as a product of elements of A (2*3) and 0
representations as a product of elements of B.
2. n = 1 has 0 representations as a product of elements of A and 1
representation as a product of elements of B (1). If you permit the empty
product, the numbers of representations increase by 1 for both A and B, but
remain unequal.
3. n = 6 has 1 representation as a product of elements of A (2*3) and 0
representations as a product of elements of B.
4. n = 60 has 1 representation as a product of elements of A (2*30) and 2
representations as a product of elements of B (1*60, 6*10).
So, under any reasonable interpretation of "product of distinct elements",
the claim made by A000028 is false.
---------------------------------------------
So now let us try constructing an amazing A and B. We will start with empty
A and B, then, for n = 1, 2, 3, ..., we will try adding n to B, checking if
A and B have the same number of products for n. If not, we will move n from
B to A, then check again. If the number of products is still not equal, an
amazing A and B do not exist.
We have to attempt this procedure for each of the four interpretations of
"product of distinct elements". When we do so, we find:
1. The algorithm fails at n = 6.
2. The algorithm fails at n = 1.
3. The algorithm fails at n = 6.
4. The algorithm does not fail for n <= 10000.
So, the correct definition of amazing A and B is that A and B that partition
N and for any n in N the number of representations of n as a product of two
distinct elements of A that are <= n is the same as the number of
representations of n as a product of two distinct elements of B that are <=
n.
Under this definition, we can show that after we have placed n = 1 in B, we
have no choice as to where to place n >= 2. There is only one way to place
these elements that preserves the amazingness of A and B. This means that A
and B are indeed unique.
When we use the above algoithm to generate amazing A and B, we find that A
differs from A000028 at A(29) = 60 and A000028(29) = 61, and of course B
differs form A000379.
When we check the OEIS for our amazing A and B, we are led to A064175 and
A064176. I cannot at this juncture prove that A064175 and A064176 are the
amazing A and B, however, my investigations so far convince me of the truth
of the matter. It may be that this reference includes the proof:
J. Lambek and L. Moser, On some two way classifications of integers, Canad.
Math. Bull. 2 (1959), 85-89.
So, I recommend:
- A000028 and A000379 do not have the "amazing" property described in their
comments. These comments should be removed.
- A131180 should be killed. It is a recent duplicate of A026416, and makes
reference to the discredited "amazing" property of A000028 and A000379.
- It looks as if A064175 and A064176 do in fact have the "amazing" property.
The proof may lie in the above reference.
- Pending a proof, we can either mention the amazing property in
A064175/A064176, or else create new sequences (which will end up as
duplicates of A064175/A064176 if the proof is found).
I may have found the oldest error in the OEIS to date.
A000028 is defined as the sequence that begins with 2, with subsequent
elements being the next larger number that is not a product of two distinct
smaller elements. My computations indicate that the description, %STU
elements, and b-file elements of A000028 are correct.
A comment on A000028 claims that A = A000028 and B = A000379 represent the
only possible sequences such that A and B patition N and any n in N has an
equal number of representations as a product of distinct elements of A or of
B. For the purpose of this note, let's call A and B with this property
"amazing".
A000028 is not clear on how many numbers are involved in these products,
although A000379 says that the products involve two numbers. There seem to
be four reasonable possibilities to investigate:
1. The products involve any number of distinct elements < n.
2. The products involve any number of distinct elements <= n.
3. The products involve pairs of distinct elements < n.
4. The products involve pairs of distinct elements <= n.
For any of these choices, we find that A and B are not amazing.
1. n = 6 has 1 representation as a product of elements of A (2*3) and 0
representations as a product of elements of B.
2. n = 1 has 0 representations as a product of elements of A and 1
representation as a product of elements of B (1). If you permit the empty
product, the numbers of representations increase by 1 for both A and B, but
remain unequal.
3. n = 6 has 1 representation as a product of elements of A (2*3) and 0
representations as a product of elements of B.
4. n = 60 has 1 representation as a product of elements of A (2*30) and 2
representations as a product of elements of B (1*60, 6*10).
So, under any reasonable interpretation of "product of distinct elements",
the claim made by A000028 is false.
---------------------------------------------
So now let us try constructing an amazing A and B. We will start with empty
A and B, then, for n = 1, 2, 3, ..., we will try adding n to B, checking if
A and B have the same number of products for n. If not, we will move n from
B to A, then check again. If the number of products is still not equal, an
amazing A and B do not exist.
We have to attempt this procedure for each of the four interpretations of
"product of distinct elements". When we do so, we find:
1. The algorithm fails at n = 6.
2. The algorithm fails at n = 1.
3. The algorithm fails at n = 6.
4. The algorithm does not fail for n <= 10000.
So, the correct definition of amazing A and B is that A and B that partition
N and for any n in N the number of representations of n as a product of two
distinct elements of A that are <= n is the same as the number of
representations of n as a product of two distinct elements of B that are <=
n.
Under this definition, we can show that after we have placed n = 1 in B, we
have no choice as to where to place n >= 2. There is only one way to place
these elements that preserves the amazingness of A and B. This means that A
and B are indeed unique.
When we use the above algoithm to generate amazing A and B, we find that A
differs from A000028 at A(29) = 60 and A000028(29) = 61, and of course B
differs form A000379.
When we check the OEIS for our amazing A and B, we are led to A064175 and
A064176. I cannot at this juncture prove that A064175 and A064176 are the
amazing A and B, however, my investigations so far convince me of the truth
of the matter. It may be that this reference includes the proof:
J. Lambek and L. Moser, On some two way classifications of integers, Canad.
Math. Bull. 2 (1959), 85-89.
So, I recommend:
- A000028 and A000379 do not have the "amazing" property described in their
comments. These comments should be removed.
- A131180 should be killed. It is a recent duplicate of A026416, and makes
reference to the discredited "amazing" property of A000028 and A000379.
- It looks as if A064175 and A064176 do in fact have the "amazing" property.
The proof may exist in the above reference.
- Pending a proof, we can either mention the amazing property in
A064175/A064176, or else create new sequences for amazing A and B, which I
highly suspect will coincide with A064175/A064176, and will become
duplicates if the proof is found.
I said:
"Roberts says that there is also a splitting fore addition in place of
multiplication. Remarkably, those two sequences are not in OEIS. I will
add them soon."
There is a typo at the top of page 22. If it is corrected, we find that the
two sequences are the odious numbers and evil numbers A000069 and A0001969.
Tony
At 1:11 AM -0500 12/20/07, David Wilson wrote:
>I may have found the oldest error in the OEIS to date.
>
>A000028 is defined as the sequence that begins with 2, with subsequent
>elements being the next larger number that is not a product of two distinct
>smaller elements. My computations indicate that the description, %STU
>elements, and b-file elements of A000028 are correct.
>
>A comment on A000028 claims that A = A000028 and B = A000379 represent the
>only possible sequences such that A and B patition N and any n in N has an
>equal number of representations as a product of distinct elements of A or of
>B. For the duration of this message, I will call this the "amazing" property
>of A and B.
Although I do not have the Lambek/Moser paper, but I did read Roberts'
"Lure of the Integers", which discusses the results of the Lambek/Moser
paper. Roberts says that splitting the integers based on the infinitary
Moebius function leads the two sequences with the "amazing" property.
Hence, the comments in A000028/A000379 should really be in A064175/A064176.
Roberts says that there is also a splitting fore addition in place of
multiplication. Remarkably, those two sequences are not in OEIS. I will
add them soon.
Tony
More information about the SeqFan
mailing list