A000028 - OEIS

A000028

Let k = p_1^e_1 p_2^e_2 p_3^e_3 ... be the prime factorization of n. Sequence gives k such that the sum of the numbers of 1's in the binary expansions of e_1, e_2, e_3, ... is odd.
(Formerly M0520 N0187)

2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19, 23, 24, 25, 29, 30, 31, 37, 40, 41, 42, 43, 47, 49, 53, 54, 56, 59, 60, 61, 66, 67, 70, 71, 72, 73, 78, 79, 81, 83, 84, 88, 89, 90, 96, 97, 101, 102, 103, 104, 105, 107, 108, 109, 110, 113, 114, 121, 126, 127, 128, 130, 131, 132, 135, 136, 137

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

This sequence and A000379 (its complement) give the unique solution to the problem of splitting the positive integers into two classes in such a way that products of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000069, A001969.

Contains (for example) 180, so is different from A123193. - Max Alekseyev, Sep 20 2007

The sequence contains products of odd number of distinct terms of A050376. - Vladimir Shevelev, May 04 2010

From Vladimir Shevelev, Oct 28 2013: (Start)

Numbers m such that infinitary Moebius function of m (A064179) equals -1. This follows from the definition of A064179.

Number m is in the sequence if and only if the number k = k(m) of terms of A050376 which divide m with odd maximal exponent is odd.

For example, if m = 96, then the maximal exponent of 2 that divides 96 is 5, for 3 it is 1, for 4 it is 2, for 16 it is 1. Thus k(96) = 3 and 96 is a term.

(End)

Positions of odd terms in A064547, A268386 and A293439. - Antti Karttunen, Nov 09 2017

Lexicographically earliest sequence of distinct nonnegative integers such that no term is the A059897 product of 2 terms. (A059897 can be considered as a multiplicative operator related to the Fermi-Dirac factorization of numbers described in A050376.) Specifying that the A059897 product be of 2 distinct terms leaves the sequence unchanged. The equivalent sequences using standard integer multiplication are A026416 (with the 2 terms specified as distinct) and A026424 (otherwise). - Peter Munn, Mar 16 2019

From Amiram Eldar, Oct 02 2024: (Start)

Numbers whose number of infinitary divisors (A037445) is not a square.

Numbers whose exponentially odious part (A367514) has an odd number of distinct prime factors, i.e., numbers k such that A092248(A367514(k)) = 1. (End)

REFERENCES

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

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull. 2 (1959), 85-89.

Index entries for sequences computed from exponents in factorization of n.

EXAMPLE

If k = 96 then the maximal exponent of 2 that divides 96 is 5, for 3 it is 1. 5 in binary is 101_2 and has so has a sum of binary digits of 1 + 0 + 1 = 2. 1 in binary is 1_2 and so has a sum of binary digits of 1. Thus the sum of digits of binary exponents is 2 + 1 = 3 which is odd and so 96 is a term. - Vladimir Shevelev, Oct 28 2013, edited by David A. Corneth, Mar 20 2019

MAPLE

(Maple program from N. J. A. Sloane, Dec 20 2007) expts:=proc(n) local t1, t2, t3, t4, i; if n=1 then RETURN([0]); fi; if isprime(n) then RETURN([1]); fi; t1:=ifactor(n); if nops(factorset(n))=1 then RETURN([op(2, t1)]); fi; t2:=nops(t1); t3:=[]; for i from 1 to t2 do t4:=op(i, t1); if nops(t4) = 1 then t3:=[op(t3), 1]; else t3:=[op(t3), op(2, t4)]; fi; od; RETURN(t3); end; # returns a list of the exponents e_1, e_2, ...

A000120 := proc(n) local w, m, i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end: # returns weight of binary expansion

LamMos:= proc(n) local t1, t2, t3, i; t1:=expts(n); add( A000120(t1[i]), i=1..nops(t1)); end; # returns sum of weights of exponents

M:=400; t0:=[]; t1:=[]; for n from 1 to M do if LamMos(n) mod 2 = 0 then t0:=[op(t0), n] else t1:=[op(t1), n]; fi; od: t0; t1; # t0 is A000379, t1 is the present sequence

MATHEMATICA

iMoebiusMu[ n_ ] := Switch[ MoebiusMu[ n ], 1, 1, -1, -1, 0, If[ OddQ[ Plus@@ (DigitCount[ Last[ Transpose[ FactorInteger[ n ] ] ], 2, 1 ]) ], -1, 1 ] ]; q=Select[ Range[ 20000 ], iMoebiusMu[ # ]===-1& ] (* Wouter Meeussen, Dec 21 2007 *)

Rest[Select[Range[150], OddQ[Count[Flatten[IntegerDigits[#, 2]&/@ Transpose[ FactorInteger[#]][[2]]], 1]]&]] (* Harvey P. Dale, Feb 25 2012 *)

PROG

(Haskell)

a000028 n = a000028_list !! (n-1)

a000028_list = filter (odd . sum . map a000120 . a124010_row) [1..]

-- Reinhard Zumkeller, Oct 05 2011

(PARI) is(n)=my(f=factor(n)[, 2]); sum(i=1, #f, hammingweight(f[i]))%2 \\ Charles R Greathouse IV, Aug 31 2013

CROSSREFS

Cf. A133008, A000379 (complement), A000120 (binary weight function), A064547; also A066724, A026477, A050376, A084400, A268386, A293439.

Note that A000069 and A001969, also A000201 and A001950 give other decompositions of the integers into two classes.

Cf. A124010 (prime exponents).

Cf. A026416, A026424, A059897.

Cf. A030230, A037445, A092248, A367514.

Sequence in context: A173345 A226091 A064175 * A026416 A123193 A345944

Adjacent sequences: A000025 A000026 A000027 * A000029 A000030 A000031

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane, Simon Plouffe

EXTENSIONS

Entry revised by N. J. A. Sloane, Dec 20 2007, restoring the original definition, correcting the entries and adding a new b-file.

STATUS

approved