Joseph Garvin
Reputation
Next privilege 250 Rep.
 Nov28 comment Such a thing as a circular arithmetic progression? @coffeemath: Yep, I noticed that too. Maybe they're not specifically studied and that's why? It definitely would make it easier to prove properties about them. Nov28 revised Such a thing as a circular arithmetic progression? added 1 characters in body Nov28 awarded Student Nov28 asked Such a thing as a circular arithmetic progression? Nov11 accepted Negative coefficients and Bezout's identity Nov11 comment Negative coefficients and Bezout's identity This is what I was confused about, looks safe: math.stackexchange.com/questions/37806/… Nov11 comment Negative coefficients and Bezout's identity I guess the question here is whether $gcd(a, b)$ and $gcd(a, -b)$ produce the same bezout coefficients, and thus the same $x, y, k$. Although if it did that would seem to imply that when $ax + by = gcd(a, b)*k$ is true that $ax - by = gcd(a, b) * k$ is also true, which would mean you could toggle the +/- sign in Bezout's identity, which doesn't seem right. Nov10 awarded Commentator Nov10 awarded Editor Nov10 comment Negative coefficients and Bezout's identity Added a note about $k$, in the main question so you could better see what I mean. Nov10 revised Negative coefficients and Bezout's identity added 93 characters in body Nov10 comment Negative coefficients and Bezout's identity Substitution does make things more clear but doesn't seem to get me all the way there. I can write $ax_1 + by_1 = gcd(a, b) * k_1$, and I can say $c = -b$ and use substitution to get $ax_2 + cy_2 = gcd(a, c) * k_2$, then plug $-b$ back in for $c$ and get $ax_2 - by_2 = gcd(a, -b) * k_2 = gcd(a, b) * k_2$, but it's unclear what the relationship between $x_1, y_1, k_1$ and $x_2, y_2, k_2$ are. $x_2$ and $y_2$ correspond to the $d$ and $f$ in the original example and are the numbers I actually want, but the identity/algo only let me compute $x_1$ and $y_1$, and I don't see how to substitute back. Nov10 asked Negative coefficients and Bezout's identity Nov3 comment Euclidean Algorithm vs Factorization Just have your brother try both on a large number. Oct16 comment Representing circular bitwise shift mathematically I think I get it, it makes more sense to me if the floor is multiplied out so you get $floor(x/2^{m-1}) - 2^mfloor(x/2^{m-1})$. It's a conditional add of 1 to flip the bit in the lowest place if needed, and a conditional subtraction of the $2^m$ if it was needed. It'd be even clearer if we stored $floor(x/2^{m-1})$ in value called 'highbitset' ;) That's nifty. Oct16 comment Representing circular bitwise shift mathematically I get that checking for the value being bigger than $2^{m-1}$ is checking whether the high bit is set, and I get that because we did $2x$ not modulo we need to somehow cancel out the 1 that may be in the 33rd bit, and somehow set the least significant bit, but that addition appears to kill two birds with one stone somehow. Oct16 comment Representing circular bitwise shift mathematically Could you explain how you derived this? Based on how left circular shift is usually implemented in code, ((x << 1) | (x >> (m - 1))), I can see the $2x$ as being the left shift, but I'm confused how the rest becomes equivalent to the right shift and the bitwise or. $floor(x/2^{m−1})$ will only ever be 0 or 1, since in the m-bit unsigned integers nothing is twice as big as $2^{m−1}$ since it wraps to 0. So we're conditionally deciding whether to add $(1−2^m)$ based on whether our starting value is greater than $2^{m−1}$. But passed that I'm not sure why adding $(1−2^m)$ does the trick. Oct13 awarded Scholar Oct13 awarded Supporter Oct13 comment Why don't all elements of an arithmetic progression divide the lcm of the start and step? Ah, so the problem isn't that they don't work with ∀ and ∃, it's that they only work with ∀ and ∃.