A007306 -id:A007306 - cp's OEIS frontend

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2n) = a(n), a(2n+1) = a(n) + a(n+1).

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19

Offset: 0

N. J. A. Sloane

Also called fusc(n) [Dijkstra].
a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once [Stern; Calkin and Wilf].
If the terms are written as an array:
  column 0 1 2 3 4 5 6 7 8 9 ...
  row 0: 0
  row 1: 1
  row 2: 1,2
  row 3: 1,3,2,3
  row 4: 1,4,3,5,2,5,3,4
  row 5: 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5
  row 6: 1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,...
  ...
then (ignoring row 0) the sum of the k-th row is 3^(k-1), each column is an arithmetic progression and the steps are nothing but the original sequence. - Takashi Tokita (butaneko(AT)fa2.so-net.ne.jp), Mar 08 2003
From N. J. A. Sloane, Oct 15 2017: (Start)
The above observation can be made more precise. Let A(n,k), n >= 0, 0 <= k <= 2^(n-1)-1 for k > 0, denote the entry in row n and column k of the left-justified array above.
The equations for columns 0,1,2,3,4,... are successively (ignoring row 0):
     1 (n >= 1),
     n (n >= 2),
   n-1 (n >= 3),
  2n-3 (n >= 3),
   n-2 (n >= 4),
  3n-7 (n >= 4),
  ...
and in general column k > 0 is given by
A(n,k) = a(k)*n - A156140(k) for n >= ceiling(log_2(k+1))+1, and 0 otherwise.
(End)
a(n) is the number of odd Stirling numbers S_2(n+1, 2r+1) [Carlitz].
Moshe Newman proved that the fraction a(n+1)/a(n+2) can be generated from the previous fraction a(n)/a(n+1) = x by 1/(2*floor(x) + 1 - x). The successor function f(x) = 1/(floor(x) + 1 - frac(x)) can also be used.
a(n+1) = number of alternating bit sets in n [Finch].
If f(x) = 1/(1 + floor(x) - frac(x)) then f(a(n-1)/a(n)) = a(n)/a(n+1) for n >= 1. If T(x) = -1/x and f(x) = y, then f(T(y)) = T(x) for x > 0. - Michael Somos, Sep 03 2006
a(n+1) is the number of ways of writing n as a sum of powers of 2, each power being used at most twice (the number of hyperbinary representations of n) [Carlitz; Lind].
a(n+1) is the number of partitions of the n-th integer expressible as the sum of distinct even-subscripted Fibonacci numbers (= A054204(n)), into sums of distinct Fibonacci numbers [Bicknell-Johnson, theorem 2.1].
a(n+1) is the number of odd binomial(n-k, k), 0 <= 2*k <= n. [Carlitz], corrected by Alessandro De Luca, Jun 11 2014
a(2^k) = 1. a(3*2^k) = a(2^(k+1) + 2^k) = 2. Sequences of terms between a(2^k) = 1 and a(2^(k+1)) = 1 are palindromes of length 2^k-1 with a(2^k + 2^(k-1)) = 2 in the middle. a(2^(k-1) + 1) = a(2^k - 1) = k+1 for k > 1. - Alexander Adamchuk, Oct 10 2006
The coefficients of the inverse of the g.f. of this sequence form A073469 and are related to binary partitions A000123. - Philippe Flajolet, Sep 06 2008
It appears that the terms of this sequence are the number of odd entries in the diagonals of Pascal's triangle at 45 degrees slope. - Javier Torres (adaycalledzero(AT)hotmail.com), Aug 06 2009
Let M be an infinite lower triangular matrix with (1, 1, 1, 0, 0, 0, ...) in every column shifted down twice:
   1;
   1, 0;
   1, 1, 0;
   0, 1, 0, 0;
   0, 1, 1, 0, 0;
   0, 0, 1, 0, 0, 0;
   0, 0, 1, 1, 0, 0, 0;
   ...
   Then this sequence A002487 (without initial 0) is the first column of lim_{n->oo} M^n. (Cf. A026741.) - Gary W. Adamson, Dec 11 2009 [Edited by M. F. Hasler, Feb 12 2017]
Member of the infinite family of sequences of the form a(n) = a(2*n); a(2*n+1) = r*a(n) + a(n+1), r = 1 for A002487 = row 1 in the array of A178239. - Gary W. Adamson, May 23 2010
Equals row 1 in an infinite array shown in A178568, sequences of the form
a(2*n) = r*a(n), a(2*n+1) = a(n) + a(n+1); r = 1. - Gary W. Adamson, May 29 2010
Row sums of A125184, the Stern polynomials. Equivalently, B(n,1), the n-th Stern polynomial evaluated at x = 1. - T. D. Noe, Feb 28 2011
The Kn1y and Kn2y triangle sums, see A180662 for their definitions, of A047999 lead to the sequence given above, e.g., Kn11(n) = A002487(n+1) - A000004(n), Kn12(n) = A002487(n+3) - A000012(n), Kn13(n) = A002487(n+5) - A000034(n+1) and Kn14(n) = A002487(n+7) - A157810(n+1). For the general case of the knight triangle sums see the Stern-Sierpiński triangle A191372. This triangle not only leads to Stern's diatomic series but also to snippets of this sequence and, quite surprisingly, their reverse. - Johannes W. Meijer, Jun 05 2011
Maximum of terms between a(2^k) = 1 and a(2^(k+1)) = 1 is the Fibonacci number F(k+2). - Leonid Bedratyuk, Jul 04 2012
Probably the number of different entries per antidiagonal of A223541. That would mean there are exactly a(n+1) numbers that can be expressed as a nim-product 2^x*2^y with x + y = n. - Tilman Piesk, Mar 27 2013
Let f(m,n) be the frequency of the integer n in the interval [a(2^(m-1)), a(2^m-1)]. Let phi(n) be Euler's totient function (A000010). Conjecture: for all integers m,n n<=m f(m,n) = phi(n). - Yosu Yurramendi, Sep 08 2014
Back in May 1995, it was proved that A000360 is the modulo 3 mapping, (+1,-1,+0)/2, of this sequence A002487 (without initial 0). - M. Jeremie Lafitte (Levitas), Apr 24 2017
Define a sequence chf(n) of Christoffel words over an alphabet {-,+}: chf(1) = '-'; chf(2*n+0) = negate(chf(n)); chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))). Then the length of the chf(n) word is fusc(n) = a(n); the number of '-'-signs in the chf(n) word is c-fusc(n) = A287729(n); the number of '+'-signs in the chf(n) word is s-fusc(n) = A287730(n). See examples below. - I. V. Serov, Jun 01 2017
The sequence can be extended so that a(n) = a(-n), a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1) for all n in Z. - Michael Somos, Jun 25 2019
Named after the German mathematician Moritz Abraham Stern (1807-1894), and sometimes also after the French clockmaker and amateur mathematician Achille Brocot (1817-1878). - Amiram Eldar, Jun 06 2021
It appears that a(n) is equal to the multiplicative inverse of A007305(n+1) mod A007306(n+1).  For example, a(12) is 2, the multiplicative inverse of A007305(13) mod A007306(13), where A007305(13) is 4 and A007306(13) is 7. - Gary W. Adamson, Dec 18 2023

			Stern's diatomic array begins:
  1,1,
  1,2,1,
  1,3,2,3,1,
  1,4,3,5,2,5,3,4,1,
  1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1,
  1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,...
  ...
a(91) = 19, because 91_10 = 1011011_2; b_6=b_4=b_3=b_1=b_0=1, b_5=b_2=0;  L=5; m_1=0, m_2=1, m_3=3, m_4=4, m_5=6; c_1=2, c_2=3, c_3=2, c_4=3; f(1)=1, f(2)=2, f(3)=5, f(4)=8, f(5)=19. - _Yosu Yurramendi_, Jul 13 2016
From _I. V. Serov_, Jun 01 2017: (Start)
a(n) is the length of the Christoffel word chf(n):
n  chf(n) A070939(n)   a(n)
1   '-'       1          1
2   '+'       2          1
3   '+-'      2          2
4   '-'       3          1
5   '--+'     3          3
6   '-+'      3          2
... (End)
G.f. = x + x^2 + 2*x^3 + x^4 + 3*x^5 + 2*x^6 + 3*x^7 + x^8 + ... - _Michael Somos_, Jun 25 2019

M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg, New York: Springer-Verlag, 2004, p. 97.
Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 114.
Krishna Dasaratha, Laure Flapan, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse and Matthew Stroegeny, A family of multi-dimensional continued fraction Stern sequences, Abtracts Amer. Math. Soc., Vol. 33 (#1, 2012), #1077-05-2543.
Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence is called fusc).
F. G. M. Eisenstein, Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen abhaengen und durch gewisse lineare Funktional-Gleichungen definirt werden, Verhandlungen der Koenigl. Preuss. Akademie der Wiss. Berlin (1850), pp. 36-42, Feb 18, 1850. Werke, II, pp. 705-711.
Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3; pp. 148-149.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
Thomas Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000
Boris Adamczewski, Non-converging continued fractions related to the Stern diatomic sequence, Acta Arithm. 142 (1) (2010) 67-78.
Jean-Paul Allouche and Michel Mendès France, Lacunary formal power series and the Stern-Brocot sequence, arXiv preprint arXiv:1202.0211 [math.NT], 2012-2013. - _N. J. A. Sloane_, May 10 2012
Jean-Paul Allouche, On the Stern sequence and its twisted version, arXiv preprint arXiv:1202.4171 [math.NT], 2012.
Jean-Paul Allouche, Michel Mendès France, Anna Lubiw, Alfred J. van der Poorten and Jeffrey Shallit, Convergents of folded continued fractions.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197. [Preprint.]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29. [Preprint.]
Michael Baake and Michael Coons, A natural probability measure derived from Stern's diatomic sequence, arXiv:1706.00187 [math.NT], 2017.
Roland Bacher, Twisting the Stern sequence, arXiv:1005.5627 [math.CO], 2010.
Bruce Bates, Martin Bunder and Keith Tognetti, Linking the Calkin-Wilf and Stern-Brocot trees, Eur. J. Comb., Vol. 31, No. 7 (2010), pp. 1637-1661.
Bruce Bates and Toufik Mansour, The q-Calkin-Wilf tree, Journal of Combinatorial Theory Series A, Vol. 118, No. 3 (2011), pp. 1143-1151.
Marjorie Bicknell-Johnson, Stern's Diatomic Array Applied to Fibonacci Representations, Fibonacci Quarterly, Vol. 41 (2003), pp. 169-180.
Arie Bos, Graph connecting p/q and r/s where |q*r-p*s|=1 and p=a(n), q= a(n+1), r=a(m), s=a(m+1) and 0<=p/q,r/s<=1.
Richard P. Brent, Michael Coons and Wadim Zudilin, Asymptotics of a Mahler Function, Slides of talk presented at AustMS/NZMS 2014, Melbourne, 8 December 2014.
Neil Calkin and Herbert S. Wilf, Recounting the rationals, Amer. Math. Monthly, Vol. 107, No. 4 (2000), pp. 360-363.
L. Carlitz, A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., Vol. 70, No. 2 (1964), pp. 275-278. [Abstract.]
L. Carlitz, A problem in partitions related to the Stirling numbers, Riv. Mat. Univ. Parma, (2) 5 (1964), 61-75.
Michael Coons, The transcendence of series related to Stern's diatomic sequence, International Journal of Number Theory 6.01 (2010): 211-217.
Michael Coons, On some conjectures concerning Stern's sequence and its twist, Integers 11.6 (2011): 775-789.
Michael Coons, A Correlation Identity for Stern's Sequence, Integers 12.3 (2012): 459-464.
Michael Coons and Jeffrey Shallit, A pattern sequence approach to Stern's sequence, Discrete Math., Vol. 311 (2011), pp. 2630-2633.
Michael Coons and Jason Tyler, The maximal order of Stern's diatomic sequence, arXiv:1307.1521 [math.NT], 2013-2014.
Kevin M. Courtright and James A. Sellers, Arithmetic Properties for Hyper m-ary Partitions, INTEGERS, Vol. 4 (2004), Article A6.
Valerio De Angelis, The Stern diatomic sequence via generalized Chebyshev polynomials, American Mathematical Monthly 124.5 (2017): 451-455. See also, arXiv:1511.02422 [math.NT], 2015.
Philip de Castro et al., Counting binomial coefficients divisible by a prime power, Amer. Math. Monthly, Vol. 125, No. 6 (2018), pp. 531-540. See Table p. 534.
Colin Defant, Upper Bounds for Stern's Diatomic Sequence and Related Sequences, Electronic Journal of Combinatorics, Vol. 23, No. 4 (2016), #P4.8.
Georges De Rham, Un peu de mathématiques à propos d'une courbe plane, Elemente der Math., Vol. 2 (1947), pp. 73-76 and 89-97.
Marc Deléglise, Paul Erdős and Jean-Louis Nicolas, Sur les ensembles représentés par les partitions d'un entier n [Sets represented by partitions of an integer n] Paul Erdős memorial collection. Discrete Math., Vol. 200, No. 1-3 (1999), pp. 27-48. MR1692277 (2000e:05012). See Table 1. _N. J. A. Sloane_, Mar 18 2012
Edsger W. Dijkstra, An exercise for Dr. R. M. Burstall.
Edsger W. Dijkstra, More about the function "fusc".
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), #P2.24.
Karl Dilcher and Larry Ericksen, Factors and irreducibility of generalized Stern polynomials, Integers, Vol. 15 (2015), #A50.
Karl Dilcher and Larry Ericksen, Continued fractions and Stern polynomials, Ramanujan Journal, Vol. 45 (2017), pp. 659-681.
Karl Dilcher and Larry Ericksen, Polynomials Characterizing Hyper b-ary Representations, J. Int. Seq., Vol. 21 (2018), Article 18.4.3.
Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
Tom Edgar, On the number of hyper m-ary partitions, Integers, Vol. 18 (2018), Article #A47.
De-Jun Feng, Pierre Liardet and Alain Thomas, Partition functions in numeration systems with bounded multiplicity, Uniform Distribution Theory, Vol. 9, No. 1 (2014).
Steven R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Aviezri S. Fraenkel, Ratwyt, Dec 28 2011.
Thomas Garrity, A multi-dimensional continued fraction generalization of Stern's diatomic sequence, arXiv:1206.6685 [math.CO], 2012-2013.
Thomas Garrity, A multi-dimensional continued fraction generalization of Stern's diatomic sequence, Journal of Integer Sequences, Vol. 16 (2013), #13.7.7.
Michael Gilleland, Some Self-Similar Integer Sequences.
Jose Grimm, Implementation of Bourbaki's Elements of Mathematics in Coq: Part Two, From Natural Numbers to Real Numbers, Journal of Formalized Reasoning, Vol. 9, No. 2 (2016), pp. 1-52; see p. 38.
Brian Hayes, On the Teeth of Wheels, American Scientist, Vol. 88, No. 4 (July-August 2000), pp. 296-300 (5 pages).
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović and Ciril Petr,, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 115. Book's website
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse and Ciril Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence European J. Combin., Vol. 26, No. 5 (2005), pp. 693-708.
Johannes Kepler, Harmonices Mundi, Vol. III (1619) p.27.
Donald E. Knuth, C. P. Rupert, Alex Smith and Richard Stong, Recounting the Rationals, Continued: 10906, solution by Moshe Newman, American Mathematical Monthly, Vol. 110, No. 7 (2003), pp. 642-643.
Jennifer Lansing, Distribution of Values of the Binomial Coefficients and the Stern Sequence, Journal of Integer Sequences, Vol. 16 (2013), Article 13.3.7.
Jennifer Lansing, Largest Values for the Stern Sequence, Journal of Integer Sequences, Vol. 17 (2014), Article 14.7.5.
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly, Vol. 36, No. 1 (1929), pp. 59-67. [Annotated and corrected scanned copy.]
Julien Leroy, Michel Rigo and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics, Vol. 340 (2017), pp. 862-881. Also available at Université de Liège.
Peter Luschny, Rational Trees and Binary Partitions.
Alan J. Macfarlane, Linear reversible second-order cellular automata and their first-order matrix equivalents, Journal of Physics A: Mathematical and General 37.45 (2004): 10791. See Fig. 2.
Laura Monroe, Binary Signed-Digit Integers, the Stern Diatomic Sequence and Stern Polynomials, arXiv:2103.05810 [math.NT], 2021.
Sam Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ..., Amer. Math. Monthly, Vol. 117, No. 7 (2010), pp. 581-598.
Sam Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, Vol. 18 (2015), Article 15.11.6.
Sam Northshield, Re^3counting the Rationals, arXiv:1905.10369 [math.NT], 2019.
Project Euler, Problem 169 - Exploring the number of different ways a number can be expressed as a sum of powers of 2.
Bruce Reznick, Some binary partition functions, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990, pp. 451-477.
Bruce Reznick, Regularity properties of the Stern enumeration of the Rationals, Journal of Integer Sequences, Vol. 11 (2008) Article 08.4.1.
Jürgen W. Sander, Jörn Steuding and Rasa Steuding, Diophantine aspects of the Calkin-Wilf iteration, El. Math., Vol. 66, No. 2 (2011) pp. 45-55. doi:10.4171/EM/170.
Anton Shakov, Polynomials in Z[x] whose divisors are enumerated by SL_2(N_0), arXiv:2405.03552 [math.NT], 2024. See p. 27.
Rémy Sigrist, Nonperiodic tilings related to Stern's diatomic series and based on tiles decorated with elements of F_p, arXiv:2301.06039 [math.CO], 2023.
N. J. A. Sloane, Stern-Brocot or Farey Tree.
N. J. A. Sloane and Brady Haran, Amazing Graphs III, Numberphile video (2019).
Richard P. Stanley and Herbert S. Wilf, Refining the Stern Diatomic Sequence, unpublished.
Richard P. Stanley and Herbert S. Wilf, Refining the Stern Diatomic Sequence [Cached copy, with permission]
Jörn Steuding, Stefanie Hofmann and Gertraud Schuster, Euclid, Calkin & Wilf - playing with rationals, Elemente der Mathematik, Vol. 63, No. 3 (2008), pp. 109-117.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
M. A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., Vol. 55 (1858), pp. 193-220.
Maciej Ulas, Arithmetic properties of the sequence of degrees of Stern polynomials and related results, arXiv:1102.5111 [math.CO], 2011.
Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials, arXiv:1102.5109 [math.CO], 2011.
Igor Urbiha, Some properties of a function studied by De Rham, Carlitz and Dijkstra and its relation to the (Eisenstein -) Stern's diatomic sequence, Math. Commun., Vol. 6 (2002), pp. 181-198.
Eric Weisstein's World of Mathematics, Calkin-Wilf Tree and Stern's Diatomic Series.
Yasuhisa Yamada, A function from Stern's diatomic sequence, and its properties, arXiv:2004.00278 [math.NT], 2020.
Index entries for "core" sequences
Index entries for fraction trees
Index entries for sequences related to enumerating the rationals
Index entries for sequences related to Stern's sequences
Index entries for sequences related to trees

Cf. A000120, A000123, A000360, A001045, A002083, A011655, A020950, A026741, A037227, A046815, A070871, A070872, A071883, A073459, A084091, A101624, A126606, A168081, A174980, A174981, A178239, A178568, A212288, A213369, A260443, A277020, A277325, A287729, A287730, A293160.
Record values are in A212289.
If the 1's are replaced by pairs of 1's we obtain A049456.
Inverse: A020946.
Cf. a(A001045(n)) = A000045(n). a(A062092(n)) = A000032(n+1).
Cf. A064881-A064886 (Stern-Brocot subtrees).
A column of A072170.
Cf. A049455 for the 0,1 version of Stern's diatomic array.
Cf. A000119, A262097 for analogous sequences in other bases and A277189, A277315, A277328 for related sequences with similar graphs.
Cf. A086592 and references therein to other sequences related to Kepler's tree of fractions.

a002487 n = a002487_list !! n
a002487_list = 0 : 1 : stern [1] where
   stern fuscs = fuscs' ++ stern fuscs' where
     fuscs' = interleave fuscs $ zipWith (+) fuscs $ (tail fuscs) ++ [1]
   interleave []     ys = ys
   interleave (x:xs) ys = x : interleave ys xs
-- Reinhard Zumkeller, Aug 23 2011

using Nemo
function A002487List(len)
    a, A = QQ(0), [0,1]
    for n in 1:len
        a = next_calkin_wilf(a)
        push!(A, denominator(a))
    end
A end
A002487List(91) |> println # Peter Luschny, Mar 13 2018

[&+[(Binomial(k, n-k-1) mod 2): k in [0..n]]: n in [0..100]]; // Vincenzo Librandi, Jun 18 2019

A002487 := proc(n) option remember; if n <= 1 then n elif n mod 2 = 0 then procname(n/2); else procname((n-1)/2)+procname((n+1)/2); fi; end: seq(A002487(n),n=0..91);
A002487 := proc(m) local a,b,n; a := 1; b := 0; n := m; while n>0 do if type(n,odd) then b := a+b else a := a+b end if; n := floor(n/2); end do; b; end proc: seq(A002487(n),n=0..91); # Program adapted from E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. - Igor Urbiha (urbiha(AT)math.hr), Oct 28 2002. Since A007306(n) = a(2*n+1), this program can be adapted for A007306 by replacing b := 0 by b := 1.
A002487 := proc(n::integer) local k; option remember; if n = 0 then 0 elif n=1 then 1 else add(K(k,n-1-k)*procname(n - k), k = 1 .. n) end if end proc:
K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n and n-k <= 2 then KC:=1; else KC:= 0; end if; end proc: seq(A002487(n),n=0..91); # Thomas Wieder, Jan 13 2008
# next Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      (q-> a(q)+(n-2*q)*a(n-q))(iquo(n, 2)))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 11 2021
fusc := proc(n) local a, b, c; a := 1; b := 0;
    for c in convert(n, base, 2) do
        if c = 0 then a := a + b else b := a + b fi od;
    b end:
seq(fusc(n), n = 0..91); # Peter Luschny, Nov 09 2022
Stern := proc(n, u) local k, j, b;
    b := j -> nops({seq(Bits:-Xor(k, j-k), k = 0..j)}):
    ifelse(n=0, 1-u, seq(b(j), j = 2^(n-1)-1..2^n-1-u)) end:
seq(print([n], Stern(n, 1)), n = 0..5); # As shown in the comments.
seq(print([n], Stern(n, 0)), n = 0..5); # As shown in the examples. # Peter Luschny, Sep 29 2024

a[0] = 0; a[1] = 1; a[n_] := If[ EvenQ[n], a[n/2], a[(n-1)/2] + a[(n+1)/2]]; Table[ a[n], {n, 0, 100}] (* end of program *)
Onemore[l_] := Transpose[{l, l + RotateLeft[l]}] // Flatten;
NestList[Onemore, {1}, 5] // Flatten  (*gives [a(1), ...]*) (* Takashi Tokita, Mar 09 2003 *)
ToBi[l_] := Table[2^(n - 1), {n, Length[l]}].Reverse[l]; Map[Length,
Split[Sort[Map[ToBi, Table[IntegerDigits[n - 1, 3], {n, 500}]]]]]  (*give [a(1), ...]*) (* Takashi Tokita, Mar 10 2003 *)
A002487[m_] := Module[{a = 1, b = 0, n = m}, While[n > 0, If[OddQ[n], b = a+b, a = a+b]; n = Floor[n/2]]; b]; Table[A002487[n], {n, 0, 100}] (* Jean-François Alcover, Sep 06 2013, translated from 2nd Maple program *)
a[0] = 0; a[1] = 1;
Flatten[Table[{a[2*n] = a[n], a[2*n + 1] = a[n] + a[n + 1]}, {n, 0, 50}]] (* Horst H. Manninger, Jun 09 2021 *)
nmax = 100; CoefficientList[Series[x*Product[(1 + x^(2^k) + x^(2^(k+1))), {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Oct 08 2022 *)

{a(n) = n=abs(n); if( n<2, n>0, a(n\2) + if( n%2, a(n\2 + 1)))};

fusc(n)=local(a=1,b=0);while(n>0,if(bitand(n,1),b+=a,a+=b);n>>=1);b \\ Charles R Greathouse IV, Oct 05 2008

A002487(n,a=1,b=0)=for(i=0,logint(n,2),if(bittest(n,i),b+=a,a+=b));b \\ M. F. Hasler, Feb 12 2017, updated Feb 14 2019

from functools import lru_cache
@lru_cache(maxsize=None)
def a(n): return n if n<2 else a(n//2) if n%2==0 else a((n - 1)//2) + a((n + 1)//2) # Indranil Ghosh, Jun 08 2017; corrected by Reza K Ghazi, Dec 27 2021

def a(n):
    a, b = 1, 0
    while n > 0:
        if n & 1:
            b += a
        else:
            a += b
        n >>= 1
    return b
# Reza K Ghazi, Dec 29 2021

def A002487(n): return sum(int(not (n-k-1) & ~k) for k in range(n)) # Chai Wah Wu, Jun 19 2022

# (fast way for big vectors)
from math import log, ceil
import numpy
how_many_terms = 2**20  # (Powers of 2 recommended but other integers are also possible.)
A002487, A002487[1]  = numpy.zeros(2**(ce:=ceil(log(how_many_terms,2))), dtype=object), 1
for exponent in range(1,ce):
    L, L2 = 2**exponent, 2**(exponent+1)
    A002487[L2 - 1] = exponent + 1
    A002487[L:L2][::2] = A002487[L >> 1: L]
    A002487[L + 1:L2 - 2][::2] = A002487[L:L2 - 3][::2]  +  A002487[L + 2:L2 - 1][::2]
print(list(A002487[0:100])) # Karl-Heinz Hofmann, Jul 22 2025

N <- 50 # arbitrary
a <- 1
for (n in 1:N)
{
  a[2*n    ] = a[n]
  a[2*n + 1] = a[n] + a[n+1]
  a
}
a
# Yosu Yurramendi, Oct 04 2014

# Given n, compute a(n) by taking into account the binary representation of n
a <- function(n){
  b <- as.numeric(intToBits(n))
  l <- sum(b)
  m <- which(b == 1)-1
  d <- 1
  if(l > 1) for(j in 1:(l-1)) d[j] <- m[j+1]-m[j]+1
  f <- c(0,1)
  if(l > 1) for(j in 3:(l+1)) f[j] <- d[j-2]*f[j-1]-f[j-2]
  return(f[l+1])
} # Yosu Yurramendi, Dec 13 2016

# computes the sequence as a vector A, rather than function a() as above.
A <- c(1,1)
maxlevel <- 5 # by choice
for(m in 1:maxlevel) {
  A[2^(m+1)] <- 1
  for(k in 1:(2^m-1)) {
    r <- m - floor(log2(k)) - 1
    A[2^r*(2*k+1)] <- A[2^r*(2*k)] + A[2^r*(2*k+2)]
}}
A # Yosu Yurramendi, May 08 2018

def A002487(n):
    M = [1, 0]
    for b in n.bits():
        M[b] = M[0] + M[1]
    return M[1]
print([A002487(n) for n in (0..91)])
# For a dual see A174980. Peter Luschny, Nov 28 2017

;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
(definec (A002487 n) (cond ((<= n 1) n) ((even? n) (A002487 (/ n 2))) (else (+ (A002487 (/ (- n 1) 2)) (A002487 (/ (+ n 1) 2))))))
;; Antti Karttunen, Nov 05 2016

a(n+1) = (2*k+1)*a(n) - a(n-1) where k = floor(a(n-1)/a(n)). - David S. Newman, Mar 04 2001
Let e(n) = A007814(n) = exponent of highest power of 2 dividing n. Then a(n+1) = (2k+1)*a(n)-a(n-1), n > 0, where k = e(n). Moreover, floor(a(n-1)/a(n)) = e(n), in agreement with D. Newman's formula. - Dragutin Svrtan (dsvrtan(AT)math.hr) and Igor Urbiha (urbiha(AT)math.hr), Jan 10 2002
Calkin and Wilf showed 0.9588 <= limsup a(n)/n^(log(phi)/log(2)) <= 1.1709 where phi is the golden mean. Does this supremum limit = 1? - Benoit Cloitre, Jan 18 2004.  Coons and Tyler show the limit is A246765 = 0.9588... - Kevin Ryde, Jan 09 2021
a(n) = Sum_{k=0..floor((n-1)/2)} (binomial(n-k-1, k) mod 2). - Paul Barry, Sep 13 2004
a(n) = Sum_{k=0..n-1} (binomial(k, n-k-1) mod 2). - Paul Barry, Mar 26 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^3 + 2*u*v*w - u^2*w. - Michael Somos, May 02 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u1^3*u6 - 3*u1^2*u2*u6 + 3*u2^3*u6 - u2^3*u3. - Michael Somos, May 02 2005
G.f.: x * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))) [Carlitz].
a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1)). - Mike Stay, Nov 06 2006
A079978(n) = (1 + e^(i*Pi*A002487(n)))/2, i=sqrt(-1). - Paul Barry, Jan 14 2005
a(n) = Sum_{k=1..n} K(k, n-k)*a(n - k), where K(n,k) = 1 if 0 <= k AND k <= n AND n-k <= 2 and K(n,k) = 0 else. (When using such a K-coefficient, several different arguments to K or several different definitions of K may lead to the same integer sequence. For example, if we drop the condition k <= n in the above definition, then we arrive at A002083 = Narayana-Zidek-Capell numbers.) - Thomas Wieder, Jan 13 2008
a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1; a(2^n - k) + a(k) = a(2^(n+1) + k). Both formulas hold for 0 <= k <= 2^n - 1. G.f.: G(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ... Define f(z) = (1 + z + z^2), then G(z) = lim f(z)*f(z^2)*f(z^4)* ... *f(z^(2^n))*... = (1 + z + z^2)*G(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 11 2008
a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1 (0 <= k <= 2^n - 1). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
a(2^n + k) = a(2^n - k) + a(k) (0 <= k <= 2^n). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
Let g(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ..., f(z) = 1 + z + z^2. Then g(z) = lim_{n->infinity} f(z)*f(z^2)*f(z^4)*...*f(z^(2^n)), g(z) = f(z)*g(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
For 0 <= k <= 2^n - 1, write k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1) where b(0), b(1), etc. are 0 or 1. Define a 2 X 2 matrix X(m) with entries x(1,1) = x(2,2) = 1, x(1,2) = 1 - b(m), x(2,1) = b(m). Let P(n)= X(0)*X(1)* ... *X(n-1). The entries of the matrix P are members of the sequence: p(1,1) = a(k+1), p(1,2) = a(2^n - (k+1)), p(2,1) = a(k), p(2,2) = a(2^n - k). - Arie Werksma (werksma(AT)tiscali.nl), Apr 20 2008
Let f(x) = A030101(x); if 2^n + 1 <= x <= 2^(n + 1) and y = 2^(n + 1) - f(x - 1) then a(x) = a(y). - Arie Werksma (Werksma(AT)Tiscali.nl), Jul 11 2008
a(n) = A126606(n + 1) / 2. - Reikku Kulon, Oct 05 2008
Equals infinite convolution product of [1,1,1,0,0,0,0,0,0] aerated A000079 - 1 times, i.e., [1,1,1,0,0,0,0,0,0] * [1,0,1,0,1,0,0,0,0] * [1,0,0,0,1,0,0,0,1]. - Mats Granvik and Gary W. Adamson, Oct 02 2009; corrected by Mats Granvik, Oct 10 2009
a(2^(p+2)*n+2^(p+1)-1) - a(2^(p+1)*n+2^p-1) = A007306(n+1), p >= 0 and n >= 0. - Johannes W. Meijer, Feb 07 2013
a(2*n-1) = A007306(n), n > 0. - Yosu Yurramendi, Jun 23 2014
a(n*2^m) = a(n), m>0, n > 0. - Yosu Yurramendi, Jul 03 2014
a(k+1)*a(2^m+k) - a(k)*a(2^m+(k+1)) = 1 for m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Nov 07 2014
a(2^(m+1)+(k+1))*a(2^m+k) - a(2^(m+1)+k)*a(2^m+(k+1)) = 1 for m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Nov 07 2014
a(5*2^k) = 3. a(7*2^k) = 3. a(9*2^k) = 4. a(11*2^k) = 5. a(13*2^k) = 5. a(15*2^k) = 4. In general: a((2j-1)*2^k) = A007306(j), j > 0, k >= 0 (see Adamchuk's comment). - Yosu Yurramendi, Mar 05 2016
a(2^m+2^m'+k') = a(2^m'+k')*(m-m'+1) - a(k'), m >= 0, m' <= m-1, 0 <= k' < 2^m'. - Yosu Yurramendi, Jul 13 2016
From Yosu Yurramendi, Jul 13 2016: (Start)
Let n be a natural number and [b_m b_(m-1) ... b_1 b_0] its binary expansion with b_m=1.
Let L = Sum_{i=0..m} b_i be the number of binary digits equal to 1 (L >= 1).
Let {m_j: j=1..L} be the set of subindices such that b_m_j = 1, j=1..L, and 0 <= m_1 <= m_2 <= ... <= m_L = m.
If L = 1 then c_1 = 1, otherwise let {c_j: j=1..(L-1)} be the set of coefficients such that c_(j) = m_(j+1) - m_j + 1, 1 <= j <= L-1.
Let f be a function defined on {1..L+1} such that f(1) = 0, f(2) = 1, f(j) = c_(j-2)*f(j-1) - f(j-2), 3 <= j <= L+1.
Then a(n) = f(L+1) (see example). (End)
a(n) = A001222(A260443(n)) = A000120(A277020(n)). Also a(n) = A000120(A101624(n-1)) for n >= 1. - Antti Karttunen, Nov 05 2016
(a(n-1) + a(n+1))/a(n) = A037227(n) for n >= 1. - Peter Bala, Feb 07 2017
a(0) = 0; a(3n) = 2*A000360(3n-1); a(3n+1) = 2*A000360(3n) - 1; a(3n+2) = 2*A000360(3n+1) + 1. - M. Jeremie Lafitte (Levitas), Apr 24 2017
From I. V. Serov, Jun 14 2017: (Start)
a(n) = A287896(n-1) - 1*A288002(n-1) for n > 1;
a(n) = A007306(n-1) - 2*A288002(n-1) for n > 1. (End)
From Yosu Yurramendi, Feb 14 2018: (Start)
a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1) + 2^m + k) = 2*a(k), m >= 0, 0 <= k < 2^m.
a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1)       + k) = a(2^m + k), m >= 0, 0 <= k < 2^m.
a(2^m + k) = a(k)*(m - floor(log_2(k)) - 1) + a(2^(floor(log_2(k))+1) + k), m >= 0, 0 < k < 2^m,  a(2^m) = 1, a(0) = 0. (End)
From Yosu Yurramendi, May 08 2018: (Start)
a(2^m) = 1, m >= 0.
a(2^r*(2*k+1)) = a(2^r*(2*k)) + a(2^r*(2*k+2)), r < - m - floor(log_2(k)) - 1, m > 0, 1 <= k < 2^m. (End)
Trow(n) = [card({k XOR (j-k): k=0..j}) for j = 2^(n-1)-1..2^n-2] when regarded as an irregular table (n >= 1). - Peter Luschny, Sep 29 2024
a(n) = A000120(A168081(n)). - Karl-Heinz Hofmann, Jun 16 2025

Additional references and comments from Len Smiley, Joshua Zucker, Rick L. Shepherd and Herbert S. Wilf
Typo in definition corrected by Reinhard Zumkeller, Aug 23 2011
Incorrect formula deleted and text edited by Johannes W. Meijer, Feb 07 2013

A016777 a(n) = 3*n + 1.

Original entry on oeis.org

1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139, 142, 145, 148, 151, 154, 157, 160, 163, 166, 169, 172, 175, 178, 181, 184, 187

Offset: 0

N. J. A. Sloane, Dec 11 1996

Numbers k such that the concatenation of the first k natural numbers is not divisible by 3. E.g., 16 is in the sequence because we have 123456789101111213141516 == 1 (mod 3).
Ignoring the first term, this sequence represents the number of bonds in a hydrocarbon: a(#of carbon atoms) = number of bonds. - Nathan Savir (thoobik(AT)yahoo.com), Jul 03 2003
n such that Sum_{k=0..n} (binomial(n+k,n-k) mod 2) is even (cf. A007306). - Benoit Cloitre, May 09 2004
Hilbert series for twisted cubic curve. - Paul Barry, Aug 11 2006
If Y is a 3-subset of an n-set X then, for n >= 3, a(n-3) is the number of 3-subsets of X having at least two elements in common with Y. - Milan Janjic, Nov 23 2007
a(n) = A144390 (1, 9, 23, 43, 69, ...) - A045944 (0, 5, 16, 33, 56, ...). From successive spectra of hydrogen atom. - Paul Curtz, Oct 05 2008
Number of monomials in the n-th power of polynomial x^3+x^2+x+1. - Artur Jasinski, Oct 06 2008
A145389(a(n)) = 1. - Reinhard Zumkeller, Oct 10 2008
Union of A035504, A165333 and A165336. - Reinhard Zumkeller, Sep 17 2009
Hankel transform of A076025. - Paul Barry, Sep 23 2009
From Jaroslav Krizek, May 28 2010: (Start)
a(n) = numbers k such that the antiharmonic mean of the first k positive integers is an integer.
A169609(a(n-1)) = 1. See A146535 and A169609. Complement of A007494.
See A005408 (odd positive integers) for corresponding values A146535(a(n)). (End)
Apart from the initial term, A180080 is a subsequence; cf. A180076. - Reinhard Zumkeller, Aug 14 2010
Also the maximum number of triangles that n + 2 noncoplanar points can determine in 3D space. - Carmine Suriano, Oct 08 2010
A089911(4*a(n)) = 3. - Reinhard Zumkeller, Jul 05 2013
The number of partitions of 6*n into at most 2 parts. - Colin Barker, Mar 31 2015
For n >= 1, a(n)/2 is the proportion of oxygen for the stoichiometric combustion reaction of hydrocarbon CnH2n+2, e.g., one part propane (C3H8) requires 5 parts oxygen to complete its combustion. - Kival Ngaokrajang, Jul 21 2015
Exponents n > 0 for which 1 + x^2 + x^n is reducible. - Ron Knott, Oct 13 2016
Also the number of independent vertex sets in the n-cocktail party graph. - Eric W. Weisstein, Sep 21 2017
Also the number of (not necessarily maximal) cliques in the n-ladder rung graph. - Eric W. Weisstein, Nov 29 2017
Also the number of maximal and maximum cliques in the n-book graph. - Eric W. Weisstein, Dec 01 2017
For n>=1, a(n) is the size of any snake-polyomino with n cells. - Christian Barrientos and Sarah Minion, Feb 27 2018
The sum of two distinct terms of this sequence is never a square. See Lagarias et al. p. 167. - Michel Marcus, May 20 2018
It seems that, for any n >= 1, there exists no positive integer z such that digit_sum(a(n)*z) = digit_sum(a(n)+z). - Max Lacoma, Sep 18 2019
For n > 2, a(n-2) is the number of distinct values of the magic constant in a normal magic triangle of order n (see formula 5 in Trotter). - Stefano Spezia, Feb 18 2021
Number of 3-permutations of n elements avoiding the patterns 132, 231, 312. See Bonichon and Sun. - Michel Marcus, Aug 20 2022
Erdős & Sárközy conjecture that a set of n positive integers with property P must have some element at least a(n-1) = 3n - 2. Property P states that, for x, y, and z in the set and z < x, y, z does not divide x+y. An example of such a set is {2n-1, 2n, ..., 3n-2}. Bedert proves this for large enough n. (This is an upper bound, and is exact for all known n; I have verified it for n up to 12.) - Charles R Greathouse IV, Feb 06 2023
a(n-1) = 3*n-2 is the dimension of the vector space of all n X n tridiagonal matrices, equals the number of nonzero coefficients: n + 2*(n-1) (see Wikipedia link). - Bernard Schott, Mar 03 2023

			G.f. = 1 + 4*x + 7*x^2 + 10*x^3 + 13*x^4 + 16*x^5 + 19*x^6 + 22*x^7 + ... - _Michael Somos_, May 27 2019

W. Decker, C. Lossen, Computing in Algebraic Geometry, Springer, 2006, p. 22.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.1 Terminology, p. 264.
Konrad Knopp, Theory and Application of Infinite Series, Dover, p. 269.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Hacène Belbachir, Toufik Djellal, and Jean-Gabriel Luque, On the self-convolution of generalized Fibonacci numbers, arXiv:1703.00323 [math.CO], 2017.
Benjamin Bedert, On a problem of Erdős and Sárközy about sequences with no term dividing the sum of two larger terms, arXiv preprint, arXiv:2301.07065 [math.NT], 2023.
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
Paul Erdős and András Sárközy, On the divisibility properties of sequences of integers, Proc. London Math. Soc. (3), 21 (1970), pp. 97-101.
Leonhard Euler, Observatio de summis divisorum p. 9.
Leonhard Euler, An observation on the sums of divisors, arXiv:math/0411587 [math.HO], 2004-2009, see p. 9.
L. B. W. Jolley, Summation of Series, Dover, 1961, pp. 16, 38.
Tanya Khovanova, Recursive Sequences
Konrad Knopp, Theorie und Anwendung der unendlichen Reihen, Berlin, J. Springer, 1922. (Original German edition of "Theory and Application of Infinite Series")
J. C. Lagarias, A. M. Odlyzko, and J. B. Shearer, On the density of sequences of integers the sum of no two of which is a square. I. Arithmetic progressions, Journal of Combinatorial Theory. Series A, 33 (1982), pp. 167-185.
T. Mansour, Permutations avoiding a set of patterns from S_3 and a pattern from S_4, arXiv:math/9909019 [math.CO], 1999.
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
Terrel Trotter, Normal Magic Triangles of Order n, Journal of Recreational Mathematics Vol. 5, No. 1, 1972, pp. 28-32.
Eric Weisstein's World of Mathematics, Book Graph
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Ladder Rung Graph
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Maximum Clique
Wikipedia, Tridiagonal matrix.
Chengcheng Yang, A Problem of Erdös Concerning Lattice Cubes, arXiv:2011.15010 [math.CO], 2020. See Table p. 27.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A000290, A001477, A005408, A007306, A007494, A016789, A016933.
Cf. A017569, A035504, A045944, A058183, A076025, A089911, A144390.
Cf. A145389, A146535, A165333, A165336, A169609, A180076, A180080.
Cf. A214550, A238731.
Cf. A007559 (partial products), A051536 (lcm).
First differences of A000326.
Row sums of A131033.
Complement of A007494. - Reinhard Zumkeller, Oct 10 2008
Some subsequences: A002476 (primes), A291745 (nonprimes), A135556 (squares), A016779 (cubes).

a016777 = (+ 1) . (* 3)
a016777_list = [1, 4 ..]  -- Reinhard Zumkeller, Feb 28 2013, Feb 10 2012

[3*n+1 : n in [1..70]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

Range[1, 199, 3] (* Vladimir Joseph Stephan Orlovsky, May 26 2011 *)
(* Start from Eric W. Weisstein, Sep 21 2017 *)
3 Range[0, 70] + 1
Table[3 n + 1, {n, 0, 70}]
LinearRecurrence[{2, -1}, {1, 4}, 70]
CoefficientList[Series[(1 + 2 x)/(-1 + x)^2, {x, 0, 70}], x]
(* End *)

A016777(n):=3*n+1$
makelist(A016777(n),n,0,30); /* Martin Ettl, Oct 31 2012 */

a(n)=3*n+1 \\ Charles R Greathouse IV, Jul 28 2015

[3*n+1 for n in range(1,71)] # G. C. Greubel, Mar 15 2024

G.f.: (1+2*x)/(1-x)^2.
a(n) = A016789(n) - 1.
a(n) = 3 + a(n-1).
Sum_{n>=1} (-1)^n/a(n) = (1/3)*(Pi/sqrt(3) + log(2)). [Jolley, p. 16, (79)] - Benoit Cloitre, Apr 05 2002
(1 + 4*x + 7*x^2 + 10*x^3 + ...) = (1 + 2*x + 3*x^2 + ...)/(1 - 2*x + 4*x^2 - 8*x^3 + ...). - Gary W. Adamson, Jul 03 2003
E.g.f.: exp(x)*(1+3*x). - Paul Barry, Jul 23 2003
a(n) = 2*a(n-1) - a(n-2); a(0)=1, a(1)=4. - Philippe Deléham, Nov 03 2008
a(n) = 6*n - a(n-1) - 1 (with a(0) = 1). - Vincenzo Librandi, Nov 20 2010
Sum_{n>=0} 1/a(n)^2 = A214550. - R. J. Mathar, Jul 21 2012
a(n) = A238731(n+1,n) = (-1)^n*Sum_{k = 0..n} A238731(n,k)*(-5)^k. - Philippe Deléham, Mar 05 2014
Sum_{i=0..n} (a(i)-i) = A000290(n+1). - Ivan N. Ianakiev, Sep 24 2014
From Wolfdieter Lang, Mar 09 2018: (Start)
a(n) = denominator(Sum_{k=0..n-1} 1/(a(k)*a(k+1))), with the numerator n = A001477(n), where the sum is set to 0 for n = 0. [Jolley, p. 38, (208)]
G.f. for {n/(1 + 3*n)}_{n >= 0} is (1/3)*(1-hypergeom([1, 1], [4/3], -x/(1-x)))/(1-x). (End)
a(n) = -A016789(-1-n) for all n in Z. - Michael Somos, May 27 2019

Better description from T. D. Noe, Aug 15 2002

Partially edited by Joerg Arndt, Mar 11 2010

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1

Offset: 0

N. J. A. Sloane

Restored the alternative spelling of Sierpinski to facilitate searching for this triangle using regular-expression matching commands in ASCII. - N. J. A. Sloane, Jan 18 2016
Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - Hans Havermann, May 26 2002
Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - Philippe Deléham, Oct 02 2003
Self-inverse when regarded as an infinite lower triangular matrix over GF(2).
Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe]
Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - Philippe Deléham, Jun 18 2005
J. H. Conway writes (in Math Forum): at least the first 31 rows give odd-sided constructible polygons (sides 1, 3, 5, 15, 17, ... see A001317). The 1's form a Sierpiński sieve. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005
When regarded as an infinite lower triangular matrix, its inverse is a (-1,0,1)-matrix with zeros undisturbed and the nonzero entries in every column form the Prouhet-Thue-Morse sequence (1,-1,-1,1,-1,1,1,-1,...) A010060 (up to relabeling). - David Callan, Oct 27 2006
Triangle read by rows: antidiagonals of an array formed by successive iterates of running sums mod 2, beginning with (1, 1, 1, ...). - Gary W. Adamson, Jul 10 2008
T(n,k) = A057427(A143333(n,k)). - Reinhard Zumkeller, Oct 24 2010
The triangle sums, see A180662 for their definitions, link Sierpiński’s triangle A047999 with seven sequences, see the crossrefs. The Kn1y(n) and Kn2y(n), y >= 1, triangle sums lead to the Sierpiński-Stern triangle A191372. - Johannes W. Meijer, Jun 05 2011
Used to compute the total Steifel-Whitney cohomology class of the Real Projective space. This was an essential component of the proof that there are no product operations without zero divisors on R^n for n not equal to 1, 2, 4 or 8 (real numbers, complex numbers, quaternions, Cayley numbers), proved by Bott and Milnor. - Marcus Jaiclin, Feb 07 2012
T(n,k) = A134636(n,k) mod 2. - Reinhard Zumkeller, Nov 23 2012
T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - Reinhard Zumkeller, Nov 30 2012
From Vladimir Shevelev, Dec 31 2013: (Start)
Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = Sum_{i=0..n} (binomial(n,i) mod 2)*x^k. These polynomials we naturally call Sierpiński's polynomials. They also are defined by the recursion: s_0(x)=1, s_(2*n+1)(x) = (x+1)*s_n(x^2), n>=0, and s_(2*n)(x) = s_n(x^2), n>=1.
Note that: s_n(1)  = A001316(n),
           s_n(2)  = A001317(n),
           s_n(3)  = A100307(n),
           s_n(4)  = A001317(2*n),
           s_n(5)  = A100308(n),
           s_n(6)  = A100309(n),
           s_n(7)  = A100310(n),
           s_n(8)  = A100311(n),
           s_n(9)  = A100307(2*n),
           s_n(10) = A006943(n),
           s_n(16) = A001317(4*n),
           s_n(25) = A100308(2*n), etc.
The equality s_n(10) = A006943(n) means that sequence A047999 is obtained from A006943 by the separation by commas of the digits of its terms. (End)
Comment from N. J. A. Sloane, Jan 18 2016: (Start)
Take a diamond-shaped region with edge length n from the top of the triangle, and rotate it by 45 degrees to get a square S_n. Here is S_6:
  [1, 1, 1, 1, 1, 1]
  [1, 0, 1, 0, 1, 0]
  [1, 1, 0, 0, 1, 1]
  [1, 0, 0, 0, 1, 0]
  [1, 1, 1, 1, 0, 0]
  [1, 0, 1, 0, 0, 0].
Then (i) S_n contains no square (parallel to the axes) with all four corners equal to 1 (cf. A227133); (ii) S_n can be constructed by using the greedy algorithm with the constraint that there is no square with that property; and (iii) S_n contains A064194(n) 1's. Thus A064194(n) is a lower bound on A227133(n). (End)
See A123098 for a multiplicative encoding of the rows, i.e., product of the primes selected by nonzero terms; e.g., 1 0 1 => 2^1 * 3^0 * 5^1. - M. F. Hasler, Sep 18 2016
From Valentin Bakoev, Jul 11 2020: (Start)
The Sierpinski's triangle with 2^n rows is a part of a lower triangular matrix M_n of dimension 2^n X 2^n. M_n is a block matrix defined recursively: M_1= [1, 0], [1, 1], and for n>1, M_n = [M_(n-1), O_(n-1)], [M_(n-1), M_(n-1)], where M_(n-1) is a block matrix of the same type, but of dimension 2^(n-1) X 2^(n-1), and O_(n-1) is the zero matrix of dimension 2^(n-1) X 2^(n-1). Here is how M_1, M_2 and M_3 look like:
1 0     1 0 0 0      1 0 0 0 0 0 0 0
1 1     1 1 0 0      1 1 0 0 0 0 0 0   - It is seen the self-similarity of the
        1 0 1 0      1 0 1 0 0 0 0 0     matrices M_1, M_2, ..., M_n, ...,
        1 1 1 1      1 1 1 1 0 0 0 0     analogously to the Sierpinski's fractal.
                     1 0 0 0 1 0 0 0
                     1 1 0 0 1 1 0 0
                     1 0 1 0 1 0 1 0
                     1 1 1 1 1 1 1 1
M_n can also be defined as M_n = M_1 X M_(n-1) where X denotes the Kronecker product. M_n is an important matrix in coding theory, cryptography, Boolean algebra, monotone Boolean functions, etc. It is a transformation matrix used in computing the algebraic normal form of Boolean functions. Some properties and links concerning M_n can be seen in LINKS. (End)
Sierpinski's gasket has fractal (Hausdorff) dimension log(A000217(2))/log(2) = log(3)/log(2) = 1.58496... (and cf. A020857). This gasket is the first of a family of gaskets formed by taking the Pascal triangle (A007318) mod j, j >= 2 (see CROSSREFS). For prime j, the dimension of the gasket is log(A000217(j))/log(j) = log(j(j + 1)/2)/log(j) (see Reiter and Bondarenko references). - Richard L. Ollerton, Dec 14 2021

			Triangle begins:
              1,
             1,1,
            1,0,1,
           1,1,1,1,
          1,0,0,0,1,
         1,1,0,0,1,1,
        1,0,1,0,1,0,1,
       1,1,1,1,1,1,1,1,
      1,0,0,0,0,0,0,0,1,
     1,1,0,0,0,0,0,0,1,1,
    1,0,1,0,0,0,0,0,1,0,1,
   1,1,1,1,0,0,0,0,1,1,1,1,
  1,0,0,0,1,0,0,0,1,0,0,0,1,
  ...

Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
Brand, Neal; Das, Sajal; Jacob, Tom. The number of nonzero entries in recursively defined tables modulo primes. Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990). Congr. Numer. 78 (1990), 47--59. MR1140469 (92h:05004).
John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46).
H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..10584 [First 144 rows, flattened; first 50 rows from T. D. Noe].
J.-P. Allouche and V. Berthe, Triangle de Pascal, complexité et automates, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.
J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.],
J. Baer, Explore patterns in Pascal's Triangle
Valentin Bakoev, Fast Bitwise Implementation of the Algebraic Normal Form Transform, Serdica J. of Computing 11 (2017), No 1, 45-57.
Valentin Bakoev, Properties and links concerning M_n
Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.
A. Bogomolny, Dot Patterns and Sierpinski Gasket
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see pp. 130-132.
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
E. Burlachenko, Fractal generalized Pascal matrices, arXiv:1612.00970 [math.NT], 2016. See p. 9.
S. Butkevich, Pascal Triangle Applet
David Callan, Sierpinski's triangle and the Prouhet-Thue-Morse word, arXiv:math/0610932 [math.CO], 2006.
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part I
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part II
C. Cobeli, A. Zaharescu, A game with divisors and absolute differences of exponents, arXiv:1411.1334 [math.NT], 2014; Journal of Difference Equations and Applications, Vol. 20, #11, 2014.
Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m)
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
Brady Haran, Chaos Game, Numberphile video, YouTube (April 27, 2017).
I. Kobayashi et al., Pascal's Triangle
Dr. Math, Regular polygon formulas [Broken link?]
Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.
National Curve Bank, Sierpinski Triangles
Hieu D. Nguyen, A Digital Binomial Theorem, arXiv:1412.3181 [math.NT], 2014.
S. Northshield, Sums across Pascal's triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.
A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quarterly, 31(2), 1993, pp. 112-120.
F. Richman, Javascript for computing Pascal's triangle modulo n. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.
N. J. A. Sloane, Illustration of rows 0 to 32 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 64 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 128 (encoignure style)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Eric Weisstein's World of Mathematics, Sierpiński Sieve, Rule 60, Rule 102
Index entries for sequences related to cellular automata
Index entries for triangles and arrays related to Pascal's triangle
Index entries for sequences generated by sieves

Sequences based on the triangles formed by reading Pascal's triangle mod m: (this sequence) (m = 2), A083093 (m = 3), A034931 (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).
Other versions: A090971, A038183.
Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133.
From Johannes W. Meijer, Jun 05 2011: (Start)
A106344 is a skew version of this triangle.
Triangle sums (see the comments): A001316 (Row1; Related to Row2), A002487 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A007306 (Kn3, Kn4), A060632 (Fi1, Fi2), A120562 (Ca1, Ca2), A112970 (Gi1, Gi2), A127830 (Ze3, Ze4). (End)

import Data.Bits (xor)
a047999 :: Int -> Int -> Int
a047999 n k = a047999_tabl !! n !! k
a047999_row n = a047999_tabl !! n
a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Dec 11 2011, Oct 24 2010

A047999:= func< n,k | BitwiseAnd(n-k, k) eq 0 select 1 else 0 >;
[A047999(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Dec 03 2024

# Maple code for first M rows (here M=10) - N. J. A. Sloane, Feb 03 2016
ST:=[1,1,1]; a:=1; b:=2; M:=10;
for n from 2 to M do ST:=[op(ST),1];
for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od:
ST:=[op(ST),1];
a:=a+n; b:=a+n; od:
ST; # N. J. A. Sloane
# alternative
A047999 := proc(n,k)
    modp(binomial(n,k),2) ;
end proc:
seq(seq(A047999(n,k),k=0..n),n=0..12) ; # R. J. Mathar, May 06 2016

Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* Robert G. Wilson v, May 26 2004 *)
rows = 14; ca = CellularAutomaton[60, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, 1 ;; k]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)
Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* Harvey P. Dale, Jun 26 2019 *)
A047999[n_,k_]:= Boole[BitAnd[n-k,k]==0];
Table[A047999[n,k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Sep 03 2025 *)

\\ Recurrence for Pascal's triangle mod p, here p = 2.
p = 2; s=13; T=matrix(s,s); T[1,1]=1;
for(n=2,s, T[n,1]=1; for(k=2,n, T[n,k] = (T[n-1,k-1] + T[n-1,k])%p ));
for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ Gerald McGarvey, Oct 10 2009

A011371(n)=my(s);while(n>>=1,s+=n);s
T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ Charles R Greathouse IV, Aug 09 2013

T(n,k)=bitand(n-k,k)==0 \\ Charles R Greathouse IV, Aug 11 2016

def A047999_T(n,k):
    return int(not ~n & k) # Chai Wah Wu, Feb 09 2016

Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators. - Chai Wah Wu, Feb 09 2016 and N. J. A. Sloane, Feb 10 2016
Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n).
T(n,k) = T(n-1,k-1) XOR T(n-1,k), 0 < k < n; T(n,0) = T(n,n) = 1. - Reinhard Zumkeller, Dec 13 2009
T(n,k) = (T(n-1,k-1) + T(n-1,k)) mod 2 = |T(n-1,k-1) - T(n-1,k)|, 0 < k < n; T(n,0) = T(n,n) = 1. - Rick L. Shepherd, Feb 23 2018
From Vladimir Shevelev, Dec 31 2013: (Start)
For polynomial {s_n(x)} we have
s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1),
if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i;
G.f. Sum_{n>=0} s_n(x)*z^n = Product_{k>=0} (1 + (x^(2^k)+1)*z^(2^k)) (0Let x>1, t>0 be real numbers. Then
Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t);
Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t).
In particular, for t=1, x>1, we have
Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End)
From Valentin Bakoev, Jul 11 2020: (Start)
(See my comment about the matrix M_n.) Denote by T(i,j) the number in the i-th row and j-th column of M_n (0 <= i, j < 2^n). When i>=j, T(i,j) is the j-th number in the i-th row of the Sierpinski's triangle. For given i and j, we denote by k the largest integer of the type k=2^m and kT(i,0) = T(i,i) = 1, or
T(i,j) = 0 if i < j, or
T(i,j) = T(i-k,j), if j < k, or
T(i,j) = T(i-k,j-k), if j >= k.
Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End)

Additional links from Lekraj Beedassy, Jan 22 2004

A025480 a(2n) = n, a(2n+1) = a(n).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 0, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10

Offset: 0

David W. Wilson

These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap. - R. K. Guy, Mar 30 2006. See Levine 2004/2006 for more about this. - N. J. A. Sloane, Aug 14 2016
When n > 0 is written as (2k+1)*2^j then k = a(n-1) and j = A007814(n), so: when n is written as (2k+1)*2^j-1 then k = a(n) and j = A007814(n+1), when n > 1 is written as (2k+1)*2^j+1 then k = a(n-2) and j = A007814(n-1). - Henry Bottomley, Mar 02 2000 [sequence id corrected by Peter Munn, Jun 22 2022]
According to the comment from Deuard Worthen (see Example section), this may be regarded as a triangle where row r=1,2,3,... has length 2^(r-1) and values T(r,2k-1)=T(r-1,k), T(r,2k)=2^(r-1)+k-1; i.e., previous row gives 1st, 3rd, 5th, ... term and 2nd, 4th, ... terms are numbers 2^(r-1),...,2^r-1 (i.e., those following the last one from the previous row). - M. F. Hasler, May 03 2008
Let StB be a Stern-Brocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n-1)<>0 and a(n)<>0 then mediant(StB(a(n-1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n-1)),Right) else mediant(Left,StB(a(n-1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). - Reinhard Zumkeller, Dec 22 2008
This sequence is the unique fixed point of the function (a(0), a(1), a(2), ...) |--> (0, a(0), 1, a(1), 2, a(2), ...) which interleaves the nonnegative integers between the elements of a sequence. - Cale Gibbard (cgibbard(AT)gmail.com), Nov 18 2009
Also the number of remaining survivors in a Josephus problem after the person originally first in line has been eliminated (see A225381). - Marcus Hedbring, May 18 2013
A fractal sequence - see Levine 2004/2006. - N. J. A. Sloane, Aug 14 2016
From David James Sycamore, Apr 29 2020: (Start)
One of a family of fractal sequences, S_k; defined as follows for k >= 2: a(k*n) = n, a(k*n+r) = a((k-1)*n + (r-1)), r = 1..(k-1). S_2 is A025480; S_3 gives: a(3*n) = n, a(3*n + 1) = a(2*n), a(3*n + 2) = a(2*n + 1), which is A263390.
The subsequence of all nonzero terms is A131987. (End)
Similar to but different from A108202. - N. J. A. Sloane, Nov 26 2020
This sequence can be otherwise defined in two alternative (but related) ways, with a(0)=0, as follows: (i) If a(n) is a novel term, then a(n+1) = a(a(n)); if a(n) has been seen before, most recently at a(m), then a(n+1) = n-m (as in A181391). (ii) As above for novel a(n), then if a(n) has been seen before, a(n+1) = smallest k < a(n) which is not already a term. - David James Sycamore, Jul 13 2021
From a binary perspective, the sequence can be seen as even,odd pairs where the odd value is the previous even value, dropping the rightmost bits up to and including the lowest zero bit, aka right-shifted past the lowest clear bit. E.g., (5)101 -> 1, (17)10001 -> (4)100, (29)11101 -> (7)111, (39)100111 -> (2)10. - Joe Nellis, Oct 09 2022

			From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)
The sequence can be constructed as a triangle as:
  0
  0  1
  0  2  1  3
  0  4  2  5  1  6  3  7
  0  8  4  9  2 10  5 11  1 12  6 13  3 14  7 15
  ...
At each stage we interleave the next 2^m numbers in the previous row. (End)
Left=0/1, Right=1/0: StB=A007305/A047679; Left=0/1, Right=1/1: StB=A007305/A007306; Left=1/3, Right=2/3: StB=A153161/A153162. - _Reinhard Zumkeller_, Dec 22 2008

L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
Ralf Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.4.
L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Ralf Stephan, Some divide-and-conquer sequences ....
Ralf Stephan, Table of generating functions.
Paul Tarau, A Groupoid of Isomorphic Data Transformations, Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
Index entries for sequences related to the Josephus Problem.

The Y-projection of A075300.

Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381, A131987, A263390, A181391, A007814.

import Data.List
interleave xs ys = concat . transpose $ [xs,ys]
a025480 = interleave [0..] a025480
-- Cale Gibbard, Nov 18 2009

Cf. comments by Worthen and Hasler.
import Data.List (transpose)
a025480 n k = a025480_tabf !! n !! k
a025480_row n = a025480_tabf !! n
a025480_tabf = iterate (\xs -> concat $
   transpose [xs, [length xs .. 2 * length xs - 1]]) [0]
a025480_list = concat $ a025480_tabf
-- Reinhard Zumkeller, Apr 29 2012

A025480 := proc(n)
    option remember ;
    if type(n,'even') then
        n/2 ;
    else
        procname((n-1)/2) ;
    end if;
end proc:
seq(A025480(n),n=0..100) ; # R. J. Mathar, Jul 16 2020

a[n_] := a[n] = If[OddQ@n, a[(n - 1)/2], n/2]; Table[ a[n], {n, 0, 83}] (* Robert G. Wilson v, Mar 30 2006 *)
Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* IWABUCHI Yu(u)ki, Oct 13 2012 *)

a(n)={while(n%2,n\=2);n\2} \\ M. F. Hasler, May 03 2008

A025480(n)=n>>valuation(n*2+2,2) \\ M. F. Hasler, Apr 12 2012

def A025480(n): return n>>((~(n+1)&n).bit_length()+1) # Chai Wah Wu, Jul 13 2022

A025480 = lambda n: odd_part(n+1)//2
[A025480(n) for n in (0..83)] # Peter Luschny, May 20 2014

a(n) = A003602(n+1) - 1. [Corrected by Max Alekseyev, May 05 2022]
a(n) = (A000265(n+1)-1)/2 = ((n+1)/A006519(n+1)-1)/2.
a(n) = A153733(n)/2. - Reinhard Zumkeller, Dec 31 2008
2^A007814(n+1)*(2*a(n)+1) = n+1. (See functions hd, tl and cons in [Paul Tarau 2009].) - Paul Tarau (paul.tarau(AT)gmail.com), Mar 21 2010
a(3*n + 1) = A173732(n). - Reinhard Zumkeller, Apr 29 2012
a((2*n+1)*2^p-1) = n, p >= 0 and n >= 0. - Johannes W. Meijer, Jan 24 2013
a(n) = n - A225381(n). - Marcus Hedbring, May 18 2013
G.f.: -1/(1-x) + Sum_{k>=0} x^(2^k-1)/(1-2*x^2^(k+1)+x^2^(k+2)). - Ralf Stephan, May 19 2013
a(n) = A049084(A181363(n+1)). - Reinhard Zumkeller, Mar 22 2014
a(n) = floor(n / 2^A001511(n+1)). - Adam Shelly, Mar 05 2019
Recursion: a(0) = 0; a(n + 1) = a(a(n)) if a(n) is a first occurrence of a term, else a(n + 1) = n - a(n-1). - David James Sycamore, Apr 29 2020
a(n) * 2^(A007814(n+1)+1) + 2^A007814(n+1) - 1 = n (equivalent to the formula given in the comment by Paul Tarau). - Ruud H.G. van Tol, Apr 14 2023
Sum_{k=1..n} a(k) = n^2/6 + O(n). - Amiram Eldar, Aug 07 2023

Edited by M. F. Hasler, Mar 16 2018

A007305 Numerators of Farey (or Stern-Brocot) tree fractions.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 5, 4, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9, 6, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11

Offset: 0

N. J. A. Sloane

From Yosu Yurramendi, Jun 25 2014: (Start)
If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
   1,
   1,2,
   1,2,3,3,
   1,2,3,3,4,5,5,4,
   1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,
   1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,
then the sum of the m-th row is 3^m (m = 0,1,2,), each column k is constant, and the constants are from A007306, denominators of Farey (or Stern-Brocot) tree fractions (see formula).
If the rows are written in a right-aligned fashion:
                                                                          1,
                                                                        1,2,
                                                                   1, 2,3,3,
                                                       1, 2, 3, 3, 4, 5,5,4,
                                  1,2, 3, 3, 4, 5, 5,4,5, 7, 8, 7, 7, 8,7,5,
  1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,
then each column is an arithmetic sequence. The differences of the arithmetic sequences also give the sequence A007306 (see formula). The first terms of columns are from A007305 itself (a(A004761(n+1)) = a(n), n>0), and the second ones from A049448 (a(A004761(n+1)+2^A070941(n)) = A049448(n), n>0). (End)
If the sequence is considered in blocks of length 2^m, m = 0,1,2,..., the blocks are the reverse of the blocks of A047679: (a(2^m+1+k) = A047679(2^(m+1)-2-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). - Yosu Yurramendi, Jun 30 2014

			A007305/A007306 = [ 0/1; 1/1; ] 1/2; 1/3, 2/3; 1/4, 2/5, 3/5, 3/4; 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, ...
Another version of Stern-Brocot is A007305/A047679 = 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5, 5, 1/5, 5/4, 4/5, ...

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..4096
A. Bogomolny, Stern-Brocot Tree
A. Bogomolny, Inspiration for Maple code
A. Brocot, Calcul des rouages par approximation, nouvelle méthode, Revue Chonométrique 3, 186-194, 1861.
G. A. Jones, The Farey graph, Séminaire Lotharingien de Combinatoire, B18e (1987), 2 pp.
Shin-ichi Katayama, Modified Farey trees and Pythagorean triples, Journal of mathematics, the University of Tokushima, 47, 2013.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
Hugo Pfoertner, Ratio A007305(n)/A007306(n) vs n, using Plot 2.
N. J. A. Sloane, Stern-Brocot or Farey Tree
Noam Zimhoni, A forest of Eisensteinian triplets, arXiv:1904.11782 [math.NT], 2019.
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

Cf. A007306, A006842, A006843, A047679, A054424, A057114, A152975.

A007305 := proc(n) local b; b := proc(n) option remember; local msb, r;
if n < 3 then return 1 fi; msb := ilog2(n); r := n - 2^msb;
if ilog2(r) = msb - 1 then b(r) + b(3*2^(msb-1) - r - 1) else b(2^(msb - 1) + r) fi end: if n = 0 then 0 else b(n-1) fi end: # Antti Karttunen, Mar 19 2000 [Corrected and rewritten by Peter Luschny, Apr 24 2024]
seq(A007305(n), n = 0..92);

sbt[n_] := Module[{R,L,Y}, R={{1,0},{1,1}}; L={{1,1},{0,1}}; Y={{1,0},{0,1}}; w[b_] := Fold[ #1.If[ #2 == 0,L,R] &,Y,b]; u[a_] := {a[[2,1]]+a[[2,2]],a[[1,1]]+a[[1,2]]}; Map[u,Map[w,Tuples[{0,1},n]]]]
A007305(n) = Flatten[Append[{0,1},Table[Map[First,sbt[i]],{i,0,5}]]]
A047679(n) = Flatten[Table[Map[Last,sbt[i]],{i,0,5}]]
(* Peter Luschny, Apr 27 2009 *)

a <- 1
for(m in 1:6) for(k in 0:(2^(m-1)-1)) {
  a[2^m+        k] <- a[2^(m-1)+k]
  a[2^m+2^(m-1)+k] <- a[2^(m-1)+k] + a[2^m-k-1]
}
a
# Yosu Yurramendi, Jun 25 2014

a(n) = SternBrocotTreeNum(n-1) # n starting from 2 gives the sequence from 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 5, 4, 1, ...
From Reinhard Zumkeller, Dec 22 2008: (Start)
For n > 1: a(n+2) = if A025480(n-1) != 0 and A025480(n) != 0 then a(A025480(n-1)+2) + a(A025480(n)+2) else if A025480(n)=0 then a(A025480(n-1)+2)+1 else 0 + a(A025480(n-1)+2).
a(A054429(n)+2) = A047679(n).
a(n+2) = A047679(A054429(n)).
A153036(n+1) = floor(a(n+2)/A047679(n)). (End)
From Yosu Yurramendi, Jun 25 2014: (Start)
For m = 1,2,3,..., and k = 0,1,2,...,2^(m-1)-1, with a(1)=1:
a(2^m+k) = a(2^(m-1)+k);
a(2^m+2^(m-1)+k) = a(2^(m-1)+k) + a(2^m-k-1). (End)
a(2^(m+2)-k) = A007306(2^(m+1)-k), m=0,1,2,..., k=0,1,2,...,2^m-1. - Yosu Yurramendi, Jul 04 2014
a(2^(m+1)+2^m+k) - a(2^m+k) = A007306(2^m-k+1), m=1,2,..., k=1,2,...,2^(m-1). - Yosu Yurramendi, Jul 05 2014
From Yosu Yurramendi, Jan 01 2015: (Start)
a(2^m+2^q-1) = q+1, q = 0, 1, 2,..., m = q, q+1, q+2,...
a(2^m+2^q)   = q+2, q = 0, 1, 2,..., m = q+1, q+2, q+3,... (End)
a(2^m+k) = A007306(k+1), m >= 0, 0 <= k < 2*m.  - Yosu Yurramendi, May 20 2019
a(n) = A002487(A059893(n)), n > 0. - Yosu Yurramendi, Sep 29 2021

A006843 Triangle read by rows: row n gives denominators of Farey series of order n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 2, 3, 1, 1, 4, 3, 2, 3, 4, 1, 1, 5, 4, 3, 5, 2, 5, 3, 4, 5, 1, 1, 6, 5, 4, 3, 5, 2, 5, 3, 4, 5, 6, 1, 1, 7, 6, 5, 4, 7, 3, 5, 7, 2, 7, 5, 3, 7, 4, 5, 6, 7, 1, 1, 8, 7, 6, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 6, 7, 8, 1, 1, 9, 8, 7, 6, 5, 9, 4, 7, 3, 8, 5, 7, 9, 2, 9, 7, 5, 8, 3, 7, 4, 9, 5, 6, 7, 8, 9, 1

Offset: 1

N. J. A. Sloane

			0/1, 1/1;
0/1, 1/2, 1/1;
0/1, 1/3, 1/2, 2/3, 1/1;
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1;
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1;
... = A006842/A006843.

J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152.
Martin Gardner, The Last Recreations, Chapter 12: Strong Laws of Small Primes, Springer-Verlag, 1997, pp. 191-205, especially p. 199.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
A. O. Matveev, Farey Sequences, De Gruyter, 2017.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..10563
R. K. Guy, The strong law of small numbers, Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Andrey O. Matveev, Neighboring Fractions in Farey Subsequences, arXiv:0801.1981 [math.NT], 2008-2010.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
N. J. A. Sloane, Stern-Brocot or Farey Tree
Eric Weisstein's World of Mathematics, Farey Sequence.
Index entries for sequences related to Stern's sequences

Row n has A005728(n) terms. - Michel Marcus, Jun 27 2014
Row sums give A240877.
Cf. A006842 (numerators), A049455, A049456, A007305, A007306.
See also A177405/A177407.

Farey := proc(n) sort(convert(`union`({0},{seq(seq(m/k,m=1..k),k=1..n)}),list)) end: seq(denom(Farey(i)),i=1..5); # Peter Luschny, Apr 28 2009

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Denominator[ Farey[n]], {n, 9}]] (* Robert G. Wilson v, Apr 08 2004 *)
Table[Denominator[FareySequence[n]],{n,10}]//Flatten (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Oct 04 2016 *)

row(n) = {vf = [0]; for (k=1, n, for (m=1, k, vf = concat(vf, m/k););); vf = vecsort(Set(vf)); for (i=1, #vf, print1(denominator(vf[i]), ", "));} \\ Michel Marcus, Jun 27 2014

More terms from Robert G. Wilson v, Apr 08 2004

Changed offset (=order of first row) to 1 by R. J. Mathar, Apr 26 2009

A006842 Triangle read by rows: row n gives numerators of Farey series of order n.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 1, 2, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 3, 4, 1, 0, 1, 1, 1, 1, 2, 1, 3, 2, 3, 4, 5, 1, 0, 1, 1, 1, 1, 2, 1, 2, 3, 1, 4, 3, 2, 5, 3, 4, 5, 6, 1, 0, 1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 5, 6, 7, 1, 0, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 3, 4, 1, 5, 4, 3, 5, 2, 5, 3, 7, 4, 5, 6, 7, 8, 1

Offset: 1

N. J. A. Sloane

			0/1, 1/1;
0/1, 1/2, 1/1;
0/1, 1/3, 1/2, 2/3, 1/1;
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1;
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1;
... = A006842/A006843

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923. See Vol. 1.
Guthery, Scott B. A motif of mathematics. Docent Press, 2011.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
A. O. Matveev, Farey Sequences, De Gruyter, 2017.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..10563
Maxim Bruckheimer and Abraham Arcavi, Farey series and Pick’s area theorem, The Mathematical Intelligencer, 17.4 (1995): 64-67.
Cristian Cobeli and Alexandru Zaharescu, The Haros-Farey sequence at two hundred years, Acta Univ. Apulensis Math. Inform 5 (2003): 1-38.
Andrey O. Matveev, Neighboring Fractions in Farey Subsequences, arXiv:0801.1981 [math.NT], 2008-2010.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
N. J. A. Sloane, Stern-Brocot or Farey Tree
Eric Weisstein's World of Mathematics, Farey Sequence.
Index entries for sequences related to Stern's sequences

Row n has A005728(n) terms. - Michel Marcus, Jun 27 2014

Cf. A006843 (denominators), A049455, A049456, A007305, A007306. Also A177405/A177407.

Farey := proc(n) sort(convert(`union`({0},{seq(seq(m/k,m=1..k),k=1..n)}),list)) end: seq(numer(Farey(i)),i=1..5); # Peter Luschny, Apr 28 2009

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Numerator[ Farey[n]], {n, 0, 9}]] (* Robert G. Wilson v, Apr 08 2004 *)
Table[FareySequence[n] // Numerator, {n, 1, 9}] // Flatten (* Jean-François Alcover, Sep 25 2018 *)

row(n) = {vf = [0]; for (k=1, n, for (m=1, k, vf = concat(vf, m/k););); vf = vecsort(Set(vf)); for (i=1, #vf, print1(numerator(vf[i]), ", "));} \\ Michel Marcus, Jun 27 2014

More terms from Robert G. Wilson v, Apr 08 2004

A047679 Denominators in full Stern-Brocot tree.

Original entry on oeis.org

1, 2, 1, 3, 3, 2, 1, 4, 5, 5, 4, 3, 3, 2, 1, 5, 7, 8, 7, 7, 8, 7, 5, 4, 5, 5, 4, 3, 3, 2, 1, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9, 6, 5, 7, 8, 7, 7, 8, 7, 5, 4, 5, 5, 4, 3, 3, 2, 1, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19, 17, 18

Offset: 0

Wouter Meeussen

Numerators are A007305.
Write n in binary; list run lengths; add 1 to last run length; make into continued fraction. Sequence gives denominator of fraction obtained.
From Reinhard Zumkeller, Dec 22 2008: (Start)
  For n > 1: a(n) = if A025480(n-1) != 0 and A025480(n) != 0 then = a(A025480(n-1)) + a(A025480(n)) else if A025480(n)=0 then a(A025480(n-1))+0 else 1+a(A025480(n-1));
  a(n) = A007305(A054429(n)+2) and a(A054429(n)) = A007305(n+2);
  A153036(n+1) = floor(A007305(n+2)/a(n)). (End)
From Yosu Yurramendi, Jun 25 2014 and Jun 30 2014: (Start)
If the terms are written as an array a(m, k) = a(2^(m-1)-1+k) with m >= 1 and k = 0, 1, ..., 2^(m-1)-1:
 1,
 2,1,
 3,3, 2, 1,
 4,5, 5, 4, 3, 3, 2,1,
 5,7, 8, 7, 7, 8, 7,5,4, 5, 5, 4, 3, 3,2,1,
 6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,5,7,8,7,7,8,7,5,4,5,5,4,3,3,2,1,
then the sum of the m-th row is 3^(m-1), and each column is an arithmetic sequence. The differences of these arithmetic sequences give the sequence A007306(k+1). The first terms of columns are 1 for k = 0 and a(k-1) for k >= 1.
In a row reversed version A(m, k) = a(m, m-(k+1)):
 1
 1,2
 1,2,3,3,
 1,2,3,3,4,5,5,4
 1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5
 1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,12,9,9,12,13,11,10,11,9,6
each column k >= 0 is constant, namely A007306(k+1).
This row reversed version coincides with the array for A007305 (see the Jun 25 2014 comment there). (End)
Looking at the plot, the sequence clearly shows a fractal structure. (The repeating pattern oddly resembles the [first completed] facade of the Sagrada Familia!) - Daniel Forgues, Nov 15 2019

			E.g., 57->111001->[ 3,2,1 ]->[ 3,2,2 ]->3 + 1/(2 + 1/(2) ) = 17/2. For n=1,2, ... we get 2, 3/2, 3, 4/3, 5/3, 5/2, 4, 5/4, 7/5, 8/5, ...
1; 2,1; 3,3,2,1; 4,5,5,4,3,3,2,1; ....
Another version of Stern-Brocot is A007305/A047679 = 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5, 5, 1/5, 5/4, 4/5, ...

Alois P. Heinz, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

Cf. A007305, A007306, A054424, A152976.

CFruns[ n_Integer ] := Fold[ #2+1/#1&, Infinity, Reverse[ MapAt[ #+1&, Length/@Split[ IntegerDigits[ n, 2 ] ], {-1} ] ] ]
(* second program: *)
a[n_] := Module[{LL = Length /@ Split[IntegerDigits[n, 2]]}, LL[[-1]] += 1; FromContinuedFraction[LL] // Denominator]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 25 2016 *)

{a(n) = local(v, w); v = binary(n++); w = [1]; for( n=2, #v, if( v[n] != v[n-1], w = concat(w, 1), w[#w]++)); w[#w]++; contfracpnqn(w)[2, 1]} /* Michael Somos, Jul 22 2011 */

a <- 1
for(m in 1:6) for(k in 0:(2^(m-1)-1)) {
  a[2^m+        k] = a[2^(m-1)+k] + a[2^m-k-1]
  a[2^m+2^(m-1)+k] = a[2^(m-1)+k]
}
a
# Yosu Yurramendi, Dec 31 2014

a(n) = SternBrocotTreeDen(n) # n starting from 1.
From Yosu Yurramendi, Jul 02 2014: (Start)
For m >0 and 0 <= k < 2^(m-1), with a(0)=1, a(1)=2:
a(2^m+k-1) = a(2^(m-1)+k-1) + a((2^m-1)-k-1);
a(2^m+2^(m-1)+k-1) = a(2^(m-1)+k-1). (End)
a(2^m-2^q  ) = q+1, q >= 0, m > q
a(2^m-2^q-1) = q+2, q >= 0, m > q+1. - Yosu Yurramendi, Jan 01 2015
a(2^(m+1)-1-k) = A007306(k+1), m >= 0, 0 <= k <= 2^m. - Yosu Yurramendi, May 20 2019
a(n) = A002487(1+A059893(n)), n > 0. - Yosu Yurramendi, Sep 29 2021

Edited by Wolfdieter Lang, Mar 31 2015

A049456 Triangle T(n,k) = denominator of fraction in k-th term of n-th row of variant of Farey series. This is also Stern's diatomic array read by rows (version 1).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 2, 3, 1, 1, 4, 3, 5, 2, 5, 3, 4, 1, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13

Offset: 1

N. J. A. Sloane

Row n has length 2^(n-1) + 1.
A049455/a(n) gives another version of the Stern-Brocot tree.
Define mediant of a/b and c/d to be (a+c)/(b+d). We get A006842/A006843 if we omit terms from n-th row in which denominator exceeds n.
Largest term of n-th row = A000045(n+1), Fibonacci numbers. - Reinhard Zumkeller, Apr 02 2014

			0/1, 1/1; 0/1, 1/2, 1/1; 0/1, 1/3, 1/2, 2/3, 1/1; 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1; 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, ... = A049455/A049456
Array begins
1...............................1
1...............2...............1
1.......3.......2.......3.......1
1...4...3...5...2...5...3...4...1
1.5.4.7.3.8.5.7.2.7.5.8.3.7.4.5.1
.................................

J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

Reinhard Zumkeller, Rows n = 1..13 of table, flattened
C. Giuli and R. Giuli, A primer on Stern's diatomic sequence, Fib. Quart., 17 (1979), 103-108, 246-248 and 318-320 (but beware errors).
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(2) 1929, pp. 59-67.
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]
M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for sequences related to Stern's sequences

Coincides with A002487 if pairs of adjacent 1's are replaced by single 1's.
Cf. A049455, A007305, A007306, A006842, A006843, A064881-A064886, A070878, A070879.
Cf. A000051 (row lengths), A034472 (row sums), A293160 (distinct terms in each row).

import Data.List (transpose)
a049456 n k = a049456_tabf !! (n-1) !! (k-1)
a049456_row n = a049456_tabf !! (n-1)
a049456_tabf = iterate
   (\row -> concat $ transpose [row, zipWith (+) row $ tail row]) [1, 1]
-- Reinhard Zumkeller, Apr 02 2014

A049456 := proc(n,k)
    option remember;
    if n =1 then
        if k >= 0 and k <=1 then
            1;
        else
            0 ;
        end if;
    elif type(k,'even') then
        procname(n-1,k/2) ;
    else
        procname(n-1,(k+1)/2)+procname(n-1,(k-1)/2) ;
    end if;
end proc: # R. J. Mathar, Dec 12 2014

Flatten[NestList[Riffle[#,Total/@Partition[#,2,1]]&,{1,1},10]] (* Harvey P. Dale, Mar 16 2013 *)

Each row is obtained by copying the previous row but interpolating the sums of pairs of adjacent terms. E.g. after 1 2 1 we get 1 1+2 2 2+1 1.

Row 1 of Farey tree is 0/1, 1/1. Obtain row n from row n-1 by inserting mediants between each pair of terms.

Previous Showing 21-30 of 94 results. Next

cp's OEIS Frontend

A335699 Irregular tree read by rows: take the Stern-Brocot tree A007305(n)/A007306(n) and set a(n) = A007306(n) - A007305(n) mod 3.

Views

Author

Keywords

Examples

Links

Crossrefs

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Python

R

R

R

Sage

Scheme

Formula

Extensions

A016777 a(n) = 3*n + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Maxima

PARI

SageMath

Formula

Extensions

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A025480 a(2n) = n, a(2n+1) = a(n).

Views

Author

Keywords

Comments

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2n) = a(n), a(2n+1) = a(n) + a(n+1).