mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-07-25, 02:01   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5·239 Posts
Default Low-pops 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 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.
preda is online now   Reply With Quote
Old 2020-07-25, 02:38   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×5×173 Posts
Default

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

\log\prod_{p\le N}p \;\sim\; 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

\frac{N}{2\log(2)}\;\pm\;\sqrt{<br />
{N}}

(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 2020-07-25 at 02:41 Reason: xingif posty (mistyped "binary" for "binomial")
Dr Sardonicus is offline   Reply With Quote
Old 2020-07-25, 02:48   #3
axn
 
axn's Avatar
 
Jun 2003

13·192 Posts
Default

Quote:
Originally Posted by preda View Post
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
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
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
1.4% improvement.

Last fiddled with by axn on 2020-07-25 at 02:56 Reason: improvement
axn is online now   Reply With Quote
Old 2020-07-25, 02:55   #4
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

4AB16 Posts
Default

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 is online now   Reply With Quote
Old 2020-07-25, 03:00   #5
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5·239 Posts
Default

Quote:
Originally Posted by axn View Post
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).
preda is online now   Reply With Quote
Old 2020-07-25, 04:17   #6
axn
 
axn's Avatar
 
Jun 2003

10010010101012 Posts
Default

Quote:
Originally Posted by preda View Post
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.
axn is online now   Reply With Quote
Old 2020-07-26, 12:58   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1101100001002 Posts
Default

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.

Last fiddled with by Dr Sardonicus on 2020-07-26 at 17:08 Reason: w
Dr Sardonicus is offline   Reply With Quote
Old 2020-07-28, 10:34   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

210368 Posts
Default

Quote:
Originally Posted by preda View Post
(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)

Last fiddled with by LaurV on 2020-07-28 at 11:01
LaurV is offline   Reply With Quote
Old 2020-07-28, 11:23   #9
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

4AB16 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
preda is online now   Reply With Quote
Old 2020-07-28, 14:05   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

D8416 Posts
Default

I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is odd, then p does not divide 2n + 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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-07-28, 16:49   #11
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5×31 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
I note that, if p > 2 is prime, and the multiplicative order of 2 (mod p) is odd, then p does not divide 2n + 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
JeppeSN is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primorial offsets robert44444uk Prime Gap Searches 7 2018-11-29 08:40
Primorial calculation FreakyPotato Programming 7 2015-02-06 10:33
Primorial puzzle Citrix Puzzles 3 2006-03-07 15:07
Primorial question Dougy Math 2 2005-07-28 13:13
Multiple systems/multiple CPUs. Best configuration? BillW Software 1 2003-01-21 20:11

All times are UTC. The time now is 10:26.

Mon Sep 21 10:26:23 UTC 2020 up 11 days, 7:37, 0 users, load averages: 1.29, 1.60, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.