A368558 Number of fractions i/n that are in the Cantor set.

2, 2, 4, 4, 2, 4, 2, 4, 8, 6, 2, 8, 8, 2, 4, 4, 2, 8, 2, 8, 4, 2, 2, 8, 2, 8, 16, 10, 2, 12, 2, 4, 4, 2, 2, 16, 2, 2, 16, 16, 2, 4, 2, 4, 8, 2, 2, 8, 2, 6, 4, 10, 2, 16, 2, 10, 4, 2, 2, 16, 2, 2, 8, 4, 8, 4, 2, 4, 4, 6, 2, 16, 2, 2, 4, 4, 2, 16, 2, 16

Offset: 1

Author

Jason Yuen, Dec 30 2023

Keywords

• nonn
• easy

Comments

The Cantor set is all reals in the range [0,1] which can be written in ternary without using digit 1 (including allowing 0222... to be used instead of 1000...).

All terms are even.

a(n) = O(n^(log_3(2))).

a(n) is the number of solutions to CCC 2023, Problem S5.

Does this sequence contain every positive even integer?

Examples

			For n = 12, there are a(12) = 8 fractions, and their numerators are i = 0, 1, 3, 4, 8, 9, 11, 12.
		

Links

• Jason Yuen, Table of n, a(n) for n = 1..10000
• 2023 Canadian Computing Competition Senior Committee, 2023 CCC Senior Problems, Problem S5: The Filter, University of Waterloo.
• 2023 Canadian Computing Competition Senior Committee, 2023 CCC Senior Problem Commentary, S5 The Filter, University of Waterloo.
• Zixiang Zhou, main.cpp. This C++ program solves CCC 2023, Problem S5 with a time complexity of O(n^(log_3(2)) log n).

Crossrefs

Cf. A170951, A054591.

Programs

Python

def is_member(i, n):  # Returns True if i/n is in the Cantor set
  visited = set()
  while True:
    if n < 3 * i < 2 * n: return False
    if i in visited: return True
    visited.add(i)
    i = 3 * min(i, n - i)
def a(n): return sum(is_member(i, n) for i in range(n + 1))