cp's OEIS Frontend

A086342 Smallest number of 1's in binary expansion of any positive multiple of n.

%I A086342 #31 Dec 19 2024 12:19:24
%S A086342 0,1,1,2,1,2,2,3,1,2,2,2,2,2,3,4,1,2,2,2,2,3,2,3,2,2,2,2,3,2,4,5,1,2,
%T A086342 2,3,2,2,2,3,2,2,3,2,2,4,3,3,2,3,2,4,2,2,2,3,3,2,2,2,4,2,5,6,1,2,2,2,
%U A086342 2,3,3,3,2,3,2,4,2,3,3,3,2,2,2,2,3,4,2,3,2,4,4,3,3,5,3,3,2,2,3,2,2,2,4,3,2
%N A086342 Smallest number of 1's in binary expansion of any positive multiple of n.
%C A086342 If n is a power of 2 then a(n)=1. All other positive n have a(n)>1. a(n)=2 precisely in cases where some multiple of n is a factor of 2^q+1 for some q.
%H A086342 T. D. Noe, <a href="/A086342/b086342.txt">Table of n, a(n) for n = 0..10000</a>
%H A086342 Trevor Clokie et al., <a href="https://arxiv.org/abs/2002.02731">Computational Aspects of Sturdy and Flimsy Numbers</a>, arxiv preprint arXiv:2002.02731 [cs.DS], February 7 2020.
%H A086342 Eugen J. Ionascu, Florian Luca, and Thomas Merino, <a href="https://arxiv.org/abs/2412.10839">On the average value of the minimal Hamming multiple</a>, arXiv:2412.10839 [math.NT], 2024. See pp. 4, 17.
%F A086342 a(2^k-1) = k. - _Thomas Dybdahl Ahle_, May 01 2013
%e A086342 a(n)=2 for n=53, 59, 61, 67, 81, 97 and 101 because n divides 2^k+1 for k=26, 29, 30, 33, 27, 24 and 50, respectively. - _T. D. Noe_, Jul 22 2008
%o A086342 (PARI) a(n)=if(!n, return(0)); n>>=valuation(n,2); my(o=znorder(Mod(2, n)), v1=Set(powers(Mod(2, n), o)), v=v1, s=1); while(!setsearch(v, Mod(0, n)), v=setbinop((x, y)->x+y, v, v1); s++); s \\ _Charles R Greathouse IV_, Dec 07 2016
%Y A086342 Cf. A005360 (flimsy numbers), A125121 (sturdy numbers), A143069 (least multiple).
%K A086342 base,nonn
%O A086342 0,4
%A A086342 _Sean A. Irvine_, Sep 02 2003
%E A086342 More terms from _Robert G. Wilson v_, Feb 21 2005
%E A086342 Corrected by _T. D. Noe_, Jul 22 2008
%E A086342 An incorrect Mathematica program was deleted Aug 01 2008