I wasn't sure how to best title this as I don't know a name for this outside of my own exploration. Suppose there are some number sequences that tend toward 0 like so:
111, 102, 93, 84, 75 (down by 9s)
110, 100, 90, 80, 70 (down by 10s)
109, 100, 91, 82, 73 (down by 11s)
With the starting number on the left one higher whenever the rate of decrease is also one lower.
119 (down by 1s)
118 (down by 2s)
117 (down by 3s)
116 (down by 4s)
115 (down by 5s)
114 (down by 6s)
113 (down by 7s)
112 (down by 8s)
111 (down by 9s)
110 (down by 10s)
109 (down by 11s)
108 (down by 12s)
107 (down by 13s)
My question is: given a number n, what is the most optimal way to find where that number earliest appears in the sequence with a minimal decrease per part (down by xs) knowing the rate of decrement is never more than 13.
So if n was 104, the answer would be the row of 112, since that has 104 before 109 by 11s, 110 by 10s, 111 by 9s, etc.
What I've tried so far:
I have so far been calculating each row from the start to the first number less than zero, checking each row for an occurrence of the number, but this seems much slower than it should need to be. It's also clear 119 (down by 1s) will always have the answer even if not the most optimal one.
Does anyone have any other ideas to make this better? Thank you.
When starting number is always 119 and you should make many queries with different n's, the fastest approach is to make a table of size 119. Fill it once and you'll get sequence start number in one step
table = [0]*120
for diff in range(1, 14):
head = 120 - diff
for i in range(head, 0, -diff):
table[i] = head
print(table(104))
You can get ready table here
Note that table entries with value 119 have prime difference with 120, and we perhaps can calculate any other entry using factorization of 120 - n, but I don't think that this is rightly for real usage.