A180938 Smallest k such that k*n has an even number of 1's in its base-2 expansion.

3, 3, 1, 3, 1, 1, 9, 3, 1, 1, 3, 1, 3, 9, 1, 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, 3, 1, 9, 1, 1, 33, 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 3, 9, 1, 1, 3, 1, 3, 33, 1, 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 5, 3, 1, 1, 5, 1, 11, 3, 1, 1, 3, 3, 1, 3, 1, 1, 9, 3, 1

Offset: 1

Author

Jeffrey Shallit, Sep 26 2010

Keywords

• nonn
• base

Comments

From Robert G. Wilson v, Sep 29 2010: (Start)

k must always be odd.

First occurrence of odd k: 3, 1, 87, 109, 7, 93, 457, 1143, 5501, 7921, 889, 12775, 11753, 635, 111209, 6093, 31, 33823, 7665, ..., .

(End)

Examples

			For n = 7, a(n) = 9, since the smallest multiple of 7 with an even number of 1's in its base-2 expansion is 9*7 = 63.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..32768

Crossrefs

Cf. A001969, A178757.

Cf. A083420 (where records occur). - Alois P. Heinz, Oct 16 2011

Programs

Mathematica

a[n_] := Block[{k = 1}, While[OddQ@ DigitCount[k*n, 2, 1], k++ ]; k]; Array[a, 100] (* Robert G. Wilson v, Sep 29 2010 *)

PARI

A180938(n) = my(k=1); while(hammingweight(k*n)%2, k += 2); k; \\ Antti Karttunen, Jul 09 2017

Python

def a(n):
    k=1
    while True:
        if not bin(k*n)[2:].count('1')%2: return k
        k+=1
print([a(n) for n in range(1, 61)]) # Indranil Ghosh, Jul 11 2017

Extensions

More terms from Robert G. Wilson v, Sep 29 2010