mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-08-03, 10:26   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

24·83 Posts
Default 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
preda is offline   Reply With Quote
Old 2020-08-03, 13:24   #2
axn
 
axn's Avatar
 
Jun 2003

22·5·239 Posts
Default

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
axn is offline   Reply With Quote
Old 2020-08-04, 01:00   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

24·83 Posts
Default

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.
preda is offline   Reply With Quote
Old 2020-08-04, 14:11   #4
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

24×23 Posts
Default 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.
kruoli is offline   Reply With Quote
Old 2020-08-04, 14:15   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

100111110100112 Posts
Default

Quote:
Originally Posted by kruoli View Post
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?
xilman is offline   Reply With Quote
Old 2020-08-04, 14:19   #6
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

1011100002 Posts
Default

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.
kruoli is offline   Reply With Quote
Old 2020-08-04, 14:43   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5×2,039 Posts
Default

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?
xilman is offline   Reply With Quote
Old 2020-08-04, 15:07   #8
uau
 
Jan 2017

10011112 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
uau is offline   Reply With Quote
Old 2020-08-05, 03:57   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

157510 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
Citrix is offline   Reply With Quote
Old 2020-08-05, 08:14   #10
axn
 
axn's Avatar
 
Jun 2003

22·5·239 Posts
Default

Quote:
Originally Posted by preda View Post
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
axn is offline   Reply With Quote
Old 2020-08-05, 09:39   #11
axn
 
axn's Avatar
 
Jun 2003

10010101011002 Posts
Default

Code:
136110417:717547
173564051:717463

Last fiddled with by axn on 2020-08-05 at 10:38 Reason: Another improvement
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some puzzle Harrywill Puzzles 4 2017-05-03 05:10
Four 1's puzzle Uncwilly Puzzles 75 2012-06-12 13:42
a puzzle bcp19 Puzzles 18 2012-03-02 04:11
Dot puzzle nibble4bits Puzzles 37 2006-02-27 09:35
now HERE'S a puzzle. Orgasmic Troll Puzzles 6 2005-12-08 07:19

All times are UTC. The time now is 07:42.

Sat Nov 28 07:42:24 UTC 2020 up 79 days, 4:53, 3 users, load averages: 1.35, 1.23, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.