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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005228 Sequence and first differences (A030124) together list all positive numbers exactly once.
(Formerly M2629)
42
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

In view of the definition of A075326 (anti-Fibonacci numbers): start with a(0) = 0, and extend by rule that the next term is the sum of the predecessor and the most recent non-member of the sequence. - Reinhard Zumkeller, Oct 26 2014

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.

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

D. R. Hofstadter, Eta-Lore [Cached copy, with permission]

D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]

D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991

Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.

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

a(n) = n^2/2 + C*n^(3/2) + O(n), where C = 2^(1/2) - 2^(3/2)/6 = 0.9428... According to the a(n) = (n + sqrt(2n))^2/2 - sqrt(2n)^3/6 + O(n) from a simplified model: the sum of n consecutive numbers without the triangular numbers. - Thomas Ordowski, Sep 17 2014

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.

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.

Cf. A075326.

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

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 December 22 19:34 EST 2014. Contains 252365 sequences.