20200803, 10:26  #1 
"Mihai Preda"
Apr 2015
3·421 Posts 
Is this a puzzle?
Consider the number PowerSmooth(1000000) with the 2 factors removed; e.g. in parigp:
Code:
PowerSmooth(B1)= result=1; forprime(p=3, B1, result *= p^floor(log(B1)/log(p))); return(result) PowerSmooth(1000000) 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 20200803 at 10:26 
20200803, 13:24  #2 
Jun 2003
2^{2}·11·107 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 Code:
10:720468 12:719859 242:719603 607:719455 1945:719364 1954:718901 5343:718576 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 
20200804, 01:00  #3 
"Mihai Preda"
Apr 2015
3·421 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. 
20200804, 14:11  #4 
"Oliver"
Sep 2017
Porta Westfalica, DE
3×109 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}\]
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 20200804 at 14:14 Reason: Minor clarifications. 
20200804, 14:15  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·3,371 Posts 
Quote:


20200804, 14:19  #6 
"Oliver"
Sep 2017
Porta Westfalica, DE
101000111_{2} 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.

20200804, 14:43  #7 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2781_{16} 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?

20200804, 15:07  #8  
Jan 2017
79 Posts 
Quote:
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. 

20200805, 03:57  #9 
Jun 2003
2×787 Posts 
This should follow a binomial distributionI suspect. Though no proof as bits are not independent.

20200805, 08:14  #10 
Jun 2003
1001001100100_{2} Posts 

20200805, 09:39  #11 
Jun 2003
2^{2}·11·107 Posts 
Code:
136110417:717547 173564051:717463 Last fiddled with by axn on 20200805 at 10:38 Reason: Another improvement 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some puzzle  Harrywill  Puzzles  4  20170503 05:10 
Four 1's puzzle  Uncwilly  Puzzles  75  20120612 13:42 
a puzzle  bcp19  Puzzles  18  20120302 04:11 
Dot puzzle  nibble4bits  Puzzles  37  20060227 09:35 
now HERE'S a puzzle.  Orgasmic Troll  Puzzles  6  20051208 07:19 