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,4

Comments

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

See A245196 for more about this class of sequences.

Run length transform of A011782: 1,1,2,4,8,16,32,64,... - Chai Wah Wu, Oct 19 2016

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.

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).

a(n) = A162510(A005940(1+n)). - Antti Karttunen, Oct 29 2016

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.

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A293438 A318622 A353785 * A340191 A182105 A023506

Adjacent sequences: A245192 A245193 A245194 * A245196 A245197 A245198

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jul 24 2014

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

Status

approved