A095115 -id:A095115 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane

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 "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: 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

			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!

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

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
Cristian Francu, C program to generate the N-th element in O(sqrt(N))
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
Benoit Jubin, Asymptotic series for Hofstadter's figure-figure sequences, arXiv:1404.1791; J. Integer Sequences, 17 (2014), #14.7.2.
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).
David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.
Eric Weisstein's World of Mathematics, Hofstadter Figure-Figure Sequence.
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for Hofstadter-type sequences

Cf. A030124 (complement), A037257, A056731, A056738, A140778, A225687.
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. A075326, A095115.
Cf. A225850, A232746, A232747 (inverse), A232739, A232740, A232750 and also permutation pair A232751/A232752 constructed from this sequence and its complement.
Cf. A001651 (analog with sums instead of differences), A121229 (analog with products).
The same recurrence a(n) = a(n-1) + c(n-1) with different starting conditions: A061577 (starting with 2), A022935 (3), A022936 (4), A022937 (5), A022938 (6).
Related recurrences:
a(n-1) + c(n+1) - A022953, A022954.
a(n-1) + c(n) - A022946 to A022952.
a(n-1) + c(n-2) - A022940, A022941.
a(n-2) + c(n-1) - A022942 to A022944.
a(n-2) + c(n-2) - A022939.
a(n-3) + c(n-3) - A022955.
a(n-4) + c(n-4) - A022956.
a(n-5) + c(n-5) - A022957.

a005228 = scanl (+) 1 a030124
a030124 = go 1 a005228 where go x ys | x < head ys = x     : go (x + 1) ys
                                     | otherwise   = x + 1 : go (x + 2) (tail ys)
-- Maks Verver, Jun 30 2025

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

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

A005228(n,print_all=0,s=1,used=0)={while(n--,used += 1<M. F. Hasler, Feb 05 2013

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 + n^(3/2)/(3*sqrt(2)) + O(n^(5/4)) [proved in Jubin link]. - Benoit Jubin, May 13 2015
For all n >= 1, A232746(a(n)) = n and A232747(a(n)) = n. [Both sequences work as left inverses of this sequence.] - Antti Karttunen, May 14 2015

Additional comments from Robert G. Wilson v, Oct 24 2001

Incorrect formula removed by Benoit Jubin, May 13 2015

A257941 Lexicographically earliest sequence of positive integers such that the terms and their absolute first differences are all distinct and no term is the sum of two distinct earlier terms.

Original entry on oeis.org

1, 3, 7, 12, 18, 26, 9, 20, 34, 24, 39, 55, 22, 45, 66, 28, 47, 72, 85, 49, 76, 108, 68, 99, 53, 82, 112, 70, 114, 149, 74, 122, 172, 93, 145, 203, 101, 160, 95, 162, 216, 118, 187, 224, 141, 214, 143, 235, 139, 195, 281, 164, 241, 329, 166, 260, 170, 283, 168

Offset: 1

Eric Angelini and Alois P. Heinz, May 13 2015

The sequence of absolute first differences begins: 2, 4, 5, 6, 8, 17, 11, 14, 10, 15, 16, 33, 23, 21, 38, 19, 25, 13, 36, 27, 32, 40, ... .

The sequence is 0-additive.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
E. Angelini et al., 0-additive and first differences and follow-up messages on the SeqFan list, May 13 2015
Eric Weisstein's World of Mathematics, s-Additive Sequence

Cf. A005228, A030124, A033627, A095115, A140778, A257944.

s:= proc() false end: b:= proc() false end:
a:= proc(n) option remember; local i, k;
      if n=1 then b(1):= true; 1
    else for k while b(k) or s(k) or
         (t-> b(t) or t=k)(abs(a(n-1)-k)) do od;
         for i to n-1 do s(a(i)+k):= true od;
         b(k), b(abs(a(n-1)-k)):= true$2; k
      fi
    end:
seq(a(n), n=1..101);

s[] = False; b[] = False;
a[n_] := a[n] = Module[{i, k}, If[n == 1, b[1] = True; 1, For[k = 1, b[k] || s[k] || Function[t, b[t] || t == k][Abs[a[n-1]-k]], k++]; For[i = 1, i <= n-1, i++, s[a[i]+k] = True]; {b[k], b[Abs[a[n-1]-k]]} = {True, True}; k]];
Array[a, 101] (* Jean-François Alcover, Oct 28 2020, after Maple *)

A257944 Lexicographically earliest sequence of positive integers such that the terms and their absolute first differences are all distinct and no term is the sum of two distinct terms.

Original entry on oeis.org

1, 3, 7, 12, 18, 26, 16, 31, 20, 37, 50, 22, 41, 64, 35, 56, 83, 39, 69, 45, 54, 79, 111, 58, 92, 130, 60, 96, 136, 73, 115, 163, 75, 121, 168, 77, 134, 193, 98, 149, 182, 102, 157, 206, 117, 178, 244, 138, 210, 277, 140, 214, 282, 153, 229, 307, 155, 220, 263

Offset: 1

Eric Angelini and Alois P. Heinz, May 13 2015

The sequence of absolute first differences begins: 2, 4, 5, 6, 8, 10, 15, 11, 17, 13, 28, 19, 23, 29, 21, 27, 44, 30, 24, 9, 25, 32, 53, ... .

Alois P. Heinz, Table of n, a(n) for n = 1..10000
E. Angelini et al., 0-additive and first differences and follow-up messages on the SeqFan list, May 13 2015

Cf. A005228, A030124, A095115, A140778, A257941.

s:= proc() false end: b:= proc() false end:
a:= proc(n) option remember; local i, k, ok;
      if n=1 then b(1):= true; 1
    else for k do if b(k) or s(k) or (t-> b(t) or t=k)(
           abs(a(n-1)-k)) then next fi; ok:=true;
           for i to n-1 while ok do if b(k+a(i))
             then ok:=false fi od; if ok then break fi
         od;
         for i to n-1 do s(a(i)+k):= true od;
         b(k), b(abs(a(n-1)-k)):= true$2; k
      fi
    end:
seq(a(n), n=1..101);

s[] = False; b[] = False;
a[n_] := a[n] = Module[{i, k, ok}, If[n == 1, b[1] = True; 1,
     For[k = 1, True, k++, If[b[k] || s[k] || Function[t, b[t] ||
     t == k][Abs[a[n-1] - k]], Continue[]]; ok = True;
             For[i = 1, i <= n-1 && ok, i++, If[b[k + a[i]],
             ok = False]]; If[ok, Break[]]];
          For[i = 1, i <= n-1, i++, s[a[i] + k] = True];
          {b[k], b[Abs[a[n-1] - k]]} = {True, True}; k]];
Table[a[n], {n, 1, 101}] (* Jean-François Alcover, Jul 16 2021, after Alois P. Heinz *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A257941 Lexicographically earliest sequence of positive integers such that the terms and their absolute first differences are all distinct and no term is the sum of two distinct earlier terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A257944 Lexicographically earliest sequence of positive integers such that the terms and their absolute first differences are all distinct and no term is the sum of two distinct terms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica