A005590 -id:A005590 - cp's OEIS frontend

A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.

1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 64, 67, 69, 70, 73, 74, 76, 79, 81, 82, 84, 87, 88, 91, 93, 94, 97, 98, 100, 103, 104, 107, 109, 110, 112, 115, 117, 118, 121, 122, 124, 127, 128

Offset: 1

N. J. A. Sloane

This sequence and A001969 give the unique solution to the problem of splitting the nonnegative integers into two classes in such a way that sums of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000028, A000379.
In French: les nombres impies.
Has asymptotic density 1/2, since exactly 2 of the 4 numbers 4k, 4k+1, 4k+2, 4k+3 have an even sum of bits, while the other 2 have an odd sum. - Jeffrey Shallit, Jun 04 2002
Nim-values for game of mock turtles played with n coins.
A115384(n) = number of odious numbers <= n; A000120(a(n)) = A132680(n). - Reinhard Zumkeller, Aug 26 2007
Indices of 1's in the Thue-Morse sequence A010060. - Tanya Khovanova, Dec 29 2008
For any positive integer m, the partition of the set of the first 2^m positive integers into evil ones E and odious ones O is a fair division for any polynomial sequence p(k) of degree less than m, that is, Sum_{k in E} p(k) = Sum_{k in O} p(k) holds for any polynomial p with deg(p) < m. - Pietro Majer, Mar 15 2009
For n>1 let b(n) = a(n-1). Then b(b(n)) = 2b(n). - Benoit Cloitre, Oct 07 2010
Lexicographically earliest sequence of distinct nonnegative integers with no term being the binary exclusive OR of any terms. The equivalent sequence for addition or for subtraction is A005408 (the odd numbers) and for multiplication is A026424. - Peter Munn, Jan 14 2018
Numbers of the form m XOR (2*m+1) for some m >= 0. - Rémy Sigrist, Apr 14 2022

			For k=2, x=0 and x=0.2 we respectively have 1^2 + 2^2 + 4^2 + 7^2 = 0^2 + 3^2 + 5^2 + 6^2 = 70;
(1.2)^2 + (2.2)^2 + (4.2)^2 + (7.2)^2 = (0.2)^2 + (3.2)^2 + (5.2)^2 + (6.2)^2 = 75.76;
for k=3, x=1.8, we have (2.8)^3 + (3.8)^3 + (5.8)^3 + (8.8)^3 + (9.8)^3 + (12.8)^3 + (14.8)^3 + (15.8)^3 = (1.8)^3 + (4.8)^3 + (6.8)^3 + (7.8)^3 + (10.8)^3 + (11.8)^3 + (13.8)^3 + (16.8)^3 = 11177.856. - _Vladimir Shevelev_, Jan 16 2012

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 433.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 22.
Vladimir S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the North-Caucasus region, Nature sciences 4 (1997), 21-23 (in Russian).
N. J. A. Sloane, A handbook of Integer Sequences, Academic Press, 1973 (including this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10001
Jean-Paul Allouche, The zeta-regularized product of odious numbers, arXiv:1906.10532 [math.NT], 2019.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Jean-Paul Allouche, Jeffrey Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, Aequationes mathematicae, March 2015, pp 1-13.
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 19.
E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann. Vol. 305, No. 1 (1996), 571-599, DOI:10.1007/BF01444238, MR1397437 (97k:11029).
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Mathematics, Volume 312, Issue 1, 6 January 2012, Pages 42-46.
Maciej Gawron, and Maciej Ulas, On formal inverse of the Prouhet-Thue-Morse sequence, Discrete Mathematics 339.5 (2016): 1459-1470. Also arXiv preprint, arXiv:1601.04840 [math.CO], 2016.
R. K. Guy, The unity of combinatorics, Proc. 25th Iranian Math. Conf, Tehran, (1994), Math. Appl 329 129-159, Kluwer Dordrecht 1995, Math. Rev. 96k:05001.
R. K. Guy, Impartial games, pp. 35-55 of Combinatorial Games, ed. R. K. Guy, Proc. Sympos. Appl. Math., 43, Amer. Math. Soc., 1991.
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, Thesis, 2017.
Sajed Haque and Jeffrey Shallit, Discriminators and k-Regular Sequences, arXiv:1605.00092 [cs.DM], 2016.
K. Jensen, Aesthetics and quality of numbers using the primety measure, Int. J. Arts and Technology, Vol. 7, Nos. 2/3, 2014.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160. [From _N. J. A. Sloane_, Jan 31 2012]
Tanya Khovanova, There are no coincidences, arXiv:1410.2193 [math.CO], 2014.
J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull. 2 (1959), 85-89.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
D. J. Newman, A Problem Seminar, Problem 15 pp. 5; 15 Springer-Verlag NY 1982.
Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, Additive Number Theory via Automata Theory, Theory of Computing Systems (2019) 1-26.
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, arXiv:1207.0404 [math.NT], 2012-2014. - From _N. J. A. Sloane_, Dec 17 2012
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, INTEGERS, 14(2014) #64.
Vladimir Shevelev and Peter J. C. Moses, A family of digit functions with large periods, arXiv:1209.5705 [math.NT], 2012.
Andrzej Tomski and Maciej Zakarczemny, A note on Browkin's and Cao's cancellation algorithm, Technical Transections 7/2018.
Eric Weisstein's World of Mathematics, Odious Number
Index entries for sequences related to binary expansion of n
Index entries for "core" sequences

The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Complement of A001969 (the evil numbers). Cf. A133009.
a(n) = 2*n + 1 - A010060(n) = A001969(n) + (-1)^A010060(n).
First differences give A007413.
Cf. A000773, A181155, A019568, A059009.
Note that A000079, A083420, A002042, A002089, A132679 are subsequences.
See A027697 for primes, also A230095.
Cf. A005408 (odd numbers), A006068, A026424.
Cf. A010059, A010060.

a000069 n = a000069_list !! (n-1)
a000069_list = [x | x <- [0..], odd $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012

[ n: n in [1..130] | IsOdd(&+Intseq(n, 2)) ]; // Klaus Brockhaus, Oct 07 2010

s := proc(n) local i,j,k,b,sum,ans; ans := [ ]; j := 0; for i while jA000069 := n->t1[n]; # s(k) gives first k terms.
is_A000069 := n -> type(add(i,i=convert(n,base,2)),odd):
seq(`if`(is_A000069(i),i,NULL),i=0..40); # Peter Luschny, Feb 03 2011

Select[Range[300], OddQ[DigitCount[ #, 2][[1]]] &] (* Stefan Steinerberger, Mar 31 2006 *)
a[ n_] := If[ n < 1, 0, 2 n - 1 - Mod[ Total @ IntegerDigits[ n - 1, 2], 2]]; (* Michael Somos, Jun 01 2013 *)

{a(n) = if( n<1, 0, 2*n - 1 - subst( Pol(binary( n-1)), x, 1) % 2)}; /* Michael Somos, Jun 01 2013 */

{a(n) = if( n<2, n==1, if( n%2, a((n+1)/2) + n-1, -a(n/2) + 3*(n-1)))}; /* Michael Somos, Jun 01 2013 */

a(n)=2*n-1-hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013

[n for n in range(1, 201) if bin(n)[2:].count("1") % 2] # Indranil Ghosh, May 03 2017

def A000069(n): return ((m:=n-1)<<1)+(m.bit_count()&1^1) # Chai Wah Wu, Mar 03 2023

G.f.: 1 + Sum_{k>=0} (t*(2+2t+5t^2-t^4)/(1-t^2)^2) * Product_{j=0..k-1} (1-x^(2^j)), t=x^2^k. - Ralf Stephan, Mar 25 2004
a(n+1) = (1/2) * (4*n + 1 + (-1)^A000120(n)). - Ralf Stephan, Sep 14 2003
Numbers n such that A010060(n) = 1. - Benoit Cloitre, Nov 15 2003
a(2*n+1) + a(2*n) = A017101(n) = 8*n+3. a(2*n+1) - a(2*n) gives the Thue-Morse sequence (1, 3 version): 1, 3, 3, 1, 3, 1, 1, 3, 3, 1, 1, 3, 1, ... A001969(n) + A000069(n) = A016813(n) = 4*n+1. - Philippe Deléham, Feb 04 2004
(-1)^a(n) = 2*A010060(n)-1. - Benoit Cloitre, Mar 08 2004
a(1) = 1; for n > 1: a(2*n) = 6*n-3 -a(n), a(2*n+1) = a(n+1) + 2*n. - Corrected by Vladimir Shevelev, Sep 25 2011
For k >= 1 and for every real (or complex) x, we have Sum_{i=1..2^k} (a(i)+x)^s = Sum_{i=1..2^k} (A001969(i)+x)^s, s=0..k.
For x=0, s <= k-1, this is known as Prouhet theorem (see J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence). - Vladimir Shevelev, Jan 16 2012
a(n+1) mod 2 = 1 - A010060(n) = A010059(n). - Robert G. Wilson v, Jan 18 2012
A005590(a(n)) > 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n)) = -1. - Reinhard Zumkeller, Apr 29 2012
a(n+1) = A006068(n) XOR (2*A006068(n) + 1). - Rémy Sigrist, Apr 14 2022

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

Original entry on oeis.org

0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 95, 96, 99, 101, 102, 105, 106, 108, 111, 113, 114, 116, 119, 120, 123, 125, 126, 129

Offset: 1

N. J. A. Sloane

This sequence and A000069 give the unique solution to the problem of splitting the nonnegative integers into two classes in such a way that sums of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000028, A000379.
In French: les nombres païens.
Theorem: First differences give A036585. (Observed by Franklin T. Adams-Watters.)
Proof from Max Alekseyev, Aug 30 2006 (edited by N. J. A. Sloane, Jan 05 2021): (Start)
Observe that if the last bit of a(n) is deleted, we get the nonnegative numbers 0, 1, 2, 3, ... in order.
The last bit in a(n+1) is 1 iff the number of bits in n is odd, that is, iff A010060(n+1) is 1.
So, taking into account the different offsets here and in A010060, we have a(n) = 2*(n-1) + A010060(n-1).
Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585.  QED (End)
Integers k such that A010060(k-1)=0. - Benoit Cloitre, Nov 15 2003
Indices of zeros in the Thue-Morse sequence A010060 shifted by 1. - Tanya Khovanova, Feb 13 2009
Conjecture, checked up to 10^6: a(n) is also the sequence of numbers k representable as k = ror(x) XOR rol(x) (for some integer x) where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left, and XOR is the binary exclusive-or operator. - Alex Ratushnyak, May 14 2016
From Charlie Neder, Oct 07 2018: (Start)
Conjecture is true: ror(x) and rol(x) have an even number of 1 bits in total (= 2 * A000120(x)), and XOR preserves the parity of this total, so the resulting number must have an even number of 1 bits. An x can be constructed corresponding to a(n) like so:
If the number of bits in a(n) is even, add a leading 0 so a(n) is 2k+1 bits long.
Do an inverse shuffle on a(n), then "divide" by 11, rotate the result k bits to the right, and shuffle to get x. (End)
Numbers of the form m XOR (2*m) for some m >= 0. - Rémy Sigrist, Feb 07 2021
The terms "evil numbers" and "odious numbers" were coined by Richard K. Guy, c. 1976 (Haque and Shallit, 2016) and appeared in the book by Berlekamp et al. (Vol. 1, 1st ed., 1982). - Amiram Eldar, Jun 08 2021

Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, 2nd ed., A K Peters, 2001, chapter 14, p. 110.
Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
Donald J. Newman, A Problem Seminar, Springer; see Problem #89.
Vladimir S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the North-Caucasus region, Nature sciences 4 (1997), 21-23 (Russian).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Henri Cohen, Dirichlet series and curious infinite products, Bull. London Math. Soc., Vol. 17 (1985), pp. 531-538.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197; DOI.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, Aequationes mathematicae, Vol. 90 (2016), pp. 341-353; alternative link.
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 19.
Chris Bernhardt, Evil twins alternate with odious twins, Math. Mag., Vol. 82, No. 1 (2009), pp. 57-62; alternative link.
Joshua N. Cooper, Dennis Eichhorn and Kevin O'Bryant, Reciprocals of binary power series, International Journal of Number Theory, Vol. 2, No. 4 (2006), pp. 499-522; arXiv preprint, arXiv:math/0506496 [math.NT], 2005.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math., Vol. 312, No. 1 (2012), pp. 42-46.
E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann., Vol. 305, No. 3 (1996), pp. 571-599. MR1397437 (97k:11029)
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, thesis, University of Waterloo, Ontario, Canada, 2017. See p. 38.
Sajed Haque and Jeffrey Shallit, Discriminators and k-Regular Sequences Integers, Vol. 16 (2016), Article A76; arXiv preprint, arXiv:1605.00092 [cs.DM], 2016.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull., Vol. 2, No. 2 (1959), pp. 85-89.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3, No. 4 (1974), pp. 255-261.
Jeffrey O. Shallit, On infinite products associated with sums of digits, J. Number Theory, Vol. 21, No. 2 (1985), pp. 128-134.
Jeffrey Shallit, Frobenius Numbers and Automatic Sequences, arXiv:2103.10904 [math.NT], 2021.
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, arXiv preprint arXiv:1207.0404 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 17 2012
Vladimir Shevelev and Peter J. C. Moses, A family of digit functions with large periods, arXiv preprint arXiv:1209.5705 [math.NT], 2012.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, INTEGERS, Vol. 14 (2014) #64.
Eric Weisstein's World of Mathematics, Evil Number.
Index entries for sequences related to binary expansion of n
Index entries for "core" sequences

Complement of A000069 (the odious numbers). Cf. A133009.
a(n)=2*n+A010060(n)=A000069(n)-(-1)^A010060(n). Cf. A018900.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Cf. A036585 (differences), A010060, A006364.
For primes see A027699, also A130593.
Cf. A006068, A048724, A059010, A094677.

a001969 n = a001969_list !! (n-1)
a001969_list = [x | x <- [0..], even $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012

[ n : n in [0..129] | IsEven(&+Intseq(n,2)) ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

s := proc(n) local i,j,ans; ans := [ ]; j := 0; for i from 0 while jA001969 := n->t1[n]; # s(k) gives first k terms.
# Alternative:
seq(`if`(add(k, k=convert(n,base,2))::even, n, NULL), n=0..129); # Peter Luschny, Jan 15 2021
# alternative for use outside this sequence
isA001969 := proc(n)
    add(d,d=convert(n,base,2)) ;
    type(%,'even') ;
end proc:
A001969 := proc(n)
    option remember ;
    local a;
    if n = 0 then
        1;
    else
        for a from procname(n-1)+1 do
            if isA001969(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A001969(n),n=1..200) ; # R. J. Mathar, Aug 07 2022

Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]
a[ n_] := If[ n < 1, 0, With[{m = n - 1}, 2 m + Mod[-Total@IntegerDigits[m, 2], 2]]]; (* Michael Somos, Jun 09 2019 *)

a(n)=n-=1; 2*n+subst(Pol(binary(n)),x,1)%2

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

a(n)=2*(n-1)+hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013

def ok(n): return bin(n)[2:].count('1') % 2 == 0
print(list(filter(ok, range(130)))) # Michael S. Branicky, Jun 02 2021

from itertools import chain, count, islice
def A001969_gen(): # generator of terms
    return chain((0,),chain.from_iterable((sorted(n^ n<<1 for n in range(2**l,2**(l+1))) for l in count(0))))
A001969_list = list(islice(A001969_gen(),30)) # Chai Wah Wu, Jun 29 2022

def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # Chai Wah Wu, Mar 03 2023

a(n+1) - A001285(n) = 2n-1 has been verified for n <= 400. - John W. Layman, May 16 2003 [This can be directly verified by comparing Ralf Stephan's formulas for this sequence (see below) and for A001285. - Jianing Song, Nov 04 2024]
Note that 2n+1 is in the sequence iff 2n is not and so this sequence has asymptotic density 1/2. - Franklin T. Adams-Watters, Aug 23 2006
a(n) = (1/2) * (4n - 3 - (-1)^A000120(n-1)). - Ralf Stephan, Sep 14 2003
G.f.: Sum_{k>=0} (t(3+2t+3t^2)/(1-t^2)^2) * Product_{l=0..k-1} (1-x^(2^l)), where t = x^2^k. - Ralf Stephan, Mar 25 2004
a(2*n+1) + a(2*n) = A017101(n-1) = 8*n-5.
a(2*n) - a(2*n-1) gives the Thue-Morse sequence (3, 1 version): 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, .... A001969(n) + A000069(n) = A016813(n-1) = 4*n-3. - Philippe Deléham, Feb 04 2004
a(1) = 0; for n > 1: a(n) = 3*n-3 - a(n/2) if n even, a(n) = a((n+1)/2)+n-1 if n odd.
Let b(n) = 1 if sum of digits of n is even, -1 if it is odd; then Shallit (1985) showed that Product_{n>=0} ((2n+1)/(2n+2))^b(n) = 1/sqrt(2).
a(n) = 2n - 2 + A010060(n-1). - Franklin T. Adams-Watters, Aug 28 2006
A005590(a(n-1)) <= 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n-1)) = 1. - Reinhard Zumkeller, Apr 29 2012
a(n) = (a(n-1) + 2) XOR A010060(a(n-1) + 2). - Falk Hüffner, Jan 21 2022
a(n+1) = A006068(n) XOR (2*A006068(n)). - Rémy Sigrist, Apr 14 2022

More terms from Robin Trew (trew(AT)hcs.harvard.edu)

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.

Original entry on oeis.org

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

cp's OEIS Frontend

A182093 Partial sums of A005590.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Formula

Extensions

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

A229817 Even bisection gives sequence a itself, n->a(2*(2*n+k)-1) gives k-th differences of a for k=1..2 with a(n)=n for n<2.

Views

Author

Keywords

Links

Crossrefs

A229817 Even bisection gives sequence a itself, n->a(2(2n+k)-1) gives k-th differences of a for k=1..2 with a(n)=n for n<2.

A229818 Even bisection gives sequence a itself, n->a(2(3n+k)-1) gives k-th differences of a for k=1..3 with a(n)=n for n<2.

A229819 Even bisection gives sequence a itself, n->a(2(4n+k)-1) gives k-th differences of a for k=1..4 with a(n)=n for n<2.

A229820 Even bisection gives sequence a itself, n->a(2(5n+k)-1) gives k-th differences of a for k=1..5 with a(n)=n for n<2.

A229821 Even bisection gives sequence a itself, n->a(2(6n+k)-1) gives k-th differences of a for k=1..6 with a(n)=n for n<2.

A229822 Even bisection gives sequence a itself, n->a(2(7n+k)-1) gives k-th differences of a for k=1..7 with a(n)=n for n<2.