A125121 Sturdy numbers: n such that in binary notation k*n has at least as many 1-bits as n for all k>0.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 17, 18, 20, 21, 24, 28, 30, 31, 32, 33, 34, 35, 36, 40, 42, 45, 48, 49, 51, 56, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 73, 75, 80, 84, 85, 89, 90, 93, 96, 98, 102, 105, 112, 120, 124, 126, 127, 128, 129, 130, 132, 133, 135, 136

Offset: 1

Author

Jonathan Vos Post, Jul 07 2008

Keywords

• nonn
• look
• base

Comments

Is there some absolute upper limit of k for each n, after which the program can finish the testing loop? - Antti Karttunen, Dec 20 2009

Reply from T. D. Noe, Dec 20 2009: Although theorem 2.1 in the paper by Stolarsky is useful, the seqfan e-mail from Jack Brennen sometime around July 2008 is the key to computing these numbers. "To determine if an odd number N is flimsy, take the finite set of residues of 2^a (mod N). Assume that the number of 1's in the binary representation of N is equal to C. To show that the number is flimsy, find a way to construct zero (mod N) by adding up some number of residues of 2^a (mod N) using less than C terms. To show that the number is sturdy, show that it's impossible to do so." In short, this sequence, though difficult to compute, is well defined.

Numbers of the form 2^m-1 (A000225) is a subsequence. - David A. Corneth, Oct 01 2016

Links

• T. D. Noe, Table of n, a(n) for n = 1..2475 (sturdy numbers <= 2^16)
• Trevor Clokie et al., Computational Aspects of Sturdy and Flimsy Numbers, arxiv preprint arXiv:2002.02731 [cs.DS], February 7 2020.
• Tony D. Noe, S000848 Odd sturdy numbers, Integer Sequences.
• K. B. Stolarsky, Integers whose multiples have anomalous digital frequencies, Acta Arithmetica, 38 (1980), 117-128.

Crossrefs

See A143027 for prime sturdy numbers.

Programs

Mathematica

nmax = 136; kmax = 200; nn = (* numbers for which k exceeds kmax *) {37, 67, 81, 83, 97, 101, 113, 131}; sturdyQ[n_ /; MemberQ[nn, n] || MatchQ[ FactorInteger[ n], {{2, }, {Alternatives @@ nn, 1}}]] = False; sturdyQ[n] := For[k = 2, True, k++, Which[ DigitCount[k*n, 2, 1] < DigitCount[n, 2, 1], Return[False], k > kmax, Return[True]]]; A125121 = Reap[ Do[ If[sturdyQ[n], Sow[n]], {n, 1, nmax}]][[2, 1]] (* Jean-François Alcover, Dec 28 2012 *)
nmax = 200; Bits[n_Integer] := Count[IntegerDigits[n, 2], 1]; FlimsyQ[ n_Integer] := FlimsyQ[n] = Module[{res, b = Bits[n], k}, If[b <= 2, False, If[EvenQ[n], FlimsyQ[n/2], res = Union[Mod[2^Range[n], n]]; If[ Length[res] == n - 1, True, k = 2; While[k < b && !MemberQ[ Union[ Mod[ Plus @@@ Subsets[res, {k}], n]], 0], k++]; k < b]]]]; Select[Range[nmax], !FlimsyQ[#]&] (* Jean-François Alcover, Feb 11 2016, Almost all this improved code is due to Tony D. Noe, updated Feb 26 2016 *)

Formula

Complement of A005360. - T. D. Noe, Jul 17 2008

2n + o(n) < a(n) < 4n^2, see Stolarsky link. - Charles R Greathouse IV, Aug 07 2015

Extensions

Corrected and extended by T. D. Noe, Jul 17 2008