A086342 - OEIS

A086342

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

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, 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, 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

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

OFFSET

0,4

COMMENTS

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.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..10000

Trevor Clokie et al., Computational Aspects of Sturdy and Flimsy Numbers, arxiv preprint arXiv:2002.02731 [cs.DS], February 7 2020.

FORMULA

a(2^k-1) = k. - Thomas Dybdahl Ahle, May 01 2013

EXAMPLE

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

PROG

(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

CROSSREFS

Cf. A005360 (flimsy numbers), A125121 (sturdy numbers), A143069 (least multiple).

Sequence in context: A371452 A211097 A354907 * A274036 A194449 A370820

Adjacent sequences: A086339 A086340 A086341 * A086343 A086344 A086345

KEYWORD

base,nonn

AUTHOR

Sean A. Irvine, Sep 02 2003

EXTENSIONS

More terms from Robert G. Wilson v, Feb 21 2005

Corrected by T. D. Noe, Jul 22 2008

An incorrect Mathematica program was deleted Aug 01 2008

STATUS

approved