A006843 -id:A006843 - cp's OEIS frontend

A278051 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).

2, 3, 10, 35, 252, 2772, 6435, 858, 680680, 12932920, 5290740, 121687020, 1029659400, 3088978200, 582272390700, 18050444111700, 128701918800, 25740383760, 70301729698200, 10043104242600, 109530094869795600, 523310453266801200, 51193413906534900, 481218090721428060

Offset: 1

N. J. A. Sloane, Nov 23 2016

			The fractions b(n) are 1/2, 2/3, 9/10, 38/35, 347/252, 4189/2772, 11767/6435, 1733/858, 1548081/680680, 31464371/12932920, 14680543/5290740, 353517989/121687020, 3350216417/1029659400, 10571768267/3088978200, ...

J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187. See Eq. (20).

Cf. A006843, A005728, A240877, A278046, A278050.

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end:
ans:=[];
for n from 1 to 30 do
t1:=denom(Farey(n));
t2:=add( 1/(t1[i]+t1[i+1]), i=1..nops(t1)-1);
ans:=[op(ans),t2];
od:
ans;
map(numer,ans); # A278050
map(denom,ans); # A278051

A179240 a(n) is the smallest prime q > a(n-1) such that, for the previous prime p and the following prime r, the fraction (q-p)/(r-q) has denominator equal to A006843(n) (or 0, if such a prime does not exist).

Original entry on oeis.org

5, 11, 17, 19, 29, 41, 47, 67, 73, 97, 101, 359, 367, 379, 383, 389, 397, 419, 421, 449, 467, 547, 613, 631, 647, 683, 691, 733, 769, 797, 811, 929, 941, 1021, 1087, 1153, 1181, 1193, 1249, 1709, 1721, 1747, 1847, 1889, 2017, 2153, 2357

Offset: 1

Vladimir Shevelev, Jan 06 2011

nonn

Conjecture: a(n) > 0 for all n.

			For n = 1..3, A006843(n) = 1, and p,q,r have to obey the condition
r-q | q-p. Thus a(1) = 5, a(2) = 11, a(3) = 17.

Cf. A006843, A168253, A179210, A179234, A179256, A001223

More terms from Alois P. Heinz, Jan 06 2011

A278047 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(kk'(k+k')), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

Original entry on oeis.org

1, 1, 7, 4, 37, 53, 707, 85, 179077, 289613, 379721, 641671, 62836087, 35819033, 6367281023, 55181728027, 13442946373, 490167893, 596530310479, 576997238399, 116144361532321, 4931206160615, 164890340129357, 1514840590670747, 10181612956306486603, 3295813969039399097

Offset: 1

N. J. A. Sloane, Nov 22 2016

			The fractions b(n) are 1/2, 1/3, 7/30, 4/21, 37/252, 53/396, 707/6435, 85/858, 179077/2042040, 289613/3527160, 379721/5290740, 641671/9360540, 62836087/1029659400, 35819033/617795640, ...

J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187.

Cf. A006843, A005728, A240877, A278046, A278048.

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end:
ans:=[];
for n from 1 to 50 do
t1:=denom(Farey(n));
t2:=add( 1/(t1[i]*t1[i+1]*(t1[i]+t1[i+1])),i=1..nops(t1)-1);
ans:=[op(ans),t2];
od:
ans;
map(numer,ans); # A278047
map(denom,ans); # A278048

A278048 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(kk'(k+k')), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).

Original entry on oeis.org

2, 3, 30, 21, 252, 396, 6435, 858, 2042040, 3527160, 5290740, 9360540, 1029659400, 617795640, 116454478140, 1061790830100, 283144221360, 10644519600, 14060345939640, 14060345939640, 2960272834318800, 130015019445168, 4653946718775900, 43747099156493460

Offset: 1

N. J. A. Sloane, Nov 22 2016

			The fractions b(n) are 1/2, 1/3, 7/30, 4/21, 37/252, 53/396, 707/6435, 85/858, 179077/2042040, 289613/3527160, 379721/5290740, 641671/9360540, 62836087/1029659400, 35819033/617795640, ...

J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187.

Cf. A006843, A005728, A240877, A278046, A278047.

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end:
ans:=[];
for n from 1 to 50 do
t1:=denom(Farey(n));
t2:=add( 1/(t1[i]*t1[i+1]*(t1[i]+t1[i+1])),i=1..nops(t1)-1);
ans:=[op(ans),t2];
od:
ans;
map(numer,ans); # A278047
map(denom,ans); # A278048

A278050 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

Original entry on oeis.org

1, 2, 9, 38, 347, 4189, 11767, 1733, 1548081, 31464371, 14680543, 353517989, 3350216417, 10571768267, 2114915577977, 69039991480573, 538250871701, 110983833313, 328448743696081, 48484885139543, 553270527392631611, 2736415713954900433, 286367762285513933, 2754025786313797907

Offset: 1

N. J. A. Sloane, Nov 23 2016

			The fractions b(n) are 1/2, 2/3, 9/10, 38/35, 347/252, 4189/2772, 11767/6435, 1733/858, 1548081/680680, 31464371/12932920, 14680543/5290740, 353517989/121687020, 3350216417/1029659400, 10571768267/3088978200, ...

J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187. See Eq. (20).

Cf. A006843, A005728, A240877, A278046, A278051.

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end:
ans:=[];
for n from 1 to 30 do
t1:=denom(Farey(n));
t2:=add( 1/(t1[i]+t1[i+1]), i=1..nops(t1)-1);
ans:=[op(ans),t2];
od:
ans;
map(numer,ans); # A278050
map(denom,ans); # A278051

A278052 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum k*k'/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

Original entry on oeis.org

1, 4, 39, 52, 4069, 8573, 258017, 46639, 53371999, 113518551, 768140741, 1560819091, 242830653007, 169134016817, 38186305937387, 408881289764107, 143220706672837, 41293923006131, 9928250098118791, 10936700271572951, 97615258031147892517, 643700119549549507, 62211198375587838727

Offset: 1

N. J. A. Sloane, Nov 23 2016

			The fractions b(n) are 1/2, 4/3, 39/10, 52/7, 4069/252, 8573/396, 258017/6435, 46639/858, 53371999/680680, 113518551/1175720, 768140741/5290740, 1560819091/9360540, 242830653007/1029659400, 169134016817/617795640, 38186305937387/116454478140, ...

J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187. See Eq. (21).

Cf. A006843, A005728, A240877, A278046-A278051, A278561 (denominators).

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end:
ans:=[];
for n from 1 to 30 do
t1:=denom(Farey(n));
t2:=add( t1[i]*t1[i+1]/(t1[i]+t1[i+1]), i=1..nops(t1)-1);
od:
ans;
map(numer,ans); # A278052
map(denom,ans); # A278561

A278561 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum k*k'/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).

Original entry on oeis.org

2, 3, 10, 7, 252, 396, 6435, 858, 680680, 1175720, 5290740, 9360540, 1029659400, 617795640, 116454478140, 1061790830100, 283144221360, 74511637200, 14060345939640, 14060345939640, 109530094869795600, 650075097225840, 51193413906534900, 481218090721428060

Offset: 1

N. J. A. Sloane, Nov 23 2016

			The fractions b(n) are 1/2, 4/3, 39/10, 52/7, 4069/252, 8573/396, 258017/6435, 46639/858, 53371999/680680, 113518551/1175720, 768140741/5290740, 1560819091/9360540, 242830653007/1029659400, 169134016817/617795640, 38186305937387/116454478140, ...

J. Lehner and M. Newman, Sums involving Farey fractions, Acta Arithmetica 15.2 (1969): 181-187. See Eq. (21).

Cf. A006843, A005728, A240877, A278046-A278051, A278052 (numerators).

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end:
ans:=[];
for n from 1 to 30 do
t1:=denom(Farey(n));
t2:=add( t1[i]*t1[i+1]/(t1[i]+t1[i+1]), i=1..nops(t1)-1);
od:
ans;
map(numer,ans); # A278052
map(denom,ans); # A278561

A308483 Irregular triangle read by rows: T(n,k) = Farey(n,k+1) - Farey(n,k) where Farey(n,k) = A006842(n,k)/A006843(n,k).

Original entry on oeis.org

1, 2, 2, 3, 6, 6, 3, 4, 12, 6, 6, 12, 4, 5, 20, 12, 15, 10, 10, 15, 12, 20, 5, 6, 30, 20, 12, 15, 10, 10, 15, 12, 20, 30, 6, 7, 42, 30, 20, 28, 21, 15, 35, 14, 14, 35, 15, 21, 28, 20, 30, 42, 7, 8, 56, 42, 30, 20, 28, 21, 24, 40, 35, 14, 14, 35, 40, 24, 21, 28, 20, 30, 42, 56, 8

Offset: 1

Isaac Kaufmann, May 30 2019

This is also the product of the denominators of pairs of consecutive terms in the Farey sequence.
Each term of this sequence is an integer: (Proof by induction)
Assume that the reciprocal of Farey differences of order n are the product of the consecutive denominators, i.e., if x/y and c/d are adjacent, then |x/y - c/d| = 1/dy. Let a/b and p/q be adjacent in Farey sequence up to n, such that n+1 = b+q (so only their mediant is in the middle).
As |a/b - p/q| = 1/bq, |aq - bp| = 1, so |aq - bp + ab - ab| = 1, so |a/b - (a+p)/(b+q)| = 1. The base case is trivial. QED

			T(1,1) = 1/(1 - 0);
T(2,1) = 1/(1/2 - 0);
T(2,2) = 1/(1 - 1/2);
T(3,1) = 1/(1/3 - 0);
T(3,2) = 1/(1/2 - 1/3);
T(3,3) = 1/(2/3 - 1/2);
T(3,4) = 1/(1 - 2/3);
...
If written as an array:
  1;
  2,  2;
  3,  6,  6,  3;
  4, 12,  6,  6, 12,  4;
  5, 20, 12, 15, 10, 10, 15, 12, 20, 5;
  ...

Cf. A006842, A006843.

rowf(n) = {my(vf = [0]); for (k=1, n, for (m=1, k, vf = concat(vf, m/k); ); ); vecsort(Set(vf));} \\ A006842/A006843
row(n) = my(vf = rowf(n)); vector(#vf-1, k, 1/(vf[k+1] - vf[k])); \\ Michel Marcus, Jun 07 2019

T(n,k) = Farey(n,k+1) - Farey(n,k) with Farey(n,k) = A006842(n,k)/A006843(n,k).

T(n,k) = A006843(n,k)*A006843(n,k+1).

More terms from Michel Marcus, Jun 07 2019

A005728 Number of fractions in Farey series of order n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, 81, 97, 103, 121, 129, 141, 151, 173, 181, 201, 213, 231, 243, 271, 279, 309, 325, 345, 361, 385, 397, 433, 451, 475, 491, 531, 543, 585, 605, 629, 651, 697, 713, 755, 775, 807, 831, 883, 901, 941, 965

Offset: 0

N. J. A. Sloane

Sometimes called Phi(n).
Leo Moser found an interesting way to generate this sequence, see Gardner.
a(n) is a prime number for nine consecutive values of n: n = 1, 2, 3, 4, 5, 6, 7, 8, 9. - Altug Alkan, Sep 26 2015
Named after the English geologist and writer John Farey, Sr. (1766-1826). - Amiram Eldar, Jun 17 2021

			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.

Martin Gardner, The Last Recreations, 1997, chapter 12.
Ronald L. Graham, Donald E. Knuth and Oren 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.
William Judson LeVeque, Topics in Number Theory, Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
Andrey O. Matveev, Farey Sequences, De Gruyter, 2017, Table 1.7.
Leo Moser, Solution to Problem P42, Canadian Mathematical Bulletin, Vol. 5, No. 3 (1962), pp. 312-313.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antoine Mathys, Table of n, a(n) for n = 0..20000 (terms 0 to 1000 from T. D. Noe)
Richard K. Guy, Letter to N. J. A. Sloane, 1986.
Richard K. Guy, Letter to N. J. A. Sloane, 1987.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]
Brady Haran and Grant Sanderson, Prime Pyramid (with 3Blue1Brown), Numberphile video (2022).
Sameen Ahmed Khan, Mathematica notebook.
Sameen Ahmed Khan, How Many Equivalent Resistances?, RESONANCE, May 2012.
Sameen Ahmed Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.), Vol. 122, No. 2 (May 2012), pp. 153-162.
Sameen Ahmed Khan, Beginning to count the number of equivalent resistances, Indian Journal of Science and Technology, Vol. 9, No. 44 (2016), pp. 1-7.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
Shmuel Schreiber and N. J. A. Sloane, Correspondence, 1980.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021. (Includes this sequence)
Vladimir Sukhoy and Alexander Stoytchev, Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle, Scientific Reports, Vol. 10, Article No. 4852 (2020).
Vladimir Sukhoy and Alexander Stoytchev, Formulas and algorithms for the length of a Farey sequence, Scientific Reports, Vol. 11 (2021), Article No. 22218.
Eric Weisstein's World of Mathematics, Farey Sequence.
Wikipedia, Farey sequence.

For the Farey series see A006842/A006843.
Essentially the same as A049643.
Cf. A002088, A055197, A055201.

List([0..60],n->Sum([1..n],i->Phi(i)))+1; # Muniru A Asiru, Jul 31 2018

a005728 n = a005728_list
a005728_list = scanl (+) 1 a000010_list
-- Reinhard Zumkeller, Aug 04 2012

[1] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // Vincenzo Librandi, Sep 27 2015

A005728 := proc(n)
    1+add(numtheory[phi](i),i=1..n) ;
end proc:
seq(A005728(n),n=0..80) ; # R. J. Mathar, Nov 29 2017

Accumulate@ Array[ EulerPhi, 54, 0] + 1
f[n_] := 1 + Sum[ EulerPhi[m], {m, n}]; Array[f, 55, 0] (* or *)
f[n_] := (Sum[ MoebiusMu[m] Floor[n/m]^2, {m, n}] + 3)/2; f[0] = 1; Array[f, 55, 0] (* or *)
f[n_] := n (n + 3)/2 - Sum[f[Floor[n/m]], {m, 2, n}]; f[0] = 1; Array[f, 55, 0] (* Robert G. Wilson v, Sep 26 2015 *)
a[n_] := If[n == 0, 1, FareySequence[n] // Length];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2022 *)

a(n)=1+sum(k=1,n,eulerphi(k)) \\ Charles R Greathouse IV, Jun 03 2013

from functools import lru_cache
@lru_cache(maxsize=None)
def A005728(n): # based on second formula in A018805
    if n == 0:
        return 1
    c, j = -2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A005728(k1)-3)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

a(n) = 1 + Sum_{i=1..n} phi(i).
a(n) = n*(n+3)/2 - Sum_{k=2..n} a(floor(n/k)). - David W. Wilson, May 25 2002
a(n) = a(n-1) + phi(n) with a(0) = 1. - Arkadiusz Wesolowski, Oct 13 2012
a(n) = 1 + A002088(n). - Robert G. Wilson v, Sep 26 2015

A007306 Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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 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:
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 1, 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_{k=1..2^m} a(2^m+k) = A000045(m+3) (Fibonacci sequence). - Yosu Yurramendi, Jun 05 2016
For all 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_{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
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
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

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

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Suayb S. Arslan, Asymptotically MDS Array BP-XOR Codes, arXiv:1709.07949 [cs.IT], 2017.
Alexander Bogomolny, Stern-Brocot tree.
J. Hermes, Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden (The number of partitions of a rational integer, Part I), Mathematischen Annalen 45(3) (1894), 371-380.
J. Hermes, Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden (The number of partitions of a rational integer, Part I), Mathematischen Annalen 45(3) (1894), 371-380.
J. Hermes, Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden, II (The number of partitions of a rational integer, Part II), Mathematischen Annalen 47(2-3) (1896), 281-297.
M. Herzberger, Gaussian optics and Gaussian brackets, 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).]
Jennifer Lansing, On the Stern sequence and a related sequence, 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)).]
Julien Leroy, Michel Rigo, and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics 340 (2017), 862-881.
Julien Leroy, Michel Rigo, and Manon Stipulanti, Counting subword occurrences in base-b expansions, Integers (2018) 18A, Article #A13.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math. 210 (2000), 137-149.
N. J. A. Sloane, Stern-Brocot or Farey Tree.
M. S. Srinivasan, The enumeration of positive rational numbers, Proc. Indian Acad. Sci. Sect. A 47 (1958), 12-24.
M. Stern, Über eine zahlentheoretische Function, 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.]
Manon Stipulanti, Convergence of Pascal-Like Triangles in Parry-Bertrand Numeration Systems, arXiv:1801.03287 [math.CO], 2018.
Javier Torres Suarez, Number theory - geometric connection (part 2) (YouTube video that mentions this sequence - link sent by Pacha Nambi, Aug 26 2009).
Eric Weisstein's World of Mathematics, Gaussian brackets; they are related to this sequence.
Wikipedia, Johann Gustav Hermes. [He is the person who introduced this sequence and the person who completed or constructed a regular polygon with 65537 sides.]
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

For numerators see A007305.
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.
See also A282714.

[1] cat [&+[Binomial(n+k,2*k) mod 2: k in [0..n]]: n in [0..80]]; // Vincenzo Librandi, Jun 10 2019

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

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 *)
a[0] = 0; a[1] = 1;
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 *)

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

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

from sympy import binomial
def a(n):
    return 1 if n<1 else sum(binomial(n + k - 1, 2*k) % 2 for k in range(n + 1))
print([a(n) for n in range(101)]) # Indranil Ghosh, Mar 22 2017

from functools import reduce
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

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

# Given n, compute directly a(n)
# by taking into account the binary representation of n-1
# aa <- 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(1,m[1]+2) # In A002487: 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])
}
# a(0) = 1, a(1) = 1, a(n) = aa(n-1)   n > 1
#
# Example
n <- 73
aa(n-1)
#
# Yosu Yurramendi, Dec 15 2016

@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

def A007306(n):
    if n == 0: return 1
    M = [1, 1]
    for b in (n-1).bits():
        M[b] = M[0] + M[1]
    return M[1]
print([A007306(n) for n in (0..77)]) # Peter Luschny, Nov 28 2017

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

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
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
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 & Apr 12 2017: (Start)
For n > 0, a(n) = A001222(A277324(n-1)) = A001222(A260443(n-1)*A260443(n)).
The following decompositions hold for all n > 0:
a(n) = A277328(n-1) + A284009(n-1).
a(n) = A283986(n) + A283988(n) = A283987(n) + 2*A283988(n).
a(n) = 2*A284265(n-1) + A284266(n-1).
a(n) = A284267(n-1) + A284268(n-1).
a(n) = A284565(n-1) + A284566(n-1).
a(n) = A285106(n-1) + A285108(n-1) = A285107(n-1) + 2*A285108(n-1). (End)
a(A059893(n)) = a(n+1) for n > 0. - Yosu Yurramendi, May 30 2017
a(n) = A287731(n) + A287732(n) for n > 0. - I. V. Serov, Jun 09 2017
a(n) = A287896(n) + A288002(n) for n > 1.
a(n) = A287896(n-1) + A002487(n-1) - A288002(n-1) for n > 1.
a(n) = a(n-1) + A002487(n-1) - 2*A288002(n-1) for n > 1. - I. V. Serov, Jun 14 2017
From Yosu Yurramendi, May 14 2019: (Start)
For m >= 0, M >= m, 0 <= k < 2^m,
a((2^(m+1) + A119608(2^m+k+1))*2^(M-m) - A000035(2^m+k)) =
a((2^(m+2) - A119608(2^m+k+1))*2^(M-m) - A000035(2^m+k)-1) =
a(2^(M+2) - (2^m+k)) = a(2^(M+1) + (2^m+k) + 1) =
a(2^m+k+1)*(M-m) + a(2^(m+1)+2^m+k+1). (End)
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
G.f.: 1 + x * (1 + x) * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))). - Ilya Gutkovskiy, Jul 19 2019
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

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

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

cp's OEIS Frontend

A278051 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A179240 a(n) is the smallest prime q > a(n-1) such that, for the previous prime p and the following prime r, the fraction (q-p)/(r-q) has denominator equal to A006843(n) (or 0, if such a prime does not exist).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A278047 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(k*k'*(k+k')), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A278048 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(k*k'*(k+k')), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A278050 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A278052 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum k*k'/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A278561 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum k*k'/(k+k'), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A308483 Irregular triangle read by rows: T(n,k) = Farey(n,k+1) - Farey(n,k) where Farey(n,k) = A006842(n,k)/A006843(n,k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A005728 Number of fractions in Farey series of order n.

Views

Author

Keywords

Comments

Examples

A278047 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(kk'(k+k')), where (k,k') are pairs of successive terms of v; a(n) = numerator of b(n).

A278048 Let v = list of denominators of Farey series of order n (see A006843); let b(n) = Sum 1/(kk'(k+k')), where (k,k') are pairs of successive terms of v; a(n) = denominator of b(n).