

A125121


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


11



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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 email 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^m1 (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), 117128.


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


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]] (* JeanFranç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[#]&] (* JeanFrançois Alcover, Feb 11 2016, Almost all this improved code is due to Tony D. Noe, updated Feb 26 2016 *)


CROSSREFS

See A143027 for prime sturdy numbers.
Sequence in context: A164707 A057890 A161604 * A333762 A295235 A136490
Adjacent sequences: A125118 A125119 A125120 * A125122 A125123 A125124


KEYWORD

nonn,look,base


AUTHOR

Jonathan Vos Post, Jul 07 2008


EXTENSIONS

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


STATUS

approved



