A129760 -id:A129760 - cp's OEIS frontend

A347204 a(n) = a(f(n)/2) + a(floor((n+f(n))/2)) for n > 0 with a(0) = 1 where f(n) = A129760(n).

1, 2, 3, 5, 4, 7, 10, 15, 5, 9, 13, 20, 17, 27, 37, 52, 6, 11, 16, 25, 21, 34, 47, 67, 26, 43, 60, 87, 77, 114, 151, 203, 7, 13, 19, 30, 25, 41, 57, 82, 31, 52, 73, 107, 94, 141, 188, 255, 37, 63, 89, 132, 115, 175, 235, 322, 141, 218, 295, 409, 372, 523, 674

Offset: 0

Mikhail Kurkov, Aug 23 2021 [verification needed]

Modulo 2 binomial transform of A243499(n).

Antti Karttunen, Table of n, a(n) for n = 0..8191
Kevin Ryde, PARI/GP Code

Cf. A000110, A000120, A002720, A005493, A005494, A007814, A008277, A035009, A045379, A053645, A129760, A143494, A143495, A196834, A265649, A295989.

Similar recurrences: A124758, A243499, A284005, A329369, A341392.

function a = A347204(max_n)
    a(1) = 1;
    a(2) = 2;
    for nloop = 3:max_n
        n = nloop-1;
        s = 0;
        for k = 0:floor(log2(n))-1
            s = s + a(1+A053645(n)-2^k*(mod(floor(n/(2^k)),2)));
        end
        a(nloop) = 2*a(A053645(n)+1) + s;
    end
end
function a_n = A053645(n)
    a_n = n - 2^floor(log2(n));
end % Thomas Scheuerle, Oct 25 2021

f[n_] := BitAnd[n, n - 1]; a[0] = 1; a[n_] := a[n] = a[f[n]/2] + a[Floor[(n + f[n])/2]]; Array[a, 100, 0] (* Amiram Eldar, Nov 19 2021 *)

f(n) = bitand(n, n-1); \\ A129760
a(n) = if (n<=1, n+1, if (n%2, a(n\2)+a(n-1), a(f(n/2)) + a(n/2+f(n/2)))); \\ Michel Marcus, Oct 25 2021

PARI
```
\\ Also see links.
```

A129760(n) = bitand(n, n-1);
memoA347204 = Map();
A347204(n) = if (n<=1, n+1, my(v); if(mapisdefined(memoA347204,n,&v), v, v = if(n%2, A347204(n\2)+A347204(n-1), A347204(A129760(n/2)) + A347204(n/2+A129760(n/2))); mapput(memoA347204,n,v); (v))); \\ (Memoized version of Michel Marcus's program given above) - Antti Karttunen, Nov 20 2021

a(n) = a(n - 2^f(n)) + (1 + f(n))*a((n - 2^f(n))/2) for n > 0 with a(0) = 1 where f(n) = A007814(n).
a(2n+1) = a(n) + a(2n) for n >= 0.
a(2n) = a(n - 2^f(n)) + a(2n - 2^f(n)) for n > 0 with a(0) = 1 where f(n) = A007814(n).
a(n) = 2*a(f(n)) + Sum_{k=0..floor(log_2(n))-1} a(f(n) - 2^k*T(n,k)) for n > 1 with a(0) = 1, a(1) = 2, and where f(n) = A053645(n), T(n,k) = floor(n/2^k) mod 2.
Sum_{k=0..2^n - 1} a(k) = A035009(n+1) for n >= 0.
a((4^n - 1)/3) = A002720(n) for n >= 0.
a(2^n - 1) = A000110(n+1),
a(2*(2^n - 1)) = A005493(n),
a(2^2*(2^n - 1)) = A005494(n),
a(2^3*(2^n - 1)) = A045379(n),
a(2^4*(2^n - 1)) = A196834(n),
a(2^m*(2^n-1)) = T(n,m+1) is the n-th (m+1)-Bell number for n >= 0, m >= 0 where T(n,m) = m*T(n-1,m) + Sum_{k=0..n-1} binomial(n-1,k)*T(k,m) with T(0,m) = 1.
a(n) = Sum_{j=0..2^A000120(n)-1} A243499(A295989(n,j)) for n >= 0. Also A243499(n) = Sum_{j=0..2^f(n)-1} (-1)^(f(n)-f(j)) a(A295989(n,j)) for n >= 0 where f(n) = A000120(n). In other words, a(n) = Sum_{j=0..n} (binomial(n,j) mod 2)*A243499(j) and A243499(n) = Sum_{j=0..n} (-1)^(f(n)-f(j))*(binomial(n,j) mod 2)*a(j) for n >= 0 where f(n) = A000120(n).
Generalization:
b(n, x) = (1/x)*b((n - 2^f(n))/2, x) + (-1)^n*b(floor((2n - 2^f(n))/2), x) for n > 0 with b(0, x) = 1 where f(n) = A007814(n).
Sum_{k=0..2^n - 1} b(k, x) = (1/x)^n for n >= 0.
b((4^n - 1)/3, x) = (1/x)^n*n!*L_{n}(x) for n >= 0 where L_{n}(x) is the n-th Laguerre polynomial.
b((8^n - 1)/7, x) = (1/x)^n*Sum_{k=0..n} (-x)^k*A265649(n, k) for n >= 0.
b(2^n - 1, x) = (1/x)^n*Sum_{k=0..n} (-x)^k*A008277(n+1, k+1),
b(2*(2^n - 1), x) = (1/x)^n*Sum_{k=0..n} (-x)^k*A143494(n+2, k+2),
b(2^2*(2^n - 1), x) = (1/x)^n*Sum_{k=0..n} (-x)^k*A143495(n+3, k+3),
b(2^m*(2^n - 1), x) = (1/x)^n*Sum_{k=0..n} (-x)^k*T(n+m+1, k+m+1, m+1) for n >= 0, m >= 0 where T(n,k,m) is m-Stirling numbers of the second kind.

A104594 A129760/2.

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 3, 0, 4, 4, 5, 4, 6, 6, 7, 0, 8, 8, 9, 8, 10, 10, 11, 8, 12, 12, 13, 12, 14, 14, 15, 0, 16, 16, 17, 16, 18, 18, 19, 16, 20, 20, 21, 20, 22, 22, 23, 16, 24, 24, 25, 24, 26, 26, 27, 24, 28, 28, 29, 28, 30, 30, 31, 0, 32, 32, 33, 32, 34, 34, 35, 32, 36, 36, 37, 36, 38, 38, 39

Offset: 1

N. J. A. Sloane, May 25 2008

nonn

a(n) is the degree of the n-th Stern polynomial defined in Beck and Dilcher. - Michel Marcus, May 20 2022

George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
R. Brown and J. L. Merzel, The number of Ducci sequences with a given period, Fib. Quart., 45 (2007), 115-121.

Cf. A129760.

a:= n-> Bits[And](n, n-1)/2:
seq(a(n), n=1..100);  # Alois P. Heinz, May 20 2022

a(n) = bitand(n, n-1)/2; \\ Michel Marcus, Sep 06 2017

A322018 a(n) = A006068(A129760(A003188(n))).

Original entry on oeis.org

0, 0, 3, 0, 7, 4, 7, 0, 15, 8, 11, 8, 15, 12, 15, 0, 31, 16, 19, 16, 23, 20, 23, 16, 31, 24, 27, 24, 31, 28, 31, 0, 63, 32, 35, 32, 39, 36, 39, 32, 47, 40, 43, 40, 47, 44, 47, 32, 63, 48, 51, 48, 55, 52, 55, 48, 63, 56, 59, 56, 63, 60, 63, 0, 127, 64, 67, 64, 71, 68, 71, 64, 79, 72, 75, 72, 79, 76, 79, 64, 95, 80, 83, 80, 87, 84, 87, 80

Offset: 0

Antti Karttunen, Nov 27 2018

nonn

For all n, A207901(a(n)) divides A207901(n), and similarly for A302033.

Antti Karttunen, Table of n, a(n) for n = 0..16383
Index entries for sequences related to binary expansion of n

Cf. A003188, A006068, A035327, A129760.

Cf. also A207901, A302033, A322017.

A003188(n) = bitxor(n, n>>1);
A006068(n)= { my(s=1, ns); while(1, ns = n >> s; if(0==ns, break()); n = bitxor(n, ns); s <<= 1; ); return (n); } \\ After code in A006068
A129760(n) = bitand(n,n-1); \\ From A129760
A322018(n) = A006068(A129760(A003188(n)));

a(n) = A006068(A129760(A003188(n))).

A048881 a(n) = A000120(n+1) - 1 = wt(n+1) - 1.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3

Offset: 0

Wolfdieter Lang

Highest power of 2 dividing n-th Catalan number (A000108).
a(n) = 0 iff n = 2^k - 1, k=0,1,...
Appears to be number of binary left-rotations (iterations of A006257) to reach fixed point of form 2^k-1. Right-rotation analog is A063250. This would imply that for n >= 0, a(n)=f(n), recursively defined to be 0 for n=0, otherwise as f( ( (1-n)(1-p)(1-s) - (1-n-p-s) ) / 2) + p (s+1) / 2, where p = n mod 2 and s = - signum(n) (f(n<0) is A000120(-n)). - Marc LeBrun, Jul 11 2001
Let f(0) = 01, f(1) = 12, f(2) = 23, f(3) = 34, f(4) = 45, etc. Sequence gives concatenation of 0, f(0), f(f(0)), f(f(f(0))), ... Also f(f(...f(0)...)) converges to A000120. - Philippe Deléham, Aug 14 2003
C(n, k) is the number of occurrence of k in the n-th group of terms in this sequence read by rows: {0}; {0, 1}; {0, 1, 1, 2}; {0, 1, 1, 2, 1, 2, 2, 3}; {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; ... - Philippe Deléham, Jan 01 2004
Highest power of 2 dividing binomial(n,floor(n/2)). - Benoit Cloitre, Oct 20 2003
2^a(n) are numerators in the Maclaurin series for (sin x)^2. - Jacob A. Siehler, Nov 11 2009
Conjecture: a(n) is the sum of digits of the n-th word in A076478, for n >= 1; has been confirmed for n up to 20000. - Clark Kimberling, Jul 14 2021

			From _Omar E. Pol_, Mar 08 2011: (Start)
Sequence can be written in the following form (irregular triangle):
  0,
  0,1,
  0,1,1,2,
  0,1,1,2,1,2,2,3,
  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  ...
Row sums are A001787.
(End)

R. Alter and K. K. Kubota, Prime and Prime Power Divisibility of Catalan Numbers, J. Comb. Th. A 15 (1973) pp. 243-256.
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.

Cf. A000120, A006257, A007318, A063250.

First differences of A078903.

a048881 n = a048881_list !! n
a048881_list = c [0] where c (x:xs) = x : c (xs ++ [x,x+1])
-- Reinhard Zumkeller, Mar 07 2011
(Python 3.10+)
def A048881(n): return (n+1).bit_count()-1 # Chai Wah Wu, Nov 15 2022

A048881 := proc(n)
    A000120(n+1)-1 ;
end proc:
seq(A048881(n),n=0..200) ; # R. J. Mathar, Mar 12 2018

a[n_] := IntegerExponent[ CatalanNumber[n], 2]; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Jun 21 2013 *)

{ a(n) = if( n<0, 0, n++; n /= 2^valuation(n,2); subst( Pol( binary( n ) ), x, 1) - 1 ) } /* Michael Somos, Aug 23 2007 */

{a(n) = if( n<0, 0, valuation( (2*n)! / n! / (n+1)!, 2 ) ) } /* Michael Somos, Aug 23 2007 */

a(n) = hammingweight(n+1) - 1; \\ Michel Marcus, Nov 15 2022

Writing n as 2^m+k with -1 <= k < 2^m-1, then a(n) = A000120(k+1). - Henry Bottomley, Mar 28 2000
a(n) = k if 2^k divides A000108(n) but 2^(k+1) does not divide A000108(n).
a(2*n) = a(n-1)+1, a(2*n+1) = a(n). - Vladeta Jovovic, Oct 10 2002
G.f.: (1/(x-x^2)) * (x^2/(1-x) - Sum_{k>=1} x^(2^k)/(1-x^(2^k))). - Ralf Stephan, Apr 13 2002
a(n) = A000120(A129760(n+1)). - Reinhard Zumkeller, Jun 30 2010
a(n+k) = A240857(n,k), 0 <= k <= n; in particular: a(n) = A240857(n,0). - Reinhard Zumkeller, Apr 14 2014
a(n) = (n+1)*2 - A101925(n+1). - Gleb Ivanov, Jan 12 2022

Entry revised by N. J. A. Sloane, Jun 07 2009

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.

Original entry on oeis.org

1, 3, 2, 10, 3, 7, 4, 36, 5, 11, 6, 26, 7, 15, 8, 136, 9, 19, 10, 42, 11, 23, 12, 100, 13, 27, 14, 58, 15, 31, 16, 528, 17, 35, 18, 74, 19, 39, 20, 164, 21, 43, 22, 90, 23, 47, 24, 392, 25, 51, 26, 106, 27, 55, 28, 228, 29, 59, 30, 122, 31, 63, 32, 2080, 33, 67, 34, 138, 35

Offset: 1

Johannes W. Meijer, Dec 24 2012

The a(n) appeared in the analysis of A220002, a sequence related to the Catalan numbers.
The first Maple program makes use of a program by Peter Luschny for the calculation of the a(n) values. The second Maple program shows that this sequence has a beautiful internal structure, see the first formula, while the third Maple program makes optimal use of this internal structure for the fast calculation of a(n) values for large n.
The cross references lead to sequences that have the same internal structure as this sequence.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences with simple ordinary generating functions, The OEIS, Jan 01 2004.

Cf. A000027 (the natural numbers), A000120 (1's-counting sequence), A000265 (remove 2's from n), A001316 (Gould's sequence), A001511 (the ruler function), A003484 (Hurwitz-Radon numbers), A003602 (a fractal sequence), A006519 (highest power of 2 dividing n), A007814 (binary carry sequence), A010060 (Thue-Morse sequence), A014577 (dragon curve), A014707 (dragon curve), A025480 (nim-values), A026741, A035263 (first Feigenbaum symbolic sequence), A037227, A038712, A048460, A048896, A051176, A053381 (smooth nowhere-zero vector fields), A055975 (Gray code related), A059134, A060789, A060819, A065916, A082392, A085296, A086799, A088837, A089265, A090739, A091512, A091519, A096268, A100892, A103391, A105321 (a fractal sequence), A109168 (a continued fraction), A117973, A129760, A151930, A153733, A160467, A162728, A181988, A182241, A191488 (a companion to Gould's sequence), A193365, A220466 (this sequence).

-- Following Ralf Stephan's recurrence:
import Data.List (transpose)
a220466 n = a006519_list !! (n-1)
a220466_list = 1 : concat
   (transpose [zipWith (-) (map (* 4) a220466_list) a006519_list, [2..]])
-- Reinhard Zumkeller, Aug 31 2014

# First Maple program
a := n -> 2^padic[ordp](n, 2)*(n+1)/2 : seq(a(n), n=1..69); # Peter Luschny, Dec 24 2012
# Second Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 4^p*(n-1)  + 2^(p-1)*(1+2^p) od: od: seq(a(n), n=1..nmax);
# Third Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do n:=2^p: n1:=1: while n <= nmax do a(n) := 4^p*(n1-1)+2^(p-1)*(1+2^p): n:=n+2^(p+1): n1:= n1+1: od: od:  seq(a(n), n=1..nmax);

A220466 = Module[{n, p}, p = IntegerExponent[#, 2]; n = (#/2^p + 1)/2; 4^p*(n - 1) + 2^(p - 1)*(1 + 2^p)] &; Array[A220466, 50] (* JungHwan Min, Aug 22 2016 *)

a(n)=if(n%2,n\2+1,4*a(n/2)-2^valuation(n/2,2)) \\ Ralf Stephan, Dec 17 2013

a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1. Observe that a(2^p) = A007582(p).
a(n) = ((n+1)/2)*(A060818(n)/A060818(n-1))
a(n) = (-1/64)*(q(n+1)/q(n))/(2*n+1) with q(n) = (-1)^(n+1)*2^(4*n-5)*(2*n)!*A060818(n-1) or q(n) = (1/8)*A220002(n-1)*1/(A098597(2*n-1)/A046161(2*n))*1/(A008991(n-1)/A008992(n-1))
Recurrence: a(2n) = 4a(n) - 2^A007814(n), a(2n+1) = n+1. - Ralf Stephan, Dec 17 2013

A295989 Irregular triangle T(n, k), read by rows, n >= 0 and 0 <= k < A001316(n): T(n, k) is the (k+1)-th nonnegative number m such that n AND m = m (where AND denotes the bitwise AND operator).

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, Dec 02 2017

The (n+1)-th row has A001316(n) terms and sums to n * A001316(n) / 2.
For any n >= 0 and k such that 0 <= k < A001316(n):
- if A000120(n) > 0 then T(n, 1) = A006519(n),
- if A000120(n) > 1 then T(n, 2) = 2^A285099(n),
- if A000120(n) > 0 then T(n, A001316(n)/2 - 1) = A053645(n),
- if A000120(n) > 0 then T(n, A001316(n)/2) = 2^A000523(n),
- if A000120(n) > 0 then T(n, A001316(n) - 2) = A129760(n),
- T(n, A001316(n) - 1) = n,
- the six previous relations correspond respectively (when applicable) to the second term, the third term, the pair of central terms, the penultimate term and the last term of a row,
- T(n, k) AND T(n, A001316(n) - k - 1) = 0,
- T(n, k) + T(n, A001316(n) - k - 1) = n,
- T(n, k) = k for any k < A006519(n+1),
- A000120(T(n, k)) = A000120(k).
If we plot (n, T(n,k)) then we obtain a skewed Sierpinski triangle (see Links section).
If interpreted as a flat sequence a(n) for n >= 0:
- a(n) = 0 iff n = A006046(k) for some k >= 0,
- a(n) = 1 iff n = A006046(2*k + 1) + 1 for some k >= 0,
- a(A006046(k) - 1) = k - 1 for any k > 0.

			Triangle begins:
  0:   [0]
  1:   [0, 1]
  2:   [0, 2]
  3:   [0, 1, 2, 3]
  4:   [0, 4]
  5:   [0, 1, 4, 5]
  6:   [0, 2, 4, 6]
  7:   [0, 1, 2, 3, 4, 5, 6, 7]
  8:   [0, 8]
  9:   [0, 1, 8, 9]
  10:  [0, 2, 8, 10]
  11:  [0, 1, 2, 3, 8, 9, 10, 11]
  12:  [0, 4, 8, 12]
  13:  [0, 1, 4, 5, 8, 9, 12, 13]
  14:  [0, 2, 4, 6, 8, 10, 12, 14]
  15:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Rémy Sigrist, Rows n = 0..256, flattened
Rémy Sigrist, Scatterplot of (n, T(n, k)) for n = 0..1023 and k = 0..A001316(n)-1

Cf. A000120, A000523, A001316 (row lengths), A006046, A006519, A053645, A129760, A285099.

First column of array in A352909.

A295989row[n_] := Select[Range[0, n], BitAnd[#, n-#] == 0 &];
Array[A295989row, 25, 0] (* Paolo Xausa, Feb 24 2024 *)

T(n,k) = if (k==0, 0, n%2==0, 2*T(n\2,k), k%2==0, 2*T(n\2, k\2), 2*T(n\2, k\2)+1)

For any n >= 0 and k such that 0 <= k < A001316(n):
- T(n, 0) = 0,
- T(2*n, k) = 2*T(n, k),
- T(2*n+1, 2*k) = 2*T(n, k),
- T(2*n+1, 2*k+1) = 2*T(n, k) + 1.

A109168 Continued fraction expansion of the constant x (A109169) such that the continued fraction of 2*x yields the continued fraction of x interleaved with the positive even numbers.

Original entry on oeis.org

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 6, 8, 7, 8, 8, 16, 9, 10, 10, 12, 11, 12, 12, 16, 13, 14, 14, 16, 15, 16, 16, 32, 17, 18, 18, 20, 19, 20, 20, 24, 21, 22, 22, 24, 23, 24, 24, 32, 25, 26, 26, 28, 27, 28, 28, 32, 29, 30, 30, 32, 31, 32, 32, 64, 33, 34, 34, 36, 35, 36, 36, 40, 37, 38, 38

Offset: 1

Paul D. Hanna, Jun 21 2005

Compare with continued fraction A100338.

The sequence is equal to the sequence of positive integers (1, 2, 3, 4, ...) interleaved with the sequence multiplied by two, 2*(1, 2, 2, 4, 3, ...) = (2, 4, 4, 8, 6, ...): see the first formula. - M. F. Hasler, Oct 19 2019

			x=1.408494279228906985748474279080697991613998955782051281466263817524862977...
The continued fraction expansion of 2*x = A109170:
[2;1, 4,2, 6,2, 8,4, 10,3, 12,4, 14,4, 16,8, 18,5, ...]
which equals the continued fraction of x interleaved with the even numbers.

Cf. A109169 (digits of x), A109170 (continued fraction of 2*x), A109171 (digits of 2*x).
Cf. A006519 and A129760. [Johannes W. Meijer, Jun 22 2011]
Half the terms of A285326.

nmax:=75; pmax:= ceil(log(nmax)/log(2)); for p from 0 to pmax do for n from 1 to nmax do a((2*n-1)*2^p):= n*2^p: od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Jun 22 2011

PARI
```
a(n)=if(n%2==1,(n+1)/2,2*a(n/2))
```

A109168(n)=(n+bitand(n,-n))\2 \\ M. F. Hasler, Oct 19 2019

;; With memoization-macro definec
(definec (A109168 n) (if (zero? n) n (if (odd? n) (/ (+ 1 n) 2) (* 2 (A109168 (/ n 2))))))
;; Antti Karttunen, Apr 19 2017

a(2*n-1) = n, a(2*n) = 2*a(n) for all n >= 1.
a((2*n-1)*2^p) = n * 2^p, p >= 0. - Johannes W. Meijer, Jun 22 2011
a(n) = n - (n AND n-1)/2. - Gary Detlefs, Jul 10 2014
a(n) = A285326(n)/2. - Antti Karttunen, Apr 19 2017
a(n) = A140472(n). - M. F. Hasler, Oct 19 2019

A108918 Reversed binary words in reversed lexicographic order.

Original entry on oeis.org

1, 3, 2, 5, 7, 6, 4, 9, 11, 10, 13, 15, 14, 12, 8, 17, 19, 18, 21, 23, 22, 20, 25, 27, 26, 29, 31, 30, 28, 24, 16, 33, 35, 34, 37, 39, 38, 36, 41, 43, 42, 45, 47, 46, 44, 40, 49, 51, 50, 53, 55, 54, 52, 57, 59, 58, 61, 63, 62, 60, 56, 48, 32, 65

Offset: 1

Joerg Arndt, Jul 20 2005

nonn

The lexicographic order of the subsets of the 4-element set is:
  1... {0}
  11.. {0, 1}
  111. {0, 1, 2}
  1111 {0, 1, 2, 3}
  11.1 {0, 1, 3}
  1.1. {0, 2}
  1.11 {0, 2, 3}
  1..1 {0, 3}
  .1.. {1}
  .11. {1, 2}
  .111 {1, 2, 3}
  .1.1 {1, 3}
  ..1. {2}
  ..11 {2, 3}
  ...1 {3}
The strings of dots and ones interpreted as binary words give this sequence:
  ...1   1
  ..11   3
  ..1.   2
  .1.1   5
  .111   7
  .11.   6
  .1..   4
  1..1   9
  1.11  11
  1.1.  10
  11.1  13
  1111  15
  111.  14
  11..  12
  1...   8
The index of the lowest set bit of a(n) is A082850(n) - 1. - Joerg Arndt, Apr 06 2011
The sequence is a permutation of the positive integers. - Joerg Arndt, Jan 31 2012
This is the output of the depth-first search with postordering in the binomial tree described in A129760 where the children of every node are visited in the ascending order of their values. Descending order cannot be used because 0 has infinite number of children; using preordering instead of postordering gives the natural numbers in their standard order. - Andrey Zabolotskiy, Sep 06 2019

Donald E. Knuth, The Art of Computer Programming, Volume 4A, section 7.2.1.3 exercise 19 (binomial tree traversed in post-order).

Alois P. Heinz, Table of n, a(n) for n = 1..8192
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26 "Binary words in lexicographic order for subsets", pp.70-74
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014-2015.
Index entries for sequences that are permutations of the natural numbers

The sequence of lowest bits is A079559. The sequence of fixed points (i.e. a(n)=n) is A079471. The inverse permutation is A118319.

The corresponding Gray code is described in A217262.

n=6; Reverse[ SortBy[ Range[2^n - 1], PadRight[ Flatten[ Position[ IntegerDigits[#, 2, n], 1] ], n] &]] (* Birkas Gyorgy, Jul 09 2012 *)

a(n) = my(s); forstep(k=logint(n,2),0,-1, if(bittest(n,k), n++;s=k)); n-(1<Kevin Ryde, Mar 31 2020

def a(n):
    s = 0
    for k in range(n.bit_length()-1, -1, -1):
        if n & (1 << k): n += 1; s = k
    return n - (1 << s)
print([a(n) for n in range(1, 65)]) # Michael S. Branicky, Aug 15 2022 after Kevin Ryde

a(2^(m+1)-1) = 2^m; a(2^m+k) = a(k+1) + 2^m for 0 <= k < 2^m-1. - Andrey Zabolotskiy, Oct 10 2019

A175330 a(n) = bitwise AND of prime(n) and prime(n+1).

Original entry on oeis.org

2, 1, 5, 3, 9, 1, 17, 19, 21, 29, 5, 33, 41, 43, 37, 49, 57, 1, 67, 65, 73, 67, 81, 65, 97, 101, 99, 105, 97, 113, 3, 129, 137, 129, 149, 149, 129, 163, 165, 161, 177, 181, 129, 193, 197, 195, 211, 195, 225, 225, 233, 225, 241, 1, 257, 261, 269, 261, 273, 281

Offset: 1

Leroy Quet, Apr 07 2010

Read each binary representation of the primes from right to left and then AND respective digits to form the binary equivalent of each term of this sequence.

Indices of 1's: 2, 6, 18, 54, 564, 3512, 6542, 564163, 2063689, 54400028, ... - Alex Ratushnyak, Apr 22 2012

			For n = 15, a(15) = 37 because the 15th prime is 47 and the 16th is 53, which have binary representations of 101111 and 110101 respectively; the bitwise AND of these values is 100101 which is the binary representation of 37:
  101111
& 110101
--------
  100101

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Wikipedia, Bitwise operation

Cf. A000040, A175329 (bitwise OR).
Cf. A129760 (bitwise AND of n and n-1).
Cf. A366550 (indices of ones).

read("transforms") ; A175330 := proc(n) ANDnos(ithprime(n),ithprime(n+1)) ; end proc: seq(A175330(n),n=1..60) ; # R. J. Mathar, Apr 15 2010
# second Maple program:
a:= n-> Bits[And](ithprime(n), ithprime(n+1)):
seq(a(n), n=1..70);  # Alois P. Heinz, Apr 15 2020

a[n_] := Prime[n]~BitAnd~Prime[n+1];
Array[a, 60] (* Jean-François Alcover, Jan 11 2021 *)

a(n) = bitand(prime(n), prime(n+1)); \\ Michel Marcus, Apr 16 2020

val prime: LazyList[Int] = 2 #:: LazyList.from(3).filter(i => prime.takeWhile {
   j => j * j <= i
}.forall {
   k => i % k != 0
})
(0 to 63).map(n => prime(n) & prime(n + 1)) // Alonso del Arte, Apr 18 2020

More terms from R. J. Mathar, Apr 15 2010

A285099 a(n) is the zero-based index of the second least significant 1-bit in the base-2 representation of n, or 0 if there are fewer than two 1-bits in n.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 2, 1, 0, 3, 3, 1, 3, 2, 2, 1, 0, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4

Offset: 0

Antti Karttunen, Apr 19 2017

			For n = 3, "11" in binary, the second least significant 1-bit (the second 1-bit from the right) is at position 1 (when the rightmost position is position 0), thus a(3) = 1.
For n = 4, "100" in binary, there is just one 1-bit present, thus a(4) = 0.
For n = 5, "101" in binary, the second 1-bit from the right is at position 2, thus a(5) = 2.
For n = 25, "11001" in binary, the second 1-bit from the right is at position 3, thus a(25) = 3.

Antti Karttunen, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A000120, A004198, A007814, A129760, A285097.

a007814[n_]:=IntegerExponent[n, 2]; a[n_]:=If[DigitCount[n, 2, 1]<2, 0, a007814[BitAnd[n, n - 1]]]; Table[a[n], {n, 0, 150}] (* Indranil Ghosh, Apr 20 2017 *)

import math
def a007814(n): return int(math.log(n - (n & n - 1), 2))
def a(n): return 0 if bin(n)[2:].count("1") < 2 else a007814(n & (n - 1)) # Indranil Ghosh, Apr 20 2017

(define (A285099 n) (if (<= (A000120 n) 1) 0 (A007814 (A004198bi n (- n 1))))) ;; A004198bi implements bitwise-and.

If A000120(n) < 2, a(n) = 0, otherwise a(n) = A007814(A129760(n)) = A007814(n AND (n-1)). [Where AND is bitwise-and, A004198].
From Jeffrey Shallit, Apr 19 2020: (Start)
This is a 2-regular sequence, satisfying the identities
a(4n) = -a(n) + a(2n),
a(4n+2) = a(4n+1),
a(8n+1) = -a(2n+1) + 2a(4n+1),
a(8n+3) = a(4n+3),
a(8n+5) = 2a(4n+3),
a(8n+7) = a(4n+3). (End)

cp's OEIS Frontend

A347204 a(n) = a(f(n)/2) + a(floor((n+f(n))/2)) for n > 0 with a(0) = 1 where f(n) = A129760(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

MATLAB

Mathematica

PARI

PARI

PARI

Formula

A104594 A129760/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

A322018 a(n) = A006068(A129760(A003188(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A048881 a(n) = A000120(n+1) - 1 = wt(n+1) - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A220466 a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A295989 Irregular triangle T(n, k), read by rows, n >= 0 and 0 <= k < A001316(n): T(n, k) is the (k+1)-th nonnegative number m such that n AND m = m (where AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A109168 Continued fraction expansion of the constant x (A109169) such that the continued fraction of 2*x yields the continued fraction of x interleaved with the positive even numbers.

Views

Author

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.