[math-fun] Binary number divisible by 3? (was Re: FW: squares beginning with n)
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000. Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3. Examples: 2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2. 2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3. 2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
Dear Sylvia, A moment that Dave had to go get another bulb ... Let's see: I would like to know something about whether there is much noise from other tenants or the street. But maybe you can ask that subtly so as not to give the impression that I'm oversensitive about that issue. Also: Is there anything they think a prospective tenant should know? (Like what the management is like, etc.) Warm \\xoxoxox// <smb://xoxoxox//>, Dan
On May 24, 2016, at 3:10 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3.
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
P.S. ALSO — Maybe try to find out how flexible they are as regard the start and end dates. Thanx!!!
On May 24, 2016, at 4:00 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Dear Sylvia,
A moment that Dave had to go get another bulb ...
Let's see: I would like to know something about whether there is much noise from other tenants or the street.
But maybe you can ask that subtly so as not to give the impression that I'm oversensitive about that issue.
Also: Is there anything they think a prospective tenant should know? (Like what the management is like, etc.)
Warm \\xoxoxox// <smb://xoxoxox//>,
Dan
On May 24, 2016, at 3:10 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3.
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
_______________________________________________ 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
Please ignore. As if you didn't know I sent this to the wrong address. Thanks! —Anonymous
On May 24, 2016, at 4:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
P.S. ALSO — Maybe try to find out how flexible they are as regard the start and end dates. Thanx!!!
On May 24, 2016, at 4:00 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Dear Sylvia,
A moment that Dave had to go get another bulb ...
Let's see: I would like to know something about whether there is much noise from other tenants or the street.
But maybe you can ask that subtly so as not to give the impression that I'm oversensitive about that issue.
Also: Is there anything they think a prospective tenant should know? (Like what the management is like, etc.)
Warm \\xoxoxox// <smb://xoxoxox//>,
Dan
On May 24, 2016, at 3:10 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3.
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If you want only a yes/no of divisibility by 3, a binary number and its reverse have the same divisibility. So an FSM can be made that reads the binary input starting at either end.
On May 24, 2016, at 6:10 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3.
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The same trick that works in base 10 also works in base 4. So just group the bits into pairs and add them, then repeat on the result until the sum is less than 4. If the sum is divisible by 3 (i.e., if the sum is 3 (or 0, if the original number was 0)), then the number is divisible by 3. Otherwise it isn't. Example: 101110001 (369) -> 1 + 01 + 11 + 00 + 01 = 110 (6) -> 110 (6) -> 1 + 10 = 11 (3) Answer: yes I think this is an n*log(n) algorithm where n is the number of bits, so log(v)*log(log(v)) where v is the value. Tom Keith F. Lynch writes:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time. The number of 1s left will be the original number's remainder when divided by 3.
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oops, my mistake, this is clearly O(n) where n is the number of bits, so O(log(v)) where v is the value. Here's a Python implementation (which has bignums): def div3_check(n): v = n while v > 3: s = 0 while v != 0: s += v & 0x3 v >>= 2 v = s return v in (0, 3) You can also replace the multiple passes with a single pass, by renormalizing the sum on the fly (keeping it in the range 0..3): def div3_check(n): v = n s = 0 while v != 0: s += v & 0x3 s = (s >> 2) + (s & 0x3) v >>= 2 return s in (0, 3) Tom Tom Karzes writes:
The same trick that works in base 10 also works in base 4. So just group the bits into pairs and add them, then repeat on the result until the sum is less than 4. If the sum is divisible by 3 (i.e., if the sum is 3 (or 0, if the original number was 0)), then the number is divisible by 3. Otherwise it isn't.
Example:
101110001 (369) -> 1 + 01 + 11 + 00 + 01 = 110 (6) -> 110 (6) -> 1 + 10 = 11 (3)
Answer: yes
I think this is an n*log(n) algorithm where n is the number of bits, so log(v)*log(log(v)) where v is the value.
Tom
To be fair: parity rule is the same in b10 & b2 while div-by-4 rule is even simper in b2. However, in div5 case, b2 again desperately looses:( Zak
On 25/05/2016 04:05, Zak Seidov via math-fun wrote:
To be fair: parity rule is the same in b10 & b2 while div-by-4 rule is even simper in b2. However, in div5 case, b2 again desperately looses:(
Well, sure, divisibility by p is easier to test in a base that's a multiple of p. But divisibility by 5 isn't *hard* in binary. Group digits in pairs and add and subtract alternately. So e.g. 45893 -> 1011001101000101 -> -10+11-00+11-01+00-01+01 -> -10+11+11-01 [deleting 00 and cancelling pairs] -> 11 [noticing that 11-10-01=0] and we correctly infer that 45893 is 3 mod 5. (You can work from the left instead of from the right so long as you remember to add an extra 0 if need be and either care only whether the result is 0 or make the appropriate corrections for zero-padding and sign-changing to get the result mod 5.) -- g
To tell if a binary numeral is divisible by 3: Repeatedly remove adjacent pairs of matching digits (00 or 11) until remaining digits are alternating. If number of 1's in remaining number a multiple of 3, so was original number.
* David Wilson <davidwwilson@comcast.net> [May 26. 2016 07:51]:
To tell if a binary numeral is divisible by 3: Repeatedly remove adjacent pairs of matching digits (00 or 11) until remaining digits are alternating. If number of 1's in remaining number a multiple of 3, so was original number.
All these recipes are consequence of the following. Let N be written in base B and D = B+1. Then N is divisible by D iff the alternating sum of over the digits of N is divisible by D. As far as I recall one obtains such rules by considering numbers as polynomials where the "free variable" is taken to be the base B (and the digits are the coefficients). One checks divisibility by "x - D" = B - D.
[...]
That's a fun game!: 1->1 10->10 11->(blank) 100->1 101->101 110->0 111->1 1000->10 1001->(blank) 1010->1010 1011->10 1100->(blank) 1101->01 1110->10 1111->(blank) One question that comes to mind is, if you randomly pick an integer between 2^(n-1) and 2^n-1, what's the expected number of uneliminated bits that remain, or equivalently, what is the expected number of bit-runs of odd length? (If you prefer, you can look at all bit strings of length n, whether they begin with a 1 or a 0; the answer is the same.) I get the sequence of answers 1, 1, 3/2, 3/2, ...; I'm guessing the pattern continues as 2, 2, 5/2, 5/2, etc. There are standard techniques for problems like this via recurrence relations, but I suspect there's a cute direct proof; does anyone see it? Jim Propp On Wednesday, May 25, 2016, David Wilson <davidwwilson@comcast.net <javascript:_e(%7B%7D,'cvml','davidwwilson@comcast.net');>> wrote:
To tell if a binary numeral is divisible by 3: Repeatedly remove adjacent pairs of matching digits (00 or 11) until remaining digits are alternating. If number of 1's in remaining number a multiple of 3, so was original number.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 26/05/2016 16:14, James Propp wrote:
One question that comes to mind is, if you randomly pick an integer between 2^(n-1) and 2^n-1, what's the expected number of uneliminated bits that remain, or equivalently, what is the expected number of bit-runs of odd length? (If you prefer, you can look at all bit strings of length n, whether they begin with a 1 or a 0; the answer is the same.)
I get the sequence of answers 1, 1, 3/2, 3/2, ...; I'm guessing the pattern continues as 2, 2, 5/2, 5/2, etc.
I get a different answer. Using the alternative formulation (all length-n bit-strings) and starting at length 0, I get 0, 1, 1, 3/2, 7/4, 17/8, 39/16, 89/32, ... which doesn't seem especially beautiful. (The corresponding integer sequence 0, 2, 4, 12, 28, 68, ... doesn't appear to be in OEIS.) Have I miscalculated? -- g
Gareth, One of us miscalculated. I get 0000->(Empty): 0 0001->01: 2 0010->10: 2 0011->(Empty): 0 0100->01: 2 0101->0101: 4 0110->(Empty): 0 0111->01: 2 1000->10: 2 1001->(Empty): 0 1010->1010: 4 1011->10: 2 1100->(Empty): 0 1101->01: 2 1110->10: 2 1111->(Empty): 0 0+2+2+0+2+4+0+2+2+0+4+2+0+2+2+0=24 And 24/16=3/2, not 7/4. Can you find my mistake (or yours)? Jim On Thursday, May 26, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 26/05/2016 16:14, James Propp wrote:
One question that comes to mind is, if you randomly pick an integer between
2^(n-1) and 2^n-1, what's the expected number of uneliminated bits that remain, or equivalently, what is the expected number of bit-runs of odd length? (If you prefer, you can look at all bit strings of length n, whether they begin with a 1 or a 0; the answer is the same.)
I get the sequence of answers 1, 1, 3/2, 3/2, ...; I'm guessing the pattern continues as 2, 2, 5/2, 5/2, etc.
I get a different answer. Using the alternative formulation (all length-n bit-strings) and starting at length 0, I get 0, 1, 1, 3/2, 7/4, 17/8, 39/16, 89/32, ... which doesn't seem especially beautiful.
(The corresponding integer sequence 0, 2, 4, 12, 28, 68, ... doesn't appear to be in OEIS.)
Have I miscalculated?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 26/05/2016 22:37, James Propp wrote:
One of us miscalculated. I get
0000->(Empty): 0 0001->01: 2 0010->10: 2 0011->(Empty): 0 0100->01: 2 0101->0101: 4 0110->(Empty): 0 0111->01: 2 1000->10: 2 1001->(Empty): 0 1010->1010: 4 1011->10: 2 1100->(Empty): 0 1101->01: 2 1110->10: 2 1111->(Empty): 0
0+2+2+0+2+4+0+2+2+0+4+2+0+2+2+0=24
And 24/16=3/2, not 7/4.
Can you find my mistake (or yours)?
Originally you wrote: | what's the expected number of uneliminated bits that | remain, or equivalently, what is the expected number | of bit-runs of odd length? but those two things are not equivalent. Consider, for instance, 0110. It has two bit-runs of odd length, one at each end, but because they are separated only by even-length runs they get merged and eliminated by the "keep removing pairs" process. The same goes for 1001, and the extra four odd runs turn your 24/16=3/2 into my 28/16=7/4. My numbers are from counting bit-runs of odd length; yours are from counting bit-runs of odd length not separated only by even-length runs. Given how much simpler your numbers come out than mine, I'm thinking there is probably a simpler characterization of what you're counting... -- g
So neither of us miscalculated; we correctly calculated two different things that I overhastily and mistakenly assumed were equal! (Is there a nice "static" way to characterize "the number of bits that remain" without reference to the bit-elimination process?) Anyway, I have to retract what I said about using recurrence relations; I don't see how to solve for the nth term of the sequence using finite-state-machines technology. Jim On Thursday, May 26, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 26/05/2016 22:37, James Propp wrote:
One of us miscalculated. I get
0000->(Empty): 0 0001->01: 2 0010->10: 2 0011->(Empty): 0 0100->01: 2 0101->0101: 4 0110->(Empty): 0 0111->01: 2 1000->10: 2 1001->(Empty): 0 1010->1010: 4 1011->10: 2 1100->(Empty): 0 1101->01: 2 1110->10: 2 1111->(Empty): 0
0+2+2+0+2+4+0+2+2+0+4+2+0+2+2+0=24
And 24/16=3/2, not 7/4.
Can you find my mistake (or yours)?
Originally you wrote:
| what's the expected number of uneliminated bits that | remain, or equivalently, what is the expected number | of bit-runs of odd length?
but those two things are not equivalent. Consider, for instance, 0110. It has two bit-runs of odd length, one at each end, but because they are separated only by even-length runs they get merged and eliminated by the "keep removing pairs" process.
The same goes for 1001, and the extra four odd runs turn your 24/16=3/2 into my 28/16=7/4.
My numbers are from counting bit-runs of odd length; yours are from counting bit-runs of odd length not separated only by even-length runs. Given how much simpler your numbers come out than mine, I'm thinking there is probably a simpler characterization of what you're counting...
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Also, I now think my original conjecture was wrong: 10000->1: 1 10001->101: 3 10010->0: 1 10011->1: 1 10100->101: 3 10101->10101: 5 10110->1: 1 10111->101: 3 11000->0: 1 11001->1: 1 11010->010: 3 11011->0: 1 11100->1: 1 11101->101: 3 11110->0: 1 11111->1: 1 1+3+1+1+3+5+1+3+1+1+3+1+1+3+1+1=30, not 32. So the sequence of averages goes 1,1,3/2,3/2,15/16,... Anyone care to write some code to compute more terms? Jim On Thursday, May 26, 2016, James Propp <jamespropp@gmail.com <javascript:_e(%7B%7D,'cvml','jamespropp@gmail.com');>> wrote:
So neither of us miscalculated; we correctly calculated two different things that I overhastily and mistakenly assumed were equal!
(Is there a nice "static" way to characterize "the number of bits that remain" without reference to the bit-elimination process?)
Anyway, I have to retract what I said about using recurrence relations; I don't see how to solve for the nth term of the sequence using finite-state-machines technology.
Jim
On Thursday, May 26, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 26/05/2016 22:37, James Propp wrote:
One of us miscalculated. I get
0000->(Empty): 0 0001->01: 2 0010->10: 2 0011->(Empty): 0 0100->01: 2 0101->0101: 4 0110->(Empty): 0 0111->01: 2 1000->10: 2 1001->(Empty): 0 1010->1010: 4 1011->10: 2 1100->(Empty): 0 1101->01: 2 1110->10: 2 1111->(Empty): 0
0+2+2+0+2+4+0+2+2+0+4+2+0+2+2+0=24
And 24/16=3/2, not 7/4.
Can you find my mistake (or yours)?
Originally you wrote:
| what's the expected number of uneliminated bits that | remain, or equivalently, what is the expected number | of bit-runs of odd length?
but those two things are not equivalent. Consider, for instance, 0110. It has two bit-runs of odd length, one at each end, but because they are separated only by even-length runs they get merged and eliminated by the "keep removing pairs" process.
The same goes for 1001, and the extra four odd runs turn your 24/16=3/2 into my 28/16=7/4.
My numbers are from counting bit-runs of odd length; yours are from counting bit-runs of odd length not separated only by even-length runs. Given how much simpler your numbers come out than mine, I'm thinking there is probably a simpler characterization of what you're counting...
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I've solved my problem: the first key was to look at the whole distribution instead of just its mean (and to notice binomial coefficients), and the second key was to think inductively (if you prepend a bit to an already-reduced bit-string, and then reduce the result, what happens?). Here's the array you get when you count the number of bit strings of length n that reduce to a bit string of length k: 0 1 2 3 4 5 6 7 8 1: 1 2: 1 1 3: 3 1 4: 3 4 1 5: 10 5 1 6: 10 15 6 1 7: 35 21 7 1 8: 35 56 28 8 1 See the pattern? It's a bisected Pascal triangle, where numbers that are to the left of the symmetry line are omitted, numbers to the right of the line are included, and numbers ON the line get HALVED. (Oh, and also, the zeroeth row gets omitted.) A fun way to generate this table is with stacks of chips on {0,1,2,3,...}. To derive a new row, double the number of chips at each site and then "fire" each stack, where firing means sending half the chips to the left and half to the right, unless the stack is at 0, in which case firing means sending all the chips to the right (from 0 to 1). The sequence of expected values goes 1/1, 2/2, 6/4, 12/8, 30/16, 60/32, 140/64, 280/128, ... where the numerators are terms of OEIS sequence A100071 and the denominators are powers of two. Indeed, I'm not the first person to notice this: Apparently also the count of 'unmatched symbols' in the binary strings of length n (see A008314 <http://oeis.org/A008314>). - Wouter Meeussen <http://oeis.org/wiki/User:Wouter_Meeussen>, May 26 2013 Hi, Wouter! :-) Entry A008314 gives a variant of my triangular array in the form of a sequence, namely 1 1 1 1 1 3 1 4 3 1 5 10 1 6 15 10 1 7 21 35 1 8 28 56 35 ... and says: Row k also counts the binary strings of length k that have 0, 2 up to 2*floor(k/2) 'unmatched symbols'. See contributions by Marc van Leeuwen in Math StackExchange link. [Wouter Meeussen <http://oeis.org/wiki/User:Wouter_Meeussen>, Apr 17 2013] The text of entry A008314 never mentions that the entries are given by binomial coefficients. But they are, aren't they? Jim On Thursday, May 26, 2016, James Propp <jamespropp@gmail.com> wrote:
Also, I now think my original conjecture was wrong:
10000->1: 1 10001->101: 3 10010->0: 1 10011->1: 1 10100->101: 3 10101->10101: 5 10110->1: 1 10111->101: 3 11000->0: 1 11001->1: 1 11010->010: 3 11011->0: 1 11100->1: 1 11101->101: 3 11110->0: 1 11111->1: 1
1+3+1+1+3+5+1+3+1+1+3+1+1+3+1+1=30, not 32.
So the sequence of averages goes 1,1,3/2,3/2,15/16,...
Anyone care to write some code to compute more terms?
Jim
On Thursday, May 26, 2016, James Propp <jamespropp@gmail.com> wrote:
So neither of us miscalculated; we correctly calculated two different things that I overhastily and mistakenly assumed were equal!
(Is there a nice "static" way to characterize "the number of bits that remain" without reference to the bit-elimination process?)
Anyway, I have to retract what I said about using recurrence relations; I don't see how to solve for the nth term of the sequence using finite-state-machines technology.
Jim
On Thursday, May 26, 2016, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 26/05/2016 22:37, James Propp wrote:
One of us miscalculated. I get
0000->(Empty): 0 0001->01: 2 0010->10: 2 0011->(Empty): 0 0100->01: 2 0101->0101: 4 0110->(Empty): 0 0111->01: 2 1000->10: 2 1001->(Empty): 0 1010->1010: 4 1011->10: 2 1100->(Empty): 0 1101->01: 2 1110->10: 2 1111->(Empty): 0
0+2+2+0+2+4+0+2+2+0+4+2+0+2+2+0=24
And 24/16=3/2, not 7/4.
Can you find my mistake (or yours)?
Originally you wrote:
| what's the expected number of uneliminated bits that | remain, or equivalently, what is the expected number | of bit-runs of odd length?
but those two things are not equivalent. Consider, for instance, 0110. It has two bit-runs of odd length, one at each end, but because they are separated only by even-length runs they get merged and eliminated by the "keep removing pairs" process.
The same goes for 1001, and the extra four odd runs turn your 24/16=3/2 into my 28/16=7/4.
My numbers are from counting bit-runs of odd length; yours are from counting bit-runs of odd length not separated only by even-length runs. Given how much simpler your numbers come out than mine, I'm thinking there is probably a simpler characterization of what you're counting...
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, May 24, 2016 at 6:10 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ???
Replace any pairs of 1s that have an even number (possibly 0) of 0s between them and that have no other digits between them, with 0s. For instance 11->00, 1001->0000, 100001->00000.
Repeat the above as many times as possible. Then discard any remaining 1s three at a time.
The number of 1s left will be the
original number's remainder when divided by 3.
While it's true that the original number is divisible by 3 just if you have a number of remaining 1's that's a multiple of 3, it's not true that the number of 1's remaining is the original number 's remainder when divided by 3...
Examples:
2015: 11111011111 -> 11111011100 -> 11111010000 -> 11100010000 -> 10000010000. Two 1s left, so its 3-remainder is 2.
2016: 11111100000 -> 11110000000 -> 11000000000 -> 0. Divisible by 3.
2017: 11111100001 -> 11110000001 -> 11000000001 -> 1. One 1 left, so its 3-remainder is 1.
Counterexample: 2: 10. one 1 left, but it's 3-remainder is 2, not 1. In general, your rule is correct if there are an even number of 0's after the final 1, but if there are an odd number of 0's after the final 1, you have to subtract the number of 1's from 3 to get the remainder mod 3. Andy
participants (10)
-
Andy Latto -
Dan Asimov -
David Wilson -
Gareth McCaughan -
James Propp -
Joerg Arndt -
Keith F. Lynch -
Mike Beeler -
Tom Karzes -
Zak Seidov