login
Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci number system) then a(n) = 2^(i1 - 2) + 2^(i2 - 2) + ... + 2^(ik - 2). Also numbers whose binary representation contains no two adjacent 1's.
225

%I #286 Aug 22 2024 20:34:43

%S 0,1,2,4,5,8,9,10,16,17,18,20,21,32,33,34,36,37,40,41,42,64,65,66,68,

%T 69,72,73,74,80,81,82,84,85,128,129,130,132,133,136,137,138,144,145,

%U 146,148,149,160,161,162,164,165,168,169,170,256,257,258,260,261,264

%N Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci number system) then a(n) = 2^(i1 - 2) + 2^(i2 - 2) + ... + 2^(ik - 2). Also numbers whose binary representation contains no two adjacent 1's.

%C The name "Fibbinary" is due to _Marc LeBrun_.

%C "... integers whose binary representation contains no consecutive ones and noticed that the number of such numbers with n bits was fibonacci(n)". [posting to sci.math by Bob Jenkins (bob_jenkins(AT)burtleburtle.net), Jul 17 2002]

%C From _Benoit Cloitre_, Mar 08 2003: (Start)

%C A number m is in the sequence if and only if C(3m, m) (or equally, C(3m, 2m)) is odd.

%C a(n) == A003849(n) (mod 2). (End)

%C Numbers m such that m XOR 2*m = 3*m. - _Reinhard Zumkeller_, May 03 2005. [This implies that A003188(2*a(n)) = 3*a(n) holds for all n.]

%C Numbers whose base-2 representation contains no two adjacent ones. For example, m = 17 = 10001_2 belongs to the sequence, but m = 19 = 10011_2 does not. - _Ctibor O. Zizka_, May 13 2008

%C m is in the sequence if and only if the central Stirling number of the second kind S(2*m, m) = A007820(m) is odd. - O-Yeat Chan (math(AT)oyeat.com), Sep 03 2009

%C A000120(3*a(n)) = 2*A000120(a(n)); A002450 is a subsequence.

%C Every nonnegative integer can be expressed as the sum of two terms of this sequence. - _Franklin T. Adams-Watters_, Jun 11 2011

%C Subsequence of A213526. - _Arkadiusz Wesolowski_, Jun 20 2012

%C This is also the union of A215024 and A215025 - see the Comment in A014417. - _N. J. A. Sloane_, Aug 10 2012

%C The binary representation of each term m contains no two adjacent 1's, so we have (m XOR 2m XOR 3m) = 0, and thus a two-player Nim game with three heaps of (m, 2m, 3m) stones is a losing configuration for the first player. - _V. Raman_, Sep 17 2012

%C Positions of zeros in A014081. - _John Keith_, Mar 07 2022

%C These numbers are similar to Fibternary numbers A003726, Tribbinary numbers A060140 and Tribternary numbers. This sequence is a subsequence of Fibternary numbers A003726. The number of Fibbinary numbers less than any power of two is a Fibonacci number. We can generate this sequence recursively: start with 0 and 1; then, if x is in the sequence add 2x and 4x+1 to the sequence. The Fibbinary numbers have the property that the n-th Fibbinary number is even if the n-th term of the Fibonacci word is a. Respectively, the n-th Fibbinary number is odd (of the form 4x+1) if the n-th term of the Fibonacci word is b. Every number has a Fibbinary multiple. - _Tanya Khovanova_ and PRIMES STEP Senior, Aug 30 2022

%C This is the ordered set S of numbers defined recursively by: 0 is in S; if x is in S, then 2*x and 4*x + 1 are in S. See Kimberling (2006) Example 3, in references below. - _Harry Richman_, Jan 31 2024

%D Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493.

%H G. C. Greubel and T. D. Noe, <a href="/A003714/b003714.txt">Table of n, a(n) for n = 0..5000</a> (terms 0 to 1363 by T. D. Noe)

%H J.-P. Allouche, J. Shallit, and G. Skordev, <a href="http://dx.doi.org/10.1016/j.disc.2004.12.004">Self-generating sets, integers with missing blocks and substitutions</a>, Discrete Math., Vol. 292, No. 1-3 (2005), pp. 1-15.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 74-77, pp. 754-756.

%H Robert Baillie and Thomas Schmelzer, <a href="https://library.wolfram.com/infocenter/MathSource/7166/">Summing Kempner's Curious (Slowly-Convergent) Series</a>, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.

%H Marc Chamberland and Karl Dilcher, <a href="http://dx.doi.org/10.1016/j.jnt.2009.05.010">A Binomial Sum Related to Wolstenholme's Theorem</a>, J. Number Theory, Vol. 171, Issue 11 (Nov. 2009), pp. 2659-2672. See Lemma 4.2 p. 2668.

%H O-Yeat Chan and Dante Manna, <a href="http://www.oyeat.com/papers/stirling9.pdf">Divisibility properties of Stirling numbers of the second kind</a>.

%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.

%H David Eppstein, <a href="https://11011110.github.io/blog/2021/10/02/generating-fibbinary-numbers.html">Generating fibbinary numbers, three ways</a>, 2021.

%H Clark Kimberling, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00085-2">Affinely recursive sets and orderings of languages</a>, Discrete Math., Vol. 274, No. 1-3 (2004), pp. 147-160.

%H Roman S. Klyujkov, <a href="https://gist.github.com/uxn/93d8ebf9cd022cb42a54597fe99d4599">Quick Fibbinary Numbers Addition</a>, C++ function with test program.

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html">Rabbit Sequence in Zeckendorf Expansion (A003714)</a>.

%H Linus Lindroos, Andrew Sills, and Hua Wang, <a href="https://www.fq.math.ca/Papers1/52-1/LindroosSillsWang.pdf">Odd fibbinary numbers and the golden ratio</a>, Fib. Q., Vol. 52, No. 1 (2014), pp. 61-65; <a href="http://digitalcommons.georgiasouthern.edu/math-sci-facpubs/182/">alternative link</a>.

%H A. J. Macfarlane, <a href="https://arxiv.org/abs/2405.18128">On the fibbinary numbers and the Wythoff array</a>, arXiv:2405.18128 [math.CO], 2024. See pages 1, 5.

%H Douglas M. McKenna, <a href="https://doi.org/10.54550/ECA2022V2S2R13">Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-Style Square-Filling Curves</a>, ECA 2:2 (2022) Article S2R13.

%H Joris Nieuwveld, <a href="https://arxiv.org/abs/2108.11382">Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding</a>, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.

%H Yaron Shany and Amit Berman, <a href="https://arxiv.org/abs/2408.08218">The Generating Idempotent Is a Minimum-Weight Codeword for Some Binary BCH Codes</a>, arXiv:2408.08218 [cs.IT], 2024. See p. 10.

%H N. J. A. Sloane, <a href="/A003714/a003714.txt">Table of n, a(n) (base 10), a(n) (base 2), for n = 0..1000</a>.

%H Chai Wah Wu, <a href="https://arxiv.org/abs/1810.02293">Record values in appending and prepending bitstrings to runs of binary digits</a>, arXiv:1810.02293 [math.NT], 2018.

%H <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.

%H <a href="/index/Con#CongruCrossDomain">Index entries for sequences defined by congruent products between domains N and GF(2)[X]</a>.

%H <a href="/index/Con#CongruXOR">Index entries for sequences defined by congruent products under XOR</a>.

%F No two adjacent 1's in binary expansion.

%F Let f(x) := Sum_{n >= 0} x^Fibbinary(n). (This is the generating function of the characteristic function of this sequence.) Then f satisfies the functional equation f(x) = x*f(x^4) + f(x^2).

%F a(0) = 0, a(1) = 1, a(2) = 2, a(n) = 2^(A072649(n) - 1) + a(n - A000045(1 + A072649(n))). - _Antti Karttunen_

%F It appears that this sequence gives m such that A082759(3*m) is odd; or, probably equivalently, m such that A037011(3*m) = 1. - _Benoit Cloitre_, Jun 20 2003

%F If m is in the sequence then so are 2*m and 4*m + 1. - _Henry Bottomley_, Jan 11 2005

%F A116361(a(n)) <= 1. - _Reinhard Zumkeller_, Feb 04 2006

%F A085357(a(n)) = 1; A179821(a(n)) = a(n). - _Reinhard Zumkeller_, Jul 31 2010

%F a(n)/n^k is bounded (but does not tend to a limit), where k = 1.44... = A104287. - _Charles R Greathouse IV_, Sep 19 2012

%F a(n) = a(A193564(n+1))*2^(A003849(n) + 1) + A003849(n) for n > 0. - _Daniel Starodubtsev_, Aug 05 2021

%F There are Fibonacci(n+1) terms with up to n bits in this sequence. - _Charles R Greathouse IV_, Oct 22 2021

%F Sum_{n>=1} 1/a(n) = 3.704711752910469457886531055976801955909489488376627037756627135425780134020... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - _Amiram Eldar_, Feb 12 2022

%e From _Joerg Arndt_, Jun 11 2011: (Start)

%e In the following, dots are used for zeros in the binary representation:

%e a(n) binary(a(n)) n

%e 0: ....... 0

%e 1: ......1 1

%e 2: .....1. 2

%e 4: ....1.. 3

%e 5: ....1.1 4

%e 8: ...1... 5

%e 9: ...1..1 6

%e 10: ...1.1. 7

%e 16: ..1.... 8

%e 17: ..1...1 9

%e 18: ..1..1. 10

%e 20: ..1.1.. 11

%e 21: ..1.1.1 12

%e 32: .1..... 13

%e 33: .1....1 14

%e 34: .1...1. 15

%e 36: .1..1.. 16

%e 37: .1..1.1 17

%e 40: .1.1... 18

%e 41: .1.1..1 19

%e 42: .1.1.1. 20

%e 64: 1...... 21

%e 65: 1.....1 22

%e (End)

%p A003714 := proc(n)

%p option remember;

%p if n < 3 then

%p n ;

%p else

%p 2^(A072649(n)-1) + procname(n-combinat[fibonacci](1+A072649(n))) ;

%p end if;

%p end proc:

%p seq(A003714(n),n=0..10) ;

%p # To produce a table giving n, a(n) (base 10), a(n) (base 2) - from _N. J. A. Sloane_, Sep 30 2018

%p # binary: binary representation of n, in human order

%p binary:=proc(n) local t1,L;

%p if n<0 then ERROR("n must be nonnegative"); fi;

%p if n=0 then return([0]); fi;

%p t1:=convert(n,base,2); L:=nops(t1);

%p [seq(t1[L+1-i],i=1..L)];

%p end;

%p for n from 0 to 100 do t1:=A003714(n); lprint(n, t1, binary(t1)); od:

%t fibBin[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k--]; FromDigits[fr, 2]]; Table[fibBin[n], {n, 0, 61}] (* _Robert G. Wilson v_, Sep 18 2004 *)

%t Select[Range[0, 270], ! MemberQ[Partition[IntegerDigits[#, 2], 2, 1], {1, 1}] &] (* _Harvey P. Dale_, Jul 17 2011 *)

%t Select[Range[256], BitAnd[#, 2 #] == 0 &] (* _Alonso del Arte_, Jun 18 2012 *)

%t With[{r = Range[10^5]}, Pick[r, BitAnd[r, 2 r], 0]] (* _Eric W. Weisstein_, Aug 18 2017 *)

%t Select[Range[0, 299], SequenceCount[IntegerDigits[#, 2], {1, 1}] == 0 &] (* Requires Mathematica version 10 or later. -- _Harvey P. Dale_, Dec 06 2018 *)

%o (Haskell)

%o import Data.Set (Set, singleton, insert, deleteFindMin)

%o a003714 n = a003714_list !! n

%o a003714_list = 0 : f (singleton 1) where

%o f :: Set Integer -> [Integer]

%o f s = m : (f $ insert (4*m + 1) $ insert (2*m) s')

%o where (m, s') = deleteFindMin s

%o -- _Reinhard Zumkeller_, Jun 03 2012, Feb 07 2012

%o (PARI) msb(n)=my(k=1); while(k<=n, k<<=1); k>>1

%o for(n=1,1e4,k=bitand(n,n<<1);if(k,n=bitor(n,msb(k)-1),print1(n", "))) \\ _Charles R Greathouse IV_, Jun 15 2011

%o (PARI) select( is_A003714(n)=!bitand(n,n>>1), [0..266])

%o {(next_A003714(n,t)=while(t=bitand(n+=1,n<<1), n=bitor(n,1<<exponent(t)-1));n);} t=0; vector(60,i,t=next_A003714(t)) \\ _M. F. Hasler_, Nov 30 2021

%o (Python)

%o for n in range(300):

%o if 2*n & n == 0:

%o print(n, end=",") # _Alex Ratushnyak_, Jun 21 2012

%o (Python)

%o def A003714(n):

%o tlist, s = [1,2], 0

%o while tlist[-1]+tlist[-2] <= n:

%o tlist.append(tlist[-1]+tlist[-2])

%o for d in tlist[::-1]:

%o s *= 2

%o if d <= n:

%o s += 1

%o n -= d

%o return s # _Chai Wah Wu_, Jun 14 2018

%o (Python)

%o def fibbinary():

%o x = 0

%o while True:

%o yield x

%o y = ~(x >> 1)

%o x = (x - y) & y # _Falk Hüffner_, Oct 23 2021

%o (C++)

%o /* start with x=0, then repeatedly call x=next_fibrep(x): */

%o ulong next_fibrep(ulong x)

%o {

%o // 2 examples: // ex. 1 // ex.2

%o // // x == [*]0 010101 // x == [*]0 01010

%o ulong y = x | (x>>1); // y == [*]? 011111 // y == [*]? 01111

%o ulong z = y + 1; // z == [*]? 100000 // z == [*]? 10000

%o z = z & -z; // z == [0]0 100000 // z == [0]0 10000

%o x ^= z; // x == [*]0 110101 // x == [*]0 11010

%o x &= ~(z-1); // x == [*]0 100000 // x == [*]0 10000

%o return x;

%o }

%o /* _Joerg Arndt_, Jun 22 2012 */

%o (Scala) (0 to 255).filter(n => (n & 2 * n) == 0) // _Alonso del Arte_, Apr 12 2020

%o (C#)

%o public static bool IsFibbinaryNum(this int n) => ((n & (n >> 1)) == 0) ? true : false; // _Frank Hollstein_, Jul 07 2021

%Y A007088(a(n)) = A014417(n) (same sequence in binary). Complement: A004780. Char. function: A085357. Even terms: A022340, odd terms: A022341. First difference: A129761.

%Y Other sequences based on similar restrictions on binary expansion: A003726 & A278038, A003754, A048715, A048718, A107907, A107909.

%Y Cf. A000045, A005203, A005590, A007895, A037011, A048728, A048679, A056017, A060112, A072649, A083368, A089939, A106027, A106028, A116361.

%Y 3*a(n) is in A001969.

%Y Cf. also A215022-A215025, A242407.

%Y Cf. A014081 (count 11 bits).

%K nonn,nice,easy,look

%O 0,3

%A _N. J. A. Sloane_

%E Edited by _Antti Karttunen_, Feb 21 2006

%E Cross reference to A007820 added (into O-Y.C. comment) by _Jason Kimberley_, Sep 14 2009

%E Typo corrected by _Jeffrey Shallit_, Sep 26 2014