cp's OEIS Frontend

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

%I A368558 #28 Jun 28 2025 19:46:39
%S A368558 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,
%T A368558 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,
%U A368558 8,4,2,4,4,6,2,16,2,2,4,4,2,16,2,16
%N A368558 Number of fractions i/n that are in the Cantor set.
%C A368558 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...).
%C A368558 All terms are even.
%C A368558 a(n) = O(n^(log_3(2))).
%C A368558 a(n) is the number of solutions to CCC 2023, Problem S5.
%C A368558 Does this sequence contain every positive even integer?
%H A368558 Jason Yuen, <a href="/A368558/b368558.txt">Table of n, a(n) for n = 1..10000</a>
%H A368558 2023 Canadian Computing Competition Senior Committee, <a href="https://cemc.uwaterloo.ca/sites/default/files/documents/2023/2023CCCSrProblemSet.html#problem-s5-the-filter">2023 CCC Senior Problems, Problem S5: The Filter</a>, University of Waterloo.
%H A368558 2023 Canadian Computing Competition Senior Committee, <a href="https://cemc.uwaterloo.ca/sites/default/files/documents/2024/2023CCCSrCommentary.html#s5-the-filter">2023 CCC Senior Problem Commentary, S5 The Filter</a>, University of Waterloo.
%H A368558 Zixiang Zhou, <a href="/A368558/a368558.cpp.txt">main.cpp</a>. This C++ program solves CCC 2023, Problem S5 with a time complexity of O(n^(log_3(2)) log n).
%e A368558 For n = 12, there are a(12) = 8 fractions, and their numerators are i = 0, 1, 3, 4, 8, 9, 11, 12.
%o A368558 (Python)
%o A368558 def is_member(i, n):  # Returns True if i/n is in the Cantor set
%o A368558   visited = set()
%o A368558   while True:
%o A368558     if n < 3 * i < 2 * n: return False
%o A368558     if i in visited: return True
%o A368558     visited.add(i)
%o A368558     i = 3 * min(i, n - i)
%o A368558 def a(n): return sum(is_member(i, n) for i in range(n + 1))
%Y A368558 Cf. A170951, A054591.
%K A368558 nonn,easy
%O A368558 1,1
%A A368558 _Jason Yuen_, Dec 30 2023