20200725, 02:01  #1 
"Mihai Preda"
Apr 2015
2^{4}×83 Posts 
Lowpops primorial multiple
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 1bits 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 lowpops 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 lowpops multiple of it. 
20200725, 02:38  #2  
Feb 2017
Nowhere
37×103 Posts 
Quote:
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. Last fiddled with by Dr Sardonicus on 20200725 at 02:41 Reason: xingif posty (mistyped "binary" for "binomial") 

20200725, 02:48  #3  
Jun 2003
2^{2}×5×239 Posts 
Quote:
However there is informationtheoretic 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 Code:
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 N=product of first 10000 primes. size=150607 bits. weight=75304 Code:
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 Last fiddled with by axn on 20200725 at 02:56 Reason: improvement 

20200725, 02:55  #4 
"Mihai Preda"
Apr 2015
10100110000_{2} Posts 
In general, for a number M, there are lowpops multiples of it. (are there any numbers that are "resistant to popsreductionthroughmultiplication"?).
But what is an efficient way/algorithm of finding such a lowpops 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. 
20200725, 03:00  #5  
"Mihai Preda"
Apr 2015
2^{4}×83 Posts 
Quote:
About the informationtheoretic 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 bitsize of the multiple should be at least as large as the bitreduction that it achieves. So for a lot of reduction, the search space is huge (exponential in the number of bits of reduction). 

20200725, 04:17  #6  
Jun 2003
2^{2}·5·239 Posts 
Quote:
There is one interesting observation, though. We know how to make the lowest nbits 0 in a nontrivial manner. If you take lowest n bits, multiply it by its multiplicative inverse (mod 2^n), then you'll turn the lowest nbits 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. 

20200726, 12:58  #7 
Feb 2017
Nowhere
37·103 Posts 
One notion that crossed my mind: The number of nbit numbers M with b(M) = k binary ones is around binomial (n,k) [actually binomial(n1,k1) 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 lowpops multiples, but I am cheerfully ignoring this.) That is, D should be large enough that the number of lowpops "target" 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. Last fiddled with by Dr Sardonicus on 20200726 at 17:08 Reason: w 
20200728, 10:34  #8  
Romulan Interpreter
Jun 2011
Thailand
21344_{8} Posts 
Quote:
(edit: as well as all numbers with 2 bits set) Last fiddled with by LaurV on 20200728 at 11:01 

20200728, 11:23  #9 
"Mihai Preda"
Apr 2015
2^{4}·83 Posts 
Yes indeed. There are the categories of "sturdy numbers" and the opposite of "flimsy numbers". see e.g. https://oeis.org/A125121

20200728, 14:05  #10 
Feb 2017
Nowhere
7343_{8} Posts 
I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is odd, then p does not divide 2^{n} + 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. 
20200728, 16:49  #11  
"Jeppe"
Jan 2016
Denmark
2×3^{4} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primorial offsets  robert44444uk  Prime Gap Searches  7  20181129 08:40 
Primorial calculation  FreakyPotato  Programming  7  20150206 10:33 
Primorial puzzle  Citrix  Puzzles  3  20060307 15:07 
Primorial question  Dougy  Math  2  20050728 13:13 
Multiple systems/multiple CPUs. Best configuration?  BillW  Software  1  20030121 20:11 