[Question]
  [
# The Challenge
For this challenge, you are supposed to determine if a given number is in the Cantor set. So first, let's define the Cantor set.
First, start with the numbers between 0 and 1. Any numbers outside this range are not in the Cantor set. Now, let's divide the numbers into three equal parts: [0,1/3], [1/3,2/3], [2/3, 1]. Any numbers not inside the ranges of the first and last parts are not in the Cantor set. Now, you repeat this process for the segments [0,1/3] and [2/3, 1]. Then you repeat on what is leftover. You keep on doing this forever. In the end, all numbers that are remaining are in the Cantor set. Here is a diagram of the first six iterations:
![Cantor diagram](https://upload.wikimedia.org/wikipedia/commons/5/56/Cantor_set_in_seven_iterations.svg)
---
# Input
Two integer `x` and `y`.  
`0 < y < 2^15`  
`0 <= x <= y`  
The greatest common denominator of `x` and `y` is 1, unless `x == 0`.
---
# Output
Truthy if `x/y` is in the Cantor set.  
Falsy if `x/y` is not in the Cantor set.
---
# Examples
Now, let's see some examples of numbers that are in the Cantor set.
  
  
```
1/3 -> true  
```
It is on a boundary, and boundaries are never removed.  
  
```
1/4 -> true  
```
`1/4` is never in the middle third of a segment, though it is never on the boundary either. If you follow it's path, you will actually find that it alternates between being in the first and last thirds of a section.  
  
```
1/13 -> true  
```
`1/13` alternates between the first, first, and last sections.  
  
```
1/5 -> false
```
`1/5` falls into the first empty block of the third row in the above diagram, between 1/9 and 2/9.  
  
Other test cases:
```
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false
```
You can try other numbers with this snippet:
```
function isCantor(t,r){var n=new Set;if(0>r)return isCantor(-t,-r);if(0==r)return!1;if(0>t||t>r)return!1;for(;;){if(t%r===0)return!0;if(1===Math.floor(t/r))return!1;if(n.has(t))return!0;n.add(t),t=t%r*3}}$("#test").click(function(){var t=parseInt($("#x").val()),r=parseInt($("#y").val());if(isNaN(t)||isNaN(r)||0==r)return void $("#result").text("Invalid input");var n=isCantor(t,r),i=(n?"I":"Not i")+"n the Cantor set.";$("#result").text(i)});
```
```
input{width:30px}button{margin-left:7px}
```
```
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><input id=x>/<input id=y><button id=test>Test</button><p id=result>
```
---
# Objective
The person with the least bytes wins.
  
[Answer]
# Mathematica, 54 bytes
```
If[Last@#===1,Most@#,#]&@RealDigits[#,3][[1]]~FreeQ~1&
```
Unnamed function taking a fraction `x/y` as input, where `y > 0` and `0 ≤ x ≤ y`, and returning `True` or `False`.
A real number between 0 and 1 is in the Cantor set precisely when none of the digits in its base-3 expansion equals 1; the exception is that a fraction whose denominator is a power of 3 (whose base-3 expansion therefore terminates) is allowed to end in a 1.
`RealDigits[#,3][[1]]` gives all of the digits in the base-3 expansion of the fractional input `#`, in a form like `{1, 0, 2, {0, 1, 0, 2}}`: the last list is the periodic part of the expansion, while the integers beforehand are the digits before the periodicity starts. If the base-3 expansion is periodic right away, the output is like `{{0, 1, 0, 2}}`; if the base-3 expansion terminates, the form is like `{1, 0, 2}`.
So we want to check, using `~FreeQ~1`, whether the list is free of `1`s or not. However, because of the terminating expansion thing, we want to delete the last element of the list if it equals `1`; that's what `If[Last@#===1,Most@#,#]` accomplishes. (The `===` is needed to compare a potential list with `1`: `==` alone remains unevaluated in that situation.)
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~61~~ ~~59~~ 58 bytes
```
f(x,y,i){for(i=y;i--&&x<y;)x=(y-x<x?y-x:x)*3;return x<=y;}
```
Exploits the symmetry of the Cantor set. Breaks after `y` iterations to avoid an infinite loop.
[Try it online!](https://tio.run/nexus/c-gcc#PVDtbsMgDPwdnsJqlQpasqZfmlbI9iBbf0wj0SytpEpTyTTKs2cmzSYdxj7fgWGoJOmgUXVV3UgsgsEsWyzIBqOokCEjS28cj6SWO9OU7a3xQJZ1/TBH//VzcyXYa@uwfvp@FQJ9C/R@ggI6yDXATkdsON0wtswcHgwDejPqw6TfP4RxmxQvvJ51tHDcRv1oOH@ilwo6kcQKmU14epDIx@QGECxc8V7WFRCs/9IlcWe1Gm3JpWFnJWepW6fuCKn78DPNg@NJ8zgx8r/8V0oZkfR8y/T@3IheDL8 "C (gcc) – TIO Nexus")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~22~~ ~~17~~ ~~16~~ 15 bytes
```
,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ
```
Prints **3** for truthy, nothing for falsy.
[Try it online!](https://tio.run/nexus/jelly#@6/zcNfCQ1tVHzXuPDzd@NDWwxOO7LcCch7uaDF@uGP@f2ulw8v1HzWtcf//P9pQxzhWRwFImUAoQyjXFEQZQESNdQwNIDREkQFclSGYMtIxtAQxTHUMzSHqTCHS5hDKKBYA "Jelly – TIO Nexus")
### Background
A well-known property of the Cantor set is that it contains precisely those numbers between **0** and **1** that can be written without **1**'s in their ternary expansion.
Note that some numbers – precisely the right edges of the closed intervals involved in the set's construction – can be written either with a single (trailing) **1** or with an infinite amount of trailing **2**'s. For example, **1 = 13 = 0.22222…3** and **1/3 = 0.13 = 0.022222…3**, just as **0.510 = 0.499999…10**.
To avoid special-casing the right edges, we can check for **1**'s is the shortest decimal expansion in both **x/y** and **1 - x/y = (y - x)/y**, where **x/y** is a right edge iff **(y - x)/y** is a left edge. If at least one of them contains no **1**'s, **x/y** belongs to the Cantor set.
### How it works
```
,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ  Main link. Left argument: x. Right argument: y
 ạ               Absolute difference; yield y - x.
,                Pair; yield [x, y - x].
       µ         Begin a new, monadic chain with argument [a, b] := [x, y - x].
  µ     ÐĿ       Repeatedly execute the links in between until the results are no
                 longer unique, updating a and b after each execution. Return the
                 array of all unique results.
   %⁹              Compute [a % y, b % y].
     ×3            Compute [3(a % y), 3(b % y)].
                 This yields all unique dividends of the long division of x by y in
                 base 3.
          :⁹     Divide all dividends by y to get the corresponding ternary digits.
            Ḅ    Unbinary; turn [1, 1] into 3, other pairs into other numbers.
             3ḟ  Remove all occurrences of the resulting numbers from [3], leaving
                 an empty array if and only if one pair [a, b] is equal to [1, 1].
```
[Answer]
# JavaScript (ES6), 65 ~~67~~
**Edit** 2 bytes saved thx @Luke
```
n=>d=>(z=>{for(q=0;~-q*n*!z[n];n=n%d*3)z[n]=1,q=n/d|0})([])|q!=1|!n
```
*Less golfed*
```
n=>d=>{
  z = []; // to check for repeating partial result -> periodic number
  for(q = 0; q != 1 && n != 0 && !z[n]; )
    z[n] = 1,
    q = n / d | 0,
    n = n % d * 3
  return q!=1 | n==0
}
```
**Test**
```
f=
n=>d=>(z=>{for(q=0;~-q*n*!z[n=n%d*3];q=n/d|0)z[n]=1})([])|q!=1|!n
  
console.log(
'Truthy: 1/3 1/4 1/13 0/4 3/10 3/4 10/13 1/1\nFalsey: 1/5 12/19 5/17 3/5 1/7 1/2'.replace(/(\d+).(\d+)/g,(a,x,y)=>a+':'+f(x)(y))
)  
```
[Answer]
## JavaScript (ES6), 55 bytes
```
y=>f=(x,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,z|q==1,n+1):1
```
Use by currying in the denominator first and the numerator second. The standard form is a byte longer:
```
f=(x,y,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,y,z|q==1,n+1):1
```
### Explanation
If a fraction is not in the Cantor set, it must fall into one of the middle sections at some point; therefore, its representation in base 3 must contain a 1 followed at some point by a non-zero digit. That's how this works:
* `z` keeps track of whether we've found a 1.
* `q` is the current digit in base 3.
* `!z|!q` is true if `z` is false (we have not found a 1) or `q` is false (the current digit is 0).
If `n` runs down to zero before we find a non-zero digit somewhere after a 1, the fraction is in the Cantor set and we return `1`.
[Answer]
# [Bash](https://www.gnu.org/software/bash/) + GNU utilities, 62 bytes
```
dc -e3o9d$2^$1*$2/p|tr -cd 012|grep -P "1(?!(0{$2,}|2{$2,})$)"
```
[Try it online!](https://tio.run/nexus/bash#@5@SrKCbapxvmaJiFKdiqKVipF9QU1KkoJucomBgaFSTXpRaoKAboKBkqGGvqGFQrWKkU1tjBKY0VTSV/v//b/jf0BgA "Bash – TIO Nexus")
Pass it two integer arguments with arg1 <= arg2 and 0 < arg2.
The output is returned in the exit code (0 for falsy, 1 for truthy), as allowed by [PPCG I/O methods](http://meta.codegolf.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods/5330#5330).
I suspect the regex can be golfed further, maybe even eliminating the tr command in favor of using grep -z, but this is the shortest I've been able to come up with. (Unfortunately, grep -z is incompatible with grep -P, and the -P option to get perl-style regexes is required for the ?! syntax.)
Testbed program and output:
```
for x in '1 3' '1 4' '1 13' '1 5' '0 4' '3 10' '3 4' '10 13' '1 1' '12 19' '5 17' '3 5' '1 7' '1 2'
  do
    printf %-6s "$x "
    ./cantor $x >/dev/null && echo F || echo T
  done
1 3   T
1 4   T
1 13  T
1 5   F
0 4   T
3 10  T
3 4   T
10 13 T
1 1   T
12 19 F
5 17  F
3 5   F
1 7   F
1 2   F
```
---
**Explanation**
dc part (the arguments are x and y):
```
3o     Set output base to 3.
9      Push 9 on the stack.
d      Duplicate the top of the stack. (The extra 9 on the stack isn't actually used, but I need some delimiter in the code here so that the 9 doesn't run into the number coming up next.  If I used a space as a no-op, then I'd need to quote it for the shell, adding an extra character.)
$2^    Raise 9 to the y power. This number in base 3 is 1 followed by 2y 0's.
$1*$2/ Multiply the base-3 number 10....0 (with 2y 0's in it) by x and then divide by y (truncating). This computes 2y digits (after an implied ternary point) of x/y.  That's enough digits so that the repeating part of the rational number is there at least twice.
p      Print the result, piping it to tr.
```
tr and grep part:
A minor issue is that, although dc handles arbitrarily large integers, when dc prints a large number, it will break it up into 69-character lines, with each line except the last ending with a backslash, and with a newline after each line.
The tr command deletes any backslashes and newlines. This leaves just a single line.
The grep command then uses a perl-style regex (-P option, which is a GNU extension). The regex matches if the line contains a 1 not followed by at least y 0's or at least y 2's which then end the string.
This is exactly what's needed to identify x/y as not being in the Cantor set, because the repeating part of the base-3 representation of the rational number x/y can be viewed as starting at digit #y+1 after the ternary point, and is at most y digits long.
[Answer]
## CJam (19 bytes)
```
{_@3@#*\/3b0-W<1&!}
```
[Online test suite](http://cjam.aditsu.net/#code=q%22%2Ftf%22%22%2010%22er%22-%3Erueals%22-~%5D3%2F%7B~%40%40%0A%0A%7B_%403%40%23*%5C%2F3b0-W%3C1%26!%7D%0A%0A~%3D%7D%25&input=0%2F4%20-%3E%20true%0A3%2F10%20-%3E%20true%0A3%2F4%20-%3E%20true%0A10%2F13%20-%3E%20true%0A1%2F1%20-%3E%20true%0A12%2F19%20-%3E%20false%0A5%2F17%20-%3E%20false%0A3%2F5%20-%3E%20false%0A1%2F7%20-%3E%20false%0A1%2F2%20-%3E%20false%0A1%2F3%20-%3E%20true%0A2%2F3%20-%3E%20true)
This is an anonymous block (function) which takes two arguments on the stack and leaves `0` or `1` on the stack. It works by base converting the fraction `x/y` into `y` base `3` digits and returning true iff they contain no `1` or the only `1` is part of a suffix `1 0 0 0 ...`.
```
{            e# Begin a block
  _@3@#*\/3b e#   Base conversion
   0-W<      e#   Remove all zeros and the final non-zero digit
   1&!       e#   True iff no 1s are left
}
```
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 14 bytes
```
gu*3hS,G-QGQE0
```
Based on my C solution. `y` on first input line, `x` on second.
```
                Q = y
 u         QE   G = x
                loop y times
  *3                x = 3 *
    hS,G                min(x,
        -QG                 y-x)
g            0  return x >= 0
```
If `x/y` is within the Cantor set, `x` stays between `0` and `y`. Otherwise, `x` becomes greater than `y` at one point, then diverges to negative infinity in the remaining iterations.
[Try it online!](https://tio.run/nexus/pyth#@59eqmWcEazjrhvoHuhq8P@/oTGXoQEA "Pyth – TIO Nexus")
[Answer]
## Batch, 91 bytes
```
@set/ai=%3+1,n=%1*3%%%2,f=%1*3/%2%%2,f^|=j=!((%2-i)*n)
@if %f%==0 %0 %n% %2 %i%
@echo %j%
```
Tests the first `y-1` base 3 digits of `x/y`. `i` is the count of digits tested. `n` is the next value of `x`. `j` is true if `n` reaches zero (because the expansion terminates) or we have tested `y-1` digits without finding a `1`. `f` is true if `j` is true or if the next digit is a `1`, at which point we stop looping and output `j`.
]