 mersenneforum.org Is this a puzzle?
 Register FAQ Search Today's Posts Mark Forums Read  2020-08-03, 10:26 #1 preda   "Mihai Preda" Apr 2015 55F16 Posts Is this a puzzle? Consider the number PowerSmooth(1000000) with the 2 factors removed; e.g. in pari-gp: Code: PowerSmooth(B1)= result=1; forprime(p=3, B1, result *= p^floor(log(B1)/log(p))); return(result) PowerSmooth(1000000) This number, in binary, has 720737 bits set to 1 ("binary hamming weight", hammingweight() in pari-gp). The puzzle is: find a multiple of this number that has a Hamming Weight <= 710000. (or, How low a HW multiple can you find?) Thanks! :) Last fiddled with by preda on 2020-08-03 at 10:26   2020-08-03, 13:24 #2 axn   Jun 2003 5,197 Posts Iterating thru all odd numbers, starting from 3, Code: 3:720673 9:720566 21:720169 59:720143 89:719926 127:719857 237:719477 261:719250 817:719025 6923:718588 229095:718410 276755:718351 322621:718138 Using the multiplicative inverse of lower order n bits: Code: 10:720468 12:719859 242:719603 607:719455 1945:719364 1954:718901 5343:718576 Here 5343 means the multiplier is Mod( N, 2^5343)^-1 Using random odd numbers < 2^64 Code: 10719928016004921607:720163 9421399378650073937:719987 9838800997419312683:719646 9031419907504264227:719565 12801182192819992405:719465 11276055256514179587:719415 7687617259492261083:719397 3594335502178041641:719255 6046992651811463807:718858 12624414163832553385:718786 4750919058227643243:718688 18130704136173611049:718654 5224850625010740453:718528 1147537420811012579:718472 7233411429689023907:718469 1993933662070155813:718441 6862363197769235605:718113   2020-08-04, 01:00 #3 preda   "Mihai Preda" Apr 2015 25378 Posts I broke through 718K: multiplying with 1999099*3684553 produces HW=717965 still a long way to go to 710K.. it looks like the "brute force search" is not working very well.   2020-08-04, 14:11 #4 kruoli   "Oliver" Sep 2017 Porta Westfalica, DE 28·3 Posts Brute force probability analysis. Hitting < 718K should have a probability around 1 in 2e7, so still achievable by brute force, hitting < 710K is much less likely with 1 in 8e76. Formula used (please correct me if my approach is not applicable): $p = \frac{\sum_{k=0}^{x}{\binom{\lceil log2(n) \rceil}{k}}}{n}$ $$p$$ is the probability. $$n$$ in the number we want to "depopulize". $$x$$ is the target popcount. If our target popcount would be greater than $$\lceil log2(n) \rceil$$, take the sum from $$x$$ to $$\lceil log2(n) \rceil$$. Since we are multiplying $$n$$ with another value to "depopulize" it, the final result number is getting larger. This is not displayed by this formula, but should not make a huge difference, since our value for multiplication is really small in comparison. Last fiddled with by kruoli on 2020-08-04 at 14:14 Reason: Minor clarifications.   2020-08-04, 14:15   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

41·269 Posts Quote:
 Originally Posted by kruoli Hitting < 718K should have a probability around 1 in 2e7, so still achievable by brute force, hitting < 710K is much less likely with 1 in 8e76. Formula used (please correct me if my approach is not applicable): $p = \frac{\sum_{k=0}^{x}{\binom{\lceil log2(n) \rceil}{k}}}{n}$ $$p$$ is the probability. $$n$$ in the number we want to "depopulize". $$x$$ is the target popcount. If our target popcount would be greater than $$\lceil log2(n) \rceil$$, take the sum from $$x$$ to $$\lceil log2(n) \rceil$$. Since we are multiplying $$n$$ with another value to "depopulize" it, the final result number is getting larger. This is not displayed by this formula, but should not make a huge difference, since our value for multiplication is really small in comparison.
There appears to be a typo. Should the exceptional sum be taken from 0, not x?   2020-08-04, 14:19 #6 kruoli   "Oliver" Sep 2017 Porta Westfalica, DE 28×3 Posts Do you mean my third bullet point? In that case the sum really should still go from $$x$$ to $$\lceil log2(n) \rceil$$. But maybe I'm missing something here.    2020-08-04, 14:43 #7 xilman Bamboozled!   "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 41·269 Posts Another possibly interesting question: the quantity hammingweight(PowerSmooth(N))/N appears to converge to a value close to 0.72 ---can one prove that it converges and can one find a relatively simple expression for its value?   2020-08-04, 15:07   #8
uau

Jan 2017

112 Posts Quote:
 Originally Posted by xilman Another possibly interesting question: the quantity hammingweight(PowerSmooth(N))/N appears to converge to a value close to 0.72 ---can one prove that it converges and can one find a relatively simple expression for its value?
I assume that half the bits are ones, so that's about equivalent to length of the number x being 1.44N bits, or log(x) = 1.44N*log(2) = N. The prime number theorem says the sum of log(p) for primes p less than L is about L. The PowerSmooth function multiplies the largest power of the prime less than L instead of just the prime itself, but that shouldn't make too much difference.

So the 0.72 value is probably 1/log(2)/2, where the 1/log(2) comes from the size of the product as predicted by the prime number theorem, and an additional /2 for only half the bits being ones.   2020-08-05, 03:57   #9
Citrix

Jun 2003

5·317 Posts Quote:
 Originally Posted by xilman Another possibly interesting question: the quantity hammingweight(PowerSmooth(N))/N appears to converge to a value close to 0.72 ---can one prove that it converges and can one find a relatively simple expression for its value?
This should follow a binomial distribution-I suspect. Though no proof as bits are not independent.   2020-08-05, 08:14   #10
axn

Jun 2003

519710 Posts Quote:
 Originally Posted by preda I broke through 718K: multiplying with 1999099*3684553 produces HW=717965 still a long way to go to 710K.. it looks like the "brute force search" is not working very well.
Minor improvements from brute force:
Code:
27275863:717813
93899447:717739   2020-08-05, 09:39 #11 axn   Jun 2003 5,197 Posts Code: 136110417:717547 173564051:717463 Last fiddled with by axn on 2020-08-05 at 10:38 Reason: Another improvement   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Harrywill Puzzles 4 2017-05-03 05:10 Uncwilly Puzzles 75 2012-06-12 13:42 bcp19 Puzzles 18 2012-03-02 04:11 nibble4bits Puzzles 37 2006-02-27 09:35 Orgasmic Troll Puzzles 6 2005-12-08 07:19

All times are UTC. The time now is 18:18.

Sun Dec 5 18:18:59 UTC 2021 up 135 days, 12:47, 1 user, load averages: 1.41, 1.52, 1.59