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,1

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?

Links

Jason Yuen, Table of n, a(n) for n = 1..10000

2023 Canadian Computing Competition Senior Committee, CCC 2023, Problem S5: The Filter, University of Waterloo. See pages 17-18.

2023 Canadian Computing Competition Senior Committee, 2023 CCC Senior Problem Commentary, University of Waterloo. See pages 5-6.

Zixiang Zhou, main.cpp. This C++ program solves CCC 2023, Problem S5 with a time complexity of O(n^(log_3(2)) log n).

Example

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

Prog

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

Crossrefs

Cf. A170951, A054591.

Sequence in context: A130501 A049116 A065176 * A060267 A214516 A352502

Adjacent sequences: A368555 A368556 A368557 * A368559 A368560 A368561

Keyword

nonn,easy

Author

Jason Yuen, Dec 30 2023

Status

approved