A085357 Common residues of binomial(3n,n)/(2n+1) modulo 2: relates ternary trees (A001764) to the infinite Fibonacci word (A003849).

1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Author

Paul D. Hanna, Jun 25 2003

Keywords

• nonn

Comments

The n-th runs of ones is given by: 3 - A003849(n) (infinite Fibonacci word) = A076662(n+1). Runs of zeros are given by: A085358 and are also directly related to the Fibonacci sequence. Coefficients of A(x)^3 are found in A085359.

a(n) = 0 iff some binary digit of n is 1 while the corresponding binary digit of 3*n is 0. - Robert Israel, Jul 12 2016

The Run Length Transform of [0,1,0,0,0,...], A063524, the characteristic function of 1. (See A227349 for the definition). - Antti Karttunen, Oct 15 2016

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen, A. Petersen and G. Skordev, Automaticity of double sequences generated by one-dimensional linear cellular automata, Theoret. Comput. Sci. 186 (1997), 195-209.
• J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.
• R. Bacher and C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.
• Paul Tarau, Emulating Primality with Multiset Representations of Natural Numbers, in Theoretical Aspects of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238, DOI: 10.1007/978-3-642-23283-1_15.
• Index entries for characteristic functions
• Index entries for sequences computed with run length transform

Crossrefs

Cf. A001764 (ternary trees), A085358 (runs of zeros), A076662 (runs of ones), A003849 (infinite Fibonacci word), A085359 (A(x)^3).

Cf. also A003714, A005940, A008966, A063524, A227349, A277010, A324964.

Absolute values of A132971.

Programs

Magma

[Binomial(3*n,n) mod 2: n in [0..100]]; // Vincenzo Librandi, Jul 09 2016

Maple

f:= proc(n) local L,Lp;
  L:= convert(n,base,2);
  Lp:= convert(3*n,base,2);
  if has(L-Lp[1..nops(L)],1) then 0 else 1 fi
end proc:
map(f, [$0..100]); # Robert Israel, Jul 12 2016

Mathematica

Table[Mod[Binomial[3 n, n], 2], {n, 0, 120}] (* Michael De Vlieger, Jul 08 2016 *)

PARI

A085357(n) = !bitand(n,n<<1); \\ Antti Karttunen, Aug 22 2019

Python

def A085357(n): return int(not n&(n<<1)) # Chai Wah Wu, Jun 25 2025

Formula

G.f.: 1 + x*A(x)^3 = A(x) (Mod 2); a(n) = A001764(n) (Mod 2).

a(n) = binomial(3n, n) (mod 2). Characteristic function of Fibbinary numbers (i.e. a(n)=1 iff n is in A003714). - Benoit Cloitre, Nov 15 2003

Recurrence: a(0) = 1, a(2n) = a(4n+1) = a(n), a(4n+3) = 0.

a(n-2) = A000256(n)(mod 2), for n>2. - John M. Campbell, Jul 08 2016

a(n) = A000621(n+1)(mod 2). - John M. Campbell, Jul 15 2016

a(n) = A000625(n)(mod 2). - John M. Campbell, Jul 15 2016

a(n) = A008966(A005940(1+n)). [Follows from the Run Length Transform interpretation, see also A277010.] - Antti Karttunen, Oct 15 2016

a(n) = abs(A132971(n)) = abs(A008683(A005940(1+n))). - Antti Karttunen, May 30 2017