

A005228


Sequence and first differences (A030124) together list all positive numbers exactly once.
(Formerly M2629)


71



1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, 285, 312, 340, 369, 399, 430, 462, 495, 529, 565, 602, 640, 679, 719, 760, 802, 845, 889, 935, 982, 1030, 1079, 1129, 1180, 1232, 1285, 1339, 1394, 1451, 1509, 1568, 1628, 1689
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This is the lexicographically earliest sequence that together with its first differences (A030124) contains every positive integer exactly once.
Hofstadter introduces this sequence in his discussion of Scott Kim's "FIGUREFIGURE" drawing.  N. J. A. Sloane, May 25 2013
In view of the definition of A075326: start with a(0) = 0, and extend by rule that the next term is the sum of the predecessor and the most recent nonmember of the sequence.  Reinhard Zumkeller, Oct 26 2014


REFERENCES

E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 3235, Volume 59 (Jeux math'), April/June 2008, Paris.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 73.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

D. R. Hofstadter, EtaLore [Cached copy, with permission]


FORMULA

a(n) = a(n1) + c(n1) for n >= 2, where a(1)=1, a( ) increasing, c( ) = complement of a( ) (c is the sequence A030124).
Let a(n) = this sequence, b(n) = A030124 prefixed by 0. Then b(n) = mex{ a(i), b(i) : 0 <= i < n}, a(n) = a(n1) + b(n) + 1. (Fraenkel)
a(1) = 1, a(2) = 3; a( ) increasing; for n >= 3, if a(q) = a(n1)a(n2)+1 for some q < n then a(n) = a(n1) + (a(n1)a(n2)+2), otherwise a(n) = a(n1) + (a(n1)a(n2)+1).  Albert Neumueller (albert.neu(AT)gmail.com), Jul 29 2006
a(n) = n^2/2 + n^(3/2)/(3*sqrt(2)) + O(n^(5/4)) [proved in Jubin link].  Benoit Jubin, May 13 2015


EXAMPLE

Sequence reads 1 3 7 12 18 26 35 45..., differences are 2 4 5, 6, 8, 9, 10 ... and the point is that every number not in the sequence itself appears among the differences. This property (together with the fact that both the sequence and the sequence of first differences are increasing) defines the sequence!


MAPLE

maxn := 5000; h := array(1..5000); h[1] := 1; a := [1]; i := 1; b := []; for n from 2 to 1000 do if h[n] <> 1 then b := [op(b), n]; j := a[i]+n; if j < maxn then a := [op(a), j]; h[j] := 1; i := i+1; fi; fi; od: a; b; # a is A005228, b is A030124.
option remember;
local a, fnd, t ;
if n <= 1 then
op(n+1, [2, 4]) ;
else
for a from procname(n1)+1 do
fnd := false;
for t from 1 to n+1 do
fnd := true;
break;
end if;
end do:
if not fnd then
return a;
end if;
end do:
end if;
end proc:
option remember;
if n <= 2 then
op(n, [1, 3]) ;
else
end if;


MATHEMATICA

a = {1}; d = 2; k = 1; Do[ While[ Position[a, d] != {}, d++ ]; k = k + d; d++; a = Append[a, k], {n, 1, 55} ]; a
(* Second program: *)
(* Program from Larry Morris, Jan 19 2017: *)
d = 3; a = {1, 3, 7, 12, 18}; While[ Length[a = Join[a, a[[1]] + Accumulate[Range[a[[d]] + 1, a[[++d]]  1]]]] < 50]; a
(* Comment: This adds as many terms to the sequence as there are numbers in each set of sequential differences. Consequently, the list of numbers it produces may be longer than the limit provided. With the limit of 50 shown, the sequence produced has length 60. *)


PROG

(Haskell)
import Data.List (delete)
a005228 n = a005228_list !! (n1)
a005228_list = 1 : figure 1 [2..] where
figure n (x:xs) = n' : figure n' (delete n' xs) where n' = n + x
(PARI) A005228(n, print_all=0, s=1, used=0)={while(n, used += 1<<s; print_all & print1(s", "); for(k=s+1, 9e9, bittest(used, k) & next; bittest(used, ks) & next; used += 1<<(ks); s=k; break)); s} \\ M. F. Hasler, Feb 05 2013


CROSSREFS

The following are a group of related sequences: A005132, A006509, A037257, A037258, A037259, A081145, A093903, A099004, A100707, A129198, A129199, A140778, A225376, A225377, A225378, A225385, A225386, A225387.
Cf. A001651 (analog with sums instead of differences), A121229 (analog with products).
Related recurrences:


KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



