cp's OEIS Frontend

A245195 a(n) = 2^A014081(n).

%I A245195 #68 Mar 17 2023 15:30:33
%S A245195 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 A245195 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 A245195 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 A245195 a(n) = 2^A014081(n).
%C A245195 This sequence provides a bridge between A245180 (and, presumably, A160239) and A014081.
%C A245195 See A245196 for more about this class of sequences.
%C A245195 Run length transform of A011782: 1,1,2,4,8,16,32,64,... - _Chai Wah Wu_, Oct 19 2016
%H A245195 Chai Wah Wu and Robert Israel, <a href="/A245195/b245195.txt">Table of n, a(n) for n = 0..10000</a>
%H A245195 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 A245195 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 A245195 The entries may be arranged into blocks of sizes 1,2,4,8,...:
%F A245195 B_0: 1,
%F A245195 B_1: 1, 2,
%F A245195 B_2: 1, 1, 2, 4,
%F A245195 B_3: 1, 1, 1, 2, 2, 2, 4, 8,
%F A245195 B_4: 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16,
%F A245195 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 A245195 ...
%F A245195 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 A245195 (if j=0) a(2^k-2^r) = 2^(k-r-1),
%F A245195 (if j>0) a(2^k-2^r+j) = 2^(k-r-1)*a(j).
%F A245195 a(n) = A162510(A005940(1+n)). - _Antti Karttunen_, Oct 29 2016
%F A245195 From _Robert Israel_, Nov 02 2016: (Start)
%F A245195 a(2*k)   = a(k).
%F A245195 a(4*k+1) = a(k).
%F A245195 a(4*k+3) = 2*a(2*k+1).
%F A245195 G.f. g(x) satisfies g(x) = x + (2*x+1)*g(x^2) - x*g(x^4). (End)
%F A245195 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 A245195 # 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 A245195 # 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 A245195 # (if j=0) a(2^k-2^r) = G(k-r-1),
%p A245195 # (if j>0) a(2^k-2^r+j) = m*G(k-r-1)*a(j).
%p A245195 # Since Maple gives its lists an offset of 1, it is necessary to add 1 to the arguments of G.
%p A245195 # For the present sequence, G(n)=2^n and m=1.
%p A245195 G:=[seq(2^n,n=0..30)];
%p A245195 m:=1;
%p A245195 f:=proc(n) option remember; global m,G; local k,r,j,np;
%p A245195 if n <= 2 then G[0+1] elif n=3 then G[1+1]
%p A245195 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 A245195 else
%p A245195    k:=1+floor(log[2](n)); np:=2^k-n;
%p A245195    if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;
%p A245195    if j=0 then G[k-r-1+1]; else m*G[k-r-1+1]*f(j); fi;
%p A245195 fi;
%p A245195 end;
%p A245195 [seq(f(n),n=1..520)]:
%p A245195 # Setting G(n) = A083424(n) and m = 8 gives A245180. Setting G(n) = 2^n and m = 2 gives A048896.
%p A245195 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 A245195 Table[Sum[Mod[Binomial[n, 2 k] Binomial[n, k], 2], {k, 0, n}], {n, 0, 85}] (* _Michael De Vlieger_, Oct 21 2016 *)
%o A245195 (PARI) a(n) = 2^hammingweight(bitand(n, n>>1)) \\ _Charles R Greathouse IV_, Jul 16 2016
%o A245195 (PARI) a(n) = sum(k=0, n, binomial(n, 2*k)*binomial(n,k) % 2); \\ _Michel Marcus_, Oct 21 2016
%o A245195 (Python)
%o A245195 from __future__ import division
%o A245195 def A277560(n):
%o A245195     return sum(int(not (~n & 2*k) | (~n & k)) for k in range(n//2+1))
%o A245195 (Python)
%o A245195 def A245195(n): return 1<<(n&(n>>1)).bit_count() # _Chai Wah Wu_, Feb 11 2023
%Y A245195 Cf. A014081, A245180, A160239, A048896, A245196, A005725, A005940, A011782, A106737, A162510.
%K A245195 nonn,tabf
%O A245195 0,4
%A A245195 _N. J. A. Sloane_, Jul 24 2014
%E A245195 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