Low-pops primorial multiple

[preda]

Hi, I have this little question:

given a bound N, taking the primorial N# (the product of all the primes up to N),

we count the number of 1-bits in the binary representation of N#: pops(N#)

I would expect the pops to be around 1/2 * log2(N#), coming from a roughly equal chances of bits being 0/1 in the binary representation of N#.

I would like to find a low-pops multiple of that primorial.

i.e.: find X such that pops(N# * X) is [a lot] smaller then pops(N#). Let's define the gain in bits: gain(X)=pops(N#) - pops(N# * X)

How much "gain" can I expect, and how to find a X multiplier that produces a good gain?

What if, additionally, I bound the magnitude of X, let's say by log2(X) <= 10 * log2(N#) -- does this restriction change anything?

My intuition says that this is a "hopeless" problem, meaning that it's extremely hard to find an X that produces a gain of some significant ratio of log2(N#), e.g. a gain of 1/4*log2(N#).

Is there some mathematical argument in this area?
thanks!

PS: maybe the problem can be generalized to any number M (not only a primorial), becoming: given a number M, find a low-pops multiple of it.

[Dr Sardonicus]

Originally Posted by preda

Hi, I have this little question:

given a bound N, taking the primorial N# (the product of all the primes up to N),

we count the number of 1-bits in the binary representation of N#: pops(N#)

IIRC, for a positive integer n, b(n) is the standard notation for the number of 1's in the binary representation of n.

The PNT tells us that, for large N,



so that N# has about N/ln(2) binary digits.

I have no idea of how many binary 1's there might be in N#, but my default assumption would be "about half," so somewhere in the vicinity of (1/2)*N/ln(2) binary ones. "Somewhere in the vicinity" might be



(based on my hazy recollection of how fast binomial coefficients fall off from the middle based on Stirling's formula), but I'm too lazy to plow through the details.

[axn]

Originally Posted by preda

How much "gain" can I expect, and how to find a X multiplier that produces a good gain?

In my past trial/error of similar problems, the improvement was roughly O(log(#trial)*log(N)) bits. But it was bruteforce(running multipliers in sequence)/random methods. Maybe there is a better way to select multipliers.

However there is information-theoretic arguments why this can't be done in general case. If you're able to consistently find a small multiplier for an arbitrary number which minimises the number of lit bits significantly, then you've found a way to compress arbitrary number.

In short, try a bunch of small multipliers. If you're lucky, you will find a 1% improvement (if that).

Quick trial:
N=product of first 1000 primes. size=11271 bits. weight=5636

3:5608
9:5582
15:5521
89:5513
615:5485
1173:5483
2325:5465
4101:5459
15279:5453
20559:5448
21407:5425
182427:5421
226781:5417
289701:5410
352725:5404
2930227:5384
5664635:5351
13604855:5342

Not bad - 5.3% improvement

N=product of first 10000 primes. size=150607 bits. weight=75304

3:75131
25:75104
31:75038
37:74934
99:74918
337:74843
525:74686
8315:74621
9217:74576
19985:74547
49647:74543
270771:74500
555053:74496
574089:74475
653371:74468
714991:74394
1114041:74345
6446013:74281
43024819:74278

1.4% improvement.

[preda]

In general, for a number M, there are low-pops multiples of it. (are there any numbers that are "resistant to pops-reduction-through-multiplication"?).

But what is an efficient way/algorithm of finding such a low-pops multiples. The brute force approach consisting in "try multiples one by one" is not practical as it requires a time exponential in the number of bits of M.

[preda]

Originally Posted by axn

However there is information-theoretic arguments why this can't be done in general case. If you're able to consistently find a small multiplier for an arbitrary number which minimises the number of lit bits significantly, then you've found a way to compress arbitrary number.

First, thanks for the quick experiments!

About the information-theoretic argument above, I disagree, because in order to compress you also need to transmit information about which multiple it is, which may take a lot of bits to encode.

But I think that your argument does show that the bit-size of the multiple should be at least as large as the bit-reduction that it achieves. So for a lot of reduction, the search space is huge (exponential in the number of bits of reduction).

[axn]

Originally Posted by preda

About the information-theoretic argument above, I disagree, because in order to compress you also need to transmit information about which multiple it is, which may take a lot of bits to encode.

But I think that your argument does show that the bit-size of the multiple should be at least as large as the bit-reduction that it achieves. So for a lot of reduction, the search space is huge (exponential in the number of bits of reduction).

Agreed. I did add two qualifiers in my statement, "small multiplier" and "minimise ... significantly" for that reason.

There is one interesting observation, though. We know how to make the lowest n-bits 0 in a non-trivial manner. If you take lowest n bits, multiply it by its multiplicative inverse (mod 2^n), then you'll turn the lowest n-bits into 0000...01 pattern. There is no search involved here for the multiplier, but you still need to test with different n's to see if it will do something useful with the rest of the number. And the search space is small, so not much latitude there.

[Dr Sardonicus]

One notion that crossed my mind: The number of n-bit numbers M with b(M) = k binary ones is around binomial (n,k) [actually binomial(n-1,k-1) since the first bit is always 1].

If you want to reliably (say) cut the number of binary 1's in half by multiplication, the number of digits D in the product should be such that binomial(D,k/2) is about as large as binomial(n,k). (I know, there might be some overlap among the low-pops multiples, but I am cheerfully ignoring this.)

That is, D should be large enough that the number of low-pops "target" polynomial integer products is about as large as the number of "n-bit, k ones" polynomials integers you start with. The multipliers would then be about D-n bits long.

Using Stirling's asymptotic formulas for log Gamma, it might be possible to say something useful about D under given assumptions about n and k. Alas, I'm too lazy to work out the details.

[LaurV]

Originally Posted by preda

(are there any numbers that are "resistant to pops-reduction-through-multiplication"?).

Yes. Powers of 2.

(edit: as well as all numbers with 2 bits set)

[preda]

Originally Posted by LaurV

Yes. Powers of 2.

Yes indeed. There are the categories of "sturdy numbers" and the opposite of "flimsy numbers". see e.g. https://oeis.org/A125121

[Dr Sardonicus]

I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is odd, then p does not divide 2ⁿ + 1 for any positive integer n, so p does not divide any positive integer with two binary ones.

All primes p congruent to 7 (mod 8) satisfy this condition. Some primes congruent to 1 (mod 8) (e.g. p = 73) also satisfy the condition, while others (e.g. p = 17) do not.

[JeppeSN]

Originally Posted by Dr Sardonicus

I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is odd, then p does not divide 2ⁿ + 1 for any positive integer n, so p does not divide any positive integer with two binary ones.

All primes p congruent to 7 (mod 8) satisfy this condition. Some primes congruent to 1 (mod 8) (e.g. p = 73) also satisfy the condition, while others (e.g. p = 17) do not.

https://oeis.org/A091317 says these primes have density 7/24. /JeppeSN