This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A003714 #287 Jan 05 2025 19:51:33
%S A003714 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 A003714 69,72,73,74,80,81,82,84,85,128,129,130,132,133,136,137,138,144,145,
%U A003714 146,148,149,160,161,162,164,165,168,169,170,256,257,258,260,261,264
%N A003714 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 A003714 The name "Fibbinary" is due to _Marc LeBrun_.
%C A003714 "... 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 A003714 From _Benoit Cloitre_, Mar 08 2003: (Start)
%C A003714 A number m is in the sequence if and only if C(3m, m) (or equally, C(3m, 2m)) is odd.
%C A003714 a(n) == A003849(n) (mod 2). (End)
%C A003714 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 A003714 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 A003714 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 A003714 A000120(3*a(n)) = 2*A000120(a(n)); A002450 is a subsequence.
%C A003714 Every nonnegative integer can be expressed as the sum of two terms of this sequence. - _Franklin T. Adams-Watters_, Jun 11 2011
%C A003714 Subsequence of A213526. - _Arkadiusz Wesolowski_, Jun 20 2012
%C A003714 This is also the union of A215024 and A215025 - see the Comment in A014417. - _N. J. A. Sloane_, Aug 10 2012
%C A003714 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 A003714 Positions of zeros in A014081. - _John Keith_, Mar 07 2022
%C A003714 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 A003714 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 A003714 Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493.
%H A003714 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 A003714 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 A003714 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 74-77, pp. 754-756.
%H A003714 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 A003714 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 A003714 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 A003714 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 A003714 David Eppstein, <a href="https://11011110.github.io/blog/2021/10/02/generating-fibbinary-numbers.html">Generating fibbinary numbers, three ways</a>, 2021.
%H A003714 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 A003714 Roman S. Klyujkov, <a href="https://gist.github.com/uxn/93d8ebf9cd022cb42a54597fe99d4599">Quick Fibbinary Numbers Addition</a>, C++ function with test program.
%H A003714 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 A003714 Linus Lindroos, Andrew Sills, and Hua Wang, <a href="https://web.archive.org/web/2024*/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 A003714 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 A003714 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 A003714 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 A003714 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 A003714 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 A003714 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 A003714 <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.
%H A003714 <a href="/index/Con#CongruCrossDomain">Index entries for sequences defined by congruent products between domains N and GF(2)[X]</a>.
%H A003714 <a href="/index/Con#CongruXOR">Index entries for sequences defined by congruent products under XOR</a>.
%F A003714 No two adjacent 1's in binary expansion.
%F A003714 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 A003714 a(0) = 0, a(1) = 1, a(2) = 2, a(n) = 2^(A072649(n) - 1) + a(n - A000045(1 + A072649(n))). - _Antti Karttunen_
%F A003714 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 A003714 If m is in the sequence then so are 2*m and 4*m + 1. - _Henry Bottomley_, Jan 11 2005
%F A003714 A116361(a(n)) <= 1. - _Reinhard Zumkeller_, Feb 04 2006
%F A003714 A085357(a(n)) = 1; A179821(a(n)) = a(n). - _Reinhard Zumkeller_, Jul 31 2010
%F A003714 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 A003714 a(n) = a(A193564(n+1))*2^(A003849(n) + 1) + A003849(n) for n > 0. - _Daniel Starodubtsev_, Aug 05 2021
%F A003714 There are Fibonacci(n+1) terms with up to n bits in this sequence. - _Charles R Greathouse IV_, Oct 22 2021
%F A003714 Sum_{n>=1} 1/a(n) = 3.704711752910469457886531055976801955909489488376627037756627135425780134020... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - _Amiram Eldar_, Feb 12 2022
%e A003714 From _Joerg Arndt_, Jun 11 2011: (Start)
%e A003714 In the following, dots are used for zeros in the binary representation:
%e A003714 a(n) binary(a(n)) n
%e A003714 0: ....... 0
%e A003714 1: ......1 1
%e A003714 2: .....1. 2
%e A003714 4: ....1.. 3
%e A003714 5: ....1.1 4
%e A003714 8: ...1... 5
%e A003714 9: ...1..1 6
%e A003714 10: ...1.1. 7
%e A003714 16: ..1.... 8
%e A003714 17: ..1...1 9
%e A003714 18: ..1..1. 10
%e A003714 20: ..1.1.. 11
%e A003714 21: ..1.1.1 12
%e A003714 32: .1..... 13
%e A003714 33: .1....1 14
%e A003714 34: .1...1. 15
%e A003714 36: .1..1.. 16
%e A003714 37: .1..1.1 17
%e A003714 40: .1.1... 18
%e A003714 41: .1.1..1 19
%e A003714 42: .1.1.1. 20
%e A003714 64: 1...... 21
%e A003714 65: 1.....1 22
%e A003714 (End)
%p A003714 A003714 := proc(n)
%p A003714 option remember;
%p A003714 if n < 3 then
%p A003714 n ;
%p A003714 else
%p A003714 2^(A072649(n)-1) + procname(n-combinat[fibonacci](1+A072649(n))) ;
%p A003714 end if;
%p A003714 end proc:
%p A003714 seq(A003714(n),n=0..10) ;
%p A003714 # To produce a table giving n, a(n) (base 10), a(n) (base 2) - from _N. J. A. Sloane_, Sep 30 2018
%p A003714 # binary: binary representation of n, in human order
%p A003714 binary:=proc(n) local t1,L;
%p A003714 if n<0 then ERROR("n must be nonnegative"); fi;
%p A003714 if n=0 then return([0]); fi;
%p A003714 t1:=convert(n,base,2); L:=nops(t1);
%p A003714 [seq(t1[L+1-i],i=1..L)];
%p A003714 end;
%p A003714 for n from 0 to 100 do t1:=A003714(n); lprint(n, t1, binary(t1)); od:
%t A003714 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 A003714 Select[Range[0, 270], ! MemberQ[Partition[IntegerDigits[#, 2], 2, 1], {1, 1}] &] (* _Harvey P. Dale_, Jul 17 2011 *)
%t A003714 Select[Range[256], BitAnd[#, 2 #] == 0 &] (* _Alonso del Arte_, Jun 18 2012 *)
%t A003714 With[{r = Range[10^5]}, Pick[r, BitAnd[r, 2 r], 0]] (* _Eric W. Weisstein_, Aug 18 2017 *)
%t A003714 Select[Range[0, 299], SequenceCount[IntegerDigits[#, 2], {1, 1}] == 0 &] (* Requires Mathematica version 10 or later. -- _Harvey P. Dale_, Dec 06 2018 *)
%o A003714 (Haskell)
%o A003714 import Data.Set (Set, singleton, insert, deleteFindMin)
%o A003714 a003714 n = a003714_list !! n
%o A003714 a003714_list = 0 : f (singleton 1) where
%o A003714 f :: Set Integer -> [Integer]
%o A003714 f s = m : (f $ insert (4*m + 1) $ insert (2*m) s')
%o A003714 where (m, s') = deleteFindMin s
%o A003714 -- _Reinhard Zumkeller_, Jun 03 2012, Feb 07 2012
%o A003714 (PARI) msb(n)=my(k=1); while(k<=n, k<<=1); k>>1
%o A003714 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 A003714 (PARI) select( is_A003714(n)=!bitand(n,n>>1), [0..266])
%o A003714 {(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 A003714 (Python)
%o A003714 for n in range(300):
%o A003714 if 2*n & n == 0:
%o A003714 print(n, end=",") # _Alex Ratushnyak_, Jun 21 2012
%o A003714 (Python)
%o A003714 def A003714(n):
%o A003714 tlist, s = [1,2], 0
%o A003714 while tlist[-1]+tlist[-2] <= n:
%o A003714 tlist.append(tlist[-1]+tlist[-2])
%o A003714 for d in tlist[::-1]:
%o A003714 s *= 2
%o A003714 if d <= n:
%o A003714 s += 1
%o A003714 n -= d
%o A003714 return s # _Chai Wah Wu_, Jun 14 2018
%o A003714 (Python)
%o A003714 def fibbinary():
%o A003714 x = 0
%o A003714 while True:
%o A003714 yield x
%o A003714 y = ~(x >> 1)
%o A003714 x = (x - y) & y # _Falk Hüffner_, Oct 23 2021
%o A003714 (C++)
%o A003714 /* start with x=0, then repeatedly call x=next_fibrep(x): */
%o A003714 ulong next_fibrep(ulong x)
%o A003714 {
%o A003714 // 2 examples: // ex. 1 // ex.2
%o A003714 // // x == [*]0 010101 // x == [*]0 01010
%o A003714 ulong y = x | (x>>1); // y == [*]? 011111 // y == [*]? 01111
%o A003714 ulong z = y + 1; // z == [*]? 100000 // z == [*]? 10000
%o A003714 z = z & -z; // z == [0]0 100000 // z == [0]0 10000
%o A003714 x ^= z; // x == [*]0 110101 // x == [*]0 11010
%o A003714 x &= ~(z-1); // x == [*]0 100000 // x == [*]0 10000
%o A003714 return x;
%o A003714 }
%o A003714 /* _Joerg Arndt_, Jun 22 2012 */
%o A003714 (Scala) (0 to 255).filter(n => (n & 2 * n) == 0) // _Alonso del Arte_, Apr 12 2020
%o A003714 (C#)
%o A003714 public static bool IsFibbinaryNum(this int n) => ((n & (n >> 1)) == 0) ? true : false; // _Frank Hollstein_, Jul 07 2021
%Y A003714 A007088(a(n)) = A014417(n) (same sequence in binary). Complement: A004780. Char. function: A085357. Even terms: A022340, odd terms: A022341. First difference: A129761.
%Y A003714 Other sequences based on similar restrictions on binary expansion: A003726 & A278038, A003754, A048715, A048718, A107907, A107909.
%Y A003714 Cf. A000045, A005203, A005590, A007895, A037011, A048728, A048679, A056017, A060112, A072649, A083368, A089939, A106027, A106028, A116361.
%Y A003714 3*a(n) is in A001969.
%Y A003714 Cf. also A215022-A215025, A242407.
%Y A003714 Cf. A014081 (count 11 bits).
%K A003714 nonn,nice,easy,look
%O A003714 0,3
%A A003714 _N. J. A. Sloane_
%E A003714 Edited by _Antti Karttunen_, Feb 21 2006
%E A003714 Cross reference to A007820 added (into O-Y.C. comment) by _Jason Kimberley_, Sep 14 2009
%E A003714 Typo corrected by _Jeffrey Shallit_, Sep 26 2014