20200728, 17:32  #12  
"Robert Gerbicz"
Oct 2005
Hungary
2·727 Posts 
Quote:
binomial(10*L,L/4)>39^(L/4)=n^(log(39)/log(2)/4)=n^1.321 >> n 

20200729, 03:12  #13  
Jun 2003
62B_{16} Posts 
Quote:
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 p1 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 20200729 at 03:23 

20200729, 08:11  #14  
"Mihai Preda"
Apr 2015
1353_{10} Posts 
Quote:
How would solving the discrete log look like for: 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 == 111546435 or for: 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 27 == 3011753745 ? Let's say we want a multiple of the above of at most 300bits. Last fiddled with by preda on 20200729 at 08:13 

20200729, 18:42  #15  
"Jeppe"
Jan 2016
Denmark
2·83 Posts 
Quote:
Explicitly, that gives: Code:
3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 4670911135951830670908061342184620067675149710598085670529534071346666252078598007938153523409455974649558521668598946844822022384564386566865625495001516198504091914585194088996678565204189348577008651064806108190563645021005204603353866364622193433252633722340556755457655750039477777274990095817430693664225941478819333671787921122513794582665601788086785126662337904429323871544633703900505738061594109307716230092050162038126416108850876405244067015457154781594023741537224801608620265570120822777232090945257144958639048695692047122601957815224067108345517730425197829379478203006053099508383633795947639082623658496688308850945331899791490765912750669828993402821730858997864528028008874066832321235869648230683555567133525501757545124333133107788648153431123654740287301004622981403404043970380640605440916007872963437737182088045547772461110047503451238999919539215 But it is not an improvement, for hammingweight(3 * 5 * 7 * 11 * 13 * 17 * 19 * 23) is only 10. And surely my example exceed 300 bits by far! I could be doing everything wrong. /JeppeSN Last fiddled with by JeppeSN on 20200729 at 18:45 Reason: had to put long factor in CODE tags 

20200729, 19:06  #16 
"Jeppe"
Jan 2016
Denmark
2·83 Posts 
An improvement (i.e. lower hammingweight) I can get with that method, is the multiple 2^2513+1098793. It has pops 8. It is a multiple of 23# / 2. /JeppeSN

20200730, 02:02  #17 
"Mihai Preda"
Apr 2015
1353_{10} Posts 
A simple information theoretic argument, based on entropy, suggests that (almost all) numbers of N bits have a multiple of 2xN bits with a N/10 binary hamming weight (HW).
(below, log() is in base 2). It goes like this: if the probability of a bit of being 1 is "p" (and of being 0 is q=1p), then the information of such a bit is: p*log(1/p) +q*log(1/q). (Thus the information content of a Nbits number with p=1/2 is N bits). The information content of a number with "loaded" bits (i.e. p != 1/2) is lower perbit, thus the total number of bits must be increased to compensate. It turns out that when p=1/10, the number of bits needs to be roughly doubled (because 1/10*log(10)+9/10*log(10/9)==0.469 ~= 0.5). So overall, a 5x reduction of the HW is achieved through a doubling of the bitlength. This argument holds for arbitrary numbers Nbits in length. OTOH primorials are not arbitrary numbers at all. In fact, the information content of a primorial of Nbits in length is not N bits but log(N) bits, thus much much lower. (this can be seen like this: if I want to transmit you a primorial Q#, it's enough to transmit just the value Q, which is O(log(Q#)) in size. Because of this "low information content" of primorials, it is not excluded that they might have muchlower HW multiples then expected from the above informationtheoretic argument. (but not implied either). Last fiddled with by preda on 20200730 at 02:21 
20200730, 03:22  #18  
Jun 2003
11000101011_{2} Posts 
Quote:
You need to take LCM of p1 of all the prime factors p1,p2, in p# LCM=3960 Then you take 2^1...2^3960 (mod N#) find the number with least number of '1' and that is your solution. For limiting it under 300 bits: You calculate 2^1 (mod N#), 2^2 (mod N#)...., 2^300 (mod N#) Then for each value of y You have a set of 301 values Then you want to find a subset from the 301 values such that sum of these numbers and y=0 (mod N#) This is called the modular subset sum problem. Search on google ... there are some fast algorithms for this. You would need to modify these algorithms so the best solution is found first. If your number is extremely smooth you could possibly make your algorithm faster by solving for each factor separately and putting it together. 

20200730, 08:35  #19  
"Jeppe"
Jan 2016
Denmark
2·83 Posts 
Quote:
When you try to find the member from 2^1, 2^2, 2^3, ..., 2^7920 (mod 23#) with the least hammingweight, then nothing beats the first few terms in that list; they clearly have only one '1' bit? /JeppeSN 

20200730, 12:01  #20  
Jun 2003
1,579 Posts 
Quote:
2. 2^1, 2^2, 2^3, ..., 2^7920 (mod 23#)  only consider terms greater than 23# otherwise the number is 23# itself. Let m==2^n (mod 23#) You need to find the number of '1' bits in 2^n+23#m 

20200803, 08:42  #21 
"Mihai Preda"
Apr 2015
3×11×41 Posts 
The Why
I'm going to give away the backstory for my question about lowhammingweight multiples.
"It's all for P1" You may know, GpuOwl can do both PRP and P1. PRP has the advantage of being protected with the famous "G" error check (AKA "GEC"). P1 (as implemented) OTOH is "naked", with no error check. But there's a better way! P1 (first stage) can be run together with PRP, for better efficiency and a partial error check. P1 first stage works like this: 1. compute the exponent E=PowerSmooth(B1), 2. compute X=3^PowerSmooth(B1) (mod M) 3. do GCD(X1, M) (where PowerSmooth(B) computes the product of all primes raised to a maximal power such that they're under B, i.e. product(over p prime with p < B, of p^floor(log(B)/log(p)))). in parigp: Code:
powersmooth(b)= pr=1;forprime(p=2,b,pr*=p^floor(log(b)/log(p)));pr Code:
X=3^PowerSmooth(B1) LtoR: MSB to LSB RtoL: LSB to MSB The fastest is LtoR binary exponentiation, as it requires only squaring and multiplicationby3, which (being mul by a small constant) is free. So the cost for 3^PS(B1) is N squarings, where N is the number of bits of PS(B1). The RtoL binary exponentiation requires N squarings plus HammingWeight(PS(B1)) multiplications, so seems like a worse choice. BUT the squarings needed in the RtoL exponentiation are exactly the same squarings that take place in the initial part of the PRP test! If we assume one does P1 followed by PRP, the squarings are "free" in the P1 (i.e. counted towards the PRP), and in addition the squarings are protected by the GEC. So the cost of the RtoL exponentiation is HW(PS(B1)), i.e. the number of pops of the PowerSmooth(B1), which is about 1/2 of the bitlen of PS(B1), and this is significantly cheaper than the cost of LtoR exponentiation. The drawback is that the P1 must be followed by PRP in order to reap the cost benefit. At this point it should be clear why the quest for a lowhammingweight multiple. Instead of PS(B1) we can use just as well any multiple of it, without even needing to know which multiple it is. A reduction in the HW results in a proportional reduction in the cost of P1 (first stage). Unfortunately I could find no practical way at all for reducing the HW of the PS(B1). Let's enumerate the approaches tried: 1. lowHW multiple of a small number. (let's say "small number" being up to 32bits or maybe even 64bits, and lowHW being <7 bits) The key here is to think of the contribution of each bit that is set modulo the "base", and target a combination of bits that sum to 0 (mod "base"), i.e. represent a multiple of the base. And the problem has similarities to subsetsum. This can be solved using either dynamic programming, or a "brute search" that takes advantage of the extremelylow HW that is targeted (HW < 7). (not all the small numbers have a verylow HW multiple) The problem with this approach is that it works for small numbers only. The solution can't be extended to the huge numbers needed for PS(B1): While PS(B1) can easily be split into a product of (many) 32bit factors, the lowHW solutions for those factors can't be assembled back into a lowHW solution to PS(B1). (below, PS is without the powers of "2"): 2. For B1=1M, bitlen(PS(1M))==1442080. So we have a number of about 1.4M bits. The starting HW is: HW(PS(1M))==720737. I tried various approaches to search among the multiples of PS(1M), and the lowest HW I found was around 718K, let's say a HW reduction of about 0.4%! Impressivelly unremarkable. Feel free to try yourself, doing such experiments is not too difficult in parigp. So for some reason, the search for lowHW multiples of PS(1M) is much harder than it might seem. At this point I think an approch that might work a bit better would be to look at the base number as a pattern of bits, that can be shifted and added back (this is what multiplication does). This shiftandadd can both create and destroy 1bits. Maybe an algorithm could be constructed there. Anyway in the meantime I consider the problem "impossible" myself. But if somebody comes up with a multiple of PS(1M) that is.. let's say 1% improvement (HW<714K), I'd be impressed! Code:
ps(b)=pr=1;forprime(p=3,b,pr*=p^floor(log(b)/log(p)));pr hw(x)=hammingweight(x) base=ps(1000000) hw(base) Last fiddled with by preda on 20200803 at 08:46 
20200805, 03:16  #22 
Jun 2003
1,579 Posts 
Your idea seems interesting!
If we could find a N with low hammer weight then we can use it for testing all p1 candidates again and again so this would be useful. We could use dynamic programming to solve this once as it would be used again and again. Some questions/comments/suggestions 1) Why do we have to use all the primes in B1. A smaller subset set of primes in B1 might have an lower hammer weight N. We then take this smaller subset and the remaining B1 primes (or move them to the B2 stage). Have you tried this? 2) We do not care about the size of the lower hammer weight N just that it must be less than 50% the size of the exponent of the candidate being tested (to make this useful). Correct? 3) To assess the feasibility of this : For a small prime p taking all the multiple of p and that are odd between 1 and 2^(p1)1. We then count the frequency of various hammer weight. Is the distribution the same for various values of p. What about composites. Is this random  I suspect not? binomial distribution. We then can predict/calculate how deep we would need to search to find a low hammer weight solution for B1=1M and at what exponent level this method will become practical. Let me know what you find. I do not have PARI to test this myself. Last fiddled with by Citrix on 20200805 at 03:18 Reason: typo, grammar 
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 