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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007306 Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).
(Formerly M0437)
46
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, 11, 9, 6, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19, 17, 18, 21, 19, 14, 13, 17, 18, 15, 13, 14, 11, 7, 8, 13, 17, 16, 19, 23, 22, 17, 19, 26, 29, 25, 24 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also number of odd entries in n-th row of triangle of Stirling numbers of the second kind (A008277). - Benoit Cloitre, Feb 28 2004

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

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

From Yosu Yurramendi, Jun 23 2014: (Start)

If the terms (n>1) are written as an array:

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,

7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19, 17, 18,

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.

If the terms (n>0) are written in this way:

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, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19,

each column is an arithmetic progression and the steps give also 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:

a(2^(m+1)+k) = A049448(2^m+k+1), m>=0, 0<=k<2^m .

(End)

k>1 occurs in this sequence phi(k) = A000010(k) times. - Franklin T. Adams-Watters, May 25 2015

Except for the initial one, this is the odd bisection of A002487. The even bisection of A002487 is A002487 itself. - Franklin T. Adams-Watters, May 25 2015

For all m>=0, max(a(2^m+k), 1<=k<=2^m) = A000045(m+3) (Fibonacci sequence). - Yosu Yurramendi, Jun 05 2016

For al n>=2, max(m: a(2^m+k) = n, 1<=k<=2^m) = n-2. - Yosu Yurramendi, Jun 05 2016

a(2^m+1) =  m+2, m>=0; a(2^m+2) = 2m+1, m>=1; min(a(2^m+k), m>=0, 1<=k<=2^m) = m+2; min(a(2^m+k), m>=2, 1<k<2^m) = 2m+1. - Yosu Yurramendi, Jun 06 2016

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

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

REFERENCES

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 61.

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.

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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Alexander Bogomolny, Stern-Brocot tree

Julien Leroy, Michel Rigo, Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics 340 (2017), 862-881.

G. Melancon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.

N. J. A. Sloane, Stern-Brocot or Farey Tree

Javier Torres Suarez, Number theory - geometric connection (part 2) (YouTube video that mentions this sequence - link sent by Pacha Nambi, Aug 26 2009)

Index entries for fraction trees

Index entries for sequences related to Stern's sequences

FORMULA

For n > 0, a(n) = A002487(n-1) + A002487(n) = A002487(2*n-1).

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

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

a(n) = Sum_{k=0..n} C(n+k,2*k) mod 2. - Paul Barry, Jun 12 2006

a(0) = a(1) = 1; a(n) = a(A003602(n-1)) + a(A003602(n)), n > 1. - Alessandro De Luca, May 08 2014

a(n) = A007305(n+(2^m-1)), m=A029837(n), n=1,2,3,... . - Yosu Yurramendi, Jul 04 2014

a(n) = A007305(2^(m+1)-n) - A007305(2^m-n), m>=(A029837(n)+1), n=1,2,3,... - Yosu Yurramendi, Jul 05 2014

a(2^m) = m+1, a(2^m+1) = m+2 for m >= 0. - Yosu Yurramendi, Jan 01 2015

a(n+2) = A007305(n+2) + A047679(n) n >= 0. - Yosu Yurramendi, Mar 30 2016

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

From Antti Karttunen, Mar 21 2017: (Start)

For n > 0, a(n) = A001222(A277324(n-1)) = A001222(A260443(n-1)*A260443(n)).

For n > 0, a(n) = A277328(n-1) + A284009(n-1).

For n > 0, a(n) = A283986(n) + A283988(n) = A283987(n) + 2*A283988(n).

(End)

EXAMPLE

[ 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; ...

MAPLE

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

MATHEMATICA

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

PROG

(PARI) {a(n) = if( n<1, n==0, n--; sum( k=0, n, binomial( n+k, n-k)%2))};

(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 */

(Sage)

@CachedFunction

def a(n):

    return a((odd_part(n-1)+1)/2)+a((odd_part(n)+1)/2) if n>1 else 1

[a(n) for n in (0..77)] # after Alessandro De Luca, Peter Luschny, May 20 2014

(R)

maxrow <- 6 # by choice

a <- c(1, 2)

for(m in 0:maxrow) for(k in 1:2^m){

  a[2^(m+1)+k  ] <- a[2^m+k] + a[k]

  a[2^(m+1)-k+1] <- a[2^m+k]

}

a

# Yosu Yurramendi, Jan 05 2015

(R)

# Given n, compute directly a(n)

# by taking into account the binary representation of n-1

#

a <- function(n){

   b <- as.numeric(intToBits(n-1))

l <- sum(b)

m <- rev(which(b == 1))-1

d <- 1

if(l > 1) for(j in 2:l) d[j] <- m[j-1]-m[j]+1

f <- d[1:2]

if(l > 2) for(j in 3:l) f[j] <- d[j]*f[j-1]-f[j-2]

s1   <-                  f[l]

if(l > 1) s2 <- (m[l]+1)*f[l]-f[l-1]

else      s2 <- (m[1]+1)*f[l]

return(s1+s2)

}

#

a(n)

# Yosu Yurramendi, Dec 15 2016

(Scheme) (define (A007306 n) (if (zero? n) 1 (A002487 (+ n n -1)))) ;; Code for A002487 given in that entry. - Antti Karttunen, Mar 21 2017

(Python)

from sympy import binomial

def a(n): return 1 if n<1 else sum([binomial(n + k - 1, 2*k) % 2 for k in xrange(0, n + 1)])

print [a(n) for n in xrange(0, 101)] # Indranil Ghosh, Mar 22 2017

CROSSREFS

Cf. A001222, A007305, A002487, A006842, A006843, A047679, A054424, A065674-A065675, A065810, A260443, A277324, A277328, A283986, A283987, A283988, A284009.

See also A282714.

Sequence in context: A241435 A078338 A278149 * A238690 A229835 A196155

Adjacent sequences:  A007303 A007304 A007305 * A007307 A007308 A007309

KEYWORD

nonn,frac,tabf,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Formula fixed and extended by Franklin T. Adams-Watters, Jul 07 2009

Incorrect Maple program removed by Johannes W. Meijer, Jun 05 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 12:14 EDT 2017. Contains 284176 sequences.