login
This site is supported by donations to The OEIS Foundation.

 

Logo


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). 121
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 (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.

A116361(a(n)) <= 1. - Reinhard Zumkeller, Feb 04 2006

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]

A085357(a(n)) = 1; A179821(a(n)) = a(n). - Reinhard Zumkeller, Jul 31 2010

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

REFERENCES

D. E. Knuth, Art of Comp. Programming, Vol. 1, 2nd ed., 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. 292 (2005) 1-15.

Joerg Arndt, Matters Computational (The Fxtbook), pp.74-77, pp.754-756.

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.

C. Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160. [From N. J. A. Sloane, Jan 31 2012]

Ron Knott, Rabbit Sequence in Zeckendorf Expansion (A003714)

L. Lindroos, A. Sills and H. Wang, Odd fibbinary numbers and the golden ratio, Fib. Q., 52 (2014), 61-65.

Index entries for sequences defined by congruent products between domains N and GF(2)[X]

Index entries for sequences defined by congruent products under XOR

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

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

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

with(combinat, fibonacci); A003714 := proc(n) option remember; if(n < 3) then RETURN(n); else RETURN((2^(A072649(n)-1))+A003714(n-fibonacci(1+A072649(n)))); fi; end;

MATHEMATICA

f[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[ f[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[256], BitAnd[#, 2#] == 0 &] (* Alonso del Arte, Jun 18 2012 *)

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

(Python)

for n in range(300):

    if 2*n & n == 0:

        print n,

# Alex Ratushnyak, Jun 21 2012

(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]0 100000   // z == [0]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 */

CROSSREFS

A007088(a(n)) = A014417(n) (same sequence in binary). Complement: A004780. Char. function: A085357. Even terms: A022340, Odd terms: A022341.

Other sequences based on similar restrictions on binary expansion: 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. A003726, A215022-A215025.

Cf. A242407.

Sequence in context: A005658 A166021 A279430 * A010402 A010443 A035269

Adjacent sequences:  A003711 A003712 A003713 * A003715 A003716 A003717

KEYWORD

nonn,nice,easy,look

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by Antti Karttunen, Feb 21 2006

Cross reference to A007820 added (into O-Y.C. comment) by Jason Kimberley, Sep 14 2009

Corrected typo 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 19:24 EDT 2017. Contains 284082 sequences.