A007306 -id:A007306 - cp's OEIS frontend

A335060 a(n) is the number of values of k < n for which 4*(a(k) + a(n-k)) < n.

0, 1, 0, 2, 2, 1, 2, 0, 4, 4, 2, 5, 6, 4, 2, 3, 10, 8, 6, 2, 6, 9, 6, 4, 8, 8, 8, 4, 12, 9, 10, 7, 10, 14, 10, 6, 8, 14, 14, 11, 12, 8, 16, 10, 14, 10, 16, 15, 14, 14, 16, 14, 12, 10, 16, 11, 18, 16, 14, 22, 20, 12, 12, 17, 24, 18, 22, 18, 22, 16, 10, 19, 26, 23, 18, 22, 24

Offset: 1

Samuel B. Reid, May 21 2020

			a(6) is 1 because, if (a(k) + a(6-k)) * 4 is less than 6, k can only be 3.
a(9) is 4 because k must be 1, 3, 6, or 8 in order for (a(k) + a(9-k)) * 4 to be less than 9.

Samuel B. Reid, Table of n, a(n) for n = 1..10000
Samuel B. Reid, C program for A335060
Samuel B. Reid, Plot of 2000000 terms

Cf. A007306, A272727, A317443.

C
```
See Links section.
```

lista(nn) = {my(va=vector(nn)); for (n=2, nn, va[n] = sum(k=1, n-1, 4*(va[k] + va[n-k]) < n);); va;} \\ Michel Marcus, May 22 2020

A360564 Numerators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).

Original entry on oeis.org

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

Offset: 1

Glen Whitney, Feb 11 2023

Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node breadth-first as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q (in that order) that are less than one and have not already appeared in the tree. Then a(n) is the numerator of the n-th rational number (in lowest terms) added to the tree.
This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.
For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

			To build the tree, 1/2 only has child 1/3, since 2/2 = 1 is outside of (0,1). Then 1/3 has children 1/4 and 2/3. In turn, 1/4 only has child 1/5 because 2/4 = 1/2 has already occurred, and 2/3 has no children because 2/4 has already occurred and 3/3 is too large. Thus, the sequence begins 1, 1, 1, 2, 1, ... (the numerators of 1/2, 1/3, 1/4, 2/3, 1/5, ...).

Glen Whitney, Table of n, a(n) for n = 1..10052
G. Gordon and G. Whitney, The Playground Problem 367, Math Horizons, Vol. 26 No. 1 (2018), 32-33.

Denominators in A360565.
Level sizes of the tree in A360566.
See also the Farey tree in A007305 and A007306.
Cf. A293247.

from fractions import Fraction
row = [Fraction(1,2)]
seen = set([Fraction(1,2), Fraction(1,1)])
limit = 25 # chosen to generate 10000 fractions
nums = []
denoms = []
rowsizes = []
while row[0].denominator <= limit:
   rowsizes.append(len(row))
   newrow = []
   for frac in row:
      nums.append(frac.numerator)
      denoms.append(frac.denominator)
      for nf in [Fraction(frac.numerator, frac.denominator+1),
                 Fraction(frac.numerator+1, frac.denominator)]:
         if not(nf in seen):
            newrow.append(nf)
            seen.add(nf)
   row = newrow
print(', '.join(str(num) for num in nums))
print(', '.join(str(denom) for denom in denoms))
print(', '.join(str(rowsize) for rowsize in rowsizes))

A360565 Denominators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).

Original entry on oeis.org

2, 3, 4, 3, 5, 6, 5, 7, 5, 8, 7, 5, 9, 7, 10, 9, 8, 7, 11, 7, 12, 11, 8, 7, 13, 11, 9, 4, 14, 13, 11, 15, 13, 11, 16, 15, 14, 13, 12, 11, 17, 13, 11, 18, 17, 14, 13, 12, 11, 19, 17, 13, 11, 20, 19, 17, 13, 11, 21, 19, 17, 13, 6, 22, 21, 20, 19, 18, 17, 14, 13, 23, 19, 17, 13, 24, 23, 19, 18, 17, 14, 13, 25, 23, 10, 19, 9, 17, 15

Offset: 1

Glen Whitney, Feb 11 2023

Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node breadth-first as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q (in that order) that are less than one and have not already appeared in the tree. Then a(n) is the denominator of the n-th rational number (in lowest terms) added to the tree.
This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.
For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

			To build the tree, 1/2 only has child 1/3, since 2/2 = 1 is outside of (0,1). Then 1/3 has children 1/4 and 2/3. In turn, 1/4 only has child 1/5 because 2/4 = 1/2 has already occurred, and 2/3 has no children because 2/4 has already occurred and 3/3 is too large. Thus, the sequence begins 2, 3, 4, 3, 5, ... (the denominators of 1/2, 1/3, 1/4, 2/3, 1/5, ...).

Glen Whitney, Table of n, a(n) for n = 1..10052
G. Gordon and G. Whitney, The Playground Problem 367, Math Horizons, Vol. 26 No. 1 (2018), 32-33.

Numerators in A360564.
Level sizes of the tree in A360566.
See also the Farey tree in A007305 and A007306.
Cf. A293248.

Python
```
# See the entry for A360564.
```

A360566 Level sizes of numerator-denominator-incrementing tree of rationals in (0,1).

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 2, 4, 2, 4, 4, 3, 3, 6, 3, 6, 4, 5, 5, 8, 4, 7, 7, 7, 5, 10, 4, 8, 8, 11, 8, 11, 6, 12, 12, 11, 6, 12, 7, 12, 10, 14, 10, 18, 7, 12, 12, 13, 11, 20, 9, 14, 11, 15, 13, 22, 8, 16, 18, 17, 14, 19, 9, 18, 14, 19, 12, 24, 11, 22, 22, 19, 15, 24, 12, 24, 18, 27, 22, 36, 12, 19, 23

Offset: 3

Glen Whitney, Feb 11 2023

nonn

Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q that are less than one and have not already appeared in the tree. Then a(n) is the number of nodes n-3 levels below the root (the offset 3 is chosen so that the level number corresponds to the sum of the numerator and denominator of most fractions at level n).
This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.
It might appear at first glance that the sum of the numerator and denominator of all fractions at level n divides n. However, 7/10 and 8/9 first appear at level 33 (as children of 7/9 at level 32), but 17 does not divide 33.
Since 1/(n-1) always appears on level n, a(n) > 0. Bertrand's postulate implies that for all n > 5, a(n) > 1, since for each prime p with n/2 < p < n, (n+1-p)/p will also occur at level n.
For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

			To build the tree, 1/2 only has child 1/3, since 2/2 = 1 is outside of (0,1). Then 1/3 has children 1/4 and 2/3. In turn, 1/4 only has child 1/5 because 2/4 = 1/2 has already occurred, and 2/3 has no children because 2/4 has already occurred and 3/3 is too large. Continuing in this fashion, the first few levels of the tree look like:
1/2
 |
1/3
 | \
1/4 2/3
 |
1/5
 | \
1/6 2/5
 |   |
1/7 3/5
 | \   \
1/8 2/7 4/5
Therefore, this sequence begins 1, 1, 2, 1, 2, 2, 3, ...

Glen Whitney, Table of n, a(n) for n = 3..10002
G. Gordon and G. Whitney, The Playground Problem 367, Math Horizons, Vol. 26 No. 1 (2018), 32-33.

Numerators and denominators of the nodes in A360564 and A360565.

See also the Farey tree in A007305 and A007306.

Python
```
# See the entry for A360564.
```

A065670 Permutation of N induced by rotating the node 6 right in the infinite planar binary tree shown at A065658.

Original entry on oeis.org

1, 2, 115, 4, 5, 234881023, 7, 8, 9, 10, 11, 877, 112, 475, 15, 16, 17, 18, 19, 20, 21, 22, 23, 52, 445, 57355, 3616, 235, 1915, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 103, 13, 14191, 28615, 917506, 229630, 3613, 454, 934, 120832

Offset: 1

Antti Karttunen, Nov 22 2001

nonn

			This permutation touches only the rationals in the range ]1/2, 3/4[, which for example contains the sixth node = 3/5 of the SB ]0,1[ tree (A007305/A007306) which has an infinite, but periodic binary fractional expansion 0.100110011001... and by this permutation it is changed to 0.1010100110011001... = 53/80, which is located as the 234881023th node in the SB ]0,1[ tree.

Index entries for sequences that are permutations of the natural numbers

The sixth row of A065658. Inverse of A065671.

[seq(RotateBinFracNodeRight(6,j),j=1..256)];

A114214 Diagonal sums of number triangle A114213.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Nov 17 2005

Conjecture: a(n) = A007306(floor(n/2)+1). - Georg Fischer, Nov 28 2022

Georg Fischer, Table of n, a(n) for n = 0..1000
Jeffrey Shallit and Lukas Spiegelhofer, Continuants, run lengths, and Barry's modified Pascal triangle, arXiv:1710.06203 [math.CO], 2017.

Cf. A007306, A114213.

a(n) = sum(k=0, n\2, sum(j=0, n-2*k, binomial(k, j)*binomial(n-2*k, j)*(1+(-1)^j)/2) % 2); \\ Michel Marcus, Jun 06 2021

a(n) = Sum_{k=0..floor(n/2)} mod(Sum_{j=0..n-2k} C(k, j) C(n-2k, j) (1+(-1)^j)/2, 2). (corrected by Jeffrey Shallit, May 18 2016)

A153162 Denominators of Stern-Brocot tree hanging between 1/3 and 2/3; numerators=A153161.

Original entry on oeis.org

2, 5, 5, 8, 7, 7, 8, 11, 13, 12, 9, 9, 12, 13, 11, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19, 17, 18, 21, 19, 14, 17, 25, 30, 27, 29, 34, 31, 23, 22, 29, 31, 26, 23, 25, 20, 13, 13, 20, 25, 23, 26, 31, 29, 22, 23, 31, 34, 29, 27, 30, 25, 17, 20, 31, 39, 36, 41, 49, 46, 35, 37

Offset: 1

Reinhard Zumkeller, Dec 22 2008

For all coprime pairs (u,v) with 1/3 < u/v < 2/3 exists a unique k such that A153161(k)=u and a(k)=v;

a(1) = 2 and 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))+3 else a(n)=3+a(A025480(n-1)).

Index entries for sequences related to Stern's sequences
N. J. A. Sloane, Stern-Brocot or Farey Tree

A047679, A007306.

A203904 Triangular array T; for n>0, row n shows the coefficients of a reduced polynomial having zeros -k/(n+1) for k=1,2,...,n.

Original entry on oeis.org

1, 1, 2, 2, 9, 9, 3, 22, 48, 32, 24, 250, 875, 1250, 625, 10, 137, 675, 1530, 1620, 648, 720, 12348, 79576, 252105, 420175, 352947, 117649, 315, 6534, 52528, 216608, 501760, 659456, 458752, 131072, 4480, 109584, 1063116, 5450004, 16365321

Offset: 1

Clark Kimberling, Jan 08 2012

For n>0, the zeros of the polynomial represented by row n+1 interlace the zeros of the polynomial for row n; see the Example section.
...
T(n,1):  A119619
T(n,n):  A056916.

			First five rows(counting the top row as row 0):
1
1...2.................representing 1+2x
1...9...9.............representing 2+9x+9x^2
3...22..48...32
24...250...875...1250...625
Zeros corresponding to rows 1 to 4:
.................-1/2
............-2/3......-1/3
......-3/4.......-1/2.......-1/4
-4/5........-3/5......-2/5.......-1/5
Interlace property for successive rows illustrated by
  1/5 < 1/4 < 2/5 < 1/2 < 3/5 < 3/4 < 4/5.

Cf. A056856, A119619, A056916, A007305/A007306 (Farey fractions).

p[n_, x_] := Product[(n*x + k)/GCD[n, k], {k, 1, n - 1}]
Table[CoefficientList[p[n, x], x], {n, 1, 10}]
TableForm[%]  (* A203904 triangle *)
Flatten[%%]   (* A203904 sequence *)

A284573 Odd bisection of A278243: a(n) = A046523(A277324(n)).

Original entry on oeis.org

2, 6, 12, 30, 60, 120, 180, 210, 420, 1080, 2160, 2520, 2520, 7560, 6300, 2310, 4620, 37800, 90720, 75600, 226800, 544320, 453600, 138600, 138600, 756000, 2268000, 831600, 415800, 2079000, 485100, 30030, 60060, 2910600, 24948000, 12474000, 49896000, 272160000, 136080000, 29106000, 87318000, 1360800000, 3265920000, 1496880000, 748440000

Offset: 0

Antti Karttunen, Apr 11 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 0..1024

Cf. A007306, A046523, A277324, A278243.

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From Michel Marcus
A260443(n) = if(n<2, n+1, if(n%2, A260443(n\2)*A260443(n\2+1), A003961(A260443(n\2)))); \\ Cf. Charles R Greathouse IV's code for "ps" in A186891 and A277013.
A277324(n) = A260443((2*n)+1);
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From Charles R Greathouse IV, Aug 17 2011
A284573(n) = A046523(A277324(n));

a(n) = A046523(A277324(n)).

a(n) = A278243((2*n)+1).

A287823 a(n) = A287729(n)*A001511(n).

Original entry on oeis.org

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

Offset: 1

I. V. Serov, Jun 03 2017

For n > 0, define the sequence chf(n) of Christoffel words over an alphabet {-,+} by recursion with chf(1) = '-' and chf(2*n+0) = negate(chf(n)), chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))).
The chf(n) word has length fusc(n) = A002487(n) and splits uniquely into two parent Christoffel words - the left Christoffel word lef(n) of length l-fusc(n) = A288002(n) and the right Christoffel word rig(n) of length r-fusc(n) = A288003(n).
For n > 0, define the lap(n) word to be the chf(n) word taken to the power A001511(n), so that the factor-word chf(n) repeats in lap(n) A001511(n) times.
Consider the odd bisection CHF(n) of the chf(n) sequence. Each CHF(n) word has length A007306(n). Then the sequence lap(n) is obtained by cutting off the word lef(n) of length A288002(n) at the left side of negate(CHF(n)) and negating the first letter of the new word iff lef(n) is empty, i.e., iff A288002(n)==0.
The length of the lap(n) word is A287896(n), the number of '-'-signs in the lap(n) word is a(n) and the number of '+'-signs in the lap(n) word is A287824(n).
There are exactly n words of length n in the sequence lap(n). These n words lap(j) are all different with 1<=a(j)<=n for 1<=j<=n.
a(n)/A287824(n) enumerates all fractions along the tree of fractions.
a(n)/A287896(n) enumerates all proper fractions along the tree of proper fractions.
See the Serov links and the example below.

			n  chf(n)  A070939(n) A001511(n) A002487(n) lef(n) CHF(n)     lap(n)   a(n)
1  '-'     1          1          1          ''     '-'        '-'      1
2  '+'     2          2          1          ''     '+-'       '++'     0
3  '+-'    2          2          2          '+'    '--+'      '+-'     1
4  '-'     3          1          1          ''     '-++'      '---'    3
5  '--+'   3          3          3          '-'    '+++-'     '--+'    2
6  '-+'    3          1          2          '-'    '++-+-'    '-+-+'   2
7  '-++'   3          1          3          '-+'   '+-+--'    '-++'    1
8  '+'     4          1          1           ''    '+---'     '++++'   0
9  '+++-'  4          4          4          '+'    '----+'    '+++-'   1
10 '++-'   4          1          3          '+'    '---+--+'  '++-++-' 2
11 '++-+-' 4          1          5          '++-'  '--+--+-+' '++-+-'  2
12 '+-'    4          1          2          '+'    '--+-+-+'  '+-+-+-' 3
13 '+-+--' 4          2          5          '+-'   '-+-+-++'  '+-+--'  3
14 '+--'   4          1          3          '+-'   '-+-++-++' '+--+--' 4
15 '+---'  4          1          4          '+--'  '-++-+++'  '+---'   3
16 '-'     5          1          1          ''     '-++++'    '-----'  5
17 '----+' 5          5          5          '-'    '+++++-'   '----+'  4 .

I. V. Serov, Table of n, a(n) for n = 1..8192
J. Berstel, A. Lauve, C. Reutenauer & F. Saliola, Combinatorics on Words: Christoffel Words and Repetitions in Words, 2008.
I. V. Serov, OEIS: The tree of all fractions as sequence a(n)/A287824(n)
I. V. Serov, OEIS: The tree of all proper fractions as sequence a(n)/A287896
I. V. Serov, CHF Diatomic Algorithm Benchmark

Cf. A001511, A287729, A287824, A002487, A070939, A287896, A154269.

def c(n): return 1 if n==1 else s(n/2) if n%2==0 else s((n - 1)/2) + s((n + 1)/2)
def s(n): return 0 if n==1 else c(n/2) if n%2==0 else c((n - 1)/2) + c((n + 1)/2)
def a001511(n): return bin(n)[2:][::-1].index("1") + 1
def a(n): return c(n)*a001511(n) # Indranil Ghosh, Jun 08 2017

a(n) = A287896(n) - A287824(n).
a(n) = (A287729(n-1) + A287729(n) + A287729(n+1))/2 + A154269(n).
gcd(a(n), A287896(n)) == gcd(a(n), A287824(n)) == A001511(n).
From Yosu Yurramendi, Apr 09 2019: (Start)
For m >= 0, m even, 0 <= k < 2^m, a(2^m+k) = A287896(2^m-k).
For m >= 0, m odd,  0 <= k < 2^m, a(2^m+k) = A287896(k).  A287896(0) = 0 is needed. (End)

cp's OEIS Frontend

A335060 a(n) is the number of values of k < n for which 4*(a(k) + a(n-k)) < n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

C

PARI

A360564 Numerators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A360565 Denominators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A360566 Level sizes of numerator-denominator-incrementing tree of rationals in (0,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A065670 Permutation of N induced by rotating the node 6 right in the infinite planar binary tree shown at A065658.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A114214 Diagonal sums of number triangle A114213.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A153162 Denominators of Stern-Brocot tree hanging between 1/3 and 2/3; numerators=A153161.

Views

Author

Keywords

Comments

Links

Crossrefs

A203904 Triangular array T; for n>0, row n shows the coefficients of a reduced polynomial having zeros -k/(n+1) for k=1,2,...,n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A284573 Odd bisection of A278243: a(n) = A046523(A277324(n)).

Views

Author

Keywords