- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **Low-pops primorial multiple**
(*https://www.mersenneforum.org/showthread.php?t=25774*)

Low-pops primorial multipleHi, 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. |

[QUOTE=preda;551509]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#)[/QUOTE] 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, [tex]\log\prod_{p\le N}p \;\sim\; N[/tex] 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 [tex]\frac{N}{2\log(2)}\;\pm\;\sqrt{ {N}}[/tex] (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. |

[QUOTE=preda;551509]How much "gain" can I expect, and how to find a X multiplier that produces a good gain?[/QUOTE]
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 [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 [/code] Not bad - 5.3% improvement 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 [/CODE] 1.4% improvement. |

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. |

[QUOTE=axn;551514]
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. [/QUOTE] 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). |

[QUOTE=preda;551518]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).[/QUOTE] Agreed. I did add two qualifiers in my statement, "[B]small[/B] multiplier" and "minimise ... [B]significantly[/B]" 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. |

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" [strike]polynomial[/strike] integer products is about as large as the number of "n-bit, k ones" [strike]polynomials[/strike] 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. |

[QUOTE=preda;551515](are there any numbers that are "resistant to pops-reduction-through-multiplication"?).[/QUOTE]
Yes. Powers of 2. :razz: (edit: as well as all numbers with 2 bits set) |

[QUOTE=LaurV;551781]Yes. Powers of 2.
:razz:[/QUOTE] Yes indeed. There are the categories of "sturdy numbers" and the opposite of "flimsy numbers". see e.g. [url]https://oeis.org/A125121[/url] |

I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is [i]odd[/i], then p does not divide 2[sup]n[/sup] + 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. |

[QUOTE=Dr Sardonicus;551794]I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is [i]odd[/i], then p does not divide 2[sup]n[/sup] + 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.[/QUOTE] [URL="https://oeis.org/A091317"]https://oeis.org/A091317[/URL] says these primes have density 7/24. /JeppeSN |

All times are UTC. The time now is 03:26. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.