A381977 Number of edge intersections in the divisibility circle graph of n (base 10).

0, 0, 0, 0, 0, 3, 3, 5, 0, 0, 0, 12, 18, 19, 21, 27, 35, 36, 57, 20, 45, 25, 71, 75, 65, 88, 90, 110, 137, 81, 120, 135, 42, 162, 150, 180, 204, 215, 252, 165, 230, 252, 282, 208, 270, 315, 341, 357, 402, 290, 375, 400, 440, 441, 340, 481, 513, 530, 587, 456

Offset: 1

Author

Gil Moses, Mar 11 2025

Keywords

• nonn

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).

Examples

			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.
		

Links

• Gil Moses, Table of n, a(n) for n = 1..2000
• James Grime, Solving Seven, Numberphile video.

Programs

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)