|
| |
|
|
A005228
|
|
Sequence and first differences (A030124) together list all positive numbers exactly once.
(Formerly M2629)
|
|
33
|
|
|
|
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) contain every positive integer exactly once.
Hofstadter introduces this sequence in his discussion of Scott Kim's "FIGURE-FIGURE" drawing. - N. J. A. Sloane, May 25 2013
A225850(a(n)) = 2*n-1, cf. A167151. - Reinhard Zumkeller, May 17 2013
|
|
|
REFERENCES
|
E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 73.
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
T. D. Noe and N. J. A. Sloane, Table of n, a(n) for n=1..10001 [The first 1000 terms were computed by T. D. Noe]
A. S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Catalin Francu, C++ program
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
Eric Weisstein's World of Mathematics, Hofstadter Figure-Figure Sequence.
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for Hofstadter-type sequences
|
|
|
FORMULA
|
a(n) = a(n-1) + c(n-1) 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(n-1) + b(n) + 1. (Fraenkel)
a(1) = 1, a(2) = 3; a( ) increasing; for n >= 3, if a(q) = a(n-1)-a(n-2)+1 for some q < n then a(n) = a(n-1) + (a(n-1)-a(n-2)+2), otherwise a(n) = a(n-1) + (a(n-1)-a(n-2)+1). - Albert Neumueller (albert.neu(AT)gmail.com), Jul 29 2006
|
|
|
EXAMPLE
|
Sequence reads 1 3 7 12 18 26 35 45...,
differences are 2 4 5, 6, 8, 9, 10 ... and
the point is 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.
A030124 := proc(n)
option remember;
local a, fnd, t ;
if n <= 1 then
op(n+1, [2, 4]) ;
else
for a from procname(n-1)+1 do
fnd := false;
for t from 1 to n+1 do
if A005228(t) = a then
fnd := true;
break;
end if;
end do:
if not fnd then
return a;
end if;
end do:
end if;
end proc:
A005228 := proc(n)
option remember;
if n <= 2 then
op(n, [1, 3]) ;
else
procname(n-1)+A030124(n-2) ;
end if;
end proc: # R. J. Mathar, May 19 2013
|
|
|
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
|
|
|
PROG
|
(Haskell)
import Data.List (delete)
a005228 n = a005228_list !! (n-1)
a005228_list = 1 : figure 1 [2..] where
figure n (x:xs) = n' : figure n' (delete n' xs) where n' = n + x
-- Reinhard Zumkeller, Mar 03 2011
(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, k-s) & next; used += 1<<(k-s); s=k; break)); s} \\ - M. F. Hasler, Feb 05 2013
|
|
|
CROSSREFS
|
Cf. A030124 (complement), A225687, A056731, A056738, A061577, A037257, A140778.
Related sequences: A005228, A030124, A037257, A037258, A037259, A061577, A140778, A129198, A129199, A100707, A093903, A005132, A006509, A081145, A099004, A225376, A225377, A225378, A225385, A225386, A225387
Sequence in context: A055998 A066379 A024517 * A000969 A194117 A122250
Adjacent sequences: A005225 A005226 A005227 * A005229 A005230 A005231
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Additional comments from Robert G. Wilson v, Oct 24 2001
|
|
|
STATUS
|
approved
|
| |
|
|
