A048718 -id:A048718 - 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

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286, 299915, 413966, 571388, 788674, 1088589, 1502555, 2073943

Offset: 0

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0..m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For this family of sequences, a(n+1) is the number of compositions of n+1 into parts 1 and m. For n>=m, a(n-m+1)is the number of compositions of n in which each part is greater than m or equivalently, in which parts 1 through m are excluded. - Gregory L. Simay, Jul 14 2016
For this family of sequences, let a(m,n) = a(n-1) + a(n-m). Then the number of compositions of n having m as a least summand is a(m, n-m) - a(m+1, n-m-1). - Gregory L. Simay, Jul 14 2016
For n>=3, a(n-3) = number of compositions of n in which each part is >=4. - Milan Janjic, Jun 28 2010
For n>=1, number of compositions of n into parts == 1 (mod 4). Example: a(8)=5 because there are 5 compositions of 8 into parts 1 or 5: (1,1,1,1,1,1,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1), (5,1,1,1). - Adi Dani, Jun 16 2011
a(n+1) is the number of compositions of n into parts 1 and 4. - Joerg Arndt, Jun 25 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=4, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 4, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1,2}. - Vladimir Baltic, Mar 07 2012
a(n+4) equals the number of binary words of length n having at least 3 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
From Clark Kimberling, Jun 13 2016: (Start)
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*.
Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3, 2*x, x+1, x^2}, etc.
Let T(r) be the tree obtained by substituting r for x.
If N is a positive integer such that r = N^(1/4) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A003269(n), for n > = 1. See A274142. (End)

			G.f.: x + x^2 + x^3 + x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 10*x^10 + ...
The number of compositions of 12 having 4 as a least summand is a(4, 12 -4 + 1) - a(5, 12 - 5 + 1) = A003269(9) - A003520(8) = 7-4 = 3. The compositions are (84), (48) and (444). - _Gregory L. Simay_, Jul 14 2016

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 120.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..501
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [The hal link does not always work. - _N. J. A. Sloane_, Feb 19 2025]
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [Local copy with annotations and a correction from _N. J. A. Sloane_, Feb 19 2025]
Peter G. Anderson, More Properties of the Zeckendorf Array, Fib. Quart. 52-5 (2014), 15-21. With 2 more initial zeros.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
Hùng Việt Chu, Nurettin Irmak, Steven J. Miller, László Szalay, and Sindy Xin Zhang, Schreier Multisets and the s-step Fibonacci Sequences, arXiv:2304.05409 [math.CO], 2023. See also Integers (2024) Vol. 24A, Art. No. A7, p. 3.
Adi Dani, Compositions of natural numbers over arithmetic progressions
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,3,1).
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 377
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3} gives seq. shifted 4 places left
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 17.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 [math.CO] (2014), eq. (23).
Flaviano Morone, Ian Leifer, and Hernán A. Makse, Fibration symmetries uncover the building blocks of biological networks, Proceedings of the National Academy of Sciences (2020) Vol. 117, No. 15, 8306-8314.
Augustine O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.8.3.
Djamila Oudrar and Maurice Pouzet, Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes, arXiv:2312.05913 [math.CO], 2023. See p. 18.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
E. Wilson, The Scales of Mt. Meru
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898.
Cf. A048718, A072827, A072850, A072851, A072852, A072853, A072854, A072855, A072856.
Cf. A079955 - A080014.
See A017898 for an essentially identical sequence.
Row sums of A180184.

a003269 n = a003269_list !! n
a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
                                          (drop 3 a003269_list)
-- Reinhard Zumkeller, Feb 27 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1) + Self(n-4) :n in [1..50]]; // Marius A. Burtea, Sep 13 2019

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
seq(add(binomial(n-3*k,k),k=0..floor(n/3)),n=0..47); # Zerinvary Lajos, Apr 03 2007
A003269:=z/(1-z-z**4); # Simon Plouffe in his 1992 dissertation
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 3)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=3..50); # Zerinvary Lajos, Mar 26 2008
M:= Matrix(4, (i,j)-> if j=1 then [1,0,0,1][i] elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,2]; seq(a(n), n=0..48); # Alois P. Heinz, Jul 27 2008

a[0]= 0; a[1]= a[2]= a[3]= 1; a[n_]:= a[n]= a[n-1] + a[n-4]; Table[a[n], {n,0,50}]
CoefficientList[Series[x/(1-x-x^4), {x,0,50}], x] (* Zerinvary Lajos, Mar 29 2007 *)
Table[Sum[Binomial[n-3*i-1,i], {i,0,(n-1)/3}], {n,0,50}]
LinearRecurrence[{1,0,0,1}, {0,1,1,1}, 50] (* Robert G. Wilson v, Jul 12 2014 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+d}; NestList[nxt,{0,1,1,1},50][[;;,1]] (* Harvey P. Dale, May 27 2024 *)

{a(n) = polcoeff( if( n<0, (1 + x^3) / (1 + x^3 - x^4), 1 / (1 - x - x^4)) + x * O(x^abs(n)), abs(n))} /* Michael Somos, Jul 12 2003 */

@CachedFunction
def a(n): return ((n+2)//3) if (n<4) else a(n-1) + a(n-4) # a = A003269
[a(n) for n in (0..50)] # G. C. Greubel, Jul 25 2022

G.f.: x/(1-x-x^4).
G.f.: -1 + 1/(1-Sum_{k>=0} x^(4*k+1)).
a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) for n>4.
a(n) = floor(d*c^n + 1/2) where c is the positive real root of -x^4+x^3+1 and d is the positive real root of 283*x^4-18*x^2-8*x-1 (c=1.38027756909761411... and d=0.3966506381592033124...). - Benoit Cloitre, Nov 30 2002
Equivalently, a(n) = floor(c^(n+3)/(c^4+3) + 1/2) with c as defined above (see A086106). - Greg Dresden and Shuer Jiang, Aug 31 2019
a(n) = term (1,2) in the 4 X 4 matrix [1,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
From Paul Barry, Oct 20 2009: (Start)
a(n+1) = Sum_{k=0..n} C((n+3*k)/4,k)*((1+(-1)^(n-k))/2 + cos(Pi*n/2))/2;
a(n+1) = Sum_{k=0..n} C(k,floor((n-k)/3))(2*cos(2*Pi*(n-k)/3)+1)/3. (End)
a(n) = Sum_{j=0..(n-1)/3} binomial(n-1-3*j,j) (cf. A180184). - Vladimir Kruchinin, May 23 2011
A017817(n) = a(-4 - n) * (-1)^n. - Michael Somos, Jul 12 2003
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(2*k+1 + x^3)/( x*(2*k+2 + x^3) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 29 2013
Appears a(n) = hypergeometric([1/4-n/4,1/2-n/4,3/4-n/4,1-n/4], [1/3-n/3,2/3-n/3,1-n/3], -4^4/3^3) for n>=10. - Peter Luschny, Sep 18 2014

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

Initial 0 prepended by N. J. A. Sloane, Apr 09 2008

A048715 Binary expansion matches (100(0))(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

Original entry on oeis.org

0, 1, 2, 4, 8, 9, 16, 17, 18, 32, 33, 34, 36, 64, 65, 66, 68, 72, 73, 128, 129, 130, 132, 136, 137, 144, 145, 146, 256, 257, 258, 260, 264, 265, 272, 273, 274, 288, 289, 290, 292, 512, 513, 514, 516, 520, 521, 528, 529, 530, 544, 545, 546, 548, 576, 577, 578, 580

Offset: 0

Antti Karttunen, Mar 30 1999

No more than one 1-bit in each bit triple.
All terms satisfy A048727(n) = 7*n.
Constructed from A000930 in the same way as A003714 is constructed from A000045.
It appears that n is in the sequence if and only if C(7n,n) is odd (cf. A003714). - Benoit Cloitre, Mar 09 2003
The conjecture by Benoit is correct. This is easily proved using the well-known result that the multiplicity with which a prime p divides C(n+m,n) is the number of carries when adding n+m in base p. - Franklin T. Adams-Watters, Oct 06 2009
Appears to be the set of numbers x such that (x AND 5*x) = x and (x OR 3*x)/x = 3. - Gary Detlefs, Jun 08 2024

G. C. Greubel, Table of n, a(n) for n = 0..1275
Sebastian Karlsson, Walnut code that verifies the conjectures of Paul D. Hanna
Walnut can be downloaded from https://cs.uwaterloo.ca/~shallit/walnut.html.
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
Index entries for 2-automatic sequences.

Subsequence of A048716.

Cf. A003726, A004742, A004743, A004744, A048717, A048718, A048719, A048730, A048733, A115422, A115423, A115424.

Reap[Do[If[OddQ[Binomial[7n, n]], Sow[n]], {n, 0, 400}]][[2, 1]]
(* Second program: *)
filterQ[n_] := With[{bb = IntegerDigits[n, 2]}, !MatchQ[bb, {_, 1, 0, 1, _}|{_, 1, 1, _}]];
Select[Range[0, 580], filterQ] (* Jean-François Alcover, Dec 31 2020 *)

is(n)=!bitand(n, 6*n) \\ Charles R Greathouse IV, Oct 03 2016

for my $k (0..580) { print "$k, " if sprintf("%b", $k) =~ m{^(100(0)*)*(0|1|10)?$}; } # Georg Fischer, Jun 26 2021

import re
def ok(n): return re.fullmatch('(100(0)*)*(0|1|10)?', bin(n)[2:]) != None
print(list(filter(ok, range(581)))) # Michael S. Branicky, Jun 26 2021

a(0) = 0, a(n) = (2^(invfoo(n)-1))+a(n-foo(invfoo(n))), where foo(n) is foo(n-1) + foo(n-3) (A000930) and invfoo is its "integral" (floored down) inverse.
a(n) XOR 6*a(n) = 7*a(n); 3*a(n) XOR 4*a(n) = 7*a(n); 3*a(n) XOR 5*a(n) = 6*a(n); (conjectures). - Paul D. Hanna, Jan 22 2006
The conjectures can be verified using the Walnut theorem-prover (see links). - Sebastian Karlsson, Dec 31 2022

Definition corrected by Georg Fischer, Jun 26 2021

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

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A048715 Binary expansion matches (100(0)*)*(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Python

Formula

Extensions

A048719 Binary expansion matches ((0)*0011)*(0*).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A115424 Integers n > 0 such that n XOR 62*n = 63*n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Formula

A115422 Integers n > 0 such that n XOR 20*n = 21*n.

Views

Author

Keywords

A048715 Binary expansion matches (100(0))(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

A048719 Binary expansion matches ((0)0011)(0*).

A115424 Integers n > 0 such that n XOR 62n = 63n.

A115422 Integers n > 0 such that n XOR 20n = 21n.

A115423 Integers n > 0 such that n XOR 30n = 31n.