Are there infinitely many Ulam numbers?

[pc2-brazil]

Good evening,

I was self-studying Discrete Mathematics from a book and found the following problem:

Homework Statement

We define the Ulam numbers by setting u₁ = 1 and u₂ = 2. Furthermore, after determining whether the integers less than n are Ulam numbers, we set n equal to the next Ulam number if it can be written uniquely as the sum of two different Ulam numbers. Note that u₃ = 3, u₄ = 4, u₅ = 6, and u₆ = 8. Prove that there are infinitely many Ulam numbers.

2. The attempt at a solution

I imagine that I have to show that, if there are n Ulam numbers, for example, there is always an u_n+1. To show this, I have to show somehow that there will always be two numbers among these n numbers whose sum is unique and greater than u_n. If it were the case that u_n is the greatest Ulam number, it would mean that no sum between two of the numbers is unique and greater than u_n. I had no clue on how to continue, so I searched on the Internet and found the following proof method:

Assume that there are only finitely many Ulam numbers. Let the two largest Ulam numbers be u_n-1 and u_n. Then the integer u_n-1 + u_n is an Ulam number larger than u_n. It is the unique sum of two Ulam numbers, since it is the largest sum between two of the n Ulam numbers.

While trying to understand this proof, I found that there seems to be something wrong, because it is not always true that, for n Ulam numbers, u_n-1 + u_n will be an Ulam number. For example, consider the n Ulam numbers with n = 3: 1, 2, 3. The sum 3 + 2 = 5 is not an Ulam number, because 4 is an Ulam number and 4 + 1 = 5.

Thank you in advance.

 

[LCKurtz]

I never heard if Ulam numbers before this post, so I'm no expert. But I agree with your analysis that the argument posed is flawed, for what it's worth.

 

[Borek]

If u_n-1+u_n is not an Ulam number that means there was another Ulam number between u_n and u_n-1+u_n - which means u_n was not the largest Ulam number. That means if you think you know all, there is in fact at least one larger, so there are infinitely many.

Unless I am completely off.

 

[Mentallic]

If u_n-1+u_n is not an Ulam number that means there was another Ulam number between u_n and u_n-1+u_n

How do you know this? I can't see where one can derive that there must've been a Ulam number u_n+1 such that $u_n<u_{n+1}<u_{n-1}+u_n$

 

[daveb]

The proof works. If u_n and u_n-1 are the two greatest Ulam numbers, their sum is greater than the sum of any other two Ulam numbers. Therefore, no sum of two other Ulam numbers is equal to the sum of u_n and u_n-1. The concept behind this is that the set does not contain every integer, so even though the sum of two other integers might equal u_n plus u_n-1, at least one of those integers cannot be a Ulam number.

 

[Avijeet]

Never heard of Ulam numbers before. Can anyone tell in what context are they useful?

 

[Borek]

How do you know this? I can't see where one can derive that there must've been a Ulam number u_n+1 such that $u_n<u_{n+1}<u_{n-1}+u_n$

u_n-1+u_n is not an Ulam number only if there was another Ulam number between u_n-1+u_n and u_n - if there was no other Ulam number, u_n-1+u_n is larger than any other sum of Ulam numbers and as such is unique - so it is an Ulam number. If it is not unique, there was an Ulam number between u_n-1+u_n, as no other sum of Ulam numbers can be as large as u_n-1+u_n is.

 

[awkward]

The original proof is correct as it stands:

"Assume that there are only finitely many Ulam numbers. Let the two largest Ulam numbers be un-1 and un. Then the integer un-1 + un is an Ulam number larger than un. It is the unique sum of two Ulam numbers, since it is the largest sum between two of the n Ulam numbers."

We start by assuming that there are only finitely many Ulam numbers and arrive at a contradiction; therefore the assumption is false. You don't need to add anything more.

It is incorrect to conclude, however, that the sum of two successive Ulam numbers is an Ulam number; that doesn't follow. It's only true under the assumption that there are only finitely many Ulam numbers, which we know to be false.

A similar situation arises in the proof (Euclid's, I think) that there are infinitely many primes. Assume the contrary, i.e, there are only finitely many primes. Take their product and add 1. The result can't be divisible by any prime and so must be a larger prime than any in the list of primes, contradicting the assumption. This proves there are infinitely many primes. It is wrong to conclude, however, that the product of the first n primes, plus 1, is always a prime. I leave it to the reader to find a counterexample.

 

[LCKurtz]

The original proof is correct as it stands:

"Assume that there are only finitely many Ulam numbers. Let the two largest Ulam numbers be un-1 and un. Then the integer un-1 + un is an Ulam number larger than un. It is the unique sum of two Ulam numbers, since it is the largest sum between two of the n Ulam numbers."

We start by assuming that there are only finitely many Ulam numbers and arrive at a contradiction; therefore the assumption is false. You don't need to add anything more.

After reflecting a bit on this, I agree with you.

 

[pc2-brazil]

We start by assuming that there are only finitely many Ulam numbers and arrive at a contradiction; therefore the assumption is false. You don't need to add anything more.

It is incorrect to conclude, however, that the sum of two successive Ulam numbers is an Ulam number; that doesn't follow. It's only true under the assumption that there are only finitely many Ulam numbers, which we know to be false.

I'm not sure why it's only true under the assumption that there are only finitely many Ulam numbers. For example, if the list is "1, 2, 3", then the sum of the largest Ulam numbers (2 + 3 = 5) is not an Ulam number, because 3 + 1 = 4 is smaller.
So, I don't see how the uniqueness of the sum of the two largest Ulam numbers in the list means that there must have been a Ulam number between u_n-1+u_n and u_n.

A similar situation arises in the proof (Euclid's, I think) that there are infinitely many primes. Assume the contrary, i.e, there are only finitely many primes. Take their product and add 1. The result can't be divisible by any prime and so must be a larger prime than any in the list of primes, contradicting the assumption. This proves there are infinitely many primes. It is wrong to conclude, however, that the product of the first n primes, plus 1, is always a prime. I leave it to the reader to find a counterexample.

The problem is that, in Euclid's proof, there is the fact any integer greater than 1 must be a product of primes (or powers of primes). Then, the sum of all primes in the list plus 1 must be a product of primes. So, if it is not a prime, it can be assured that it must have in its composition prime numbers that are not in the original list. This assures that there is some non-specified prime greater than the ones on the list.
In the case of Ulam numbers, if u_n + u_n-1 is not a prime number, how can I assure that there is still an Ulam number that is greater than u_n?