For fun, I tried to find a simpler formula for seq(0,K) in Appendix A, but I didn't check if it's computationally faster and I doubt it is. The formula I found was: seq(0,K) = 2(K+1) - Hamming(K+1) - ffs(K+1)
Explanation:
When the newest hash is at position K (zero-indexed), there are K+1 level 0 hashes being stored.
The stored permanent hashes form a set of perfect binary trees. There is either 0 or 1 of each size of perfect tree. To determine if a tree of a given size exists when there are K+1 hashes, you can check the corresponding binary digit in K+1. For instance, if the eights place in K+1 is set, then there is a perfect tree with eight level 0 hashes.
Each perfect tree contains 2N - 1 hashes, where N is the number of level 0 hashes in it. To calculate the total number of permanent hashes, we can sum the totals for the individual trees. The sum of N for all of the trees is just the total number of level 0 hashes, K+1, so the 2N term becomes 2(K+1). The total number of trees is equal to the number of set bits in the binary representation of K+1, which is the hamming weight[1]. So -1 becomes -Hamming(K+1).
We now know that when the last record is at position K (zero-indexed), there are 2(K+1) - Hamming(K+1) permanent hashes stored.
Unfortunately, the last level 0 hash might not be at the end of the file, so we need to subtract the number of hashes that come after it. The number of hashes after it is the height (L, zero-indexed) of the smallest perfect tree, which is the position of the first set bit (one-indexed)[2] of K+1, less 1: ffs(K+1) - 1. We then subtract 1 to convert the number of records to the zero-indexed position. The -(-1) and -1 cancel out.
Can you comment on the scale of VIN reader deployments? They're harder to read because of the smaller size, but I'd guess they're less likely to be intentionally altered or obscured.
Explanation: When the newest hash is at position K (zero-indexed), there are K+1 level 0 hashes being stored.
The stored permanent hashes form a set of perfect binary trees. There is either 0 or 1 of each size of perfect tree. To determine if a tree of a given size exists when there are K+1 hashes, you can check the corresponding binary digit in K+1. For instance, if the eights place in K+1 is set, then there is a perfect tree with eight level 0 hashes.
Each perfect tree contains 2N - 1 hashes, where N is the number of level 0 hashes in it. To calculate the total number of permanent hashes, we can sum the totals for the individual trees. The sum of N for all of the trees is just the total number of level 0 hashes, K+1, so the 2N term becomes 2(K+1). The total number of trees is equal to the number of set bits in the binary representation of K+1, which is the hamming weight[1]. So -1 becomes -Hamming(K+1).
We now know that when the last record is at position K (zero-indexed), there are 2(K+1) - Hamming(K+1) permanent hashes stored.
Unfortunately, the last level 0 hash might not be at the end of the file, so we need to subtract the number of hashes that come after it. The number of hashes after it is the height (L, zero-indexed) of the smallest perfect tree, which is the position of the first set bit (one-indexed)[2] of K+1, less 1: ffs(K+1) - 1. We then subtract 1 to convert the number of records to the zero-indexed position. The -(-1) and -1 cancel out.
[1] https://en.wikipedia.org/wiki/Hamming_weight#Efficient_imple... [2] https://en.wikipedia.org/wiki/Find_first_set#CTZ