A245195 a(n) = 2^A014081(n).
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, 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, 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
Offset: 0
Links
- Chai Wah Wu and Robert Israel, Table of n, a(n) for n = 0..10000
- Robert Israel, Proof that A277560 is the same as A245195 [This will be modified to reflect the fact that the two sequences have now been merged]
- Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166 [math.CO], 2016.
Crossrefs
Programs
-
Maple
# 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. # 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 # (if j=0) a(2^k-2^r) = G(k-r-1), # (if j>0) a(2^k-2^r+j) = m*G(k-r-1)*a(j). # Since Maple gives its lists an offset of 1, it is necessary to add 1 to the arguments of G. # For the present sequence, G(n)=2^n and m=1. G:=[seq(2^n,n=0..30)]; m:=1; f:=proc(n) option remember; global m,G; local k,r,j,np; if n <= 2 then G[0+1] elif n=3 then G[1+1] 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] else k:=1+floor(log[2](n)); np:=2^k-n; if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi; if j=0 then G[k-r-1+1]; else m*G[k-r-1+1]*f(j); fi; fi; end; [seq(f(n),n=1..520)]: # Setting G(n) = A083424(n) and m = 8 gives A245180. Setting G(n) = 2^n and m = 2 gives A048896. 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
-
Mathematica
Table[Sum[Mod[Binomial[n, 2 k] Binomial[n, k], 2], {k, 0, n}], {n, 0, 85}] (* Michael De Vlieger, Oct 21 2016 *) -
PARI
a(n) = 2^hammingweight(bitand(n, n>>1)) \\ Charles R Greathouse IV, Jul 16 2016
-
PARI
a(n) = sum(k=0, n, binomial(n, 2*k)*binomial(n,k) % 2); \\ Michel Marcus, Oct 21 2016
-
Python
from _future_ import division def A277560(n): return sum(int(not (~n & 2*k) | (~n & k)) for k in range(n//2+1))
-
Python
def A245195(n): return 1<<(n&(n>>1)).bit_count() # Chai Wah Wu, Feb 11 2023
Formula
The entries may be arranged into blocks of sizes 1,2,4,8,...:
B_0: 1,
B_1: 1, 2,
B_2: 1, 1, 2, 4,
B_3: 1, 1, 1, 2, 2, 2, 4, 8,
B_4: 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16,
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,
...
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
(if j=0) a(2^k-2^r) = 2^(k-r-1),
(if j>0) a(2^k-2^r+j) = 2^(k-r-1)*a(j).
From Robert Israel, Nov 02 2016: (Start)
a(2*k) = a(k).
a(4*k+1) = a(k).
a(4*k+3) = 2*a(2*k+1).
G.f. g(x) satisfies g(x) = x + (2*x+1)*g(x^2) - x*g(x^4). (End)
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.
Extensions
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
Comments