20
\$\begingroup\$

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


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.

\$\endgroup\$
  • \$\begingroup\$ Are we guaranteed that the input is not (0,0)? Is the fraction given in simplest form? \$\endgroup\$ – xnor Feb 1 '17 at 6:43
  • 1
    \$\begingroup\$ @xnor look at the range given for y. I'm going to say that the fraction is in simplest form unless x == 0 \$\endgroup\$ – TheNumberOne Feb 1 '17 at 6:44
  • \$\begingroup\$ Some test cases where x!=1 would be good. Also, your snippet says 1/3 is not in the cantor set. \$\endgroup\$ – xnor Feb 1 '17 at 6:48
  • \$\begingroup\$ @xnor Added and fixed ;) \$\endgroup\$ – TheNumberOne Feb 1 '17 at 6:58
  • 6
    \$\begingroup\$ Cantor can it be found? \$\endgroup\$ – mbomb007 Feb 1 '17 at 16:16
13
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Im surprised that Mathematica does not have IsCantorNumber but has a function to determine is something is a goat. \$\endgroup\$ – Brain Guider Feb 1 '17 at 14:59
  • 3
    \$\begingroup\$ Well, I dunno, which come up more in real life: goats or fractals? ;) \$\endgroup\$ – Greg Martin Feb 1 '17 at 17:39
  • \$\begingroup\$ FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]& \$\endgroup\$ – ngenisis Feb 2 '17 at 0:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Greg Martin Feb 2 '17 at 0:23
  • \$\begingroup\$ 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. \$\endgroup\$ – ngenisis Feb 2 '17 at 1:03
9
\$\begingroup\$

C (gcc), 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!

\$\endgroup\$
7
\$\begingroup\$

Jelly, 22 17 16 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].
\$\endgroup\$
  • \$\begingroup\$ 3 is the true true +1. \$\endgroup\$ – Magic Octopus Urn Feb 1 '17 at 17:32
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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] \$\endgroup\$ – Luke Feb 1 '17 at 11:32
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.