Joseph Garvin
Reputation
Next privilege 250 Rep.
 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 revised Progressions with variable density that can be described in constant space? deleted 70 characters in body 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 revised Progressions with variable density that can be described in constant space? added 146 characters in body 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 revised Progressions with variable density that can be described in constant space? added 371 characters in body 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? Dec 16 asked Progressions with variable density that can be described in constant space? Dec 6 comment Largest subset of { 0, 1, 2, …, n } that has no 3+ element arithmetic progressions? @GerryMyerson: Oops, I misread the number on yours and thought it was different. And good point :P Dec 5 accepted Largest subset of { 0, 1, 2, …, n } that has no 3+ element arithmetic progressions? Dec 4 comment Largest subset of { 0, 1, 2, …, n } that has no 3+ element arithmetic progressions? Sweet, I finally understand enough to ask an unsolved problem ;) Dec 4 asked Largest subset of { 0, 1, 2, …, n } that has no 3+ element arithmetic progressions? Dec 4 accepted Such a thing as a circular arithmetic progression? Nov 28 comment Such a thing as a circular arithmetic progression? @coffeemath: Whoa, that's a cool trick. What prompted you to think of that?