|
%I #26 Feb 22 2022 21:28:08
%S 1,1,7,1,5,7,1,1,9,5,1,7,1,1,19,1,17,9,1,5,1,1,3,7,1,1,3,1,3,19,1,1,
%T 33,17,1,9,1,1,3,5,1,1,7,1,9,3,1,7,1,1,7,1,5,3,1,1,3,3,1,19,1,1,67,1,
%U 65,33,1,17,1,1,3,9,1,1,5,1,5,3,1,5,1,1,5,1,5,7,1,1,5,9,1,3,1,1,3,7,1,1,11,1
%N Smallest k such that k*n has an odd number of 1's in its base-2 expansion.
%C a(n) is the least integer k such that t(k*n) = 1, where t(i) is the Thue-Morse sequence.
%C From _Robert G. Wilson v_, Sep 29 2010: (Start)
%C k must always be odd.
%C First occurrence of odd ks: 1, 23, 5, 3, 9, 99, 325, 315, 17, 15, 3021, 195, 189, 645, 2313, 2295, 33, 7695, 1785, 1799, 105, 387, 23529, 5643, ..., .
%C Records occur at n: 1, 3, 9, 15, 33, 63, 129, 255, 513, 1023, 2049, 4095, 8193, 16383, 32769, 65535, 131073, 262143, ..., . (End)
%C In their paper Morgenbesser et al. prove a(n) <= n+4. They also prove that, for all n>=1, it is possible to find a k such that A010060(k*n) = 1, with k <= n+4 and Hamming weight of k <= 3. That sequence differs from the current sequence at n=195, 315, 387, 390, 630, 645, 765, 771, 774, 780, ... - _Michel Marcus_, Jan 24 2016
%H Michel Marcus, <a href="/A178757/b178757.txt">Table of n, a(n) for n = 1..10000</a>
%H Johannes F. Morgenbesser, Jeffrey Shallit, Thomas Stoll, <a href="http://dx.doi.org/10.1016/j.jnt.2011.02.006">Thue-Morse at multiples of an integer</a>, Journal of Number Theory, Volume 131, Issue 8, August 2011, Pages 1498-1512.
%e For n = 3 the sequence has value 7, since 21 is 10101 in base 2, with an odd number of 1's, and no smaller multiple works.
%t f[n_] := Block[{k = 1}, While[ EvenQ@ DigitCount[k*n, 2, 1], k++ ]; k]; Array[f, 105] (* _Robert G. Wilson v_, Sep 29 2010 *)
%o (PARI) a(n) = {my(k = 1); while (hammingweight(k*n) % 2 != 1, k++); k;} \\ _Michel Marcus_, Jan 23 2016
%o (Python)
%o def a(n):
%o k = 1
%o while not bin(k*n).count("1")%2 == 1: k += 1
%o return k
%o print([a(n) for n in range(1, 81)]) # _Michael S. Branicky_, Feb 22 2022
%Y Cf. A000069, A010060.
%K nonn,base
%O 1,3
%A _Jeffrey Shallit_, Jun 10 2010
|
