180 reputation
6
bio website
location
age
visits member for 1 year, 11 months
seen Dec 7 '13 at 23:44

Nov
4
comment Concrete Mathematics - Stability of definitions in the repertoire method
Brilliant! Never occurred to me to plug the closed form back into the recurrence to convince myself, but that makes sense to try since that's where the structure is coming from. Thanks :-)
Nov
4
comment Repertoire Method Clarification Required ( Concrete Mathematics )
@HansLundmark: I can see that it will be a combination of those, but I don't understand how we know A, B, and C will always be the same, which I have opened as a new question.
Jan
27
comment How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?
Actually #4 is OK, it does follow from the definition if you're using the Bezout's identity version.
Jan
27
comment Blending values on the number line
Were the number lines drawn by hand or is there a plotting tool for these?
Jan
26
comment How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?
How do we know c divides a in the third sentence?
Jan
26
comment How to prove $\gcd(a,\gcd(b, c)) = \gcd(\gcd(a, b), c)$?
#4 seems false. How does it follow from the definition of GCD? If d is a prime factor X common to both a and gcd(b,c), and e is a different prime factor Y common to both a and gcd(b,c), then e will not divide d or vice versa, because they're prime.
Jan
22
comment Partition minimizing maximum of Euler's totient function across terms
It maybe a great idea. I read that the ith primorial multiplied by the ith prime is sparsely totient, and used that to quickly build a list (not all sparse totients, but for rough minimization may be OK). I tried building the partition for $2^{64}$ in the style of Euclid's algorithm for GCD -- I took the biggest number in the list < $2^{64}$ and took the remainder of dividing by it, then took the biggest sparse totient in the list under the remainder and took the remainder of dividing by it, etc. etc. Turns out a linear combination of those sparse totients exactly partitioned it. Coincidence?
Jan
10
comment Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?
Ah, that makes more sense, thanks.
Jan
8
comment Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?
If I understand right, this computes the size of the set of numbers I want to iterate, but it doesn't help with iterating or computing e.g. the 5th number, or am I not thinking hard enough yet?
Dec
18
comment Primes in arithmetic progression
Is it common to use plain parens to represent gcd? I'm so used to reading those as tuples.
Dec
16
comment Progressions with variable density that can be described in constant space?
Yes, much. Thanks for your patience explaining :)
Dec
16
comment Progressions with variable density that can be described in constant space?
Oooooh, that makes much more sense.
Dec
16
comment Progressions with variable density that can be described in constant space?
Actually my confusion might stem from what you mean by $x_k$ and $x_k + 1$. I interpret $x_k$ to be the 0 or 1 in the kth bit, where k is offset from the radix point of the most significant bit. Did you mean $x_{k+1}$ instead of $x_k + 1$? Because $x_k$ would just be 1 or 0, which when 1 is added would be two? Or maybe by addition you meant string concatenation? I suck at notation :(
Dec
16
comment Progressions with variable density that can be described in constant space?
Your edit helps a bit, thanks. So it sounds like you're saying that if you take the most significant locked bit, $x_k$, you can keep adding $x_k + 1$ and get numbers satisfying the constraint that are evenly spaced. But isn't the neglecting the unfixed bits that are below $x_k$? Why don't we get variable density from those? I'm actually unsure if your conclusion is answering the question or saying it can't be answered -- my test is to eliminate possibilities, so failing the test would mean a proof that fixing bits works, but in the comments on the question you said fixing them doesn't?
Dec
16
comment Progressions with variable density that can be described in constant space?
I'm probably being dense, but I don't see how your first sentence could be true. If the number is 32-bits for example, fixing bits 3, 5, and 7 to particular values doesn't put any constraint in the "leading digits", that is, the leading bits, 8-32. Unless by first digits you mean the least significant bits, but it doesn't impose any constraint on bits 0-2 either, so I'm still not sure what you mean. Is k indexing the total number of bits, or is it indexing only the bits that we've locked?
Dec
16
comment Progressions with variable density that can be described in constant space?
@MarioCarneiro: I've added a constraint that I think gets at what I'm going for, getting the Nth element easily. I don't totally follow your explanation for why a set of fixed bits doesn't work -- are you saying that my specific example of constraining that the 3rd/5th/7th bit wouldn't work, or are you just saying it's not always true that any subset of fixed bits will work because if you only pick a chunk of adjacent digits at the beginning/end you only get multiples or all numbers below a threshold?
Dec
16
comment Progressions with variable density that can be described in constant space?
@MarioCarneiro: That may work. Makes me wonder if you can just say, all the numbers where some subset of the bits are a fixed, e.g. all numbers where the 3rd bit is 1, the 5th bit is 1, and 7th bit is 1.
Dec
16
comment Progressions with variable density that can be described in constant space?
@MarioCarneiro: My ultimate goal does involve using this in a computer program, so leading digits are a bit problematic to extract, unless it's the binary leading digit, but that's always 1 if you consider the 'leading digit' to be the most significant bit, or if you consider it the left most bit in the word just splits the space evenly in half, the numbers below $\frac{2^n - 1}{2}$ and the numbers equal and above. Sorry, I realize I'm springing more details than are in my question, I was trying to capture the essence and keep it succinct, obviously didn't succeed :P
Dec
16
comment Progressions with variable density that can be described in constant space?
@MarioCarneiro: Basically I'm trying to stick to sequences that can be generated from a bounded number of starting bits. Put another way, I'm trying to find sequences that have something like a closed form representation I can work with algebraically and reason about, rather than somebody just dropping a manually figured out list of numbers lacking any generality.
Dec
16
comment Progressions with variable density that can be described in constant space?
@MarioCarneiro: Couldn't you get away with just saying all numbers with a leading 8?