Number of set bits in multiple

[preda]

Originally Posted by R. Gerbicz

In the range [0,2^L) the number of bits of integers follow a normal distribution with L/2 mean and with c*sqrt(L) variance. So most of the numbers has number of bits in [L/2-c1*sqrt(L),L/2+c1*sqrt(L)] interval, if we suppose that the same is true for k*m then with large probability we can gain a reduction by sqrt(L) bits. (reaching with small say k<1024 in most of the cases).

I see. In my experiments I saw different empiric behavior: the number of "pops" (1-bits) in the small multiples of m has surprisingly little variation and sticks close to the middle.

For example, working with a number that has 1456417 bits and 727931 pops initially, trying all the multiples k*m with k up to 1M, the lowest number number of pops I saw was 725213.

m=7 is the first counter-example, because there is no x for that 2^x+1==0 mod 7.

Yes, thanks! My error was to believe that 2^k mod m spans all the values [1, m), and thus reaches 1. That's not true, as smaller cycles exist. In the case of 7,
2*6 % 7 = 5
2*5 % 7 = 3
2*3 % 7 = 6
So a small loop that does not reach 1.

[preda]

Originally Posted by CRGreathouse

All multiples of 1048575 have at least 20 bits set. See
http://matwbn.icm.edu.pl/ksiazki/aa/aa38/aa3825.pdf
http://list.seqfan.eu/pipermail/seqf...er/003267.html
A005360, A125121, A086342.

Thanks for pointing out these references! The existence of "sturdy numbers" seems to indicate that the behavior of "pops" under multiplication departs from a simple random model of 0/1 bits with equal & independent probability.

[kriesel]

Originally Posted by R. Gerbicz

In the range [0,2^L) the number of bits of integers follow a normal distribution with L/2 mean and with c*sqrt(L) variance. So most of the numbers has number of bits in [L/2-c1*sqrt(L),L/2+c1*sqrt(L)] interval, if we suppose that the same is true for k*m then with large probability we can gain a reduction by sqrt(L) bits. (reaching with small say k<1024 in most of the cases).

m=7 is the first counter-example, because there is no x for that 2^x+1==0 mod 7.

I assume you mean all integers in the range. Subsets apparently may behave differently. The set of known Mersenne exponents for example. At low values of L the average is noticeably above 0.5 because almost all of them are odd, and a few are 100% one bits. As I recall, it's already determined that within mersenne.org's range, we won't have another with 100% one bits.

[VBCurtis]

Originally Posted by kriesel

The set of known Mersenne exponents for example. At low values of L the average is noticeably above 0.5 because almost all of them are odd, and a few are 100% one bits. As I recall, it's already determined that within mersenne.org's range, we won't have another with 100% one bits.

Can you give an example of a number of mersenne form 2^n-1 that isn't 100% 'one' bits? I'm having a hard time understanding what you're saying, as I don't think that's possible.

[science_man_88]

Originally Posted by VBCurtis

Can you give an example of a number of mersenne form 2^n-1 that isn't 100% 'one' bits? I'm having a hard time understanding what you're saying, as I don't think that's possible.

keyword exponent, still false there's 4 .

[preda]

I have an idea for building low-pops multiples of a number "m".

Let's consider a "base" formed of elements of the form:
B(k) = 2^k + 1.

These elements have the property of having many factors and just 2 pops (of which one pop is always on the fixed position 0).

Factorize m. Starting with the largest factor, select a base element B(k) that covers that factor. Continue with the next largest factor of m that is not covered in the base elements already selected.

If all the factors of m can be covered with N bases B(k), we have a multiple with 2^N pops. Now, whether 2^N is "low" or not depends on how much success we have in covering all the factors of m with a small number N of bases.

There are some factors, e.g. 7, that are not covered by any B(k). i.e. there is no multiple of 7 of the form 2^k + 1. Maybe such bad factors could be separately multiplied-in at the end.

[preda]

Originally Posted by preda

I have an idea for building low-pops multiples of a number "m".

Sorry for the noise, it seems that idea is not useful, please ignore.

[kriesel]

Originally Posted by VBCurtis

Can you give an example of a number of mersenne form 2^n-1 that isn't 100% 'one' bits? I'm having a hard time understanding what you're saying, as I don't think that's possible.

No, pretty much by definition, unless n=0 which is 0%. (2^0-1=1-1=0) But I was writing (in http://www.mersenneforum.org/showpos...9&postcount=14) about the bit fraction in the cases of exponent n, actually prime exponent p, expressed in binary, for which 2^p-1 is also prime (not the bit fraction in the binary expression for 2^p-1, for which the ones bit fraction is always 100% in binary). The chart I showed was for the 50 known mersenne primes' exponents: 2, 3, ...77232917. https://www.mersenne.org/primes/
A simple small example: 2^2-1=3; in binary, 10^10 -1 = 100-1 = 11. The one bit fraction (reverting to decimal) of the exponent p=2 is 1/2.
Chart of 50 cases at http://www.mersenneforum.org/attachm...3&d=1535608786
Note, I'm open to suggestions of how my posts could be made clearer.

[science_man_88]

Originally Posted by kriesel

No, pretty much by definition, unless n=0 which is 0%. (2^0-1=1-1=0) But I was writing (in http://www.mersenneforum.org/showpos...9&postcount=14) about the bit fraction in the cases of exponent n, actually prime exponent p, expressed in binary, for which 2^p-1 is also prime (not the bit fraction in the binary expression for 2^p-1, for which the ones bit fraction is always 100% in binary). The chart I showed was for the 50 known mersenne primes' exponents: 2, 3, ...77232917. https://www.mersenne.org/primes/
A simple small example: 2^2-1=3; in binary, 10^10 -1 = 100-1 = 11. The one bit fraction (reverting to decimal) of the exponent p=2 is 1/2.
Chart of 50 cases at http://www.mersenneforum.org/attachm...3&d=1535608786
Note, I'm open to suggestions of how my posts could be made clearer.

10^10-1=9999999999 not 11

[kriesel]

Originally Posted by science_man_88

10^10-1=9999999999 not 11

I guess I don't get your sense of humor. I wrote

2^2-1=3; in binary, 10^10 -1 = 100-1 = 11.

In words, two squared minus one is four minus one is three; expressed twice. First is base 4 or above; second is everything in base two.

[GP2]

Originally Posted by kriesel

No, pretty much by definition, unless n=0 which is 0%. (2^0-1=1-1=0) But I was writing (in http://www.mersenneforum.org/showpos...9&postcount=14) about the bit fraction in the cases of exponent n, actually prime exponent p, expressed in binary, for which 2^p-1 is also prime (not the bit fraction in the binary expression for 2^p-1, for which the ones bit fraction is always 100% in binary). The chart I showed was for the 50 known mersenne primes' exponents: 2, 3, ...77232917. https://www.mersenne.org/primes/
A simple small example: 2^2-1=3; in binary, 10^10 -1 = 100-1 = 11. The one bit fraction (reverting to decimal) of the exponent p=2 is 1/2.
Chart of 50 cases at http://www.mersenneforum.org/attachm...3&d=1535608786
Note, I'm open to suggestions of how my posts could be made clearer.

You are talking about Mersenne primes for which the exponent is itself a Mersenne prime.

http://www.doublemersennes.org

2³−1 (where 3 = 2²−1)
2⁷−1 (where 7 = 2³−1)
2³¹−1 (where 31 = 2⁵−1)
2¹²⁷−1 (where 127 = 2⁷−1)