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
LINKS
Chai Wah Wu, Table of n, a(n) for n = 0..10000
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166 [math.CO], 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)
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
KEYWORD
nonn
AUTHOR
Benoit Cloitre, May 15 2005
STATUS
approved