Comma search tool

README.md

This is a simple search tool to find commas between intervals (maybe even irrational ones, though it would try to show them as fractions). You just specify a list of basis intervals to measure against each other, an upper bound in cents to filter interval combinations through, and the desired count. The code then iterates over suitable combinations from smaller to larger taxicab distances in the lattice spanned by the basis, ensuring simpler commas show first. (But which is simpler depends on your basis! 3/2 and 4/3 is one thing, 3 and 2 is another, 9/8 and 32/27 is yet another still.)

The output of

show_commas(['4/3', '5/4', '6/5', '7/6'], under_cents=25, count=15)

here in main is:

  7.712c = 225/224 = (4/3)^-1 (5/4)^2 (6/5)^0 (7/6)^-1 
 21.902c = 875/864 = (4/3)^0 (5/4)^1 (6/5)^-2 (7/6)^1 
 21.506c = 81/80 = (4/3)^-2 (5/4)^1 (6/5)^2 (7/6)^0
 13.795c = 126/125 = (4/3)^-1 (5/4)^-1 (6/5)^2 (7/6)^1
 13.074c = 1728/1715 = (4/3)^1 (5/4)^0 (6/5)^1 (7/6)^-3
 14.191c = 245/243 = (4/3)^1 (5/4)^-1 (6/5)^-2 (7/6)^2
 19.553c = 2048/2025 = (4/3)^3 (5/4)^-3 (6/5)^-1 (7/6)^0
  5.362c = 6144/6125 = (4/3)^2 (5/4)^-2 (6/5)^1 (7/6)^-2
  0.396c = 4375/4374 = (4/3)^2 (5/4)^0 (6/5)^-4 (7/6)^1
  8.107c = 15625/15552 = (4/3)^1 (5/4)^2 (6/5)^-4 (7/6)^0
  6.083c = 3136/3125 = (4/3)^0 (5/4)^-3 (6/5)^2 (7/6)^2
 20.785c = 2430/2401 = (4/3)^0 (5/4)^2 (6/5)^1 (7/6)^-4
 15.423c = 50625/50176 = (4/3)^-2 (5/4)^4 (6/5)^0 (7/6)^-2
 19.157c = 110592/109375 = (4/3)^1 (5/4)^-3 (6/5)^3 (7/6)^-1
  8.433c = 1029/1024 = (4/3)^-3 (5/4)^1 (6/5)^1 (7/6)^3

Use iter_commas to have more control (say, sorting or displaying the results in another manner). It generates pairs of cent values and coordinates in the lattice.

For a suitable count, the algorithm should visit all the intervals under the size bound at a given taxicab distance away from the unison. If you somehow find that’s not the case, please comment here and let me know. (I have no rigorous proof, it’s just an intuition, but if this doesn’t always work, then most probably it’s a bug in this implementation and not in the idea itself.)

comma_finder.py

from __future__ import annotations
from collections import deque
from fractions import Fraction
from itertools import islice
from math import log2, prod
from typing import Final, Iterator, Sequence

type Node = tuple[int, ...]  # coordinates

def iter_commas(intervals_cents: Sequence[float],
                under_cents: float) -> Iterator[tuple[float, Node]]:
    DIM: Final = len(intervals_cents)
    visited_nodes: set[Node] = set()
    scheduled_nodes: deque[Node] = deque([(0,) * DIM])
    while scheduled_nodes:
        node = scheduled_nodes.popleft()
        if node in visited_nodes:
            continue
        neg_node = tuple(-n for n in node)
        multiples = tuple(x * n for x, n in zip(intervals_cents, node))
        value = sum(multiples)
        if abs(value) <= under_cents:
            #print(f'{len(scheduled_nodes) = }, {len(visited_nodes) = }')
            if value < 0:
                yield -value, neg_node
            else:
                yield value, node
        visited_nodes.update([node, neg_node])
        if value <= under_cents:  # try increasing coordinates
            for i in range(DIM):
                new_node = tuple(m if i != j else m + 1 for j, m in enumerate(node))
                if new_node in visited_nodes:
                    continue
                scheduled_nodes.append(new_node)
        if -value <= under_cents:  # try decreasing coordinates
            for i in range(DIM):
                new_node = tuple(m if i != j else m - 1 for j, m in enumerate(node))
                if new_node in visited_nodes:
                    continue
                scheduled_nodes.append(new_node)

def show_commas(interval_strs: Sequence[str], under_cents: float, count: int) -> None:
    if count <= 0:
        raise ValueError('count should be positive')
    ratios = tuple(map(Fraction, interval_strs))
    cents = tuple(log2(x) * 1200 for x in ratios)
    commas = iter_commas(cents, under_cents)
    for comma_cents, coords in islice(commas, 1, count + 1):
        ratio = prod(x ** n for x, n in zip(ratios, coords))
        print(f'{comma_cents:7.3f}c = {ratio} = ', end='')
        for intv_str, multiplicity in zip(interval_strs, coords):
            print(f'({intv_str})^{multiplicity} ', end='')
        print()

def main() -> None:
    show_commas(['4/3', '5/4', '6/5', '7/6'], under_cents=25, count=15)

if __name__ == '__main__':
    main()