View source for Ulam number

{{short description|Mathematical sequence}} 
In [[Mathematics|mathematics]], the '''Ulam numbers''' comprise an [[Integer sequence|integer sequence]] devised by and named after [[Biography:Stanislaw Ulam|Stanislaw Ulam]], who introduced it in 1964.<ref>{{harvs|last=Ulam|year=1964a|year2=1964b|txt|}}.</ref>  The standard Ulam sequence (the (1,&nbsp;2)-Ulam  sequence) starts with ''U''<sub>1</sub>&nbsp;=&nbsp;1 and ''U''<sub>2</sub>&nbsp;=&nbsp;2.  Then for ''n''&nbsp;>&nbsp;2, ''U''<sub>''n''</sub> is defined to be the smallest [[Integer|integer]] that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.

==Examples==
As a consequence of the definition, 3 is an Ulam number (1&nbsp;+&nbsp;2); and 4 is an Ulam number (1&nbsp;+&nbsp;3). (Here 2&nbsp;+&nbsp;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&nbsp;=&nbsp;1&nbsp;+&nbsp;4&nbsp;=&nbsp;2&nbsp;+&nbsp;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, ... {{OEIS|id=A002858}}.

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: {{nowrap|''U''<sub>''n''−1</sub> + ''U''<sub>''n''</sub>}} 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.<ref>{{harvtxt|Recaman|1973}} gives a similar argument, phrased as a [[Proof by contradiction|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 &ndash; 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.</ref>

Ulam is said to have [[Conjecture|conjecture]]d that the numbers have zero [[Natural density|density]],<ref>The statement that Ulam made this conjecture is in OEIS {{OEIS2C|id=A002858}}, but Ulam does not address the density of this sequence in {{harvtxt|Ulam|1964a}}, and in {{harvtxt|Ulam|1964b}} he poses the question of determining its density without conjecturing a value for it. {{harvtxt|Recaman|1973}} repeats the question from {{harvtxt|Ulam|1964b}} of the density of this sequence, again without conjecturing a value for it.</ref> but they seem to have a density of approximately 0.07398.<ref>OEIS {{OEIS2C|id=A002858}}</ref>

==Properties==
Apart from 1&thinsp;+ 2 = 3 any subsequent Ulam number cannot be the sum of its two prior consecutive Ulam numbers.
:Proof: Assume that for ''n'' > 2, ''U''<sub>''n''−1</sub> + ''U''<sub>''n''</sub> = ''U''<sub>''n''+1</sub> is the required sum in only one way; then so does ''U''<sub>''n''&minus;2</sub> + ''U''<sub>''n''</sub> produce a sum in only one way, and it falls between ''U''<sub>''n''</sub> and ''U''<sub>''n''+1</sub>. This contradicts the condition that ''U''<sub>''n''+1</sub> is the next smallest Ulam number.<ref name="Recaman">{{harvtxt|Recaman|1973}}</ref>

For ''n'' > 2, any three consecutive Ulam numbers (''U''<sub>''n''−1</sub>, ''U''<sub>''n''</sub>, ''U''<sub>''n''+1</sub>)  as integer sides will form a triangle.<ref>OEIS {{OEIS2C|id=A330909}}</ref>

:Proof: The previous property states that for ''n'' > 2, ''U''<sub>''n''−2</sub> + ''U''<sub>''n''</sub> &ge; ''U''<sub>''n'' + 1</sub>. Consequently ''U''<sub>''n''&minus;1</sub> + ''U''<sub>''n''</sub> > ''U''<sub>''n''+1</sub> and because ''U''<sub>''n''−1</sub> < ''U''<sub>''n''</sub> < ''U''<sub>''n''+1</sub> the [[Triangle inequality|triangle inequality]] is satisfied.

The sequence of Ulam numbers forms a [[Complete sequence|complete sequence]].
:Proof: By definition ''U''<sub>''n''</sub> = ''U''<sub>''j''</sub> + ''U''<sub>''k''</sub> 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 ''U''<sub>''n''</sub>&nbsp;with ''n'' > 3, the greatest value that ''U''<sub>''j''</sub> can have is ''U''<sub>''n''−3</sub> and the greatest value that ''U''<sub>''k''</sub> can have is ''U''<sub>''n''−1</sub>.<ref name="Recaman"/><ref name="Gibbs">{{cite web|url=https://www.researchgate.net/publication/320980165|title=The Ulam Numbers up to One Trillion|author=Philip Gibbs and Judson McCranie|year=2017|page=1(Introduction)}}</ref>
:Hence ''U''<sub>''n''</sub> &le; ''U''<sub>''n''−1</sub> + ''U''<sub>''n''−3</sub> < 2''U''<sub>''n''−1</sub>  and ''U''<sub>''1''</sub> = 1, ''U''<sub>''2''</sub> = 2, ''U''<sub>''3''</sub> = 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 ''U''<sub>''j''</sub> such that ''n'' &le; ''U''<sub>''j''</sub> < 2''n''.
: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 ''U''<sub>''j''−1</sub> &le; ''n'' &le; ''U''<sub>''j''</sub>. From the proof above for ''n'' > 3, ''U''<sub>''j''</sub>&nbsp;&le;&nbsp;''U''<sub>''j''−1</sub>&nbsp;+&nbsp;''U''<sub>''j''−3</sub>&nbsp;<&nbsp;2''U''<sub>''j''−1</sub>. Therefore ''n''&nbsp;&le;&nbsp;''U''<sub>''j''</sub>&nbsp;<&nbsp;''2U''<sub>''j''−1</sub>&nbsp;&le;&nbsp;2''n''. Also for ''n'' = 2 and 3 the property is true by calculation.

In any sequence of 5 consecutive positive integers {''i'', ''i'' +&thinsp;1,..., ''i'' + 4}, ''i'' > 4 there can be a maximum of 2 Ulam numbers.<ref name="Gibbs"/>
:Proof: Assume that the sequence {''i'', ''i'' +&thinsp;1,..., ''i'' + 4} has its first value ''i'' = ''U''<sub>''j''</sub> an Ulam number then it is possible that ''i'' +&thinsp;1 is the next Ulam number ''U''<sub>''j''+1</sub>. Now consider ''i'' + 2, this cannot be the next Ulam number ''U''<sub>''j''+2</sub> because it is not a unique sum of two previous terms. ''i'' + 2 = ''U''<sub>''j''+1</sub> + ''U''<sub>1</sub> = ''U''<sub>''j''</sub> + ''U''<sub>2</sub>. 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 ''U''<sub>''n''+1</sub> &le; ''U''<sub>''n''</sub> + ''U''<sub>''n''−2</sub> and in any five consecutive positive integers at most two can be Ulam numbers, it can be stated that
:{{math|{{sfrac|5|2}}''n''−7}} &le; ''U''<sub>''n''</sub> &le; ''N''<sub>''n''+1</sub> for ''n'' > 0,<ref name="Gibbs"/>
where ''N''<sub>''n''</sub> are the numbers in Narayana’s cows sequence: 1,1,1,2,3,4,6,9,13,19,... with the  recurrence  relation ''N''<sub>''n''</sub> = ''N''<sub>''n''−1</sub> +''N''<sub>''n''−3</sub> that starts at ''N''<sub>0</sub>.

==Hidden structure==
It has been observed<ref>{{harvtxt|Steinerberger|2015}}</ref> that the first 10 million Ulam numbers satisfy <math>\cos{(2.5714474995 
\, U_n)} < 0</math> except for the four elements <math>\left\{2,3,47,69\right\}</math> (this has now been verified for the first <math>10^9</math> 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'',&nbsp;''v'')-Ulam numbers by selecting different starting values (''u'',&nbsp;''v''). A sequence of (''u'',&nbsp;''v'')-Ulam numbers is ''regular'' if the sequence of differences between consecutive numbers in the sequence is eventually periodic. When ''v'' is an [[Parity (mathematics)|odd]] number greater than three, the (2,&nbsp;''v'')-Ulam numbers are regular. When ''v'' is [[Modular arithmetic|congruent]] to 1 (mod 4) and at least five, the (4,&nbsp;''v'')-Ulam numbers are again regular. However, the Ulam numbers themselves do not appear to be regular.<ref>{{harvtxt|Queneau|1972}} first observed the regularity of the sequences for ''u''&nbsp;=&nbsp;2 and ''v''&nbsp;=&nbsp;7 and ''v''&nbsp;=&nbsp;9. {{harvtxt|Finch|1992}} conjectured the extension of this result to all odd ''v'' greater than three, and this conjecture was proven by {{harvtxt|Schmerl|Spiegel|1994}}. The regularity of the (4,&nbsp;''v'')-Ulam numbers was proven by {{harvtxt|Cassaigne|Finch|1995}}.</ref>

A sequence of numbers is said to be ''s''-''additive'' if each number in the sequence, after the initial 2''s'' terms of the sequence, has exactly ''s'' representations as a sum of two previous numbers. Thus, the Ulam numbers and the (''u'',&nbsp;''v'')-Ulam numbers are 1-additive sequences.<ref>{{harvtxt|Queneau|1972}}.</ref>

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 number]]s.<ref>{{harvtxt|Finch|1992}}.</ref>

==Notes==
{{reflist}}

==References==
*{{citation
 | last1 = Cassaigne | first1 = Julien
 | last2 = Finch | first2 = Steven R.
 | issue = 1
 | journal = Experimental Mathematics
 | pages = 49–60
 | title = A class of 1-additive sequences and quadratic recurrences
 | url = https://projecteuclid.org/journals/experimental-mathematics/volume-4/issue-1/A-class-of-1-additive-sequences-and-quadratic-recurrences/em/1062621142.pdf
 | volume = 4
 | year = 1995
 | doi = 10.1080/10586458.1995.10504307
 | mr = 1359417| s2cid = 9985793
 }}
*{{citation
 | last = Finch | first = Steven R.
 | doi = 10.1016/0097-3165(92)90042-S
 | issue = 1
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 123–130
 | title = On the regularity of certain 1-additive sequences
 | volume = 60
 | year = 1992
 | mr = 1156652| doi-access = 
 }}
*{{Citation
|year=2004
|title=Unsolved Problems in Number Theory
|edition=3rd
|publisher=[[Physics:Springer-Verlag|Springer-Verlag]]
|isbn= 0-387-20860-7
|pages=166–167}}
*{{citation
 | last = Queneau | first = Raymond
 | doi = 10.1016/0097-3165(72)90083-0
 | issue = 1
 | journal = Journal of Combinatorial Theory, Series A
 | language = fr
 | pages = 31–71
 | title = Sur les suites ''s''-additives
 | volume = 12
 | year = 1972
 | mr = 0302597| doi-access = free
 }}
*{{citation
 | last = Recaman | first = Bernardo
 | issue = 8
 | journal = American Mathematical Monthly
 | pages = 919–920
 | title = Questions on a sequence of Ulam
 | jstor = 2319404
 | volume = 80
 | year = 1973
 | mr = 1537172
 | doi = 10.2307/2319404}}
*{{citation
 | last1 = Schmerl | first1 = James
 | last2 = Spiegel | first2 = Eugene
 | year = 1994
 | doi = 10.1016/0097-3165(94)90058-2
 | issue = 1
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 172–175
 | title = The regularity of some 1-additive sequences
 | volume = 66
 | mr = 1273299| doi-access = 
 }}
*{{citation
 | journal = SIAM Review
 | pages = 343–355
 | title = Combinatorial analysis in infinite sets and some physical theories
 | volume = 6
 | jstor = 2027963
 | doi = 10.1137/1006090
 | year = 1964a
 | issue = 4 | bibcode = 1964SIAMR...6..343U | mr = 0170832}}
*{{citation | last = Ulam | first = Stanislaw | author-link = Stanislaw Ulam
| title = Problems in Modern Mathematics
| publisher = John Wiley & Sons, Inc
| location = New York
| year = 1964b
| page = xi
| mr = 0280310}}
*{{citation|arxiv=1507.00267|first=Stefan|
last=Steinerberger
| year = 2015
|title=A Hidden Signal in the Ulam sequence
| publisher =Experimental Mathematics|bibcode=2015arXiv150700267S}}



==External links==
* [http://mathworld.wolfram.com/UlamSequence.html Ulam Sequence from MathWorld]
* [http://vixra.org/abs/1508.0085 Fast computation of the Ulam sequence by Philip Gibbs]<!-- viXra sources tend to be unreliable, but this one has been reviewed favourably by Knuth's paper below, so it can stay per WP:USEBYOTHERS -->
* [http://www-cs-faculty.stanford.edu/~uno/ulam-gibbs.ps Description of Algorithm] by [[Biography:Donald Knuth|Donald Knuth]]
* [https://github.com/daniel3735928559/wip-ulam The github page of Daniel Ross]

{{Classes of natural numbers |state=collapsed}}
{{DEFAULTSORT:Ulam Number}}
[[Category:Integer sequences]]

{{Sourceattribution|Ulam number}}