OFFSET
1,2
COMMENTS
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
REFERENCES
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).
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 1..10001
J.-P. Allouche, The zeta-regularized product of odious numbers, arXiv:1906.10532 [math.NT], 2019.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
J.-P. Allouche, J. Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.
J.-P. Allouche, B. Cloitre, and V. Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
J.-P. Allouche, B. Cloitre, and V. Shevelev, Beyond odious and evil, Aequationes mathematicae, March 2015, pp 1-13.
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
FORMULA
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
A005590(a(n)) > 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n)) = -1. - Reinhard Zumkeller, Apr 29 2012
EXAMPLE
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
MAPLE
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.
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
MATHEMATICA
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 *)
PROG
(PARI) {a(n) = if( n<1, 0, 2*n - 1 - subst( Pol(binary( n-1)), x, 1) % 2)}; /* Michael Somos, Jun 01 2013 */
(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 */
(PARI) a(n)=2*n-1-hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013
(Magma) [ n: n in [1..130] | IsOdd(&+Intseq(n, 2)) ]; // Klaus Brockhaus, Oct 07 2010
(Haskell)
a000069 n = a000069_list !! (n-1)
a000069_list = [x | x <- [0..], odd $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012
(Python)
[n for n in range(1, 201) if bin(n)[2:].count("1") % 2] # Indranil Ghosh, May 03 2017
(Python)
def A000069(n): return ((m:=n-1)<<1)+(m.bit_count()&1^1) # Chai Wah Wu, Mar 03 2023
CROSSREFS
KEYWORD
easy,core,nonn,nice,base
AUTHOR
STATUS
approved