Re: [math-fun] A binary sieve
"... then delete every j for which ..." A priori it seems possible that the order in which such j are deleted could change the outcome. —Dan Fred Lunnon wrote: ----- Choose an integer k >= 2 , let q' = 2^k - 1 , initialise set S = {1, ..., q'-1} ; then delete every j for which i < j exists with j == i*2^h (mod q') for some h . For example, when k = 5 , q' = 31 , finally S = {1, 3, 5, 7, 11, 15} . I conjecture that max S = (q'-1)/2 for all k ; but why? -----
Multiplication by 2 mod q'-1is left-rotation of the bits. For any j > (q'-1)/2, you can get the i<j (which deletes j) by rotating a zero into the high-order bit; and you cannot do that by rotating (q'-1)/2 = b011..11 On Sun, Jan 28, 2018 at 4:32 PM, Dan Asimov <dasimov@earthlink.net> wrote:
"... then delete every j for which ..."
A priori it seems possible that the order in which such j are deleted could change the outcome.
—Dan
Fred Lunnon wrote: ----- Choose an integer k >= 2 , let q' = 2^k - 1 , initialise set S = {1, ..., q'-1} ; then delete every j for which i < j exists with j == i*2^h (mod q') for some h .
For example, when k = 5 , q' = 31 , finally S = {1, 3, 5, 7, 11, 15} . I conjecture that max S = (q'-1)/2 for all k ; but why? -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
<< Multiplication by 2 (mod q') is left-rotation of the bits. >> was intended here? Anyway, neatly nailed -- thanks! Dan seems to have assumed that i had also to lie currently in S ; however, that was not my intention. WFL On 1/28/18, Michael Collins <mjcollins10@gmail.com> wrote:
Multiplication by 2 mod q'-1is left-rotation of the bits. For any j > (q'-1)/2, you can get the i<j (which deletes j) by rotating a zero into the high-order bit; and you cannot do that by rotating (q'-1)/2 = b011..11
On Sun, Jan 28, 2018 at 4:32 PM, Dan Asimov <dasimov@earthlink.net> wrote:
"... then delete every j for which ..."
A priori it seems possible that the order in which such j are deleted could change the outcome.
—Dan
Fred Lunnon wrote: ----- Choose an integer k >= 2 , let q' = 2^k - 1 , initialise set S = {1, ..., q'-1} ; then delete every j for which i < j exists with j == i*2^h (mod q') for some h .
For example, when k = 5 , q' = 31 , finally S = {1, 3, 5, 7, 11, 15} . I conjecture that max S = (q'-1)/2 for all k ; but why? -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
Fred Lunnon -
Michael Collins