View Single Post
Old 2020-07-29, 03:12   #13
Citrix's Avatar
Jun 2003

62C16 Posts

Originally Posted by preda View Post
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?

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.
I am not sure if I understand your question correctly.
From what I understand you are looking for X*N# where the number of '1' bits are very low.

Another way of phrasing this problem would be:
Find 2^x such that 2^x==y (mod N#) and y is small and negative
This becomes a discrete log problem
With N# consisting of all the small primes this can be further be divided for each prime under N. This can be computed extremely fast.
For a random number M similar method can be used assuming p-1 of each factor is smooth to some extent.

If you want to keep x small then we can try solving 2^x+2^z==y (mod N#) and so on...

You can adjust your search space based on your needs.

Edit- This is a way of finding the solution but the gains would not be significant for data compression as you are converting the complexity of the input N# into output complexity of x,z etc.

Last fiddled with by Citrix on 2020-07-29 at 03:23
Citrix is offline   Reply With Quote