OFFSET
1,6
COMMENTS
Definition:
For each integer n, construct a divisibility circle graph as follows:
- Place the numbers 0 to n-1 evenly around a circle.
- For each number k between 0 and n-1, draw a chord from k to 10k mod n.
- Count the intersections among all the chords.
Notes:
- Two edges (a,f(a)) and (b,f(b)) are considered to intersect if their segments are only partially contained within the other.
- Edges are undirected, and intersections are counted once (i.e., duplicates from symmetric pairs are removed).
LINKS
Gil Moses, Table of n, a(n) for n = 1..2000
James Grime, Solving Seven, Numberphile video.
EXAMPLE
For n=7, the segments are 0->0, 1->3, 2->6, 3->2, 4->5, 5->1, 6->4.
When drawing these chords in a circle, 3 intersections occur: 1->3 and 2->6, 5->1 and 6->4, 2->6 and 5->1.
PROG
(Python)
import sys
base_multiplier = 10
def list_intersections(n):
"""
Computes the number of valid intersections based on range intersections.
Before checking intersections, ensures that each range is stored in ascending order
to avoid duplicate counting.
"""
# Generate remainder pairs using the base multiplier
table = [(i, (base_multiplier * i) % n) for i in range(n)]
# Ensure each range is stored in ascending order and remove duplicates
unique_ranges = set((min(num, rem), max(num, rem)) for num, rem in table)
sorted_table = list(unique_ranges) # Convert back to a list for processing
intersections = []
# Check for valid intersections
for i in range(len(sorted_table)):
num1, rem1 = sorted_table[i]
for j in range(i):
num2, rem2 = sorted_table[j]
# Find intersection range
intersection_start = max(num1, num2)
intersection_end = min(rem1, rem2)
intersection_length = max(0, intersection_end - intersection_start)
# Compute the lengths of the two ranges
range1_length = rem1 - num1
range2_length = rem2 - num2
# An intersection occurs if the intersection is smaller than the smallest range and > 0
if 0 < intersection_length < min(range1_length, range2_length):
intersections.append(((num2, rem2), (num1, rem1)))
return len(intersections)
# Define range of n values
n_values = list(range(1, 100))
intersections_values = [] # Stores intersections count for each n
for n in n_values:
# Compute intersections using the deduplicated method
intersections = list_intersections(n)
intersections_values.append(intersections)
# Output only intersection numbers for OEIS submission
for value in intersections_values:
print(value)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gil Moses, Mar 11 2025
STATUS
approved