login
a(n) = 2^A014081(n).
4

%I #68 Mar 17 2023 15:30:33

%S 1,1,1,2,1,1,2,4,1,1,1,2,2,2,4,8,1,1,1,2,1,1,2,4,2,2,2,4,4,4,8,16,1,1,

%T 1,2,1,1,2,4,1,1,1,2,2,2,4,8,2,2,2,4,2,2,4,8,4,4,4,8,8,8,16,32,1,1,1,

%U 2,1,1,2,4,1,1,1,2,2,2,4,8,1,1,1,2,1,1,2,4,2,2,2,4,4,4,8,16,2,2,2,4,2

%N a(n) = 2^A014081(n).

%C This sequence provides a bridge between A245180 (and, presumably, A160239) and A014081.

%C See A245196 for more about this class of sequences.

%C Run length transform of A011782: 1,1,2,4,8,16,32,64,... - _Chai Wah Wu_, Oct 19 2016

%H Chai Wah Wu and Robert Israel, <a href="/A245195/b245195.txt">Table of n, a(n) for n = 0..10000</a>

%H Robert Israel, <a href="/A277560/a277560.pdf">Proof that A277560 is the same as A245195</a> [This will be modified to reflect the fact that the two sequences have now been merged]

%H Chai Wah Wu, <a href="https://arxiv.org/abs/1610.06166">Sums of products of binomial coefficients mod 2 and run length transforms of sequences</a>, arXiv:1610.06166 [math.CO], 2016.

%F The entries may be arranged into blocks of sizes 1,2,4,8,...:

%F B_0: 1,

%F B_1: 1, 2,

%F B_2: 1, 1, 2, 4,

%F B_3: 1, 1, 1, 2, 2, 2, 4, 8,

%F B_4: 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16,

%F B_5: 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 2, 4, 8, 2, 2, 2, 4, 2, 2, 4, 8, 4, 4, 4, 8, 8, 8, 16, 32,

%F ...

%F Consider the block B_{k-1} containing terms a(2^(k-1)), a(2^(k-1)+1), ..., a(2^k-1). It is convenient to index the terms working backwards from the next, 2^k-th, term. For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then

%F (if j=0) a(2^k-2^r) = 2^(k-r-1),

%F (if j>0) a(2^k-2^r+j) = 2^(k-r-1)*a(j).

%F a(n) = A162510(A005940(1+n)). - _Antti Karttunen_, Oct 29 2016

%F From _Robert Israel_, Nov 02 2016: (Start)

%F a(2*k) = a(k).

%F a(4*k+1) = a(k).

%F a(4*k+3) = 2*a(2*k+1).

%F G.f. g(x) satisfies g(x) = x + (2*x+1)*g(x^2) - x*g(x^4). (End)

%F Also, a(n) = Sum_{k=0..floor(n/2)} ((binomial(n,2k)*binomial(n,k)) mod 2). - _Chai Wah Wu_, Oct 19 2016 and _Robert Israel_, Nov 04 2016. For proof, see the article by Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166, or the Robert Israel link.

%p # This Maple program applies more generally to a sequence where the recurrence across a block is as follows. The parameters to be set are the sequence G(0), G(1), G(2), ... (the final terms in the blocks), and the multiplier m.

%p # For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then

%p # (if j=0) a(2^k-2^r) = G(k-r-1),

%p # (if j>0) a(2^k-2^r+j) = m*G(k-r-1)*a(j).

%p # Since Maple gives its lists an offset of 1, it is necessary to add 1 to the arguments of G.

%p # For the present sequence, G(n)=2^n and m=1.

%p G:=[seq(2^n,n=0..30)];

%p m:=1;

%p f:=proc(n) option remember; global m,G; local k,r,j,np;

%p if n <= 2 then G[0+1] elif n=3 then G[1+1]

%p elif n=4 then G[0+1] elif n=5 then m*G[0+1] elif n=6 then G[1+1] elif n=7 then G[2+1]

%p else

%p k:=1+floor(log[2](n)); np:=2^k-n;

%p if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;

%p if j=0 then G[k-r-1+1]; else m*G[k-r-1+1]*f(j); fi;

%p fi;

%p end;

%p [seq(f(n),n=1..520)]:

%p # Setting G(n) = A083424(n) and m = 8 gives A245180. Setting G(n) = 2^n and m = 2 gives A048896.

%p A245195:=n->add(binomial(n,2*k)*binomial(n,k) mod 2, k=0..floor(n/2)): seq(A245195(n), n=0..200); # _Wesley Ivan Hurt_, Nov 01 2016

%t Table[Sum[Mod[Binomial[n, 2 k] Binomial[n, k], 2], {k, 0, n}], {n, 0, 85}] (* _Michael De Vlieger_, Oct 21 2016 *)

%o (PARI) a(n) = 2^hammingweight(bitand(n, n>>1)) \\ _Charles R Greathouse IV_, Jul 16 2016

%o (PARI) a(n) = sum(k=0, n, binomial(n, 2*k)*binomial(n,k) % 2); \\ _Michel Marcus_, Oct 21 2016

%o (Python)

%o from __future__ import division

%o def A277560(n):

%o return sum(int(not (~n & 2*k) | (~n & k)) for k in range(n//2+1))

%o (Python)

%o def A245195(n): return 1<<(n&(n>>1)).bit_count() # _Chai Wah Wu_, Feb 11 2023

%Y Cf. A014081, A245180, A160239, A048896, A245196, A005725, A005940, A011782, A106737, A162510.

%K nonn,tabf

%O 0,4

%A _N. J. A. Sloane_, Jul 24 2014

%E Changed offset to 0, merged former entry A277560 from _Chai Wah Wu_ (Oct 19 2016) with this sequence. - _N. J. A. Sloane_, Nov 05 2016