login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M0557 N0201)
64
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

D. E. 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

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(158311381) = 2139999972. - Jud McCranie, Oct 31 2012

a(317670407) = 4293999992. - Jud McCranie, Nov 26 2013

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.

Popular Computing (Calabasas, CA), "Sieves", Vol. 2 (No. 13, Apr 1974), pp. 6-7.

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).

S. Ulam, Combinatorial analysis in infinite sets and some physical theories. SIAM Rev. 6 1964 343-355. Reprinted in Selected Papers, MIT Press, see p. 393.

M. 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.

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 75T-A267, p. A-707.

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 [uses Jud McCranie's values of a(n)].

S. R. Finch, Ulam s-Additive Sequences

S. R. Finch, Stolarsky-Harborth Constant

Alois P. Heinz, Ulam spiral of Ulam numbers

D. E. Knuth, Downloadable programs

Ed Pegg, Jr., Graph of 10^6 terms of a(n) - 13.5*n

R. Queneau, Sur les suites s-additives, J. Combin. Theory, A12 (1972), 31-71.

B. Recamán, Questions on a sequence of Ulam, Amer. Math. Monthly, 80 (1973), 919-920.

J. Schmerl and E. Spiegel, The regularity of some 1-additive sequences, J. Combin. Theory Ser. A 66 (1994), no. 1, 172-175. Math. Rev. 95h:11010

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

Index entries for Ulam numbers

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]]; Ulam4Compiled[355, {1, 2}, 1]

s = {1, 2}; Do[ AppendTo[s, n = Last[s]; While[n++; Length[ DeleteCases[ Intersection[s, n-s], n/2, 1, 1]] != 2]; n], {100}]; s (* Jean-François Alcover, Sep 08 2011 *)

f[s_List, j_Integer] := Block[{k = s[[-1]] + 1, ss = Plus @@@ Subsets[s, {j}]}, While[ Count[ss, k] != 1, k++]; Append[s, k]]; Nest[f[#, 2] &, {1, 2}, 70] (* Robert G. Wilson v, Jul 05 2014 *)

PROG

(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

CROSSREFS

Cf. A054540, A072832, A002859, A003667, A001857, A007300, A117140, A214603.

Cf. A080287, A080288, A004280 (if distinct removed from definition).

Cf. A199016, A199017, A080573, A033629.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

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

Last modified September 1 09:29 EDT 2014. Contains 246289 sequences.