login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000069 Odious numbers: numbers with an odd number of 1's in their binary expansion.
(Formerly M1031 N0388)
210
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 (list; graph; refs; listen; history; text; internal format)
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.

En français: 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 ones 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 integer numbers 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

A000069(n)(mod 2) == A010060(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

REFERENCES

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 433.

Fouvry, E.; Mauduit, C. Sommes des chiffres et nombres presque premiers. (French) [Sums of digits and almost primes] Math. Ann. 305 (1996), no. 3, 571--599. MR1397437 (97k:11029)

R. K. Guy, Impartial games, pp. 35-55 of Combinatorial Games, ed. R. K. Guy, Proc. Sympos. Appl. Math., 43, Amer. Math. Soc., 1991.

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.

K. Jensen, Aesthetics and quality of numbers using the primety measure, Int. J. Arts and Technology, Vol. 7, Nos. 2/3, 2014; http://vbn.aau.dk/files/197163405/IJART0702_0307_JENSEN.pdf

C. Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160. [From N. J. A. Sloane, Jan 31 2012]

Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193, 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, Springer; see Problem #89.

J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 22.

V. 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.

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 and J. Shallit, The Ring of k-regular Sequences, II

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, V. Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214, 2014

Vladimir Shevelev, Peter J. C. Moses, Tangent power sums and their applications, arXiv preprint arXiv:1207.0404, 2012. - From N. J. A. Sloane, Dec 17 2012

V. Shevelev and P. J. C. Moses, A family of digit functions with large periods, arXiv preprint arXiv:1209.5705, 2012

Eric Weisstein's World of Mathematics, Odious Number

Index entries for sequences related to binary expansion of n

Index entries for "core" sequences

FORMULA

G.f.: 1+sum[k>=0, t(2+2t+5t^2-t^4)/(1-t^2)^2 * prod(l=0, k-1, 1-x^(2^l)), t=x^2^k]. - Ralf Stephan, Mar 25 2004

a(n) = 1/2 * (4n + 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,1,...,k.

For x=0, s<=k-1, it is known as Prouhet theorem (see: J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence). - Vladimir Shevelev, Jan 16 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

CROSSREFS

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.

Note that A000079, A083420, A002042, A002089, A132679 are subsequences.

Cf. A019568.

See A027697 for primes, also A230095.

Cf. A059009.

Sequence in context: A187418 A161989 A229829 * A140137 A080308 A089559

Adjacent sequences:  A000066 A000067 A000068 * A000070 A000071 A000072

KEYWORD

easy,core,nonn,nice,base,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 22 23:27 EDT 2014. Contains 248411 sequences.