1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about Ulam numbers

  1. Jul 4, 2011 #1
    Good evening,

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

    1. The problem statement, all variables and given/known data
    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.

    Thank you in advance.
     
  2. jcsd
  3. Jul 5, 2011 #2

    LCKurtz

    User Avatar
    Science Advisor
    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.
     
  4. Jul 5, 2011 #3

    Borek

    User Avatar

    Staff: 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.
     
  5. Jul 5, 2011 #4

    Mentallic

    User Avatar
    Homework Helper

    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 [itex]u_n<u_{n+1}<u_{n-1}+u_n[/itex]
     
  6. Jul 5, 2011 #5
    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.
     
  7. Jul 5, 2011 #6
    Never heard of Ulam numbers before. Can anyone tell in what context are they useful?
     
  8. Jul 5, 2011 #7

    Borek

    User Avatar

    Staff: Mentor

    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.
     
  9. Jul 5, 2011 #8
    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.
     
  10. Jul 5, 2011 #9

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    After reflecting a bit on this, I agree with you.
     
  11. Dec 10, 2011 #10
    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.

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question about Ulam numbers
Loading...