Is this a puzzle?

[preda]

Consider the number PowerSmooth(1000000) with the 2 factors removed; e.g. in pari-gp:

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

[axn]

Iterating thru all odd numbers, starting from 3,

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:

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

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

[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.

[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.

[xilman]

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?

[kruoli]

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.

[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?

[uau]

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.

[Citrix]

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.

[axn]

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:

27275863:717813
93899447:717739

[axn]

136110417:717547
173564051:717463