A005203 -id:A005203 - cp's OEIS frontend

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.

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

Offset: 0

N. J. A. Sloane

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]
From Benoit Cloitre, Mar 08 2003: (Start)
A number m is in the sequence if and only if C(3m, m) (or equally, C(3m, 2m)) is odd.
a(n) == A003849(n) (mod 2). (End)
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, m = 17 = 10001_2 belongs to the sequence, but m = 19 = 10011_2 does not. - Ctibor O. Zizka, May 13 2008
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
A000120(3*a(n)) = 2*A000120(a(n)); A002450 is a subsequence.
Every nonnegative integer can be expressed as the sum of two terms 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 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
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
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

			From _Joerg Arndt_, Jun 11 2011: (Start)
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
(End)

Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493.

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.
Ron Knott, Rabbit Sequence in Zeckendorf Expansion (A003714).
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.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 1, 5.
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.
Yaron Shany and Amit Berman, The Generating Idempotent Is a Minimum-Weight Codeword for Some Binary BCH Codes, arXiv:2408.08218 [cs.IT], 2024. See p. 10.
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.
Index entries for 2-automatic sequences.
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.

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

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

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([0]); 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:

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

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

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<A003714(t)) \\ M. F. Hasler, Nov 30 2021

for n in range(300):
    if 2*n & n == 0:
        print(n, end=",") # Alex Ratushnyak, Jun 21 2012

def A003714(n):
    tlist, s = [1,2], 0
    while tlist[-1]+tlist[-2] <= n:
        tlist.append(tlist[-1]+tlist[-2])
    for d in tlist[::-1]:
        s *= 2
        if d <= n:
            s += 1
            n -= d
    return s # Chai Wah Wu, Jun 14 2018

def fibbinary():
    x = 0
    while True:
        yield x
        y = ~(x >> 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]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 */

(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

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 m such that A082759(3*m) is odd; or, probably equivalently, m such that A037011(3*m) = 1. - Benoit Cloitre, Jun 20 2003
If m is in the sequence then so are 2*m and 4*m + 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

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

A048679 Compressed fibbinary numbers (A003714), with rewrite 0->0, 01->1 applied to their binary expansion.

Original entry on oeis.org

0, 1, 2, 4, 3, 8, 5, 6, 16, 9, 10, 12, 7, 32, 17, 18, 20, 11, 24, 13, 14, 64, 33, 34, 36, 19, 40, 21, 22, 48, 25, 26, 28, 15, 128, 65, 66, 68, 35, 72, 37, 38, 80, 41, 42, 44, 23, 96, 49, 50, 52, 27, 56, 29, 30, 256, 129, 130, 132, 67, 136, 69, 70, 144, 73, 74, 76, 39, 160, 81

Offset: 0

Antti Karttunen

Permutation of the nonnegative integers (A001477); inverse permutation of A048680 i.e. A048679[ A048680[ n ] ] = n for all n.

Alois P. Heinz, Table of n, a(n) for n = 0..17710 (terms n = 10001..10945 from Antti Karttunen)
Index entries for sequences that are permutations of the natural numbers

Cf. A000045, A003714, A005203, A048678, A048680, A072650, A087808, A106151, A200714, A227351, A232559, A277006, A304100, A304101.

a(n) = rewrite_0to0_x1to1(fibbinary(j)) (where fibbinary(j) = A003714[ n ])
rewrite_0to0_x1to1 := proc(n) option remember; if(0 = n) then RETURN(n); else RETURN((2 * rewrite_0to0_x1to1(floor(n/(2^(1+(n mod 2)))))) + (n mod 2)); fi; end;
fastfib := n -> round((((sqrt(5)+1)/2)^n)/sqrt(5)); fibinv_appr := n -> floor(log[ (sqrt(5)+1)/2 ](sqrt(5)*n)); fibinv := n -> (fibinv_appr(n) + floor(n/fastfib(1+fibinv_appr(n)))); fibbinary := proc(n) option remember; if(n <= 2) then RETURN(n); else RETURN((2^(fibinv(n)-2))+fibbinary_seq(n-fastfib(fibinv(n)))); fi; end;
# second Maple program:
b:= proc(n) is(n=0) end:
a:= proc(n) option remember; local h; h:= iquo(a(n-1), 2)+1;
      while b(h) do h:= h*2 od; b(h):=true; h
    end: a(0):=0:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 22 2014

b[n_] := n==0; a[n_] := a[n] = Module[{h}, h = Quotient[a[n-1], 2] + 1; While[b[h], h = h*2]; b[h] = True; h]; a[0]=0; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 27 2016, after Alois P. Heinz *)

A072649(n) = { my(m); if(n<1, 0, m=0; until(fibonacci(m)>n, m++); m-2); }; \\ From A072649
A003714(n) = { my(s=0,w); while(n>2, w = A072649(n); s += 2^(w-1); n -= fibonacci(w+1)); (s+n); }
A007814(n) = valuation(n,2);
A000265(n) = (n/2^valuation(n, 2));
A106151(n) = if(n<=1,n,if(n%2,1+(2*A106151((n-1)/2)),(2^(A007814(n)-1))*A106151(A000265(n))));
A048679(n) = if(!n,n,A106151(2*A003714(n))); \\ Antti Karttunen, May 13 2018, after Reinhard Zumkeller's May 09 2005 formula.

from itertools import count, islice
def A048679_gen(): # generator of terms
    return map(lambda n: int(bin(n)[2:].replace('01','1'),2),filter(lambda n:not (n<<1)&n,count(0)))
A048679_list = list(islice(A048679_gen(),20)) # Chai Wah Wu, Mar 18 2024

def A048679(n):
    tlist, s = [1,2], 0
    while tlist[-1]+tlist[-2] <= n: tlist.append(tlist[-1]+tlist[-2])
    for d in tlist[::-1]:
        if d <= n:
            s += 1
            n -= d
        else:
            s <<= 1
    return s # Chai Wah Wu, Apr 24 2025

a(n) = A106151(2*A003714(n)) for n > 0. - Reinhard Zumkeller, May 09 2005
a(n+1) = min{([a(n)/2]+1)*2^k} such that it is not yet in the sequence. - Gerard Orriols, Jun 07 2014
a(n) = A072650(A003714(n)) = A003188(A227351(n)). - Antti Karttunen, May 13 2018

A063896 a(n) = 2^Fibonacci(n) - 1.

Original entry on oeis.org

0, 1, 1, 3, 7, 31, 255, 8191, 2097151, 17179869183, 36028797018963967, 618970019642690137449562111, 22300745198530623141535718272648361505980415

Offset: 0

Robert G. Wilson v, Aug 29 2001

The recurrence can also be written a(n)+1 = (a(n-1)+1)*(a(n-2)+1) or log_p(a(n)+1) = log_p(a(n-1)+1) + log_p(a(n-2)+1), respectively. Setting a(1)=p-1 for any natural p>1, it follows that log_p(a(n)+1)=Fibonacci(n). Hence any other sequence p^Fibonacci(n)-1 could also serve as a valid solution to that recurrence, depending only on the value of the term a(1). - Hieronymus Fischer, Jun 27 2007
Written in binary, a(n) contains Fibonacci(n) 1's. Thus the sequence converted to base-2 is A007088(a(n)) = 0, 1, 1, 11, 111, 11111, 11111111, ... . - Hieronymus Fischer, Jun 27 2007
In general, if b(n) is defined recursively by b(0) = p, b(1) = q, b(n) = b(n-1)*b(n-2) + b(n-1) + b(n-2) for n >= 2 then b(n) = p^Fibonacci(n-1) * q^Fibonacci(n) - 1. - Rahul Goswami, Apr 15 2020
a(n) is also the numerator of the continued fraction [2^F(0), 2^F(1), 2^F(2), 2^F(3), ..., 2^F(n-2)] for n>0. For the denominator, see A005203. - Chinmay Dandekar and Greg Dresden, Sep 19 2020

Alois P. Heinz, Table of n, a(n) for n = 0..18
M. Tamba and Y. S. Valaulikar, A nonlinear extension of Fibonacci sequence, Turkish Journal of Analysis and Number Theory, Vol. 4, No. 4, 2016.

Cf. A000045 (Fibonacci), A000225, A000301, A005203, A061107.

See A131293 for a base-10 analog with Fib(n) 1's.

a:= n-> 2^(<<0|1>, <1|1>>^n)[1,2]-1:
seq(a(n), n=0..15);  # Alois P. Heinz, Aug 12 2017

2^Fibonacci[Range[0,15]]-1 (* Harvey P. Dale, May 20 2014 *)
RecurrenceTable[{a[0] == 0, a[1] == 1, a[n] == (a[n - 1] + 1)*(a[n - 2] + 1) - 1}, a[n], {n, 0, 12}] (* Ray Chandler, Jul 30 2015 *)

a(n) = 2^fibonacci(n) - 1 \\ Charles R Greathouse IV, Oct 03 2016

The solution to the recurrence a(0) = 0; a(1) = 1; a(n) = a(n-1)*a(n-2) + a(n-1) + a(n-2).
a(n) = A000301(n) - 1. - R. J. Mathar, Apr 26 2007
a(n) = a(n-2)*2^ceiling(log_2(a(n-1))) + a(n-1) for n>1. - Hieronymus Fischer, Jun 27 2007
a(n) = A000225(A000045(n)). - Alois P. Heinz, Mar 19 2020

A048680 Nonnegative integers A001477 expanded with rewrite 0->0, 01->1, then interpreted as Zeckendorffian expansions (as numbers of Fibonacci number system).

Original entry on oeis.org

0, 1, 2, 4, 3, 6, 7, 12, 5, 9, 10, 17, 11, 19, 20, 33, 8, 14, 15, 25, 16, 27, 28, 46, 18, 30, 31, 51, 32, 53, 54, 88, 13, 22, 23, 38, 24, 40, 41, 67, 26, 43, 44, 72, 45, 74, 75, 122, 29, 48, 49, 80, 50, 82, 83, 135, 52, 85, 86, 140, 87, 142, 143, 232, 21, 35, 36, 59, 37, 61

Offset: 0

Antti Karttunen, Jul 14 1999

A permutation of the nonnegative integers (A001477). Inverse permutation to A048679, i.e. A048679[ A048680[ n ] ] = n for all n and vice versa.

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Ron Knott, About Fibonacci Number System
Index entries for sequences that are permutations of the natural numbers

Cf. A003714, A005203, A048678, A048679.

Equals A074049(n+1) - 1.

rewrite_0to0_1to01 := proc(n) option remember; if(n < 2) then RETURN(n); else RETURN(((2^(1+(n mod 2))) * rewrite_0to0_1to01(floor(n/2))) + (n mod 2)); fi; end; interpret_as_zeckendorf_expansion := n -> sum('(bit_i(n,i)*fib(i+2))','i'=0..floor_log_2(n));

a(n)=my(k=1,s);while(n,if(n%2,s+=fibonacci(k++));k++;n>>=1);s \\ Charles R Greathouse IV, Nov 17 2013

a(n) = interpret_as_zeckendorf_expansion(rewrite_0to0_1to01(n)) (where rewrite_0to0_1to01(n)=A048678[ n ])

A048678 Binary expansion of nonnegative integers expanded to "Zeckendorffian format" with rewrite rules 0->0, 1->01.

Original entry on oeis.org

0, 1, 2, 5, 4, 9, 10, 21, 8, 17, 18, 37, 20, 41, 42, 85, 16, 33, 34, 69, 36, 73, 74, 149, 40, 81, 82, 165, 84, 169, 170, 341, 32, 65, 66, 133, 68, 137, 138, 277, 72, 145, 146, 293, 148, 297, 298, 597, 80, 161, 162, 325, 164, 329, 330, 661, 168, 337, 338, 677, 340

Offset: 0

Antti Karttunen

No two adjacent 1-bits. Permutation of A003714.

Replace 1 with 01 in binary. - Ralf Stephan, Oct 07 2003

			11=1011 in binary, thus is rewritten as 100101 = 37 in decimal.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Transforms

Cf. A003714, A005203, A048679, A048680.
MASKTRANS transform of A053644.
Cf. A084471, A088697, A088698.
Cf. A124108.

a048678 0 = 0
a048678 x = 2 * (b + 1) * a048678 x' + b
            where (x', b) = divMod x 2
-- Reinhard Zumkeller, Mar 31 2015

rewrite_0to0_1to01 := proc(n) option remember; if(n < 2) then RETURN(n); else RETURN(((2^(1+(n mod 2))) * rewrite_0to0_1to01(floor(n/2))) + (n mod 2)); fi; end;

f[n_] := FromDigits[ Flatten[IntegerDigits[n, 2] /. {1 -> {0, 1}}], 2]; Table[f@n, {n, 0, 60}] (* Robert G. Wilson v, Dec 11 2009 *)

a(n)=if(n<1,0,(3-(-1)^n)*a(floor(n/2))+(1-(-1)^n)/2)

a(n) = if(n == 0, 0, my(A = -2); sum(i = 0, logint(n, 2), A++; if(bittest(n, i), 1 << (A++)))) \\ Mikhail Kurkov, Mar 14 2024

def a(n):
    return 0 if n==0 else (3 - (-1)**n)*a(n//2) + (1 - (-1)**n)//2
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 30 2017

def A048678(n): return int(bin(n)[2:].replace('1','01'),2) # Chai Wah Wu, Mar 18 2024

a(n) = rewrite_0to0_1to01(n) [ Each 0->1, 1->10 in binary expansion of n ].
a(0)=0; a(n) = (3-(-1)^n)*a(floor(n/2))+(1-(-1)^n)/2. - Benoit Cloitre, Aug 31 2003
a(0)=0, a(2n) = 2a(n), a(2n+1) = 4a(n) + 1. - Ralf Stephan, Oct 07 2003

A144287 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) = Fibonacci rabbit sequence number n coded in base k.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 3, 1, 4, 10, 22, 5, 1, 5, 17, 93, 181, 8, 1, 6, 26, 276, 2521, 5814, 13, 1, 7, 37, 655, 17681, 612696, 1488565, 21, 1, 8, 50, 1338, 81901, 18105620, 4019900977, 12194330294, 34, 1, 9, 65, 2457, 289045, 255941280, 1186569930001, 6409020585966267, 25573364166211253, 55

Offset: 1

Alois P. Heinz, Sep 17 2008

			Square array begins:
  1,   1,    1,     1,     1,  ...
  1,   2,    3,     4,     5,  ...
  2,   5,   10,    17,    26,  ...
  3,  22,   93,   276,   655,  ...
  5, 181, 2521, 17681, 81901,  ...

Alois P. Heinz, Antidiagonals n = 1..16, flattened
H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr., Sequences associated with t-ary coding of Fibonacci's rabbits, Fib. Quart., 15 (1977), 311-318.

Columns k=1-10 give: A000045, A005203, A005205, A320986, A320987, A320988, A320989, A320990, A320991, A061107 and A036299.
Rows n=1-3 give: A000012, A001477, A002522.
Main diagonal gives A144288.

f:= proc(n,b) option remember; `if`(n<2, [n,n], [f(n-1, b)[1]*
       b^f(n-1, b)[2] +f(n-2, b)[1], f(n-1, b)[2] +f(n-2, b)[2]])
    end:
A:= (n,k)-> f(n,k)[1]:
seq(seq(A(n, 1+d-n), n=1..d), d=1..11);

f[n_, b_] := f[n, b] = If[n < 2, {n, n}, {f[n-1, b][[1]]*b^f[n-1, b][[2]] + f[n-2, b][[1]], f[n-1, b][[2]] + f[n-2, b][[2]]}]; t[n_, k_] := f[n, k][[1]]; Flatten[ Table[t[n, 1+d-n], {d, 1, 11}, {n, 1, d}]] (* Jean-François Alcover, translated from Maple, Dec 09 2011 *)

See program.

A061107 a(0) = 0, a(1) = 1, a(n) is the concatenation of a(n-2) and a(n-1) for n > 1.

Original entry on oeis.org

0, 1, 10, 101, 10110, 10110101, 1011010110110, 101101011011010110101, 1011010110110101101011011010110110, 1011010110110101101011011010110110101101011011010110101

Offset: 0

Amarnath Murthy, Apr 20 2001

Original name was: In the Fibonacci rabbit problem we start with an immature pair 'I' which matures after one season to 'M'. This mature pair after one season stays alive and breeds a new immature pair and we get the following sequence I, MI, MIM, MIMMI, MIMMIMIM, MIMMIMIMMIMMI... if we replace 'I' by a '0' and 'M' by a '1' we get the required binary sequence.

			a(0) = 0, a(1) = 1, a(2) = a(1)a(0)= 10, etc.

Amarnath Murthy, Smarandache Reverse auto correlated sequences and some Fibonacci derived sequences, Smarandache Notions Journal Vol. 12, No. 1-2-3, Spring 2001.
Ian Stewart, The Magical Maze.

Harry J. Smith, Table of n, a(n) for n = 0..15
Duaa Abdullah and Jasem Hamoud, Dynamic and Programmatic Analysis of Fibonacci Word Density, arXiv:2504.04087 [math.CO], 2025. See p. 10.

Cf. A063896, A131242. See A005203 for the sequence version converted to decimal.

Column k=10 of A144287.

A[0]:= 0: A[1]:= 1: A[2]:= 10:
for n from 3 to 20 do
A[n]:= 10^(ilog10(A[n-2])+1)*A[n-1]+A[n-2]
od:
seq(A[n],n=0..10); # Robert Israel, Apr 30 2015

nxt[{a_,b_}]:={b,FromDigits[Join[IntegerDigits[b],IntegerDigits[a]]]}; Transpose[NestList[nxt,{0,1},10]][[1]] (* Harvey P. Dale, Jul 05 2015 *)

{ default(realprecision, 100); L=log(10); for (n=0, 15, if (n>2, a=a1*10^(log(a2)\L + 1) + a2; a2=a1; a1=a, if (n==0, a=0, if (n==1, a=a2=1, a=a1=10))); write("b061107.txt", n, " ", a) ) } \\ Harry J. Smith, Jul 18 2009

a(0) = 0, a(1) =1, a(n) = concatenation of a(n-1) and a(n-2).
a(n) = a(n-1)*2^floor(log_2(a(n-2))+1)+a(n-2), for n>2, a(2)=10 (base 2). - Hieronymus Fischer, Jun 26 2007
a(n) = A036299(n-1), n>0. - R. J. Mathar, Oct 02 2008
a(n) can be transformed by a(n-1) when you change every single "1"(from a(n-1)) into "10" and every single "0"(from a(n-1)) into "1". [YuJiping and Sirius Caffrey, Apr 30 2015]

More terms from Hieronymus Fischer, Jun 26 2007

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Python

Scala

Formula

Extensions

A048679 Compressed fibbinary numbers (A003714), with rewrite 0->0, 01->1 applied to their binary expansion.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A063896 a(n) = 2^Fibonacci(n) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A048680 Nonnegative integers A001477 expanded with rewrite 0->0, 01->1, then interpreted as Zeckendorffian expansions (as numbers of Fibonacci number system).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A048678 Binary expansion of nonnegative integers expanded to "Zeckendorffian format" with rewrite rules 0->0, 1->01.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A144287 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) = Fibonacci rabbit sequence number n coded in base k.

Views

Author

Keywords