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 u1 = 1 and u2 = 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 u3 = 3, u4 = 4, u5 = 6, and u6 = 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 un+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 un. If it were the case that un is the greatest Ulam number, it would mean that no sum between two of the numbers is unique and greater than un. 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 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.

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, un-1 + un 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.

LCKurtz
Homework Helper
Gold Member
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
Mentor
If un-1+un is not an Ulam number that means there was another Ulam number between un and un-1+un - which means un 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
Homework Helper
If un-1+un is not an Ulam number that means there was another Ulam number between un and un-1+un

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

The proof works. If un and un-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 un and un-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 un plus un-1, at least one of those integers cannot be a Ulam number.

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

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

un-1+un is not an Ulam number only if there was another Ulam number between un-1+un and un - if there was no other Ulam number, un-1+un 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 un-1+un, as no other sum of Ulam numbers can be as large as un-1+un is.

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
Homework Helper
Gold Member
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.

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 un-1+un and un.

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 un + un-1 is not a prime number, how can I assure that there is still an Ulam number that is greater than un?