Query Data Bar Intervals

The edge list of an interval T_0 is the set of larger bar intervals for which T_0 is the largest even divisor.

Or, equivalently, given the graph with bar intervals as nodes and the evenly divisible relation as edges, prune away all redundant edges that leave the graph fully connected.

Let a roll event for a bar interval be a time, measured in seconds since the epoch, that is evenly divisible by the bar interval width.

Given a 1 second tick event, the associated number of seconds since the epoch, and a vector of last roll event times for each interval, then this graph allows us to check a minimum number of bar intervals for roll events, for the common case just two.

Note that at each second the 1 second bar necessarily rolls, and that it is trivially a common divisor of any larger interval measured in seconds. Using depth-first traversal starting at that smallest bar, and following each path until a node fails to roll or a leaf node is reached, correctness follows from transitivity for divisibility, and minimum work from the definition of the edge relation and structural induction on the graph, noting that branches are mutually disjunctive.

In practice, for the bar intervals as currently defined, the only bar of interest is m01, with the two successor nodes of m02 and m05. If the m02 interval is eliminated, the resulting graph is a list, and array traversal can be used in place of depth-first search.

Bill Pippin 2010-01-14