0,5

Contribution from Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 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) and a(n+2) = A047679(A054429(n));

A153036(n) = floor(a(n+2)/A047679(n)). (End)

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.

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

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

G. A. Jones, The Farey graph

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

Index entries for sequences related to Stern's sequences

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

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

SternBrocotTreeNum := proc(n) option remember; local msb, r; if(n < 2) then RETURN(n); fi; msb := floor_log_2(n); r := n - (2^msb); if(floor_log_2(r) = (msb-1)) then RETURN(SternBrocotTreeNum(r) + SternBrocotTreeNum(((3*(2^(msb-1)))-r)-1)); else RETURN(SternBrocotTreeNum((2^(msb-1))+r)); fi; end;

Contribution from Peter Luschny (peter(AT)luschny.de), Apr 27 2009: (Start)

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}]] (End)

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

A152975. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 22 2008]

Sequence in context: A035531 A118977 A071766 this_sequence A112531 A100002 A057041

Adjacent sequences: A007302 A007303 A007304 this_sequence A007306 A007307 A007308

nonn,frac,tabf,nice

N. J. A. Sloane (njas(AT)research.att.com).

Maple code from Antti Karttunen, Mar 19 2000

0,3

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

Contribution from Javier Torres (adaycalledzero(AT)hotmail.com), Jul 26 2009: (Start)

It appears that are also the odd entries in alternated diagonals in Pascal's triangle at 45 degrees slope

(End)

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.

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

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

A. Bogomolny, Stern-Brocot tree

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 sequences related to Stern's sequences

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

a(0)=1; for n>=1 a(n)=sum(k=0, n-1, C(n-1+k, n-1-k) mod 2 ) - Benoit Cloitre (benoit7848c(AT)orange.fr), Jun 20 2003

a(n+1)=sum{k=0..n, mod(binomial(2n-k, k), 2)}; a(n)=0^n+sum{k=0..n-1, mod(binomial(2(n-1)-k, k), 2)}; - Paul Barry (pbarry(AT)wit.ie), Dec 11 2004

a(n)=sum{k=0..n, mod(C(n+k,2k),2)}; - Paul Barry (pbarry(AT)wit.ie), Jun 12 2006

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

SB01Den := proc(n) option remember; local r; if(n <= 1) then RETURN(n+1); fi; r := n - 2^floor_log_2(n); if(0 = (floor((1+r)/2) mod 2)) then RETURN(2*SB01Den(floor(n/2)) - SB01Den(floor(n/4))); else RETURN(SB01Den(floor(n/2)) + SB01Den(floor(n/4))); fi; end;

[seq(SB01Den(n), n=0..64)]; # starts as [1, 2, 3, 3, 4, 5, 5, ...]

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

(PARI) a(n)=local(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 */

Cf. A007305, A006842, A006843, A047679, A054424, A065674-A065675, A065810

Sequence in context: A115728 A026354 A078338 this_sequence A140858 A075458 A083036

Adjacent sequences: A007303 A007304 A007305 this_sequence A007307 A007308 A007309

nonn,frac,tabf,nice

N. J. A. Sloane (njas(AT)research.att.com).

Formula fixed and extended by Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Jul 07 2009

1,4

Row n has length 2^n + 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.

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

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. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67.

W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

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

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.

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

.................................

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.

Sequence in context: A153901 A132844 A006843 this_sequence A117506 A055089 A060117

Adjacent sequences: A049453 A049454 A049455 this_sequence A049457 A049458 A049459

nonn,easy,tabf,frac,nice

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Larry Reeves (larryr(AT)acm.org), Apr 12 2000

0,2

Sometimes called Phi(n).

Leo Moser found an interesting way to generate this sequence, see Gardner.

M. Gardner, The Last Recreations, 1997, chap 12.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, a foundation for computer science, Chapter 4.5 - Relative Primality, pages 118 - 120 and Chapter 9 - Asymptotics, Problem 6, pages 448 - 449, Addison-Wesley Publishing Co., Reading, Mass., 1989.

R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

a(n) = 1+Sum_{i=1..n} phi(i).

a(n) = n(n+3)/2 - Sum(k = 2 to n, a([n/k])). - David W. Wilson, May 25, 2002

a(5)=11 because the fractions are 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.

s = 1; Table[s = s + EulerPhi[n], {n, 0, 60}]

Essentially the same as A049643. Cf. A006843, A002088, A055197, A055201.

Sequence in context: A129944 A152900 A079151 this_sequence A049643 A050437 A096246

Adjacent sequences: A005725 A005726 A005727 this_sequence A005729 A005730 A005731

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).

1,2

Index entries for sequences related to Stern's sequences

Index entries for sequences that are permutations of the natural numbers

canonical_fractions_to_whole_SternBrocot_permutation(30);

Whole Stern-Brocot tree: 1/1 1/2 2/1 1/3 2/3 3/2 3/1 1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1 1/5 2/7

Canonical fractions: 1/1 1/2 2/1 1/3 3/1 1/4 2/3 3/2 4/1 1/5 5/1 1/6 2/5 3/4 4/3 5/2 6/1

cfrac2binexp := proc(c) local i, e, n; n := 0; for i from 1 to nops(c) do e := c[i]; if(i = nops(c)) then e := e-1; fi; n := ((2^e)*n) + ((i mod 2)*((2^e)-1)); od; RETURN(n); end;

frac2position_in_whole_SB_tree := proc(r) local k, msb; if(1 = r) then RETURN(1); else if(r > 1) then k := cfrac2binexp(convert(r, confrac)); else k := ReflectBinTreePermutation(cfrac2binexp(convert(1/r, confrac))); fi; msb := floor_log_2(k); if(r > 1) then RETURN(k + (2^(msb+1))); else RETURN(k + (2^(msb+1)) - (2^msb)); fi; fi; end;

canonical_fractions_to_whole_SternBrocot_permutation := proc(u) local a, n, i; a := []; for n from 2 to u do for i from 1 to n-1 do if (1 = igcd(n, i)) then a := [op(a), frac2position_in_whole_SB_tree(i/(n-i))]; fi; od; od; RETURN(a); end; # ReflectBinTreePermutation and floor_log_2 given in A054429

Cf. A047679, A007305, A007306, A054427, A057114. In table form: A054425. Inverse permutation: A054426.

Sequence in context: A064554 A162425 A054426 this_sequence A109436 A039254 A039195

Adjacent sequences: A054421 A054422 A054423 this_sequence A054425 A054426 A054427

nonn

Antti Karttunen

1,1

Rows: {2}; {3,2}; {5,3,2}; ...; e.g. in row 3, 5 reduced fractions (0/1,1/3,1/2,2/3,1/1) are <=1; 3 are <=1/2; 2 are <=1/3.

First column: T(n, 1)=a(n+1), where a=A005728.

Sequence in context: A054494 A112764 A108728 this_sequence A104887 A064886 A029600

Adjacent sequences: A049802 A049803 A049804 this_sequence A049806 A049807 A049808

nonn,tabl

Clark Kimberling (ck6(AT)evansville.edu)

1,9

J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152

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.

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

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Index entries for sequences related to Stern's sequences

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

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); [From Peter Luschny (peter(AT)luschny.de), Apr 28 2009]

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Numerator[ Farey[n]], {n, 0, 9}]] (from Robert G. Wilson v Apr 08 2004)

Cf. A006843, A049455, A049456, A007305, A007306.

Sequence in context: A024940 A054635 A003137 this_sequence A060505 A035188 A066295

Adjacent sequences: A006839 A006840 A006841 this_sequence A006843 A006844 A006845

nonn,nice,frac,tabf

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Apr 08 2004

1,4

J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152

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.

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

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Index entries for sequences related to Stern's sequences

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

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); [From Peter Luschny (peter(AT)luschny.de), Apr 28 2009]

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Denominator[ Farey[n]], {n, 0, 9}]] (from Robert G. Wilson v Apr 08 2004)

Cf. A006842, A049455, A049456, A007305, A007306.

Sequence in context: A132463 A153901 A132844 this_sequence A049456 A117506 A055089

Adjacent sequences: A006840 A006841 A006842 this_sequence A006844 A006845 A006846

nonn,nice,frac,tabf

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Apr 08 2004

Changed offset (=order of first row) to 1 R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Apr 26 2009

1,9

Stern's diatomic array read by rows (version 4).

This sequence divided by A049456 gives another version of the Stern-Brocot tree.

Row n has length 2^n + 1.

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.

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

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.

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

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

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

Cf. A049456. Also A007305, A007306, A006842, A006843, A070878, A070879.

Row sums are A007051.

Sequence in context: A037897 A054070 A126304 this_sequence A133734 A109702 A115412

Adjacent sequences: A049452 A049453 A049454 this_sequence A049456 A049457 A049458

nonn,easy,tabf,frac

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Larry Reeves (larryr(AT)acm.org), Apr 12 2000

0,4

Given a real number x >= 1 (here x = Pi), start with 1/0 and 0/1 and construct the sequence of fractions f_n = r_n/s_n such that:

f_{n+1} = (r_k + r_n)/(s_k + s_n) where k is the greatest integer < n such that f_k <= x <= f_n. Sequence gives values r_n.

Write a 0 if f_n <= x and a 1 if f_n > x. This gives (for x = Pi) the sequence 1, 0, 0, 0, 1, 1, 1, 1, 0 (7 times), 1 (15 times, 0, 1,... Ignore the initial string 1, 0, 0, 0, which is always the same. Look at the runs lengths of the remaining sequence, which are in this case L_1 = 4, L_2 = 7, L_3 = 15, L_4 = 1, L_5 = 292, etc. (A001203). Christoffel showed that x has the continued fraction representation (L_1 - 1) + 1/(L_2 + 1/(L_3 + 1/(L_4 + ...))).

C. Brezinski, History of Continued Fractions and Pade' Approximants, Springer-Verlag, 1991; pp. 151-152.

E. B. Christoffel, Observatio arithmetica, Ann. Math. Pura Appl., (II) 6 (1875), 148-153.

Dave Rusin, Farey fractions on sci.math

The fractions are 1/0, 0/1, 1/1, 2/1, 3/1, 4/1, 7/2, 10/3, 13/4, 16/5, 19/6, 22/7, 25/8, 47/15, ...

Cf. A097546.

Sequence in context: A118426 A082008 A105330 this_sequence A073627 A062042 A107817

Adjacent sequences: A097542 A097543 A097544 this_sequence A097546 A097547 A097548

nonn,frac,nice,easy

N. J. A. Sloane (njas(AT)research.att.com), Aug 28 2004

More terms from Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), May 08 2006