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)
[/CODE]

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! :)

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]

Using the multiplicative inverse of lower order n bits:
[CODE]10:720468
12:719859
242:719603
607:719455
1945:719364
1954:718901
5343:718576[/CODE]
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[/CODE]

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.

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}[/$$]
[LIST][*][$]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[/$].[/LIST]
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.

[QUOTE=kruoli;552531]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}[/$$]
[LIST][*][$]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[/$].[/LIST]
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.[/QUOTE]There appears to be a typo. Should the exceptional sum be taken from 0, not x?

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

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?

[QUOTE=xilman;552537]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?[/QUOTE]
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.

[QUOTE=xilman;552537]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?[/QUOTE]

This should follow a binomial distribution-I suspect. Though no proof as bits are not independent.

[QUOTE=preda;552502]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.[/QUOTE]

Minor improvements from brute force:
[CODE]27275863:717813
93899447:717739[/CODE]

[CODE]136110417:717547
173564051:717463[/CODE]