Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>So this is just a preliminary sketch of an algorithm. It works when the upper bound is itself a Fibonacci number, but I'm not sure how to adapt it for general upper bounds. Hopefully someone can improve upon this.</p> <p>The general idea is to look at the structure of the Fibonacci encodings. Here are the first few numbers:</p> <pre><code> 0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 </code></pre> <p>The invariant in each of these numbers is that there's never a pair of consecutive 1s. Given this invariant, we can increment from one number to the next using the following pattern:</p> <ol> <li>If the last digit is 0, set it to 1.</li> <li>If the last digit is 1, then since there aren't any consecutive 1s, set the last digit to 0 and the next digit to 1.</li> <li>Eliminate any doubled 1s by setting them both to 0 and setting the next digit to a 1, repeating until all doubled 1s are eliminated.</li> </ol> <p>The reason that this is important is that property (3) tells us something about the structure of these numbers. Let's revisit the first few Fibonacci-encoded numbers once more. Look, for example, at the first three numbers:</p> <pre><code> 00 01 10 </code></pre> <p>Now, look at all four-bit numbers:</p> <pre><code>1000 1001 1010 </code></pre> <p>The next number will have five digits, as shown here:</p> <blockquote> <p>1011 &rarr; 1100 &rarr; 10000</p> </blockquote> <p>The interesting detail to notice is that the number of numbers with four digits is equal to the number of values with up to two digits. In fact, we get the four-digit numbers by just prefixing the at-most-two-digit-numbers with 10.</p> <p>Now, look at three-digit numbers:</p> <pre><code>000 001 010 100 101 </code></pre> <p>And look at five-digit numbers:</p> <pre><code>10000 10001 10010 10100 10101 </code></pre> <p>Notice that the five-digit numbers are just the three-digit numbers with 10 prefixed.</p> <p>This gives us a very interesting way for counting up how many 1s there are. Specifically, if you look at (k+2)-digit numbers, each of them is just a k-digit number with a 10 prefixed to it. This means that if there are B 1s total in all of the k-digit numbers, the number of Bs total in numbers that are just k+2 digits is equal to B plus the number of k-digit numbers, since we're just replaying the sequence with an extra 1 prepended to each number.</p> <p>We can exploit this to compute the number of 1s in the Fibonacci codings that have at most k digits in them. The trick is as follows - if for each number of digits we keep track of</p> <ol> <li>How many numbers have at most that many digits (call this N(d)), and</li> <li>How many 1s are represented numbers with at most d digits (call this B(d)).</li> </ol> <p>We can use this information to compute these two pieces of information for one more digit. It's a beautiful DP recurrence. Initially, we seed it as follows. For one digit, N(d) = 2 and B(d) is 1, since for one digit the numbers are 0 and 1. For two digits, N(d) = 3 (there's just one two-digit number, 10, and the two one-digit numbers 0 and 1) and B(d) is 2 (one from 1, one from 10). From there, we have that</p> <ul> <li>N(d + 2) = N(d) + N(d + 1). This is because the number of numbers with up to d + 2 digits is the number of numbers with up to d + 1 digits (N(d + 1)), plus the numbers formed by prefixing 10 to numbers with d digits (N(d))</li> <li>B(d + 2) = B(d + 1) + B(d) + N(d) (The number of total 1 bits in numbers of length at most d + 2 is the total number of 1 bits in numbers of length at most d + 1, plus the extra we get from numbers of just d + 2 digits)</li> </ul> <p>For example, we get the following:</p> <pre><code> d N(d) B(d) --------------------- 1 2 1 2 3 2 3 5 5 4 8 10 5 13 20 </code></pre> <p>We can actually check this. For 1-digit numbers, there are a total of 1 one bit used. For 2-digit numbers, there are two ones (1 and 10). For 3-digit numbers, there are five 1s (1, 10, 100, 101). For four-digit numbers, there are 10 ones (the five previous, plus 1000, 1001, 1010). Extending this outward gives us the sequence that we'd like.</p> <p>This is extremely easy to compute - we can compute the value for k digits in time O(k) with just O(1) memory usage if we reuse space from before. Since the Fibonacci numbers grow exponentially quickly, this means that if we have some number N and want to find the sum of all 1s bits to the largest Fibonacci number smaller than N, we can do so in time O(log N) and space O(1).</p> <p>That said, I'm not sure how to adapt this to work with general upper bounds. However, I'm optimistic that there is some way to do it. This is a beautiful recurrence and there just has to be a nice way to generalize it.</p> <p>Hope this helps! Thanks for an awesome problem!</p>
    singulars
    1. This table or related slice is empty.
    1. POCounting the bits set in the Fibonacci number system?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UStemplatetypedef
    1. UStemplatetypedef
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThe above shows a recurrence relation I'd not seen before with the Fibonacci sequence: each number is the sum of alternating preceding numbers, plus 1. If F[N] is the nth number in the sequence, and PSum[N] is the sum F[N]+F[N-2]+F[N-4]..., then if F[N] = PSum[N-1]+1, then F[N+1] = PSum[N]+1, and F[N+2] = PSum[N+1]+1 = (F[N+1]+PSum[N-1])+1 = F[N+1]+(PSum[N-1]+1) = F[N+1]+F[N]. Very elegant.
      singulars
      1. PO
      1. USsupercat
    2. COIncidentally, Fibinacci coding might be useful for something like magnetic data encoding with two poulse widths, if "0" means a state transition and "1" means no transition. All such encoding schemes I've seen were table based, but it's interesting that one could use Fibonacci place values instead.
      singulars
      1. PO
      1. USsupercat
    3. COTo go to general upper bounds, I believe that you should represent your bound in Zeckendorf representation and then successively overcount and overcompensate as I wrote in my solution. I hope I wrote this part clearly enough.
      singulars
      1. PO
      1. USDale Gerdemann
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload