|
|
A125121
|
|
Sturdy numbers: n such that in binary notation k*n has at least as many 1-bits 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 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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
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 *)
|
|
CROSSREFS
|
See A143027 for prime sturdy numbers.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Corrected and extended by T. D. Noe, Jul 17 2008
|
|
STATUS
|
approved
|
|
|
|