|
%I #269 Feb 04 2024 18:18:33
%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 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 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
| 