cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-7 of 7 results.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

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

Examples

			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!

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

Crossrefs

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.

Programs

  • Haskell
    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
  • 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
(* 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. *)
  • PARI
    A005228(n,print_all=0,s=1,used=0)={while(n--,used += 1<M. F. Hasler, Feb 05 2013

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 + 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

Extensions

Additional comments from Robert G. Wilson v, Oct 24 2001
Incorrect formula removed by Benoit Jubin, May 13 2015

A030124 Complement (and also first differences) of Hofstadter's sequence A005228.

Original entry on oeis.org

2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 77, 78
Offset: 1

Views

Author

Eric W. Weisstein

Keywords

Comments

For any n, all integers k satisfying sum(i=1,n,a(i))+1Benoit Cloitre, Apr 01 2002
The asymptotic equivalence a(n) ~ n follows from the fact that the values disallowed in the present sequence because they occur in A005228 are negligible, since A005228 grows much faster than A030124. The next-to-leading term in the formula is calculated from the functional equation F(x) + G(x) = x, suggested by D. Wilson (cf. reference), where F and G are the inverse functions of smooth, increasing approximations f and f' of A005228 and A030124. It seems that higher order corrections calculated from this equation do not agree with the real behavior of a(n). - M. F. Hasler, Jun 04 2008
A225850(a(n)) = 2*n, 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, "Gödel, Escher, Bach: An Eternal Golden Braid", Basic Books, 1st & 20th anniv. edition (1979 & 1999), p. 73.

Links

Crossrefs

Cf. A005228, A030124, A037257, A037258, A037259, A061577, A140778, A129198, A129199, A100707, A093903, A005132, A006509, A081145, A099004, A225376, A225377, A225378, A225385, A225386, A225387, A225687.

Programs

  • Haskell
    import Data.List (delete)
a030124 n = a030124_list !! n
a030124_list = figureDiff 1 [2..] where
   figureDiff n (x:xs) = x : figureDiff n' (delete n' xs) where n' = n + x
-- Reinhard Zumkeller, Mar 03 2011
  • Mathematica
    (* h stands for Hofstadter's sequence A005228 *) h[1] = 1; h[2] = 3; h[n_] := h[n] = 2*h[n-1] - h[n-2] + If[ MemberQ[ Array[h, n-1], h[n-1] - h[n-2] + 1], 2, 1]; Differences[ Array[h, 69]] (* Jean-François Alcover, Oct 06 2011 *)
  • PARI
    {a=b=t=1;for(i=1,100, while(bittest(t,b++),); print1(b",");t+=1<M. F. Hasler, Jun 04 2008

Formula

a(n) = n + sqrt(2n) + o(n^(1/2)). - M. F. Hasler, Jun 04 2008 [proved in Jubin's paper].

Extensions

Changed offset to agree with that of A005228. - N. J. A. Sloane, May 19 2013

A232751 Permutation of natural numbers obtained by entangling even and odd numbers with Hofstadter's complementary pair A005228 & A030124; inverse permutation to A232752.

Original entry on oeis.org

0, 1, 3, 2, 7, 5, 15, 6, 11, 31, 13, 23, 4, 63, 27, 47, 9, 127, 14, 55, 95, 19, 255, 29, 111, 191, 10, 39, 511, 59, 223, 383, 21, 79, 1023, 30, 119, 447, 767, 43, 159, 2047, 61, 239, 895, 12, 1535, 87, 319, 4095, 123, 479, 1791, 25, 3071, 175, 22, 639, 8191
Offset: 0

Views

Author

Antti Karttunen, Nov 30 2013

Keywords

Comments

The permutation A135141 was obtained in analogous way by entangling even and odd numbers with primes and composites.
Note how all even numbers occur in positions given by A005228 from its second term 3 onward: 3, 7, 12, 18, 26, 35, 45, ... .
Note how all odd numbers occur in positions given by A030124: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, ... .
See also the comments in A232752.
Interesting observation: For all numbers of form (2^n)-1, from 7 onward, the next term in the sequence which has that (2^n)-1 as its proper prefix (in decimal notation), appears to be 10*((2^n)-1)+9. For example, a(4)=7 and a(33)=79 is the first term of more than one decimal digits beginning with 7. For the higher values of A000225, we have examples of a(6)=15 & a(40)=159, a(9)=31 & a(48)=319, a(13)=63 & a(57)=639, a(17)=127 & a(66)=1279, a(22)=255 & a(76)=2559, a(28)=511 & a(87)=5119, a(34)=1023 & a(99)=10239, a(41)=2047 & a(111)=20479, a(49)=4095 & a(124)=40959, a(58)=8191 & a(138)=81919, a(67)=16383 & a(153)=163839, a(77)=32767 & a(168)=327679, a(88)=65535 & a(184)=655359.
So while each A000225(n) occurs at positions given by sequence 1, 2, 4, 6, 9, 13, 17, 22, 28, 34, 41, 49, 58, 67, 77, 88, 100, 112, 125, 139, 154, 169, 185, 202, 220, 239, 258, 278, 299, 321, 344, 367, ... (which from 2 onward are A232739, the iterates of A030124, cf. comment at A232752), each (10*A000225(n))+9 occurs at positions given by sequence 21, 27, 33, 40, 48, 57, 66, 76, 87, 99, 111, 124, 138, 153, 168, 184, 201, 219, 238, 257, 277, 298, 320, 343, 366, 390, 415, 441, 468, 496, 524, 553, ... Note how these seem to be one less than the previous sequence shifted 7 steps left.

Links

Crossrefs

Inverse permutation: A232752.
Cf. A135141, A005228, A030124, A005843 & A005408, A000079, A000225, A232747, A232749, A232739.
Cf. also the permutation pair A167151 & A225850.

Formula

a(0)=0, a(1)=1; for n > 1, when A232747(n)>0 (when n is in A005228), a(n) = 2*a(A232747(n)-1), otherwise (when n is in A030124) a(n) = (2*a(A232749(n))) + 1.
For all n >= 1, a(A232739(n)) = A000225(n+1).

A232752 Permutation of natural numbers: a(0)=0, a(1)=1, a(2n)=A005228(1+(a(n))), a(2n+1)=A030124(a(n)).

Original entry on oeis.org

0, 1, 3, 2, 12, 5, 7, 4, 114, 16, 26, 8, 45, 10, 18, 6, 7562, 127, 191, 21, 462, 32, 56, 11, 1285, 53, 83, 14, 236, 23, 35, 9, 29172079, 7677, 9314, 141, 20528, 208, 312, 27, 115291, 489, 679, 39, 1943, 65, 98, 15, 865555, 1331, 1751, 62, 4111, 94, 150, 19, 30983, 255, 369, 29, 802, 42, 69, 13
Offset: 0

Views

Author

Antti Karttunen, Nov 30 2013

Keywords

Comments

This is one example of the generic class of "entangling of two pairs of complementary sets" permutations of natural numbers. In this case, the Hofstadter's complementary pair A005228 & A030124 is entangled with complementary pair of A005843 & A005408, the even & odd numbers.
Note how, apart from 1, all the other terms of A005228 (1, 3, 7, 12, 18, 26, ...) occur in even positions, and all the terms of A030124 (2, 4, 5, 6, 8, 9, 10, 11, 13, 14, ...) occur in odd positions.
Moreover, at the positions given by two's powers, from 2^1 = 2 onwards, a(2^n) = 3, 12, 114, 7562, 29172079, ... the values are iterates of function b(n) = A005228(n+1) from b(1)=3 onward: b(1)=3, b(b(1))=12, b(b(b(1)))=114, b(b(b(b(1))))=7562, and so on.
In the same way, at the positions given by A000225, from 2^2 - 1 = 3 onwards, the iterates of A030124 appear, A030124(1), A030124(A030124(1)), A030124(A030124(A030124(1))), and so on, as: 2, 4, 6, 9, 13, 17, ... (= A232739).
The permutation A227413 is obtained in analogous way by entangling primes and composites with even and odd numbers.

Links

Crossrefs

Inverse permutation: A232751.
Cf. A227413, A005228, A030124, A005843 & A005408, A000079, A000225, A232739.
Cf. also the permutation pair A167151 & A225850.

Formula

a(0)=0, a(1)=1, and for even n > 1, a(n) = A005228(1+(a(n/2))), for odd n > 1, a(n) = A030124(a((n-1)/2)).
For all n >=1, a(A000225(n+1)) = A232739(n).

A167151 a(2n+1) = a(2n) + a(2n-1), a(2n)=least number not yet in the sequence, a(1)=1.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 5, 12, 6, 18, 8, 26, 9, 35, 10, 45, 11, 56, 13, 69, 14, 83, 15, 98, 16, 114, 17, 131, 19, 150, 20, 170, 21, 191, 22, 213, 23, 236, 24, 260, 25, 285, 27, 312, 28, 340, 29, 369, 30, 399, 31, 430, 32, 462, 33, 495, 34, 529, 36, 565, 37, 602, 38, 640, 39, 679
Offset: 0

Views

Author

M. F. Hasler, Nov 01 2009

Keywords

Comments

Lexicographically earliest reordering of the nonnegative integers (can be extended by symmetry to a permutation of all integers) such that a(2n+1) = a(2n) + a(2n-1).

Links

Crossrefs

Cf. A022941, A143344, A156031.
Cf. A225850 (inverse).

Programs

  • Haskell
    import Data.List (transpose)
a167151 n = a167151_list !! n
a167151_list = 0 : concat (transpose [a005228_list, a030124_list])
-- Reinhard Zumkeller, May 17 2013
  • Mathematica
    a[0] = 0; a[1] = 1;
a[n_?OddQ] := a[n] = a[n - 1] + a[n - 2];
a[n_?EvenQ] := a[n] = For[k = 2, True, k++,
     If[FreeQ[Array[a, n - 1], k], Return[k]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Dec 02 2021 *)
  • PARI
    {used=[]; print1(b=0); a=1; for(i=1,99, used=setunion(used,Set(a+=b)); while(setsearch(used,b++), used=setminus(used,Set(b))); print1(", "a", "b))}

Formula

a(2n-1) = A005228(n); a(2n) = A030124(n).

A232739 Iterates of Hofstadter's A030124: start with a(1) = A030124(1) = 2, thereafter a(n) = A030124(a(n-1)).

Original entry on oeis.org

2, 4, 6, 9, 13, 17, 22, 28, 34, 41, 49, 58, 67, 77, 88, 100, 112, 125, 139, 154, 169, 185, 202, 220, 239, 258, 278, 299, 321, 344, 367, 391, 416, 442, 469, 497, 525, 554, 584, 615, 647, 680, 713, 747, 782, 818, 855, 893, 931, 970, 1010, 1051, 1093, 1136, 1179
Offset: 1

Views

Author

Antti Karttunen, Dec 04 2013

Keywords

Comments

Is the ratio A005228(n)/a(n) converging towards 1 or some larger value? (Cf. the graph drawn by the OEIS Server's plot2-link).
Cf. also M. F. Hasler's comment in A030124.

Links

Crossrefs

Cf. A005228, A030124, A232751, A232752, A000225, A225850.
Concerning the ratio A005228/A232739 see also A232740, A232750, A232753.

Formula

a(1) = 2, and for n> 1, a(n) = A030124(a(n-1)).
For all n >= 1, A232751(a(n)) = A000225(n+1) and a(n) = A232752(A000225(n+1)) [This is just a consequence of how the permutation pair A232751/A232752 has been defined].
For all n >= 1, a(n) = A225850(a(n+1))/2.

A232746 n occurs A030124(n) times; a(n) = one less than the least k such that A005228(k) > n.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
Offset: 1

Views

Author

Antti Karttunen, Nov 30 2013

Keywords

Comments

The characteristic function for Hofstadter's A005228 is given by X_A005228(1)=1, and for n>1, X_A005228(n) = a(n)-a(n-1).
The characteristic function for Hofstadter's A030124 is given by X_A030124(1)=0, and for n>1, X_A030124(n) = 1-(a(n)-a(n-1)).
Useful when computing A232747, A232748, A232750 & A225850.

Links

Crossrefs

Cf. A005228, A030124, A232747, A232748, A232750, A232753, A225850.

Programs

  • Mathematica
    nmax = 100; A5228 = {1}; Module[{d = 2, k = 1}, Do[While[MemberQ[A5228, d], d++]; k += d; d++; AppendTo[A5228, k], {n, 1, nmax}]];
a[n_] := For[k = 1, True, k++, If[A5228[[k]] > n, Return[k-1]]];
Array[a, nmax] (* Jean-François Alcover, Dec 09 2021 *)

Formula

a(n) = one less than the least k such that A005228(k) > n.
Showing 1-7 of 7 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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