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

%I #43 Feb 10 2020 06:16:03

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

%T 36,40,42,45,48,49,51,56,60,62,63,64,65,66,68,69,70,72,73,75,80,84,85,

%U 89,90,93,96,98,102,105,112,120,124,126,127,128,129,130,132,133,135,136

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

%C 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

%C 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.

%C Numbers of the form 2^m-1 (A000225) is a subsequence. - _David A. Corneth_, Oct 01 2016

%H T. D. Noe, <a href="/A125121/b125121.txt">Table of n, a(n) for n = 1..2475</a> (sturdy numbers <= 2^16)

%H 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 Tony D. Noe, <a href="http://integersequences.org/s000848.html">S000848 Odd sturdy numbers</a>, Integer Sequences.

%H K. B. Stolarsky, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa38/aa3825.pdf">Integers whose multiples have anomalous digital frequencies,</a> Acta Arithmetica, 38 (1980), 117-128.

%F Complement of A005360. - _T. D. Noe_, Jul 17 2008

%F 2n + o(n) < a(n) < 4n^2, see Stolarsky link. - _Charles R Greathouse IV_, Aug 07 2015

%t 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 *)

%t 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 *)

%Y See A143027 for prime sturdy numbers.

%K nonn,look,base

%O 1,2

%A _Jonathan Vos Post_, Jul 07 2008

%E Corrected and extended by _T. D. Noe_, Jul 17 2008