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:

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. • Are we guaranteed that the input is not (0,0)? Is the fraction given in simplest form? – xnor Feb 1 '17 at 6:43 • @xnor look at the range given for y. I'm going to say that the fraction is in simplest form unless x == 0 Feb 1 '17 at 6:44 • Some test cases where x!=1 would be good. Also, your snippet says 1/3 is not in the cantor set. – xnor Feb 1 '17 at 6:48 • @xnor Added and fixed ;) Feb 1 '17 at 6:58 • Cantor can it be found? Feb 1 '17 at 16:16 9 Answers 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 1s 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.) • Im surprised that Mathematica does not have IsCantorNumber but has a function to determine is something is a goat. Feb 1 '17 at 14:59 • Well, I dunno, which come up more in real life: goats or fractals? ;) Feb 1 '17 at 17:39 • FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]& Feb 2 '17 at 0:05 • Such a rule would also strip off trailing 1s in the periodic part, which leads to incorrect answers. For example, the base-3 expansion of 7/8 is .21212121...., or {{2,1}}; but the suggested rule would change that to {{2}}, which is free of 1s but shouldn't be. Feb 2 '17 at 0:23 • Touché. How about #==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&? If it's terminating and nonzero RealDigits[#,3] will be of the form {{__Integer},-1} and if it's repeating it will be of the form {{___Integer,{__Integer}},-1}, right? I'm on mobile so it's hard to test right now. If this works, using infix notation for RealDigits might work as well. Feb 2 '17 at 1:03 C (gcc), 6159 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! Jelly, 221716 15 bytes ,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ  Prints 3 for truthy, nothing for falsy. Try it online! 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].  • 3 is the true true +1. Feb 1 '17 at 17:32 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)) )  • I think you can replace n=n%d*3 with q=n/d|0 and then replace z[n] with z[n=n%d*3] – Luke Feb 1 '17 at 11:32 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. Bash + GNU utilities, 62 bytes dc -e3o9d$2^$1*$2/p|tr -cd 012|grep -P "1(?!(0{$2,}|2{$2,})$)"  Try it online! 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. 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.

CJam (19 bytes)

{_@3@#*\/3b0-W<1&!}


Online test suite

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
}


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!

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.