cp's OEIS Frontend

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

%I A000069 M1031 N0388 #244 Aug 11 2025 07:58:45
%S A000069 1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,
%T A000069 49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,
%U A000069 94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128
%N A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.
%C A000069 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.
%C A000069 In French: les nombres impies.
%C A000069 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
%C A000069 Nim-values for game of mock turtles played with n coins.
%C A000069 A115384(n) = number of odious numbers <= n; A000120(a(n)) = A132680(n). - _Reinhard Zumkeller_, Aug 26 2007
%C A000069 Indices of 1's in the Thue-Morse sequence A010060. - _Tanya Khovanova_, Dec 29 2008
%C A000069 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
%C A000069 For n>1 let b(n) = a(n-1). Then b(b(n)) = 2b(n). - _Benoit Cloitre_, Oct 07 2010
%C A000069 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
%C A000069 Numbers of the form m XOR (2*m+1) for some m >= 0. - _Rémy Sigrist_, Apr 14 2022
%D A000069 E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 433.
%D A000069 J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 22.
%D A000069 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).
%D A000069 N. J. A. Sloane, A handbook of Integer Sequences, Academic Press, 1973 (including this sequence).
%D A000069 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000069 N. J. A. Sloane, <a href="/A000069/b000069.txt">Table of n, a(n) for n = 1..10001</a>
%H A000069 Jean-Paul Allouche, <a href="https://arxiv.org/abs/1906.10532">The zeta-regularized product of odious numbers</a>, arXiv:1906.10532 [math.NT], 2019.
%H A000069 Jean-Paul Allouche and Jeffrey Shallit, <a href="https://doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H A000069 Jean-Paul Allouche, Jeffrey Shallit and G. Skordev, <a href="https://doi.org/10.1016/j.disc.2004.12.004">Self-generating sets, integers with missing blocks and substitutions</a>, Discrete Math. 292 (2005) 1-15.
%H A000069 Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, <a href="https://arxiv.org/abs/1405.6214">Beyond odious and evil</a>, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
%H A000069 Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, <a href="http://www.math.bgu.ac.il/~shevelev/58_Beyond_J.pdf">Beyond odious and evil</a>, Aequationes mathematicae, March 2015, pp 1-13.
%H A000069 Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, <a href="https://arxiv.org/abs/2401.13524">Combinatorics on words and generating Dirichlet series of automatic sequences</a>, arXiv:2401.13524 [math.CO], 2025. See p. 19.
%H A000069 E. Fouvry and C. Mauduit, <a href="https://gdz.sub.uni-goettingen.de/id/PPN235181684_0305">Sommes des chiffres et nombres presque premiers</a>, (French) [Sums of digits and almost primes] Math. Ann. Vol. 305, No. 1 (1996), 571-599, DOI:<a href="https://doi.org/10.1007/BF01444238">10.1007/BF01444238</a>, MR1397437 (97k:11029).
%H A000069 Aviezri S. Fraenkel, <a href="https://doi.org/10.1016/j.disc.2011.03.032">The vile, dopey, evil and odious game players</a>, Discrete Mathematics, Volume 312, Issue 1, 6 January 2012, Pages 42-46.
%H A000069 Maciej Gawron, and Maciej Ulas, <a href="https://doi.org/10.1016/j.disc.2015.12.016">On formal inverse of the Prouhet-Thue-Morse sequence</a>, Discrete Mathematics 339.5 (2016): 1459-1470. Also <a href="https://arxiv.org/abs/1601.04840">arXiv preprint</a>, arXiv:1601.04840 [math.CO], 2016.
%H A000069 R. K. Guy, <a href="https://doi.org/10.1007/978-1-4613-3554-2_9">The unity of combinatorics</a>, Proc. 25th Iranian Math. Conf, Tehran, (1994), Math. Appl 329 129-159, Kluwer Dordrecht 1995, Math. Rev. 96k:05001.
%H A000069 R. K. Guy, <a href="http://library.msri.org/books/Book29/files/imp.pdf">Impartial games</a>, pp. 35-55 of Combinatorial Games, ed. R. K. Guy, Proc. Sympos. Appl. Math., 43, Amer. Math. Soc., 1991.
%H A000069 Sajed Haque, Chapter 3.2 of <a href="https://uwspace.uwaterloo.ca/handle/10012/12234">Discriminators of Integer Sequences</a>, Thesis, 2017.
%H A000069 Sajed Haque and Jeffrey Shallit, <a href="https://arxiv.org/abs/1605.00092">Discriminators and k-Regular Sequences</a>, arXiv:1605.00092 [cs.DM], 2016.
%H A000069 K. Jensen, <a href="http://vbn.aau.dk/files/197163405/IJART0702_0307_JENSEN.pdf">Aesthetics and quality of numbers using the primety measure</a>, Int. J. Arts and Technology, Vol. 7, Nos. 2/3, 2014.
%H A000069 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., 274 (2004), 147-160. [From _N. J. A. Sloane_, Jan 31 2012]
%H A000069 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv:1410.2193 [math.CO], 2014.
%H A000069 J. Lambek and L. Moser, <a href="http://dx.doi.org/10.4153/CMB-1959-013-x">On some two way classifications of integers</a>, Canad. Math. Bull. 2 (1959), 85-89.
%H A000069 M. D. McIlroy, <a href="http://dx.doi.org/10.1137/0203020">The number of 1's in binary integers: bounds and extremal properties</a>, SIAM J. Comput., 3 (1974), 255-261.
%H A000069 H. L. Montgomery, <a href="http://www-personal.umich.edu/~hlm/ten.html">Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis</a>, Amer. Math. Soc., 1996, p. 208.
%H A000069 D. J. Newman, <a href="http://dx.doi.org/10.1007/978-1-4613-8214-0">A Problem Seminar</a>, Problem 15 pp. 5; 15 Springer-Verlag NY 1982.
%H A000069 Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, <a href="https://doi.org/10.1007/s00224-019-09929-9">Additive Number Theory via Automata Theory</a>, Theory of Computing Systems (2019) 1-26.
%H A000069 Jeffrey Shallit, <a href="https://arxiv.org/abs/2112.13627">Additive Number Theory via Automata and Logic</a>, arXiv:2112.13627 [math.NT], 2021.
%H A000069 Vladimir Shevelev and Peter J. C. Moses, <a href="http://arxiv.org/abs/1207.0404">Tangent power sums and their applications</a>, arXiv:1207.0404 [math.NT], 2012-2014. - From _N. J. A. Sloane_, Dec 17 2012
%H A000069 Vladimir Shevelev and Peter J. C. Moses, <a href="http://www.emis.de/journals/INTEGERS/papers/o64/o64.Abstract.html">Tangent power sums and their applications</a>, INTEGERS, 14(2014) #64.
%H A000069 Vladimir Shevelev and Peter J. C. Moses, <a href="http://arxiv.org/abs/1209.5705">A family of digit functions with large periods</a>, arXiv:1209.5705 [math.NT], 2012.
%H A000069 Andrzej Tomski and Maciej Zakarczemny, <a href="https://doi.org/10.4467/2353737XCT.18.106.8801">A note on Browkin's and Cao's cancellation algorithm</a>, Technical Transections 7/2018.
%H A000069 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/OdiousNumber.html">Odious Number</a>
%H A000069 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A000069 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000069 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
%F A000069 a(n+1) = (1/2) * (4*n + 1 + (-1)^A000120(n)). - _Ralf Stephan_, Sep 14 2003
%F A000069 Numbers n such that A010060(n) = 1. - _Benoit Cloitre_, Nov 15 2003
%F A000069 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
%F A000069 (-1)^a(n) = 2*A010060(n)-1. - _Benoit Cloitre_, Mar 08 2004
%F A000069 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
%F A000069 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.
%F A000069 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
%F A000069 a(n+1) mod 2 = 1 - A010060(n) = A010059(n). - _Robert G. Wilson v_, Jan 18 2012
%F A000069 A005590(a(n)) > 0. - _Reinhard Zumkeller_, Apr 11 2012
%F A000069 A106400(a(n)) = -1. - _Reinhard Zumkeller_, Apr 29 2012
%F A000069 a(n+1) = A006068(n) XOR (2*A006068(n) + 1). - _Rémy Sigrist_, Apr 14 2022
%e A000069 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;
%e A000069 (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;
%e A000069 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
%p A000069 s := proc(n) local i,j,k,b,sum,ans; ans := [ ]; j := 0; for i while j<n do sum := 0; b := convert(i,base,2); for k to nops(b) do sum := sum+b[ k ]; od; if sum mod 2 = 1 then ans := [ op(ans),i ]; j := j+1; fi; od; RETURN(ans); end; t1 := s(100); A000069 := n->t1[n]; # s(k) gives first k terms.
%p A000069 is_A000069 := n -> type(add(i,i=convert(n,base,2)),odd):
%p A000069 seq(`if`(is_A000069(i),i,NULL),i=0..40); # _Peter Luschny_, Feb 03 2011
%t A000069 Select[Range[300], OddQ[DigitCount[ #, 2][[1]]] &] (* _Stefan Steinerberger_, Mar 31 2006 *)
%t A000069 a[ n_] := If[ n < 1, 0, 2 n - 1 - Mod[ Total @ IntegerDigits[ n - 1, 2], 2]]; (* _Michael Somos_, Jun 01 2013 *)
%o A000069 (PARI) {a(n) = if( n<1, 0, 2*n - 1 - subst( Pol(binary( n-1)), x, 1) % 2)}; /* _Michael Somos_, Jun 01 2013 */
%o A000069 (PARI) {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 */
%o A000069 (PARI) a(n)=2*n-1-hammingweight(n-1)%2 \\ _Charles R Greathouse IV_, Mar 22 2013
%o A000069 (Magma) [ n: n in [1..130] | IsOdd(&+Intseq(n, 2)) ]; // _Klaus Brockhaus_, Oct 07 2010
%o A000069 (Haskell)
%o A000069 a000069 n = a000069_list !! (n-1)
%o A000069 a000069_list = [x | x <- [0..], odd $ a000120 x]
%o A000069 -- _Reinhard Zumkeller_, Feb 01 2012
%o A000069 (Python)
%o A000069 [n for n in range(1, 201) if bin(n)[2:].count("1") % 2] # _Indranil Ghosh_, May 03 2017
%o A000069 (Python)
%o A000069 def A000069(n): return ((m:=n-1)<<1)+(m.bit_count()&1^1) # _Chai Wah Wu_, Mar 03 2023
%Y A000069 The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
%Y A000069 Complement of A001969 (the evil numbers). Cf. A133009.
%Y A000069 a(n) = 2*n + 1 - A010060(n) = A001969(n) + (-1)^A010060(n).
%Y A000069 First differences give A007413.
%Y A000069 Cf. A000773, A181155, A019568, A059009.
%Y A000069 Note that A000079, A083420, A002042, A002089, A132679 are subsequences.
%Y A000069 See A027697 for primes, also A230095.
%Y A000069 Cf. A005408 (odd numbers), A006068, A026424.
%Y A000069 Cf. A010059, A010060.
%K A000069 easy,core,nonn,nice,base
%O A000069 1,2
%A A000069 _N. J. A. Sloane_