I wrote a function to return the first n length sequence which occurs twice in the digits of pi. Along with the repeated sequence, I want the indices of the first and second occurrences. For example, if n is
1, code returns
(1, 0, 2) and if n is
(26, 5, 20).
For reference, here are the first digits of pi:
The code uses a breadth-first search (as opposed to a depth-first search, which I coded up to be faster, but isn't what I'm looking for). I realize code below is convoluted and inefficient because it checks same digits multiple times.
How do I make it simpler and faster?
from mpmath import mp mp.dps = 1000 pi = mp.pi def repeats(n): pi_list = [int(x) for x in str(pi)[2:]] breadth = range(n + n, len(pi_list)) for breadth_level in breadth: pattern_starts = range(breadth_level - 2 * n + 1) for p_s in pattern_starts: test_starts = range(n, breadth_level - n + 1) for t_s in test_starts: candidate = pi_list[p_s:p_s + n] test_start = max(p_s + n, t_s) test = pi_list[test_start:test_start + n] if candidate == test: return candidate, p_s, t_s print(repeats(1)) print(repeats(2)) print(repeats(3))
(, 0, 2) ([2, 6], 5, 20) ([5, 9, 2], 3, 60)
repeatmany times, it might be worth building a
suffix treeonce, and the running the queries on the tree. A suffix tree can also let you answer similar questions like: are there any that repeat more the 2 times, what's the most repeats, which pair has the earliest repeat, find all repeats, etc. \$\endgroup\$