|
%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
|
