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). 133

%I

%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

%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).

%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 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

%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 A116361(a(n)) <= 1. - _Reinhard Zumkeller_, Feb 04 2006

%C 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

%C 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]

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

%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 members 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 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

%D D. E. Knuth, Art of Comp. Programming, Vol. 1, 2nd ed., 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. 292 (2005) 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 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 C. Kimberling, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00085-2">Affinely recursive sets and orderings of languages</a>, Discrete Math., 274 (2004), 147-160. [From _N. J. A. Sloane_, Jan 31 2012]

%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 L. Lindroos, A. Sills and H. Wang, <a href="http://digitalcommons.georgiasouthern.edu/math-sci-facpubs/182/">Odd fibbinary numbers and the golden ratio</a>, Fib. Q., 52 (2014), 61-65.

%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 n such that A082759(3*n) is odd; or, probably equivalently, n such that A037011(3*n)=1. - _Benoit Cloitre_, Jun 20 2003

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

%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

%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 [_Joerg Arndt_, Jun 11 2011]

%p 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;

%t 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 *)

%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 *)

%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 (Python)

%o for n in range(300):

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

%o print n,

%o # _Alex Ratushnyak_, Jun 21 2012

%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 */

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

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

%Y Cf. A242407.

%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 Corrected typo by _Jeffrey Shallit_, Sep 26 2014

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 February 25 03:06 EST 2018. Contains 299630 sequences. (Running on oeis4.)