|
|
A007306
|
|
Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).
(Formerly M0437)
|
|
95
|
|
|
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
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)
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
|
|
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
|
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)).]
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.]
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.]
|
|
FORMULA
|
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(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(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
The following decompositions hold for all n > 0:
For m >= 0, M >= m, 0 <= k < 2^m,
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)
G.f.: 1 + x * (1 + x) * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))). - Ilya Gutkovskiy, Jul 19 2019
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
|
|
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 *)
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 *)
|
|
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 */
(PARI) A007306_upto(nMax)=my(V1, V2); V1=vector(nMax+1, i, 1); V2=vector(nMax+1, i, 1); for(i=3, nMax+1, V1[i]=V1[i-1]+V2[i-1]-2*(V1[i-1]%V2[i-1]); V2[i]=V1[i]-V2[i-1]); V1 \\ Mikhail Kurkov, Mar 13 2022
(Sage)
@CachedFunction
def a(n):
return a((odd_part(n-1)+1)/2)+a((odd_part(n)+1)/2) if n>1 else 1
(Sage)
if n == 0: return 1
M = [1, 1]
for b in (n-1).bits():
M[b] = M[0] + M[1]
return M[1]
(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
(R)
# 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)
#
(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 range(n + 1))
(Python)
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
(Magma) [1] cat [&+[Binomial(n+k, 2*k) mod 2: k in [0..n]]: n in [0..80]]; // Vincenzo Librandi, Jun 10 2019
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
nonn,frac,tabf,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|