To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

How to transfigure the Wikipedia

Would you like Wikipedia to always look as professional and up-to-date? We have created a browser extension. It will enhance any encyclopedic page you visit with the magic of the WIKI 2 technology.

Try it — you can delete it anytime.

Install in 5 seconds
4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
Great Wikipedia has got greater.
.
Leo
Newton
Brights
Milds

Ulam number

From Wikipedia, the free encyclopedia

In mathematics, the Ulam numbers comprise an integer sequence devised by and named after Stanislaw Ulam, who introduced it in 1964.[1] The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.

YouTube Encyclopedic

  • 1/5
    Views:
    1 368 153
    458 843
    390 400
    10 680
    3 631
  • Prime Spirals - Numberphile
  • 41 and more Ulam's Spiral - Numberphile
  • Business Math - Finance Math (1 of 30) Simple Interest
  • Polygonal Numbers - Introduction and method to find next polygonal number
  • Ulam's Spiral in J

Transcription

JAMES GRIME: One of the reasons we're fascinated by primes is that they are quite weird in the way they behave. On one hand, they kind of feel random. They are turning up all over the place. Sometimes you have these long gaps between primes. And then suddenly-- like buses, you get a couple of primes turn up at once. On the other hand, there are things that we can predict about primes and when they're going to turn up, which is slightly unexpected that you can do that. They're not completely random. One of the first things I want to show you, then, is a nice easy thing. So everyone can do this at home. We're going to write the numbers in a square spiral. Start with 1 in the middle. Then you write 2. But you go around it-- 4, 5, 6, 7, 8-- do you see the pattern, then? It's a square spiral. 12, 13, 14, 15-- it's called an Ulam spiral-- Stanislaw Ulam, he was a Polish mathematician. And he left Poland just before World War II, and he went to America. And he worked on the Manhattan Project. After World War II, he went into academia. The story of this spiral is, he sat in a very boring lecture in academia. It was in 1963. And so he's obviously a fan of Vi Hart or someone. He sat there doodling during this boring lecture. And he's writing out the numbers. Let's see, 30, 31, 32. The next thing he did was start to circle the prime numbers. So let's do that. 2 is a prime, and then 3, and then 5, and 7, and 11, 13, not 40, 41, 43, is prime, and so on. And he noticed, and maybe you can see, these stripes, the prime numbers seem to be lining up on diagonal lines. And if you do this larger, if you do more and more numbers, and you write them out in a spiral, that tends to be the case. I've got one here. This is a big Ulam spiral. I think this is something huge. I think this is like 200 by 200. And so there's 40,000 numbers or something here. Can you see, though, can you see the stripes? There's definitely some stripes here, these diagonal lines. So prime numbers seem to be lying on diagonal lines. Or to put it another way, some diagonal lines have lots of primes, and some diagonal lines don't have lots of primes. So you can see the stripes start to form. BRADY HARAN: Are they continuous stripes? They look a bit broken up to me. JAMES GRIME: Yeah, they are not continuous stripes. But they have more than average number of primes. So these stripes might be a good place to look for more primes, bigger primes, new primes. One thing people might say is, oh, we're just seeing patterns in randomness. Those aren't really stripes at all. It's just the human brain. See, if you compare it with randomness-- this, the same size, these are random numbers. And you can see, it's pretty much white noise. I can't really see any pattern in this. You can see that that is random. And you can see that that is something more than just being random. BRADY HARAN: These ginormous primes that get found, are they found on diagonals? Like this largest prime known, was that on diagonal? JAMES GRIME: The largest prime known was a Mersenne prime, which is of the type 2 to the power n minus 1. It's one less than a power of 2, which is a way to look for large primes. It's computationally kind of easier to do. Perhaps it's not the most fruitful way because they are quite rare, Mersenne primes. This might be another way to do it because this stripe here, this diagonal, has an equation. This equation is for this one here, this half line, which means it starts at three and goes off to infinity. The equation for that is 4x squared minus 2x plus 1. Let me just try it. Let's do the first one here. So if x is equal to 1, yeah, that's 3. If we tried the next one here, x equals 2, it's 13. And this one here, that's 31. And well, best do one more, just to show you what comes next, 56 plus 57-- is that a prime number, Brady? BRADY HARAN: 57 is not a prime number. JAMES GRIME: It's not a prime number. So the next one isn't a prime number, but 57 would be the next number on that line. BRADY HARAN: So that's one of the breaks in our dotted line? JAMES GRIME: Yeah, so all these lines, the, in fact, horizontal lines, vertical lines, and diagonal lines, they are all like this. All the quadratic equations are like that. So what we're saying is, some quadratic equations have more primes on them than others. And that's the conjecture, actually. That hasn't been proved. But that is the conjecture. It seems to be the case. So there are lines here that have seven times as many primes as other lines. And the best we've found is a diagonal line that has 12 times as many primes as the average. BRADY HARAN: Cool, has that line got a name? JAMES GRIME: I can write it out for you. I think I had it somewhere. BRADY HARAN: Yeah, I'd love to know what that line is. The golden line. JAMES GRIME: This golden line that Brady has now decided to call it, it's a quadratic equation. It starts off quite simply again. But the number you add on is not plus one. It's plus something huge. This square spiral is called Ulam's spiral. But there's one that I like even more. It's called a Sack's spiral. And it works like this. You write the square number in a line. The square numbers are 1, 4, yeah, that is 2 squared, 3 squared is 9, 16, 25, and so on. So you write the square numbers in a line. Then I connect them with what is called an Archimedean spiral like that. And then I would the other numbers on that spiral and evenly space it. So it goes 1, 2, 3, 4, 5, 6, 7, 8, 9. And if you mark off the primes for that, I've got this already sorted out for you, this is the picture you get. And you can see the relations, you can see the pattern, even more strikingly, I think. Look at these curves. These are the primes. BRADY HARAN: And obviously, you'll never get a prime along there because those are the squares. JAMES GRIME: Those are your squares, that big gap there is the squares. So it looks like we have formulas, equations-- some formulas, anyway, that have more primes than others. So if we can understand these formulas that contain these rich number of primes, then it would help us solve important conjectures in mathematics such as the Goldbach conjecture and the twin prime conjecture. So prime numbers are not as random as you might think of. There are equations to help us find prime numbers. And now I want to show you some equations that help you find prime numbers. BRADY HARAN: So we'll have more about ways to search for prime numbers coming really soon from this interview with James Grime-- unless you're watching this in the future, in which case this stuff might already be on YouTube. But you get the idea. But, I have a bit of a confession to make. I've actually recorded some stuff about the spirals and prime numbers before-- not with James Grime, but with James Clewett. And I kind of half forgot about it and never got around to editing it. This was, like, a year and a half ago. I went back and had a look, and it was actually really interesting. So I've turned that into a video as well. Now you can wait for that turn up in your subscriptions, in the next few days, or if you can't wait, you can go and have a look at it now. I've made the links available. The video's already up, so go ahead and have a look. Thanks for watching. Plenty more videos, both of stuff I've recorded, some of it quite a while ago, it turns out, and stuff we've still got to record. Really exciting stuff coming soon on "Numberphile," so make sure you've subscribed.

Examples

As a consequence of the definition, 3 is an Ulam number (1 + 2); and 4 is an Ulam number (1 + 3). (Here 2 + 2 is not a second representation of 4, because the previous terms must be distinct.) The integer 5 is not an Ulam number, because 5 = 1 + 4 = 2 + 3. The first few terms are

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, ... (sequence A002858 in the OEIS).

There are infinitely many Ulam numbers. For, after the first n numbers in the sequence have already been determined, it is always possible to extend the sequence by one more element: Un−1 + Un is uniquely represented as a sum of two of the first n numbers, and there may be other smaller numbers that are also uniquely represented in this way, so the next element can be chosen as the smallest of these uniquely representable numbers.[2]

Ulam is said to have conjectured that the numbers have zero density,[3] but they seem to have a density of approximately 0.07398.[4]

Properties

Apart from 1 + 2 = 3 any subsequent Ulam number cannot be the sum of its two prior consecutive Ulam numbers.

Proof: Assume that for n > 2, Un−1 + Un = Un+1 is the required sum in only one way; then so does Un−2 + Un produce a sum in only one way, and it falls between Un and Un+1. This contradicts the condition that Un+1 is the next smallest Ulam number.[5]

For n > 2, any three consecutive Ulam numbers (Un−1, Un, Un+1) as integer sides will form a triangle.[6]

Proof: The previous property states that for n > 2, Un−2 + Un ≥ Un + 1. Consequently Un−1 + Un > Un+1 and because Un−1 < Un < Un+1 the triangle inequality is satisfied.

The sequence of Ulam numbers forms a complete sequence.

Proof: By definition Un = Uj + Uk where j < k < n and is the smallest integer that is the sum of two distinct smaller Ulam numbers in exactly one way. This means that for all Un with n > 3, the greatest value that Uj can have is Un−3 and the greatest value that Uk can have is Un−1.[5][7]
Hence Un ≤ Un−1 + Un−3 < 2Un−1 and U1 = 1, U2 = 2, U3 = 3. This is a sufficient condition for Ulam numbers to be a complete sequence.

For every integer n > 1 there is always at least one Ulam number Uj such that n ≤ Uj < 2n.

Proof: It has been proved that there are infinitely many Ulam numbers and they start at 1. Therefore for every integer n > 1 it is possible to find j such that Uj−1 ≤ n ≤ Uj. From the proof above for n > 3, Uj ≤ Uj−1 + Uj−3 < 2Uj−1. Therefore n ≤ Uj < 2Uj−1 ≤ 2n. Also for n = 2 and 3 the property is true by calculation.

In any sequence of 5 consecutive positive integers {i, i + 1,..., i + 4}, i > 4 there can be a maximum of 2 Ulam numbers.[7]

Proof: Assume that the sequence {i, i + 1,..., i + 4} has its first value i = Uj an Ulam number then it is possible that i + 1 is the next Ulam number Uj+1. Now consider i + 2, this cannot be the next Ulam number Uj+2 because it is not a unique sum of two previous terms. i + 2 = Uj+1 + U1 = Uj + U2. A similar argument exists for i + 3 and i + 4.

Inequalities

Ulam numbers are pseudo-random and too irregular to have tight bounds. Nevertheless from the properties above, namely, at worst the next Ulam number Un+1 ≤ Un + Un−2 and in any five consecutive positive integers at most two can be Ulam numbers, it can be stated that

5/2n−7 ≤ Un ≤ Nn+1 for n > 0,[7]

where Nn are the numbers in Narayana’s cows sequence: 1,1,1,2,3,4,6,9,13,19,... with the recurrence relation Nn = Nn−1 +Nn−3 that starts at N0.

Hidden structure

It has been observed[8] that the first 10 million Ulam numbers satisfy except for the four elements (this has now been verified for the first Ulam numbers). Inequalities of this type are usually true for sequences exhibiting some form of periodicity but the Ulam sequence does not seem to be periodic and the phenomenon is not understood. It can be exploited to do a fast computation of the Ulam sequence (see External links).

Generalizations

The idea can be generalized as (u, v)-Ulam numbers by selecting different starting values (u, v). A sequence of (u, v)-Ulam numbers is regular if the sequence of differences between consecutive numbers in the sequence is eventually periodic. When v is an odd number greater than three, the (2, v)-Ulam numbers are regular. When v is congruent to 1 (mod 4) and at least five, the (4, v)-Ulam numbers are again regular. However, the Ulam numbers themselves do not appear to be regular.[9]

A sequence of numbers is said to be s-additive if each number in the sequence, after the initial 2s terms of the sequence, has exactly s representations as a sum of two previous numbers. Thus, the Ulam numbers and the (u, v)-Ulam numbers are 1-additive sequences.[10]

If a sequence is formed by appending the largest number with a unique representation as a sum of two earlier numbers, instead of appending the smallest uniquely representable number, then the resulting sequence is the sequence of Fibonacci numbers.[11]

Notes

  1. ^ Ulam (1964a, 1964b).
  2. ^ Recaman (1973) gives a similar argument, phrased as a proof by contradiction. He states that, if there were finitely many Ulam numbers, then the sum of the last two would also be an Ulam number – a contradiction. However, although the sum of the last two numbers would in this case have a unique representation as a sum of two Ulam numbers, it would not necessarily be the smallest number with a unique representation.
  3. ^ The statement that Ulam made this conjecture is in OEIS OEIS: A002858, but Ulam does not address the density of this sequence in Ulam (1964a), and in Ulam (1964b) he poses the question of determining its density without conjecturing a value for it. Recaman (1973) repeats the question from Ulam (1964b) of the density of this sequence, again without conjecturing a value for it.
  4. ^ OEIS OEIS: A002858
  5. ^ a b Recaman (1973)
  6. ^ OEIS OEIS: A330909
  7. ^ a b c Philip Gibbs and Judson McCranie (2017). "The Ulam Numbers up to One Trillion". p. 1(Introduction).
  8. ^ Steinerberger (2015)
  9. ^ Queneau (1972) first observed the regularity of the sequences for u = 2 and v = 7 and v = 9. Finch (1992) conjectured the extension of this result to all odd v greater than three, and this conjecture was proven by Schmerl & Spiegel (1994). The regularity of the (4, v)-Ulam numbers was proven by Cassaigne & Finch (1995).
  10. ^ Queneau (1972).
  11. ^ Finch (1992).

References


External links

This page was last edited on 31 December 2023, at 10:03
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.
Contact WIKI 2
Introduction
Terms of Service
Privacy Policy