Calculates and updates a_i in-place to either the n-th term or the smallest term for which c > 10^k when the terms are written in the form: a(i) = b * 10^k + c For any a(i), if digitsum(b) and c have the same value, the difference between subsequent terms will be the sa
(a_i, k, i, n)
| 18 | |
| 19 | |
| 20 | def next_term(a_i, k, i, n): |
| 21 | """ |
| 22 | Calculates and updates a_i in-place to either the n-th term or the |
| 23 | smallest term for which c > 10^k when the terms are written in the form: |
| 24 | a(i) = b * 10^k + c |
| 25 | |
| 26 | For any a(i), if digitsum(b) and c have the same value, the difference |
| 27 | between subsequent terms will be the same until c >= 10^k. This difference |
| 28 | is cached to greatly speed up the computation. |
| 29 | |
| 30 | Arguments: |
| 31 | a_i -- array of digits starting from the one's place that represent |
| 32 | the i-th term in the sequence |
| 33 | k -- k when terms are written in the from a(i) = b*10^k + c. |
| 34 | Term are calulcated until c > 10^k or the n-th term is reached. |
| 35 | i -- position along the sequence |
| 36 | n -- term to calculate up to if k is large enough |
| 37 | |
| 38 | Return: a tuple of difference between ending term and starting term, and |
| 39 | the number of terms calculated. ex. if starting term is a_0=1, and |
| 40 | ending term is a_10=62, then (61, 9) is returned. |
| 41 | """ |
| 42 | # ds_b - digitsum(b) |
| 43 | ds_b = sum(a_i[j] for j in range(k, len(a_i))) |
| 44 | c = sum(a_i[j] * base[j] for j in range(min(len(a_i), k))) |
| 45 | |
| 46 | diff, dn = 0, 0 |
| 47 | max_dn = n - i |
| 48 | |
| 49 | sub_memo = memo.get(ds_b) |
| 50 | |
| 51 | if sub_memo is not None: |
| 52 | jumps = sub_memo.get(c) |
| 53 | |
| 54 | if jumps is not None and len(jumps) > 0: |
| 55 | # find and make the largest jump without going over |
| 56 | max_jump = -1 |
| 57 | for _k in range(len(jumps) - 1, -1, -1): |
| 58 | if jumps[_k][2] <= k and jumps[_k][1] <= max_dn: |
| 59 | max_jump = _k |
| 60 | break |
| 61 | |
| 62 | if max_jump >= 0: |
| 63 | diff, dn, _kk = jumps[max_jump] |
| 64 | # since the difference between jumps is cached, add c |
| 65 | new_c = diff + c |
| 66 | for j in range(min(k, len(a_i))): |
| 67 | new_c, a_i[j] = divmod(new_c, 10) |
| 68 | if new_c > 0: |
| 69 | add(a_i, k, new_c) |
| 70 | |
| 71 | else: |
| 72 | sub_memo[c] = [] |
| 73 | else: |
| 74 | sub_memo = {c: []} |
| 75 | memo[ds_b] = sub_memo |
| 76 | |
| 77 | if dn >= max_dn or c + diff >= base[k]: |