A143027 -id:A143027 - cp's OEIS frontend

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

Jonathan Vos Post, Jul 07 2008

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

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.

See A143027 for prime sturdy numbers.

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

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

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

A278966 Least Hamming weight of multiples of the n-th prime.

Original entry on oeis.org

1, 2, 2, 3, 2, 2, 2, 2, 3, 2, 5, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 2, 4, 2, 2, 3, 2, 2, 2, 7, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 2, 2, 3, 2, 4, 2, 2, 4, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 4, 2, 3, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 2, 2, 2, 2

Offset: 1

Charles R Greathouse IV, Dec 02 2016

nonn

Since all primes after the first are odd, a(n) > 1 for n > 1.
a(n) = 2 if and only if A014664(n) is even, or equivalently prime(n) is not in A014663. - Robert Israel, Dec 08 2016
If prime(n) = A000668(k), then a(n) = A000043(k). - Robert Israel, Dec 20 2016

Robert Israel, Table of n, a(n) for n = 1..1000

Cf. A014663, A014664, A278967, A278968, A086342.

f:= proc(n) local p, R, V, W, k,v,r;
    p:= ithprime(n);
    R:= {seq(2 &^ i mod p, i=0..numtheory:-order(2,p)-1)};
    Rm:= map(t -> p-t, R);
    V:= R;
    W:= V;
    for k from 2 do
      if nops(V intersect Rm) > 0 then return k fi;
      V:= {seq(seq(v+r mod p, v=V),r=R)} minus W;
    W:= W union V;
    od
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Dec 20 2016

a[n_] := Module[{p, R, V, W, k, v, r}, p = Prime[n]; R = Union @ Table[ PowerMod[2, i, p], {i, 0, MultiplicativeOrder[2, p]-1}]; Rm = p - R; V = R; W = V; For[k = 2, True, k++, If[Length[V ~Intersection~ Rm] > 0, Return[k]]; V = Union@ Flatten@ Table[Table[v + Mod[r, p], {v, V}], {r, R}] ~Complement~ W; {W, W ~Union~ V}]];
a[1] = 1;
Array[a, 100] (* Jean-François Alcover, Jun 08 2020, after Robert Israel *)

a(n,p=prime(n))=my(o=znorder(Mod(2,p)), v1=Set(powers(Mod(2,p),o)), v=v1, s=1); while(!setsearch(v,Mod(0,p)), v=setbinop((x,y)->x+y,v,v1); s++); s

a(n) = A000120(A278967(n)). In particular, a(n) = A000120(prime(n)) whenever prime(n) is in A143027. - Max Alekseyev, May 22 2025

A140797 Numbers of the form (2^p^N-1)/(2^p^(N-1)-1), where N>0, p is prime.

Original entry on oeis.org

3, 5, 7, 17, 31, 73, 127, 257, 2047, 8191, 65537, 131071, 262657, 524287, 1082401, 8388607, 536870911, 2147483647, 4294967297, 137438953471, 2199023255551, 4432676798593, 8796093022207, 140737488355327, 9007199254740991, 18014398643699713, 576460752303423487

Offset: 1

Vladimir Shevelev, Jul 15 2008

nonn

Contains Fermat numbers A000215 (p=2) and Mersenne numbers A001348 (N=1). The terms of the sequence are either primes A000040 or overpseudoprimes A141232.

The values of A019320(n) for prime power n, sorted. This sequence is a subsequence of A064896, which means that all terms are sturdy numbers (A125121). It appears that the largest prime factor of each of these numbers is a sturdy prime (A143027). - T. D. Noe, Jul 21 2008

T. D. Noe, Table of n, a(n) for n=1..199
Vladimir Shevelev, Process of "primoverization" of numbers of the form a^n-1, arXiv:0807.2332 [math.NT], 2008.

Cf. A000040, A000215, A001348, A141232.

nmax[p_] := Which[p == 2, 6, p == 3, 4, True, 2];
Reap[Do[If[IntegerQ[k = (2^p^n-1)/(2^p^(n-1)-1)] && k<10^18, Print[{p, n, k}]; Sow[k]], {p, Prime[Range[17]]}, {n, 1, nmax[p]}]][[2, 1]] // Union (* Jean-François Alcover, Dec 10 2018 *)

Definition corrected by and more terms from T. D. Noe, Jul 21 2008

A181863 Decimal sturdy primes: primes p such that sum of digits of k*p for any positive integer k is at least the sum of digits of p.

Original entry on oeis.org

3, 11, 41, 101

Offset: 1

Max Alekseyev, Nov 14 2010

Prime elements of A181862.
Primes p such that A007953(p) = A077196(p).
Contains prime repunits A004022 as a subsequence.
a(5) > 1.4*10^7. - Giovanni Resta, Sep 18 2018
From Jason Yuen, Mar 25 2024: (Start)
For all x>log_10(p), 1+A007953(p-(10^x mod p)) >= A007953(p). This follows from the fact that 10^x+p-(10^x mod p) is a multiple of p.
a(5) > 2*10^11. See a181863_2e11.txt for more details. (End)

Trevor Clokie, Thomas F. Lidbetter, Antonio Molina Lovett, Jeffrey Shallit, and Leon Witzman, Computational Aspects of Sturdy and Flimsy Numbers, Theoretical Computer Science, Vol. 927 (2022), pp. 65-86; arXiv preprint, arXiv:2002.02731 [cs.DS], 2020.
Jason Yuen, a181863_2e11.txt. This file shows that a(5) > 2*10^11.

Cf. A004022, A007953, A077196, A143027, A181862.

A278967 a(n) = least multiple of the n-th prime that has the minimum Hamming weight (=A278966(n)).

Original entry on oeis.org

2, 3, 5, 7, 33, 65, 17, 513, 69, 16385, 31, 262145, 1025, 129, 517, 67108865, 536870913, 1073741825, 8589934593, 8449, 73, 1027, 2199023255553, 89, 16777217, 1125899906842625, 515, 9007199254740993, 262145, 16385, 127, 36893488147419103233, 17179869185, 590295810358705651713, 18889465931478580854785

Offset: 1

Charles R Greathouse IV, Dec 02 2016

nonn

Apart from the first term, all terms are odd.

			2 = 2^1 has Hamming weight 1 and so a(1) = 2.
3 = 2^1 + 2^0 has Hamming weight 2, and any multiple of 3 has a Hamming weight at least as high, so a(2) = 3.
5 = 2^2 + 2^0 has Hamming weight 2 and so similarly a(3) = 5.
7 = 2^2 + 2^1 + 2^0 has Hamming weight 3, and all powers of 2 are 1, 2, or 4 mod 7, and so all multiples of 7 have Hamming weight at least 3, so a(4) = 7.
11 = 2^3 + 2^1 + 2^0 has Hamming weight 3 but 33 = 2^5 + 2^0 has Hamming weight 2 so a(5) = 33.

Contains A143027 as subsequence.

Cf. A278966, A278968, A086342.

min1s(p)=my(o=znorder(Mod(2,p)), v1=Set(powers(Mod(2,p),o)), v=v1, s=1); while(!setsearch(v,Mod(0,p)), v=setbinop((x,y)->x+y,v,v1); s++); s
a(n,p=prime(n))=my(m=min1s(p),t=p,k=2*p); while(hammingweight(t)>m, t+=k); t

a(n) = 2^(A014664(n)/2) + 1 whenever A014664(n) is even. Also, a(n) = prime(n) whenever prime(n) is in A143027. - Max Alekseyev, May 22 2025

a(23)-a(25) from Charles R Greathouse IV, Dec 09 2016

Name clarified and terms a(26) onward added by Max Alekseyev, May 22 2025

A330696 Flimsy primes.

Original entry on oeis.org

11, 13, 19, 23, 29, 37, 41, 43, 47, 53, 59, 61, 67, 71, 79, 83, 97, 101, 103, 107, 109, 113, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313

Offset: 1

Jeffrey Shallit, Dec 26 2019

A number n is flimsy if there exists an integer k such that A000120(kn) < A000120(n).

Trevor Clokie et al., Computational Aspects of Sturdy and Flimsy Numbers, arxiv preprint arXiv:2002.02731 [cs.DS], February 7 2020.
Kenneth B. Stolarsky, Integers whose multiples have anomalous digital frequencies, Acta Arithmetica 38 (2) (1980), 117-128.

Cf. A000120. This sequence is the complementary sequence (with respect to the primes) of A143027.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A278966 Least Hamming weight of multiples of the n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A140797 Numbers of the form (2^p^N-1)/(2^p^(N-1)-1), where N>0, p is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A181863 Decimal sturdy primes: primes p such that sum of digits of k*p for any positive integer k is at least the sum of digits of p.

Views

Author

Keywords

Comments

Links

Crossrefs

A278967 a(n) = least multiple of the n-th prime that has the minimum Hamming weight (=A278966(n)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A330696 Flimsy primes.

Views

Author

Keywords

Comments

Links

Crossrefs