|
%I M1031 N0388 #236 Mar 10 2024 13:55:09
%S 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 49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,
%U 94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128
%N Odious numbers: numbers with an odd number of 1's in their binary expansion.
%C 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 In French: les nombres impies.
%C 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 Nim-values for game of mock turtles played with n coins.
%C A115384(n) = number of odious numbers <= n; A000120(a(n)) = A132680(n). - _Reinhard Zumkeller_, Aug 26 2007
%C Indices of 1's in the Thue-Morse sequence A010060. - _Tanya Khovanova_, Dec 29 2008
%C 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 For n>1 let b(n) = a(n-1). Then b(b(n)) = 2b(n). - _Benoit Cloitre_, Oct 07 2010
%C 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 Numbers of the form m XOR (2*m+1) for some m >= 0. - _Rémy Sigrist_, Apr 14 2022
%D E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 433.
%D J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 22.
%D 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 N. J. A. Sloane, A handbook of Integer Sequences, Academic Press, 1973 (including this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A000069/b000069.txt">Table of n, a(n) for n = 1..10001</a>
%H J.-P. Allouche, <a href="https://arxiv.org/abs/1906.10532">The zeta-regularized product of odious numbers</a>, arXiv:1906.10532 [math.NT], 2019.
%H J.-P. Allouche and J. 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 J.-P. Allouche, J. 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 J.-P. Allouche, B. Cloitre, and V. Shevelev, <a href="https://arxiv.org/abs/1405.6214">Beyond odious and evil</a>, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
%H J.-P. Allouche, B. Cloitre, and V. 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 E. Fouvry and C. Mauduit, <a href="http://www.digizeitschriften.de/dms/resolveppn/?PID=PPN235181684_0305%7Clog64">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 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 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 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 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 Sajed Haque, Chapter 3.2 of <a href="https://uwspace.uwaterloo.ca/handle/10012/12234">Discriminators of Integer Sequences</a>, Thesis, 2017.
%H 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 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 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 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv:1410.2193 [math.CO], 2014.
%H 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 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 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 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 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 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/OdiousNumber.html">Odious Number</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F 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 a(n+1) = (1/2) * (4*n + 1 + (-1)^A000120(n)). - _Ralf Stephan_, Sep 14 2003
%F Numbers n such that A010060(n) = 1. - _Benoit Cloitre_, Nov 15 2003
%F 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 (-1)^a(n) = 2*A010060(n)-1. - _Benoit Cloitre_, Mar 08 2004
%F 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 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 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 a(n+1) mod 2 = 1 - A010060(n) = A010059(n). - _Robert G. Wilson v_, Jan 18 2012
%F A005590(a(n)) > 0. - _Reinhard Zumkeller_, Apr 11 2012
%F A106400(a(n)) = -1. - _Reinhard Zumkeller_, Apr 29 2012
%F a(n+1) = A006068(n) XOR (2*A006068(n) + 1). - _Rémy Sigrist_, Apr 14 2022
%e 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 (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 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 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 is_A000069 := n -> type(add(i,i=convert(n,base,2)),odd):
%p seq(`if`(is_A000069(i),i,NULL),i=0..40); # _Peter Luschny_, Feb 03 2011
%t Select[Range[300], OddQ[DigitCount[ #, 2][[1]]] &] (* _Stefan Steinerberger_, Mar 31 2006 *)
%t a[ n_] := If[ n < 1, 0, 2 n - 1 - Mod[ Total @ IntegerDigits[ n - 1, 2], 2]]; (* _Michael Somos_, Jun 01 2013 *)
%o (PARI) {a(n) = if( n<1, 0, 2*n - 1 - subst( Pol(binary( n-1)), x, 1) % 2)}; /* _Michael Somos_, Jun 01 2013 */
%o (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 (PARI) a(n)=2*n-1-hammingweight(n-1)%2 \\ _Charles R Greathouse IV_, Mar 22 2013
%o (Magma) [ n: n in [1..130] | IsOdd(&+Intseq(n, 2)) ]; // _Klaus Brockhaus_, Oct 07 2010
%o (Haskell)
%o a000069 n = a000069_list !! (n-1)
%o a000069_list = [x | x <- [0..], odd $ a000120 x]
%o -- _Reinhard Zumkeller_, Feb 01 2012
%o (Python)
%o [n for n in range(1, 201) if bin(n)[2:].count("1") % 2] # _Indranil Ghosh_, May 03 2017
%o (Python)
%o def A000069(n): return ((m:=n-1)<<1)+(m.bit_count()&1^1) # _Chai Wah Wu_, Mar 03 2023
%Y The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
%Y Complement of A001969 (the evil numbers). Cf. A133009.
%Y a(n) = 2*n + 1 - A010060(n) = A001969(n) + (-1)^A010060(n).
%Y First differences give A007413.
%Y Cf. A000773, A181155, A019568, A059009.
%Y Note that A000079, A083420, A002042, A002089, A132679 are subsequences.
%Y See A027697 for primes, also A230095.
%Y Cf. A005408 (odd numbers), A006068, A026424.
%Y Cf. A010059, A010060.
%K easy,core,nonn,nice,base
%O 1,2
%A _N. J. A. Sloane_
|
