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.
%I A007306 M0437 #316 Feb 16 2025 08:32:31
%S A007306 1,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,
%T A007306 11,9,6,7,11,14,13,15,18,17,13,14,19,21,18,17,19,16,11,11,16,19,17,18,
%U A007306 21,19,14,13,17,18,15,13,14,11,7,8,13,17,16,19,23,22,17,19,26,29,25,24
%N A007306 Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).
%C A007306 Also number of odd entries in n-th row of triangle of Stirling numbers of the second kind (A008277). - _Benoit Cloitre_, Feb 28 2004
%C A007306 Apparently (except for the first term) the number of odd entries in the alternated diagonals of Pascal's triangle at 45 degrees slope. - Javier Torres (adaycalledzero(AT)hotmail.com), Jul 26 2009
%C A007306 The Kn3 and Kn4 triangle sums, see A180662 for their definitions, of Sierpiński's triangle A047999 equal a(n+1). - _Johannes W. Meijer_, Jun 05 2011
%C A007306 From _Yosu Yurramendi_, Jun 23 2014: (Start)
%C A007306 If the terms (n>1) are written as an array:
%C A007306 2,
%C A007306 3, 3,
%C A007306 4, 5, 5, 4,
%C A007306 5, 7, 8, 7, 7, 8, 7, 5,
%C A007306 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9, 6,
%C A007306 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19,17,18,
%C A007306 then the sum of the k-th row is 2*3^(k-2), each column is an arithmetic progression. The differences of the arithmetic progressions give the sequence itself (a(2^(m+1)+1+k) - a(2^m+1+k) = a(k+1), m >= 1, 1 <= k <= 2^m), because a(n) = A002487(2*n-1) and A002487 has these properties. A071585 also has these properties. Each row is a palindrome: a(2^(m+1)+1-k) = a(2^m+k), m >= 0, 1 <= k <= 2^m.
%C A007306 If the terms (n>0) are written in this way:
%C A007306 1,
%C A007306 2, 3,
%C A007306 3, 4, 5, 5,
%C A007306 4, 5, 7, 8, 7, 7, 8, 7,
%C A007306 5, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9,
%C A007306 6, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19,
%C A007306 each column is an arithmetic progression and the steps also give the sequence itself (a(2^(m+1)+k) - a(2^m+k) = a(k), m >= 0, 0 <= k < 2^m). Moreover, by removing the first term of each column:
%C A007306 a(2^(m+1)+k) = A049448(2^m+k+1), m >= 0, 0 <= k < 2^m.
%C A007306 (End)
%C A007306 k > 1 occurs in this sequence phi(k) = A000010(k) times. - _Franklin T. Adams-Watters_, May 25 2015
%C A007306 Except for the initial 1, this is the odd bisection of A002487. The even bisection of A002487 is A002487 itself. - _Franklin T. Adams-Watters_, May 25 2015
%C A007306 For all m >= 0, max_{k=1..2^m} a(2^m+k) = A000045(m+3) (Fibonacci sequence). - _Yosu Yurramendi_, Jun 05 2016
%C A007306 For all n >= 2, max(m: a(2^m+k) = n, 1<=k<=2^m) = n-2. - _Yosu Yurramendi_, Jun 05 2016
%C A007306 a(2^m+1) = m+2, m >= 0; a(2^m+2) = 2m+1, m>=1; min_{m>=0, k=1..2^m} a(2^m+k) = m+2; min_{m>=2, k=2..2^m-1} a(2^m+k) = 2m+1. - _Yosu Yurramendi_, Jun 06 2016
%C A007306 a(2^(m+2) + 2^(m+1) - k) - a(2^(m+1) + 2^m-k) = 2*a(k+1), m >= 0, 0 <= k <= 2^m. - _Yosu Yurramendi_, Jun 09 2016
%C A007306 If the initial 1 is omitted, this is the number of nonzero entries in row n of the generalized Pascal triangle P_2, see A282714 [Leroy et al., 2017]. - _N. J. A. Sloane_, Mar 02 2017
%C A007306 Apparently, this sequence was introduced by Johann Gustav Hermes in 1894. His paper gives a strong connection between this sequence and the so-called "Gaussian brackets" ("Gauss'schen Klammer"). For an independent discussion about Gaussian brackets, see the relevant MathWorld article and the article by Herzberger (1943). Srinivasan (1958) gave another, more modern, explanation of the connection between this sequence and the Gaussian brackets. (Parenthetically, J. G. Hermes is the mathematician who completed or constructed the regular polygon with 65537 sides.) - _Petros Hadjicostas_, Sep 18 2019
%D A007306 P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 61.
%D A007306 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, p. 158.
%D A007306 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.
%D A007306 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007306 Alois P. Heinz, <a href="/A007306/b007306.txt">Table of n, a(n) for n = 0..10000</a>
%H A007306 Suayb S. Arslan, <a href="https://arxiv.org/abs/1709.07446">Asymptotically MDS Array BP-XOR Codes</a>, arXiv:1709.07949 [cs.IT], 2017.
%H A007306 Alexander Bogomolny, <a href="http://www.cut-the-knot.org/blue/Stern.shtml">Stern-Brocot tree</a>.
%H A007306 J. Hermes, <a href="https://eudml.org/doc/157736">Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden (The number of partitions of a rational integer, Part I)</a>, Mathematischen Annalen 45(3) (1894), 371-380.
%H A007306 J. Hermes, <a href="https://doi.org/10.1007/BF01446684">Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden (The number of partitions of a rational integer, Part I)</a>, Mathematischen Annalen 45(3) (1894), 371-380.
%H A007306 J. Hermes, <a href="https://doi.org/10.1007/BF01447271">Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden, II (The number of partitions of a rational integer, Part II)</a>, Mathematischen Annalen 47(2-3) (1896), 281-297.
%H A007306 M. Herzberger, <a href="https://doi.org/10.1364/JOSA.33.000651">Gaussian optics and Gaussian brackets</a>, Journal of the Optical Society of America 33(12) (1943), 651-655. [This paper gives a clear description of Gaussian brackets that are related to this sequence as explained by Hermes (1894).]
%H A007306 Jennifer Lansing, <a href="http://hdl.handle.net/2142/49483">On the Stern sequence and a related sequence</a>, Ph.D. dissertation in Mathematics, University of Illinois at Urbana-Champaign, 2014. [This doctoral dissertation discusses the so-called Stern sequence on which Hermes' papers are based (according to Srinivasan (1958)).]
%H A007306 Julien Leroy, Michel Rigo, and Manon Stipulanti, <a href="http://dx.doi.org/10.1016/j.disc.2017.01.003">Counting the number of non-zero coefficients in rows of generalized Pascal triangles</a>, Discrete Mathematics 340 (2017), 862-881.
%H A007306 Julien Leroy, Michel Rigo, and Manon Stipulanti, <a href="http://math.colgate.edu/~integers/sjs13/sjs13.Abstract.html">Counting subword occurrences in base-b expansions</a>, Integers (2018) 18A, Article #A13.
%H A007306 G. Melançon, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00123-5">Lyndon factorization of sturmian words</a>, Discr. Math. 210 (2000), 137-149.
%H A007306 N. J. A. Sloane, <a href="/stern_brocot.html">Stern-Brocot or Farey Tree</a>.
%H A007306 M. S. Srinivasan, <a href="https://www.ias.ac.in/article/fulltext/seca/047/01/0012-0024">The enumeration of positive rational numbers</a>, Proc. Indian Acad. Sci. Sect. A 47 (1958), 12-24.
%H A007306 M. Stern, <a href="https://eudml.org/doc/147729">Über eine zahlentheoretische Function</a>, Journal für die reine und angewandte Mathematik 55 (1858), 193-220. [According to Srinivasan (1958), Hermes's (1894) paper, where this sequence is introduced, is based on Stern's sequence.]
%H A007306 Manon Stipulanti, <a href="https://arxiv.org/abs/1801.03287">Convergence of Pascal-Like Triangles in Parry-Bertrand Numeration Systems</a>, arXiv:1801.03287 [math.CO], 2018.
%H A007306 Javier Torres Suarez, <a href="https://www.youtube.com/watch?v=__Re3zKM9n8">Number theory - geometric connection (part 2)</a> (YouTube video that mentions this sequence - link sent by Pacha Nambi, Aug 26 2009).
%H A007306 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GaussianBrackets.html">Gaussian brackets</a>; they are related to this sequence.
%H A007306 Wikipedia, <a href="https://en.wikipedia.org/wiki/Johann_Gustav_Hermes">Johann Gustav Hermes</a>. [He is the person who introduced this sequence and the person who completed or constructed a regular polygon with 65537 sides.]
%H A007306 <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%H A007306 <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%F A007306 Recurrence: a(0) to a(8) are 1, 1, 2, 3, 3, 4, 5, 5, 4; thereafter a(n) = a(n-2^p) + a(2^(p+1)-n+1), where 2^p < n <= 2^(p+1). [J. Hermes, Math. Ann., 1894; quoted by Dickson, Vol. 1, p. 158] - _N. J. A. Sloane_, Mar 24 2019
%F A007306 a(4*n) = -a(n)+2*a(2*n); a(4*n+1) = -a(n)+a(2*n)+a(2*n+1); a(4*n+2)=a(n)-a(2*n)+2*a(2*n+1); a(4*n+3) = 4*a(n)-4*a(2*n)+3*a(2*n+1). Thus a(n) is a 2-regular sequence. - _Jeffrey Shallit_, Dec 26 2024
%F A007306 For n > 0, a(n) = A002487(n-1) + A002487(n) = A002487(2*n-1).
%F A007306 a(0) = 1; a(n) = Sum_{k=0..n-1} C(n-1+k, n-1-k) mod 2, n > 0. - _Benoit Cloitre_, Jun 20 2003
%F A007306 a(n+1) = Sum_{k=0..n} binomial(2*n-k, k) mod 2; a(n) = 0^n + Sum_{k=0..n-1} binomial(2(n-1)-k, k) mod 2. - _Paul Barry_, Dec 11 2004
%F A007306 a(n) = Sum_{k=0..n} C(n+k,2*k) mod 2. - _Paul Barry_, Jun 12 2006
%F A007306 a(0) = a(1) = 1; a(n) = a(A003602(n-1)) + a(A003602(n)), n > 1. - _Alessandro De Luca_, May 08 2014
%F A007306 a(n) = A007305(n+(2^m-1)), m=A029837(n), n=1,2,3,... . - _Yosu Yurramendi_, Jul 04 2014
%F A007306 a(n) = A007305(2^(m+1)-n) - A007305(2^m-n), m >= (A029837(n)+1), n=1,2,3,... - _Yosu Yurramendi_, Jul 05 2014
%F A007306 a(2^m) = m+1, a(2^m+1) = m+2 for m >= 0. - _Yosu Yurramendi_, Jan 01 2015
%F A007306 a(n+2) = A007305(n+2) + A047679(n) n >= 0. - _Yosu Yurramendi_, Mar 30 2016
%F A007306 a(2^m+2^r+k) = a(2^r+k)(m-r+1) - a(k), m >= 2, 0 <= r <= m-1, 0 <= k < 2^r. Example: a(73) = a(2^6+2^3+1) = a(2^3+1)*(6-3+1) - a(1) = 5*4 - 1 = 19 . - _Yosu Yurramendi_, Jul 19 2016
%F A007306 From _Antti Karttunen_, Mar 21 2017 & Apr 12 2017: (Start)
%F A007306 For n > 0, a(n) = A001222(A277324(n-1)) = A001222(A260443(n-1)*A260443(n)).
%F A007306 The following decompositions hold for all n > 0:
%F A007306 a(n) = A277328(n-1) + A284009(n-1).
%F A007306 a(n) = A283986(n) + A283988(n) = A283987(n) + 2*A283988(n).
%F A007306 a(n) = 2*A284265(n-1) + A284266(n-1).
%F A007306 a(n) = A284267(n-1) + A284268(n-1).
%F A007306 a(n) = A284565(n-1) + A284566(n-1).
%F A007306 a(n) = A285106(n-1) + A285108(n-1) = A285107(n-1) + 2*A285108(n-1). (End)
%F A007306 a(A059893(n)) = a(n+1) for n > 0. - _Yosu Yurramendi_, May 30 2017
%F A007306 a(n) = A287731(n) + A287732(n) for n > 0. - _I. V. Serov_, Jun 09 2017
%F A007306 a(n) = A287896(n) + A288002(n) for n > 1.
%F A007306 a(n) = A287896(n-1) + A002487(n-1) - A288002(n-1) for n > 1.
%F A007306 a(n) = a(n-1) + A002487(n-1) - 2*A288002(n-1) for n > 1. - _I. V. Serov_, Jun 14 2017
%F A007306 From _Yosu Yurramendi_, May 14 2019: (Start)
%F A007306 For m >= 0, M >= m, 0 <= k < 2^m,
%F A007306 a((2^(m+1) + A119608(2^m+k+1))*2^(M-m) - A000035(2^m+k)) =
%F A007306 a((2^(m+2) - A119608(2^m+k+1))*2^(M-m) - A000035(2^m+k)-1) =
%F A007306 a(2^(M+2) - (2^m+k)) = a(2^(M+1) + (2^m+k) + 1) =
%F A007306 a(2^m+k+1)*(M-m) + a(2^(m+1)+2^m+k+1). (End)
%F A007306 a(k) = sqrt(A007305(2^(m+1)+k)*A047679(2^(m+1)+k-2) - A007305(2^m+k)*A047679(2^m+k-2)), m >= 0, 0 <= k < 2^m. - _Yosu Yurramendi_, Jun 09 2019
%F A007306 G.f.: 1 + x * (1 + x) * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))). - _Ilya Gutkovskiy_, Jul 19 2019
%F A007306 Conjecture: a(n) = a(n-1) + b(n-1) - 2*(a(n-1) mod b(n-1)) for n > 1 with a(0) = a(1) = 1 where b(n) = a(n) - b(n-1) for n > 1 with b(1) = 1. - _Mikhail Kurkov_, Mar 13 2022
%e 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; ...
%p A007306 A007306 := proc(n): if n=0 then 1 else A002487(2*n-1) fi: end: A002487 := proc(m) option remember: 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(A007306(n),n=0..77); # _Johannes W. Meijer_, Jun 05 2011
%t A007306 a[0] = 1; a[n_] := Sum[ Mod[ Binomial[n+k-1, 2k] , 2], {k, 0, n}]; Table[a[n], {n, 0, 77}] (* _Jean-François Alcover_, Dec 16 2011, after _Paul Barry_ *)
%t A007306 a[0] = 0; a[1] = 1;
%t A007306 Flatten[{1,Table[a[2*n] = a[n]; a[2*n + 1] = a[n] + a[n + 1], {n, 0, 50}]}] (* _Horst H. Manninger_, Jun 09 2021 *)
%o A007306 (PARI) {a(n) = if( n<1, n==0, n--; sum( k=0, n, binomial( n+k, n-k)%2))};
%o A007306 (PARI) {a(n) = my(m); if( n<2, n>=0, m = 2^length( binary( n-1)); a(n - m/2) + a(m-n+1))}; /* _Michael Somos_, May 30 2005 */
%o A007306 (Sage)
%o A007306 @CachedFunction
%o A007306 def a(n):
%o A007306 return a((odd_part(n-1)+1)/2)+a((odd_part(n)+1)/2) if n>1 else 1
%o A007306 [a(n) for n in (0..77)] # after _Alessandro De Luca_, _Peter Luschny_, May 20 2014
%o A007306 (Sage)
%o A007306 def A007306(n):
%o A007306 if n == 0: return 1
%o A007306 M = [1, 1]
%o A007306 for b in (n-1).bits():
%o A007306 M[b] = M[0] + M[1]
%o A007306 return M[1]
%o A007306 print([A007306(n) for n in (0..77)]) # _Peter Luschny_, Nov 28 2017
%o A007306 (R)
%o A007306 maxrow <- 6 # by choice
%o A007306 a <- c(1,2)
%o A007306 for(m in 0:maxrow) for(k in 1:2^m){
%o A007306 a[2^(m+1)+k ] <- a[2^m+k] + a[k]
%o A007306 a[2^(m+1)-k+1] <- a[2^m+k]
%o A007306 }
%o A007306 a
%o A007306 # _Yosu Yurramendi_, Jan 05 2015
%o A007306 (R)
%o A007306 # Given n, compute directly a(n)
%o A007306 # by taking into account the binary representation of n-1
%o A007306 # aa <- function(n){
%o A007306 b <- as.numeric(intToBits(n))
%o A007306 l <- sum(b)
%o A007306 m <- which(b == 1)-1
%o A007306 d <- 1
%o A007306 if(l > 1) for(j in 1:(l-1)) d[j] <- m[j+1]-m[j]+1
%o A007306 f <- c(1,m[1]+2) # In A002487: f <- c(0,1)
%o A007306 if(l > 1) for(j in 3:(l+1)) f[j] <- d[j-2]*f[j-1]-f[j-2]
%o A007306 return(f[l+1])
%o A007306 }
%o A007306 # a(0) = 1, a(1) = 1, a(n) = aa(n-1) n > 1
%o A007306 #
%o A007306 # Example
%o A007306 n <- 73
%o A007306 aa(n-1)
%o A007306 #
%o A007306 # _Yosu Yurramendi_, Dec 15 2016
%o A007306 (Scheme) (define (A007306 n) (if (zero? n) 1 (A002487 (+ n n -1)))) ;; Code for A002487 given in that entry. - _Antti Karttunen_, Mar 21 2017
%o A007306 (Python)
%o A007306 from sympy import binomial
%o A007306 def a(n):
%o A007306 return 1 if n<1 else sum(binomial(n + k - 1, 2*k) % 2 for k in range(n + 1))
%o A007306 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Mar 22 2017
%o A007306 (Python)
%o A007306 from functools import reduce
%o A007306 def A007306(n): return sum(reduce(lambda x,y:(x[0],sum(x)) if int(y) else (sum(x),x[1]),bin((n<<1)-1)[-1:2:-1],(1,0))) if n else 1 # _Chai Wah Wu_, May 18 2023
%o A007306 (Magma) [1] cat [&+[Binomial(n+k,2*k) mod 2: k in [0..n]]: n in [0..80]]; // _Vincenzo Librandi_, Jun 10 2019
%Y A007306 For numerators see A007305.
%Y A007306 Cf. A001222, A002487, A006842, A006843, A047679, A054424, A065674-A065675, A065810, A260443, A277324, A277328, A283986, A283987, A283988, A284009, A284265, A284266, A284267, A284268, A284565, A284566, A285106, A285107, A285108, A287731, A287732.
%Y A007306 See also A282714.
%K A007306 nonn,frac,tabf,nice
%O A007306 0,3
%A A007306 _N. J. A. Sloane_
%E A007306 Formula fixed and extended by _Franklin T. Adams-Watters_, Jul 07 2009
%E A007306 Incorrect Maple program removed by _Johannes W. Meijer_, Jun 05 2011