cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

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
Named after the Polish-American scientist Stanislaw Ulam (1909-1984). - Amiram Eldar, Jun 08 2021

References

  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.2.
  • Richard K. Guy, Unsolved Problems in Number Theory, C4.
  • Donald 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 116.
  • Marvin C. Wunderlich, The improbable behavior of Ulam's summation sequence, pp. 249-257 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
  • David 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 75T-A267, p. A-707.

Links

Crossrefs

Cf. A002859 (version beginning 1,3), A054540, A003667, A001857, A007300, A117140, A214603.
First differences: A072832, A072540.
Cf. A080287, A080288, A004280 (if distinct removed from definition).
Cf. A199016, A199017, A033629, A274522.
See also the density plots in A080573 and A285884.

Programs

  • Haskell
    a002858 n = a002858_list !! (n-1)
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
  • 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
  • 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) = len-1 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 (* Jean-Franç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 *)
  • PARI
    aupto(N)= my(seen=vector(N), U=[]); seen[1]=seen[2]=1; for(i=1,N, if(1==seen[i], for(j=1,#U, my(sum=i+U[j]); if(sum>N, break); seen[sum]++); U=concat(U,i))); U \\ Ruud H.G. van Tol, Dec 29 2022
  • 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

Extensions

More terms from Jud McCranie

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.