Thread: Low-pops primorial multiple View Single Post
2020-07-29, 03:12   #13
Citrix

Jun 2003

62C16 Posts

Quote:
 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#) 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.
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...