The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 195
 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, 69, 72, 73, 74, 80, 81, 82, 84, 85, 128, 129, 130, 132, 133, 136, 137, 138, 144, 145, 146, 148, 149, 160, 161, 162, 164, 165, 168, 169, 170, 256, 257, 258, 260, 261, 264 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS The name "Fibbinary" is due to Marc LeBrun. "... 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] A number n is in the sequence if and only if C(3n, n) (or equally, C(3n, 2n)) is odd; also a(n) (mod 2) = A003849(n). - Benoit Cloitre, Mar 08 2003 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. Numbers whose base-2 representation contains no two adjacent ones. For example, n = 17 (10001 in binary) belongs to the sequence, but n = 19 (10011 in binary) does not. - Ctibor O. Zizka, May 13 2008 n is in the sequence if and only if the central Stirling number of the second kind S(2*n, n) = A007820(n) is odd. [O-Yeat Chan (math(AT)oyeat.com), Sep 03 2009] A000120(3*a(n)) = 2*A000120(a(n)); A002450 is a subsequence. Every nonnegative integer can be expressed as the sum of two members of this sequence. - Franklin T. Adams-Watters, Jun 11 2011 Subsequence of A213526. - Arkadiusz Wesolowski, Jun 20 2012 This is also the union of A215024 and A215025 - see the Comment in A014417. - N. J. A. Sloane, Aug 10 2012 The binary representation of these numbers contain no two adjacent 1's, so we have (n XOR 2n XOR 3n) = 0, and thus a two player Nim game with three heaps of (n, 2n, 3n) stones is a losing configuration for the first player. - V. Raman, Sep 17 2012 Positions of zeros in A014081. - John Keith, Mar 07 2022 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 REFERENCES Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493. LINKS G. C. Greubel and T. D. Noe, Table of n, a(n) for n = 0..5000 (terms 0 to 1363 by T. D. Noe) J.-P. Allouche, J. Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math., Vol. 292, No. 1-3 (2005), pp. 1-15. Joerg Arndt, Matters Computational (The Fxtbook), pp. 74-77, pp. 754-756. Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008. Marc Chamberland and Karl Dilcher, A Binomial Sum Related to Wolstenholme's Theorem, J. Number Theory, Vol. 171, Issue 11 (Nov. 2009), pp. 2659-2672. See Lemma 4.2 p. 2668. O-Yeat Chan and Dante Manna, Divisibility properties of Stirling numbers of the second kind F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1. David Eppstein, Generating fibbinary numbers, three ways, 2021. Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., Vol. 274, No. 1-3 (2004), pp. 147-160. Roman S. Klyujkov, Quick Fibbinary Numbers Addition, C++ function with test program. Linus Lindroos, Andrew Sills and Hua Wang, Odd fibbinary numbers and the golden ratio, Fib. Q., Vol. 52, No. 1 (2014), pp. 61-65; alternative link. Douglas M. McKenna, Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-Style Square-Filling Curves, ECA 2:2 (2022) Article S2R13. Joris Nieuwveld, Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding, Master's Thesis, arXiv:2108.11382 [math.NT], 2021. N. J. A. Sloane, Table of n, a(n) (base 10), a(n) (base 2), for n = 0..1000. Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018. FORMULA No two adjacent 1's in binary expansion. 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). a(0) = 0, a(1) = 1, a(2) = 2, a(n) = 2^(A072649(n) - 1) + a(n - A000045(1 + A072649(n))). - Antti Karttunen It appears that this sequence gives n such that A082759(3*n) is odd; or, probably equivalently, n such that A037011(3*n) = 1. - Benoit Cloitre, Jun 20 2003 If n is in the sequence then so are 2*n and 4*n + 1. - Henry Bottomley, Jan 11 2005 A116361(a(n)) <= 1. - Reinhard Zumkeller, Feb 04 2006 A085357(a(n)) = 1; A179821(a(n)) = a(n). - Reinhard Zumkeller, Jul 31 2010 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 a(n) = a(A193564(n+1))*2^(A003849(n) + 1) + A003849(n) for n > 0. - Daniel Starodubtsev, Aug 05 2021 There are Fibonacci(n+1) terms with up to n bits in this sequence. - Charles R Greathouse IV, Oct 22 2021 Sum_{n>=1} 1/a(n) = 3.704711752910469457886531055976801955909489488376627037756627135425780134020... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022 EXAMPLE In the following, dots are used for zeros in the binary representation: a(n) binary(a(n))  n    0:  .......     0    1:  ......1     1    2:  .....1.     2    4:  ....1..     3    5:  ....1.1     4    8:  ...1...     5    9:  ...1..1     6   10:  ...1.1.     7   16:  ..1....     8   17:  ..1...1     9   18:  ..1..1.    10   20:  ..1.1..    11   21:  ..1.1.1    12   32:  .1.....    13   33:  .1....1    14   34:  .1...1.    15   36:  .1..1..    16   37:  .1..1.1    17   40:  .1.1...    18   41:  .1.1..1    19   42:  .1.1.1.    20   64:  1......    21   65:  1.....1    22 [Joerg Arndt, Jun 11 2011] MAPLE A003714 := proc(n)     option remember;     if n < 3 then         n ;     else         2^(A072649(n)-1) + procname(n-combinat[fibonacci](1+A072649(n))) ;     end if; end proc: seq(A003714(n), n=0..10) ; # To produce a table giving n, a(n) (base 10), a(n) (base 2) - from N. J. A. Sloane, Sep 30 2018 # binary: binary representation of n, in human order binary:=proc(n) local t1, L; if n<0 then ERROR("n must be nonnegative"); fi; if n=0 then return(); fi; t1:=convert(n, base, 2); L:=nops(t1); [seq(t1[L+1-i], i=1..L)]; end; for n from 0 to 100 do t1:=A003714(n); lprint(n, t1, binary(t1)); od: MATHEMATICA fibBin[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n Sqrt]], 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 *) Select[Range[0, 270], ! MemberQ[Partition[IntegerDigits[#, 2], 2, 1], {1, 1}] &] (* Harvey P. Dale, Jul 17 2011 *) Select[Range, BitAnd[#, 2 #] == 0 &] (* Alonso del Arte, Jun 18 2012 *) With[{r = Range[10^5]}, Pick[r, BitAnd[r, 2 r], 0]] (* Eric W. Weisstein, Aug 18 2017 *) Select[Range[0, 299], SequenceCount[IntegerDigits[#, 2], {1, 1}] == 0 &] (* Requires Mathematica version 10 or later. -- Harvey P. Dale, Dec 06 2018 *) PROG (Haskell) import Data.Set (Set, singleton, insert, deleteFindMin) a003714 n = a003714_list !! n a003714_list = 0 : f (singleton 1) where    f :: Set Integer -> [Integer]    f s = m : (f \$ insert (4*m + 1) \$ insert (2*m) s')          where (m, s') = deleteFindMin s -- Reinhard Zumkeller, Jun 03 2012, Feb 07 2012 (PARI) msb(n)=my(k=1); while(k<=n, k<<=1); k>>1 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 (PARI) select( is_A003714(n)=!bitand(n, n>>1), [0..266]) {(next_A003714(n, t)=while(t=bitand(n+=1, n<<1), n=bitor(n, 1<> 1)         x = (x - y) & y # Falk Hüffner, Oct 23 2021 (C++) /* start with x=0, then repeatedly call x=next_fibrep(x): */ ulong next_fibrep(ulong x) {     // 2 examples:         //  ex. 1             //  ex.2     //                     // x == [*]0 010101   // x == [*]0 01010     ulong y = x | (x>>1);  // y == [*]? 011111   // y == [*]? 01111     ulong z = y + 1;       // z == [*]? 100000   // z == [*]? 10000     z = z & -z;            // z == 0 100000   // z == 0 10000     x ^= z;                // x == [*]0 110101   // x == [*]0 11010     x &= ~(z-1);           // x == [*]0 100000   // x == [*]0 10000     return x; } /* Joerg Arndt, Jun 22 2012 */ (Scala) (0 to 255).filter(n => (n & 2 * n) == 0) // Alonso del Arte, Apr 12 2020 (C#) public static bool IsFibbinaryNum(this int n) => ((n & (n >> 1)) == 0) ? true : false; // Frank Hollstein, Jul 07 2021 CROSSREFS A007088(a(n)) = A014417(n) (same sequence in binary). Complement: A004780. Char. function: A085357. Even terms: A022340, odd terms: A022341. First difference: A129761. Other sequences based on similar restrictions on binary expansion: A003726 & A278038, A003754, A048715, A048718, A107907, A107909. Cf. A000045, A005203, A005590, A007895, A037011, A048728, A048679, A056017, A060112, A072649, A083368, A089939, A106027, A106028, A116361. 3*a(n) is in A001969. Cf. also A215022-A215025, A242407. Cf. A014081 (count 11 bits). Sequence in context: A166021 A339906 A279430 * A340956 A010402 A010443 Adjacent sequences:  A003711 A003712 A003713 * A003715 A003716 A003717 KEYWORD nonn,nice,easy,look AUTHOR EXTENSIONS Edited by Antti Karttunen, Feb 21 2006 Cross reference to A007820 added (into O-Y.C. comment) by Jason Kimberley, Sep 14 2009 Typo corrected by Jeffrey Shallit, Sep 26 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 27 19:37 EDT 2022. Contains 357063 sequences. (Running on oeis4.)