

A002858


Ulam numbers: a(1) = 1; a(2) = 2; for n>2, a(n) = least number > a(n1) which is a unique sum of two distinct earlier terms.
(Formerly M0557 N0201)


84



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, 309, 316, 319, 324, 339
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Ulam conjectured that this sequence has density 0. However, calculations up to 6.759*10^8 (Jud McCranie) indicate that the density hovers near 0.074.
A plot of the first 3 million terms shows that they lie very close to the straight line 13.51*n, so even if we cannot prove it, we believe we now know how this sequence grows (see the plots in the links below).  N. J. A. Sloane, Sep 27 2006
After a few initial terms, the sequence settles into a regular pattern of dense clumps separated by sparse gaps, with period 21.601584+. This pattern continues up to at least a(n) = 5*10^6. (This comment is just a qualitative statement about the wavelike distribution of Ulam numbers, not meant to imply that every period includes Ulam numbers.)  David W. Wilson
Don Knuth (Sep 26 2006) remarks that a(4952)=64420 and a(4953)=64682 (a gap of more than ten "dense clumps"); and there is a gap of 315 between a(18857) and a(18858).
1,2,3,47 are the only values of x < 6.759*10^8 such that x and x+1 are both Ulam numbers.  Jud McCranie, Jun 08 2001. This holds through the first 28 billion Ulam numbers  Jud McCranie, Jan 07 2016.
From Jud McCranie on David W. Wilson's illustration, Jun 20 2008: (Start)
The integers are shown from left to right, top to bottom, with a dot where there is an Ulam number. I think his plot is 216 wide. The local density of Ulam numbers goes in waves with a period of 21.6+, so his plot shows ten cycles.
When they are arranged that way you can see the waves. The crests of the density waves don't always have Ulam numbers there but the troughs are practically void of Ulam numbers. I noticed that the ratio of that period (21.6+) to the frequency of Ulam numbers (1 in 13.52) is very close to 8/5. (End)
a(50000000) = 675904508.  Jud McCranie, Feb 29 2012
a(100000000) = 1351856726.  Jud McCranie, Jul 31 2012
a(1000000000) = 13517664323.  Jud McCranie, Aug 28 2015
a(28000000000) = 378485625853  Philip Gibbs & Jud McCranie, Sep 09 2015
3 (=1+2) and 131 (=62+69) are the only two Ulam numbers in the first 28 billion Ulam numbers that are the sum of two consecutive Ulam numbers.  Jud McCranie, Jan 09 2016


REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.2.
R. K. Guy, Unsolved Problems in Number Theory, C4.
D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.3.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. C. Wunderlich, The improbable behavior of Ulam's summation sequence, pp. 249257 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
D. Zeitlin, Ulam's sequence {U_n}, U_1=1, U_2=2, is a complete sequence, Notices Amer. Math. Soc., 22 (No. 7, 1975), Abstract 75TA267, p. A707.


LINKS

Jud McCranie, Table of n, a(n) for n = 1..10000
Richard A. Becker, Plot of residuals a(n)  13.5167*n for n <= 3000000, postscript file [uses Jud McCranie's values of a(n)].
Richard A. Becker, Plot of residuals a(n)  13.5167*n for n <= 3000000, pdf file [uses Jud McCranie's values of a(n)].
Steven R. Finch, Ulam sAdditive Sequences [From Steven Finch, Apr 20 2019]
S. R. Finch, StolarskyHarborth Constant
Steven R. Finch, StolarskyHarborth Constant [From the Wayback machine]
Philip Gibbs, An Efficient Way to Compute Ulam Numbers
Philip Gibbs, A Conjecture for Ulam Sequences
Philip Gibbs, Judson McCranie, The Ulam Numbers up to One Trillion, (2017).
Alois P. Heinz, Ulam spiral of Ulam numbers
D. E. Knuth, Downloadable programs
Noah Kravitz, Stefan Steinerberger, Ulam Sequences and Ulam Sets, arXiv:1705.01883 [math.CO], 2017.
Borys Kuca, Structures in Additive Sequences, arXiv:1804.09594 [math.NT], 2018. See p. 3.
J. W. Moon, R. K. Guy, and N. J. A. Sloane, Correspondence, 1973
Ed Pegg, Jr., Graph of 10^6 terms of a(n)  13.5*n
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 67. This is Sieve #8. [Annotated and scanned copy]
R. Queneau, Sur les suites sadditives, J. Combin. Theory, A12 (1972), 3171.
B. Recamán, Questions on a sequence of Ulam, Amer. Math. Monthly, 80 (1973), 919920.
Ivano Salvo, Agnese Pacifico, Computing Integer Sequences: Filtering vs Generation (Functional Pearl), arXiv:1807.11792 [cs.PL], 2018.
J. Schmerl and E. Spiegel, The regularity of some 1additive sequences, J. Combin. Theory Ser. A 66 (1994), no. 1, 172175. Math. Rev. 95h:11010.
Arseniy Sheydvasser, The Ulam Sequence of the Integer Polynomial Ring, arXiv:1910.00109 [math.NT], 2019.
N. J. A. Sloane, Handwritten notes on SelfGenerating Sequences, 1970 (note that A1148 has now become A005282)
Stefan Steinerberger, A hidden signal in the Ulam sequence, Research Report YALEU/DCS/TR1508, Yale University, 2015.
Stefan Steinerberger, A hidden signal in the Ulam sequence, Figure 2 from Research Report YALEU/DCS/TR1508, Yale University, 2015.
Stefan Steinerberger, The Ulam Sequence, blog post, April 12, 2016.
S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962 [Annotated scanned copy]
S. Ulam, Combinatorial analysis in infinite sets and some physical theories, SIAM Rev. 6 1964 343355. Reprinted in Selected Papers, MIT Press, see p. 393.
David W. Wilson, Plot of initial terms, showing their quasiperiodicity as vertical bars. The image width was chosen to include approximately 10 periods. For an explanation of this picture, see Comments above.
Eric Weisstein's World of Mathematics, Ulam Sequence
Wikipedia, Ulam number
R. G. Wilson, V, Letter to N. J. A. Sloane, Sep. 1992
D. Zeitlin, Ulam's sequence {U_n}, U_1=1, U_2=2, is a complete sequence, Notices Amer. Math. Soc., 22 (No. 7, 1975), Abstract 75TA267, p. A707. (Annotated scanned copy)
Index entries for Ulam numbers


MAPLE

UlamList := proc(len) local isUlam, nextUlam, behead; behead := u > u[2..numelems(u)]; isUlam := proc(n, h, u, r) local hu, tu, hr, tr; hu := u[1]; hr := r[1]; if h = 2 then return false fi; if hr <= hu then return evalb(h = 1) fi; if (hr + hu) = n then tu := behead(u); tr := behead(r); return isUlam(n, h+1, tu, tr) fi; if (hr + hu) < n then tu := behead(u): return isUlam(n, h, tu, r) fi; tr := behead(r); isUlam(n, h, u, tr) end: nextUlam := proc(n, u, r) if isUlam(n, 0, u, r) then if nops(u) = len1 then return [op(u), n] fi; nextUlam(n+1, [op(u), n], [n, op(r)]) else nextUlam(n+1, u, r) fi end: nextUlam(3, [1, 2], [2, 1]) end:
UlamList(59); # Peter Luschny, Apr 05 2019


MATHEMATICA

Ulam4Compiled = Compile[{{nmax, _Integer}, {init, _Integer, 1}, {s, _Integer}}, Module[{ulamhash = Table[0, {nmax}], ulam = init}, ulamhash[[ulam]] = 1; Do[ If[Quotient[Plus @@ ulamhash[[i  ulam]], 2] == s, AppendTo[ulam, i]; ulamhash[[i]] = 1], {i, Last[init] + 1, nmax}]; ulam]]; ulams = Ulam4Compiled[355, {1, 2}, 1]
(* Second program: *)
ulams = {1, 2}; Do[AppendTo[ulams, n = Last[ulams]; While[n++; Length[DeleteCases[Intersection[ulams, n  ulams], n/2, 1, 1]] != 2]; n], {100}]; ulams (* JeanFrançois Alcover, Sep 08 2011 *)
findUlams[s_List, j_Integer] := Block[{k = s[[1]] + 1, ss = Plus @@@ Subsets[s, {j}]}, While[ Count[ss, k] != 1, k++]; Append[s, k]]; ulams = Nest[findUlams[#, 2] &, {1, 2}, 70] (* Robert G. Wilson v, Jul 05 2014 *)


PROG

(Haskell)
a002858 n = a002858_list !! (n1)
a002858_list = 1 : 2 : ulam 2 2 a002858_list
ulam :: Int > Integer > [Integer] > [Integer]
ulam n u us = u' : ulam (n + 1) u' us where
u' = f 0 (u+1) us'
f 2 z _ = f 0 (z + 1) us'
f e z (v:vs)  z  v <= v = if e == 1 then z else f 0 (z + 1) us'
 z  v `elem` us' = f (e + 1) z vs
 otherwise = f e z vs
us' = take n us
 Reinhard Zumkeller, Nov 03 2011
(Python)
def isUlam(n, h, u, r):
if h == 2: return False
hu = u[0]; hr = r[0]
if hr <= hu: return h == 1
if hr + hu > n: r = r[1:]
elif hr + hu < n: u = u[1:]
else: h += 1; r = r[1:]; u = u[1:]
return isUlam(n, h, u, r)
def UlamList(length):
u = [1, 2]; r = [2, 1]; n = 2
while len(u) < length:
n += 1
if isUlam(n, 0, u[:], r[:]):
u.append(n); r.insert(0, n)
return u
print(UlamList(59)) # Peter Luschny, Apr 06 2019
(Julia)
function isUlam(u, n, h, i, r)
h == 2 && return false
ur = u[r]; ui = u[i]
ur <= ui && return h == 1
if ur + ui > n
r = 1
elseif ur + ui < n
i += 1
else
h += 1; i += 1; r = 1
end
isUlam(u, n, h, i, r)
end
function UlamList(len)
u = Array{Int, 1}(undef, len)
u[1] = 1; u[2] = 2; i = 2; n = 2
while i < len
n += 1
if isUlam(u, n, 0, 1, i)
i += 1
u[i] = n
end
end
return u
end
println(UlamList(59)) # Peter Luschny, Apr 07 2019


CROSSREFS

Cf. A002859 (version beginning 1,3), A054540, A002859, A003667, A001857, A007300, A117140, A214603.
First differences: A072832, A072540.
Cf. A080287, A080288, A004280 (if distinct removed from definition).
Cf. A199016, A199017, A080573, A033629, A274522.
Sequence in context: A033056 A060469 A080329 * A211522 A105799 A102463
Adjacent sequences: A002855 A002856 A002857 * A002859 A002860 A002861


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from Jud McCranie


STATUS

approved



