login
A106737
a(n) = Sum_{k=0..n} ({binomial(n+k,n-k)*binomial(n,k)} mod 2).
23
1, 2, 2, 3, 2, 4, 3, 4, 2, 4, 4, 6, 3, 6, 4, 5, 2, 4, 4, 6, 4, 8, 6, 8, 3, 6, 6, 9, 4, 8, 5, 6, 2, 4, 4, 6, 4, 8, 6, 8, 4, 8, 8, 12, 6, 12, 8, 10, 3, 6, 6, 9, 6, 12, 9, 12, 4, 8, 8, 12, 5, 10, 6, 7, 2, 4, 4, 6, 4, 8, 6, 8, 4, 8, 8, 12, 6, 12, 8, 10, 4, 8, 8, 12, 8, 16, 12, 16, 6, 12, 12, 18, 8, 16, 10, 12
OFFSET
0,2
COMMENTS
The formula (the recurrence, if confirmed to be equal to sum binomial formula) implies that this is the run length transform of the sequence 1,2,3,4,5,... - N. J. A. Sloane, Feb 05 2015. Note: That sequence should be considered as a successor function a(n) = n+1, starting from offset 0. See also A020725. - Antti Karttunen, Oct 15 2016
The recurrence formula is correct. See paper in links. - Chai Wah Wu, Oct 16 2016
FORMULA
a(0)=1, a(2n) = a(n), a(4n+1) = 2*a(2n), a(4n+3) = 2*a(2n+1) - a(n).
From Antti Karttunen, Oct 15 2016: (Start)
a(n) = A000005(A005940(1+n)). [Follows from the Run Length Transform-interpretation.]
For n > 1, a(n^2) is always even. [Based on RLT-interpretation. n^2 = 1 modulo 4 for all odd n and ((2^k)*n)^2 = 2^(2k) * (n^2), thus the last 1-bit is always alone and contributes 2 to the product, making it even.]
(End)
MATHEMATICA
Table[Sum[Mod[#, 2] &[Binomial[n + k, n - k] Binomial[n, k]], {k, 0, n}], {n, 0, 95}] (* Michael De Vlieger, Oct 17 2016 *)
PROG
(PARI) a(n) = sum(k=0, n, (binomial(n+k, n-k)*binomial(n, k)) % 2); \\ Michel Marcus, Dec 08 2013
(Python)
def A106737(n):
return sum(int(not (~(n+k) & (n-k)) | (~n & k)) for k in range(n+1)) # Chai Wah Wu, Feb 09 2016
(Scheme, two mathematically equal implementations, based on RLT-interpretation)
;; The first one implements the given recurrence and uses memoization-macro definec:
(definec (A106737 n) (cond ((zero? n) 1) ((even? n) (A106737 (/ n 2))) ((= 1 (modulo n 4)) (* 2 (A106737 (/ (- n 1) 2)))) (else (- (* 2 (A106737 (/ (- n 1) 2))) (A106737 (/ (- n 3) 4))))))
;; This one applies the Run Length Transform explicitly to r -> r+1 function:
(define (A106737 n) (fold-left (lambda (a r) (* a (+ 1 r))) 1 (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2))))) ;; See A227349 for the required other functions.
;; Antti Karttunen, Oct 15 2016
CROSSREFS
Row sums of triangle in A253084.
Cf. A000005, A005940, A020725, A227349, A277335 (positions of odd terms).
Cf. also A153013.
Sequence in context: A060025 A368572 A067399 * A359360 A323164 A363685
KEYWORD
nonn
AUTHOR
Benoit Cloitre, May 15 2005
STATUS
approved