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
Keywords
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)
Comments