Displaying 1-10 of 39 results found.
Permutation of the positive integers: this permutation transforms the enumeration system of positive irreducible fractions A007305/ A047679 (Stern-Brocot) into the enumeration system A162909/ A162910 (Bird), and vice versa.
+20
15
1, 2, 3, 5, 4, 7, 6, 10, 11, 8, 9, 14, 15, 12, 13, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 42, 43, 40, 41, 46, 47, 44, 45, 34, 35, 32, 33, 38, 39, 36, 37, 58, 59, 56, 57, 62
COMMENTS
As A117120 the permutation is self-inverse. Except for fixed points 1, 2, 3 it consists completely of 2-cycles: (4,5), (6,7), (8,10), (9,11), (12,14), (13,15), (16,21), (17,20), ..., (24,29), ..., (32,42), ... .
FORMULA
a(1) = 1, a(2) = 2, a(3) = 3. For n >= 2, m = floor(log_2(n)). If m even, then a(2*n) = 2*a(n) and a(2*n+1) = 2*a(n)+1. If m odd, then a(2*n) = 2*a(n)+1 and a(2*n+1) = 2*a(n).
PROG
(R)
a <- 1:3
maxn <- 50 # by choice
#
for(n in 2:maxn){
m <- floor(log2(n))
if(m%%2 == 0) {
a[2*n ] <- 2*a[n]
a[2*n+1] <- 2*a[n]+1 }
else {
a[2*n ] <- 2*a[n]+1
a[2*n+1] <- 2*a[n] }
}
#
a
(R)
# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- 1:3
for(n in 4:2^maxblock){
ones <- which(as.integer(intToBits(n)) == 1)
nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
anbit <- nbit
ifelse(floor(log2(n)) %% 2 == 0,
anbit[seq(1, length(anbit)-1, 2)] <- 1 - anbit[seq(1, length(anbit)-1, 2)],
anbit[seq(2, length(anbit) - 1, 2)] <- 1 - anbit[seq(2, length(anbit)-1, 2)])
a <- c(a, sum(anbit*2^(0:(length(anbit)-1))))
}
a
1, 8, 2, 27, 54, 24, 3, 64, 250, 375, 192, 108, 135, 40, 4, 125, 686, 96, 1029, 1372, 160, 1715, 500, 320, 875, 16000, 448, 189, 3456, 56, 5, 216, 1458, 3993, 3000, 5324, 10985, 8640, 2916, 3645, 12096, 281216, 9317, 7000, 170368, 5103, 1080, 750, 3087, 352, 3430, 3773, 416, 4116, 1125, 576, 1500, 1625, 704, 270, 297, 72, 6, 343
COMMENTS
Permutation of natural numbers induced by looking up the position of A007305(n+1)/ A047679(n-1) [each fraction in the full Stern-Brocot tree] in the set of positive rationals as ordered by A270418(n)/ A270419(n).
Permutation of natural numbers induced by looking up the position of fraction A270418(n)/ A270419(n) from the full Stern-Brocot tree A007305(n+1)/ A047679(n-1).
+20
5
1, 3, 7, 15, 31, 63, 127, 2, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 6, 33554431, 67108863, 4, 268435455, 536870911, 1073741823, 2147483647, 128, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 14
PROG
(Scheme)
(define (SBtree_index m n) (let loop ((m m) (n n) (z 1)) (cond ((= m n) z) ((< m n) (loop m (- n m) (+ z z))) (else (loop (- m n) n (+ z z 1))))))
(PARI)
A065620(n, c=1) = sum(i=0, logint(n+!n, 2), if(bittest(n, i), (-1)^c++<<i)); \\ From A065620
SBtree_index(r) = { my(m=numerator(r), n=denominator(r), z=1); while(m!=n, if(m<n, n-=m; z<<=1, m-=n; z<<=1; z++)); (z); };
a(n) is the integer (reduced squarefree) under the square root obtained when the inverse of Minkowski's question mark function is applied to the n-th ratio A007305(n+1)/ A047679(n-1) in the full Stern-Brocot tree and zero when it results a rational value.
+20
4
0, 0, 0, 5, 5, 0, 0, 0, 2, 2, 0, 5, 5, 0, 0, 2, 3, 0, 3, 3, 0, 3, 2, 0, 2, 2, 0, 5, 5, 0, 0, 5, 13, 17, 2, 17, 37, 5, 13, 13, 5, 37, 17, 2, 17, 13, 5, 2, 3, 0, 3, 3, 0, 3, 2, 0, 2, 2, 0, 5, 5, 0, 0, 3, 17, 3, 37, 21, 13, 10, 37, 3, 401, 6, 13, 10, 401, 0, 17, 17, 0, 401, 10, 13, 6, 401, 3, 37
COMMENTS
Note: the underlying function N2Q (see the Maple code) maps natural numbers 1, 2, 3, 4, 5, ..., through all the positive rationals 1/1, 1/2, 2/1, 1/3, 2/3, 3/2, 3/1, 1/4, ... bijectively to the union of positive rationals and quadratic surds.
In his "On Numbers and Games", Conway denotes Minkowski's question mark function with x enclosed in a box.
REFERENCES
J. H. Conway, On Numbers and Games, 2nd ed. Natick, MA: A. K. Peters, pp. 82-86 (First ed.), 2000.
EXAMPLE
The first few values for this mapping are
N2Q(1) = Inverse_of_MinkowskisQMark(1) = 1,
N2Q(2) = Inverse_of_MinkowskisQMark(1/2) = 1/2,
N2Q(3) = Inverse_of_MinkowskisQMark(2) = 2,
N2Q(4) = Inverse_of_MinkowskisQMark(1/3) = (3-sqrt(5))/2,
N2Q(5) = Inverse_of_MinkowskisQMark(2/3) = (sqrt(5)-1)/2,
N2Q(6) = Inverse_of_MinkowskisQMark(3/2) = 3/2,
N2Q(7) = Inverse_of_MinkowskisQMark(3) = 3,
N2Q(8) = Inverse_of_MinkowskisQMark(1/4) = 1/3,
N2Q(9) = Inverse_of_MinkowskisQMark(2/5) = sqrt(2)-1,
N2Q(10) = Inverse_of_MinkowskisQMark(3/5) = 2-sqrt(2).
MAPLE
[seq(find_sqrt(N2Q(j)), j=1..512)];
Inverse_of_MinkowskisQMark := proc(r) local x, y, b, d, k, s, i, q; x := numer(r); y := denom(r); if(1 = y) then RETURN(x/y); fi; if(2 = y) then RETURN(x/y); fi; b := []; d := []; k := 0; s := 0; i := 0; while(x <> 0) do q := floor(x/y); if(i > 0) then b := [op(b), q]; d := [op(d), x]; fi; x := 2*(x-(q*y)); if(member(x, d, 'k') and (k > 1) and (b[k] <> b[k-1]) and (q <> floor(x/y))) then s := eval_periodic_confrac_tail(list2runcounts(b[k..nops(b)])); b := b[1..(k-1)]; break; fi; i := i+1; od; if(0 = k) then b := b[1..(nops(b)-1)]; b := [op(b), b[nops(b)]]; fi; RETURN(factor(eval_confrac([floor(r), op(list2runcounts([0, op(b)]))], s))); end;
eval_confrac := proc(c, z) local x, i; x := z; for i in reverse(c) do x := (`if`((0=x), x, (1/x)))+i; od; RETURN(x); end;
eval_periodic_confrac_tail := proc(c) local x, i, u, r; x := (eval_confrac(c, u) - u) = 0; r := [solve(x, u)]; RETURN(max(r[1], r[2])); end; # Note: I am not sure if the larger root is always the correct one for the inverse of Minkowski's question mark function. However, whichever root we take, it does not change this sequence, as the integer under the square root is same in both cases. - Antti Karttunen, Aug 26 2006 list2runcounts := proc(b) local a, p, y, c; if(0 = nops(b)) then RETURN([]); fi; a := []; c := 0; p := b[1]; for y in b do if(y <> p) then a := [op(a), c]; c := 0; p := y; fi; c := c+1; od; RETURN([op(a), c]); end;
find_sqrt := proc(x) local n, i, y; n := nops(x); if(n < 2) then RETURN(0); fi; if((2 = n) and (`^` = op(0, x)) and (1/2 = op(2, x))) then RETURN(op(1, x)); else for i from 0 to n do y := find_sqrt(op(i, x)); if(y <> 0) then RETURN(y); fi; od; RETURN(0); fi; end; # This returns an integer under the square-root expression in Maple.
Left(0)/right(1) turning sequence needed to traverse the Stern-Brocot tree ( A007305, A047679) from the root down to e ( A001113).
+20
4
1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
COMMENTS
The sequence has the following regular pattern: 1 0{0} 1 0 1{2} 0 1 0{4} 1 0 1{6} 0 1 0{8} ... where {r} indicates that the preceding term is repeated r times.
Run lengths of this sequence ( A003417) are the coefficients of the continued fraction for e.
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd Edition, Addison-Wesley, 1989, p. 115-123.
LINKS
Michael De Vlieger, Binary tree of a(n), n = 1..2^14-1, where dark blue represents 0 and red represents 1.
FORMULA
The sequence begins with
floor(e / 1) = A003417(1) ones, followed by floor(1 / (e mod 1)) = A003417(2) zeros, followed by floor((e mod 1) / (1 mod (e mod 1))) = A003417(3) ones, followed by floor((1 mod (e mod 1)) / ((e mod 1) mod (1 mod (e mod 1)))) = A003417(4) zeros ...
Limit_{n->oo} (1/n)*Sum_{i=1..n} a(i) = 1/2. (End)
EXAMPLE
In the initial portion of the Stern-Brocot tree shown below, the arrows indicate the traversing route.
1/1
|
.----------------->-----. Right (1)
| |
1/2 2/1
| |
.-----------. .-------->--. Right (1)
| | | |
1/3 2/3 3/2 3/1
| | | |
.-----. .-----. .-----. .-<---. Left (0)
| | | | | | | |
1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1
...
The first terms of the sequence are therefore 1, 1, 0.
MATHEMATICA
(* Generate up to 2^22 terms of this sequence from the 2^11 X 2^11 bitmap *)
With[{rows = 12}, ImageData[Import["https://oeis.org/ A342991/a342991.png"]][[1 ;; rows]] /. {0. -> 1, 1. -> 0} // Flatten] (* Michael De Vlieger, Nov 04 2022 *) A342991[i_]:=Flatten[Array[{1, PadRight[{}, 4#], 1, 0, PadRight[{}, 2+4#, 1], 0}&, i, 0]]; (* Each iteration adds six runs of values *)
PROG
(Python)
from itertools import count, islice
def A342991_gen(): # generator of terms a = 0
yield from (1, 1)
for n in count(2):
q, r = divmod(n, 3)
yield from (a, )*(1 if r else q<<1)
a = 1-a
(PARI)
A342991(iter) = concat(vector(iter, i, concat([1, vector((i-1)<<2), 1, 0, vector(2+(i-1)<<2, x, 1), 0]))); \\ Each iteration adds six runs of values
(PARI) a(n) = my(r, s=sqrtint(n-1, &r)); bitand(s + (r<s-1 || r==s), 1); \\ Kevin Ryde, Nov 24 2022
Obtained by reading first the numerator then the denominator of fractions in full Stern-Brocot tree ( A007305/ A047679).
+20
3
0, 1, 1, 0, 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, 3, 8, 3, 7, 4, 7, 5, 8, 5, 7, 4, 5, 5, 4, 7, 5, 8, 5, 7, 4, 7, 3, 8, 3, 7, 2, 5, 1, 1, 6, 2, 9, 3, 11, 3, 10, 4, 11, 5, 13, 5, 12, 4, 9, 5, 9, 7, 12, 8, 13, 7, 11, 7, 10, 8, 11, 7, 9, 5, 6, 6, 5
COMMENTS
When presented in this way, every row (e.g. row 3, 1 3 2 3 3 2 3 1) is a palindrome. - Joshua Zucker, May 11 2006
MAPLE
F:= proc(n) option remember; local t;
t:= L -> [[L[1], [L[1][1]+L[2][1], L[1][2]+L[2][2]], L[2]],
[L[2], [L[2][1]+L[3][1], L[2][2]+L[3][2]], L[3]]][];
if n=0 then [[[ ], [0, 1], [ ]], [[ ], [1, 0], [ ]]]
elif n=1 then [[[0, 1], [1, 1], [1, 0]]]
else map(t, F(n-1))
fi
end:
aa:= n-> map(x-> x[], [seq(map(x-> x[2], F(j))[], j=0..n)])[]:
aa(7); # aa(n) gives the first 2^(n+1)+2 terms
MATHEMATICA
sbt[n_] := Module[{R, L, Y, w, u},
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]]]];
The exponent of 2 in the fractions of the whole ]0, inf[ Stern-Brocot tree ( A007305/ A047679) [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, ...].
+20
3
0, -1, 1, 0, 1, -1, 0, -2, 1, 0, -2, 2, 0, -1, 2, 0, 1, -3, 0, 2, -3, 0, 2, -2, 0, 3, -2, 0, 3, -1, 0, -1, 1, 0, -1, 2, 0, -2, 2, 0, -2, 3, 0, -1, 3, 0, -1, 1, 0, -3, 1, 0, -3, 2, 0, -2, 2, 0, -2, 1, 0, -1, 1, 0, 1, -1, 0, 2, -1, 0, 2, -1, 0, 3, -1, 0, 3, -4, 0, 1, -4, 0, 1, -1, 0, 2, -1, 0, 2, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -2, 0, 1, -2, 0, 1, -1
MAPLE
[seq(exp_of_2(SternBrocotTreeNum(j)/SternBrocotTreeDen(j)), j=1..128)];
Simple self-inverse permutation of natural numbers: List each block of 2^n numbers (from 2^n to 2^(n+1) - 1) in reverse order.
+10
213
1, 3, 2, 7, 6, 5, 4, 15, 14, 13, 12, 11, 10, 9, 8, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 127, 126, 125, 124, 123, 122, 121
COMMENTS
The mapping and conversion rules are as follows:
By rows, we have ...
1;
3, 2;
7, 6, 5, 4;
15, 14, 13, 12, 11, 10, 9, 8;
... onto which we are to map one-half of the Stern-Brocot infinite Farey Tree:
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
...
The conversion rules are: Convert the decimal to binary, adding a duplicate of the rightmost binary term to its right. For example, 10 = 1010, which becomes 10100. Then, from the left, record the number of runs = [1,1,1,2], the continued fraction representation of 5/8. Check: 10 decimal corresponds to 5/8 as shown in the overlaid mapping. Take decimal 9 = 1001 which becomes 10011, with a continued fraction representation of [1,2,2] = 5/7. Check: 9 decimal corresponds to 5/7 in the Farey Tree map. (End)
a(n) is the value generated when n is converted into its Elias gamma code, the 1's and 0's are interchanged and the resultant is converted back to its decimal value for all values of n > 1. For n = 1, A054429(n) = 1 but after converting 1 to Elias gamma code, interchanging the 1's and 0's and converting it back to decimal, the result produced is 0. For example, let n = 10. The Elias gamma code for 10 is '1110010'. After interchanging the 1's and 0's it becomes "0001101" and 1101_2 = 13_10. So a(10) = 13. (End)
From Yosu Yurramendi, Mar 09 2017 (similar to Zumkeller's comment): (Start)
FORMULA
a(n) = ReflectBinTreePermutation(n).
a(n) = if n=1 then 1 else 2*a(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Feb 18 2003 G.f.: 1/(1-x) * ((x-2x^2)/(1-x) + Sum_{k>=0} 3*2^k*x^2^k). - Ralf Stephan, Sep 15 2003 a(1) = 1, a(2^(m+1) + k) = a(2^m+k) + 2^(m+1),
a(2^(m+1) + 2^m+k) = a(2^m+k) + 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Apr 06 2017
MAPLE
A054429 := n -> 3*2^ilog2(n) - n - 1:
MATHEMATICA
Flatten[Table[Range[2^(n+1)-1, 2^n, -1], {n, 0, 6}]] (* Harvey P. Dale, Dec 17 2013 *)
PROG
(Haskell)
a054429 n = a054429_list !! (n-1)
a054429_list = f [1..] where
f xs@(x:_) = reverse us ++ f vs where (us, vs) = splitAt x xs
(R)
maxblock <- 10 # by choice
a <- NULL
for(m in 0:maxblock) a <- c(a, rev(2^m:(2^(m+1)-1)))
a
(Python)
from itertools import count, islice
def A054429_gen(): # generator of terms return (m for n in count(0) for m in range((1<<n+1)-1, (1<<n)-1, -1))
CROSSREFS
This is Guy Steele's sequence GS(6, 5) (see A135416).
Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.
+10
114
1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 15, 16, 24, 20, 28, 18, 26, 22, 30, 17, 25, 21, 29, 19, 27, 23, 31, 32, 48, 40, 56, 36, 52, 44, 60, 34, 50, 42, 58, 38, 54, 46, 62, 33, 49, 41, 57, 37, 53, 45, 61, 35, 51, 43, 59, 39, 55, 47, 63, 64, 96, 80, 112, 72, 104, 88, 120
COMMENTS
A self-inverse permutation of the natural numbers.
a(n) is the position in B of the reversal of the n-th term of B, where B is the left-to-right binary enumeration sequence ( A081242 with the empty word attached as first term). - Clark Kimberling, Mar 12 2003 When certain Stern-Brocot tree-related permutations are conjugated with this permutation, they induce a permutation on Z (folded to N), which is an infinite siteswap permutation (see, e.g., figure 7 in the Buhler and Graham paper, which is permutation A065174). We get: Every nonnegative integer has a unique representation c(1) + c(2)*2 + c(3)*2^2 + c(4)*2^3 + ..., where every c(i) is 0 or 1. Taking tuples of coefficients in lexical order (i.e., 0, 1; 01,11; 001,011,101,111; ...) yields A059893. - Clark Kimberling, Mar 15 2015 The reduced rationals can be ordered either as the Calkin-Wilf tree A002487(n)/ A002487(n+1) or the Stern-Brocot tree A007305(n+2)/ A047679(n). The present sequence gives the order of matching rationals in the other sequence. For reference, the Calkin-Wilf tree is 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, ..., which is A002487(n)/ A002487(n+1). The Stern-Brocot tree is 1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, 5/4, 7/5, 8/5, 7/4, 7/3, 8/3, 7/2, ..., which is A007305(n+2)/ A047679(n). There is a great little OEIS-is-useful story here. I had code for the position of fractions in the Calkin-Wilf tree. The best I had for positions of fractions in the Stern-Brocot tree was the paper "Locating terms in the Stern-Brocot tree" by Bruce Bates, Martin Bunder, Keith Tognetti. The method was opaque to me, so I used my Calkin-Wilf code on the Stern-Brocot fractions, and got A059893. And thus the problem was solved. (End)
FORMULA
a(n) = A030109(n) + A053644(n). If 2*2^k <= n < 3*2^k then a(n) = 2*a(n-2^k); if 3*2^k <= n < 4*2^k then a(n) = 1 + a(n-2^k) starting with a(1)=1. - Henry Bottomley, Sep 13 2001
EXAMPLE
a(11) = a(1011) = 1110 = 14.
With empty word e prefixed, A081242 becomes (e,1,2,11,21,12,22,111,211,121,221,112,...); (reversal of term #9) = (term #12); i.e., a(9)=12 and a(12)=9. - Clark Kimberling, Mar 12 2003 This sequence regarded as a triangle with rows of lengths 1, 2, 4, 8, 16, ...:
1;
2, 3;
4, 6, 5, 7;
8, 12, 10, 14, 9, 13, 11, 15;
16, 24, 20, 28, 18, 26, 22, 30, 17, 25, 21, 29, 19, 27, 23, 31;
32, 48, 40, 56, 36, 52, 44, ...
MAPLE
# Implements Bottomley's formula
A059893 := proc(n) option remember; local k; if(1 = n) then RETURN(1); fi; k := floor_log_2(n)-1; if(2 = floor(n/(2^k))) then RETURN(2* A059893(n-(2^k))); else RETURN(1+ A059893(n-(2^k))); fi; end;
floor_log_2 := proc(n) local nn, i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;
# second Maple program:
a:= proc(n) local i, m, r; m, r:= n, 0;
for i from 0 while m>1 do r:= 2*r +irem(m, 2, 'm') od;
r +2^i
end:
MATHEMATICA
ro[n_]:=Module[{idn=IntegerDigits[n, 2]}, FromDigits[Join[{First[idn]}, Reverse[ Rest[idn]]], 2]]; Array[ro, 80] (* Harvey P. Dale, Oct 24 2012 *)
PROG
(PARI) a(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2); \\ Michel Marcus, Sep 29 2021 (Haskell)
a059893 = foldl (\v b -> v * 2 + b) 1 . init . a030308_row
(Scheme, with memoization-macro definec)
(R)
maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)) {
a[2^(m+1)+ k] <- 2*a[2^m+k]
a[2^(m+1)+2^m+k] <- 2*a[2^m+k] + 1
}
a
(R)
maxblock <- 7 # by choice
a <- 1
for(n in 2:2^maxblock){
ones <- which(as.integer(intToBits(n)) == 1)
nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
anbit <- nbit
anbit[1:(length(anbit) - 1)] <- anbit[rev(1:(length(anbit)-1))]
a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
(Python)
def a(n): return int('1' + bin(n)[3:][::-1], 2)
Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).
(Formerly M0437)
+10
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
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(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 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 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
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 */ (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.
Search completed in 0.040 seconds
|