Determine whether rational coordinates are in the right Sierpinski triangle

Question

The Sierpinski triangle is a set of points on the plane which is constructed by starting with a single triangle and repeatedly splitting all triangles into four congruent triangles and removing the centre triangle. The right Sierpinski triangle has corners at (0,0), (0,1) and (1,0), and looks like this:

Some equivalent definitions of this set are as follows:

• Points in the nth iteration of the process described above, for all n.

• Points (x,y) with 0 <= x <= 1 and 0 <= y <= 1 such that for all positive integers n, the nth bit in the binary expansion of x and y are not both 1.

• Let T = {(0,0),(1,0),(0,1)}

  Let f be a function on sets of 2D points defined by the following:

  f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}

  Then the right Sierpinski triangle is the topological closure of the least fixed point (by set containment) of f.

• Let S be the square {(x,y) | 0<=x<=1 and 0<=y<=1}

  Let g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T} (where T is as defined above)

  Then the right Sierpinski triangle is the greatest fixed point of g.

Challenge

Write a program or function which accepts 4 integers, a,b,c,d and gives a truthy value if (a/b,c/d) belongs to the right Sierpinski triangle, and otherwise gives a falsey value.

Scoring

This is a code golf. Shortest code in bytes wins.

Test cases

The following are in the right Sierpinski triangle:

0 1 0 1
0 1 12345 123456
27 100 73 100
1 7 2 7
8 9 2 21
8 15 20 63
-1 -7 2 7

The following are not in the right Sierpinski triangle:

1 1 1 1
-1 100 1 3
1 3 1 3
1 23 1 7
4 63 3 66
58 217 4351 7577
-1 -7 3 7

Answer 1

Python 2, 68

lambda n,d,N,D:1>=n/d>=0<=N/D<=1and(n<<abs(D*d))/d&(N<<abs(D*d))/D<1

A nice way to check for gasket membership made ugly. If we were guaranteed that the inputs are non-negative and in the unit square, we would have 38:

lambda n,d,N,D:(n<<D*d)/d&(N<<D*d)/D<1

The idea is that we check whether a point lies within the gasket by checking whether their binary fraction expansions bitwise-AND to 0. To get the first k character of the expansion, we bit-shift the numerator k bits left before integer-dividing by the denominator. We need to make k sufficiently large to catch a repeat. We note that the binary expansion n/d has period at most d, so the joint expansions have period at most d*D, so k=d*D suffices.

The rest is to check whether the fraction is in the box and insulate against inputs given like -1/-3.