Determinar si las coordenadas racionales están en el triángulo rectángulo de Sierpinski

9

El triángulo de Sierpinski es un conjunto de puntos en el plano que se construye comenzando con un solo triángulo y dividiendo repetidamente todos los triángulos en cuatro triángulos congruentes y eliminando el triángulo central. El triángulo de Sierpinski derecha tiene esquinas en (0,0), (0,1)y (1,0), y se ve así:

Triángulo de Sierpinski

Algunas definiciones equivalentes de este conjunto son las siguientes:

  • Puntos en la niteración del proceso descrito anteriormente, para todos n.

  • Puntos (x,y)con 0 <= x <= 1y 0 <= y <= 1tal que para todos los enteros positivos n, el nbit th en la expansión binaria de x e y no son ambos 1.

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

    Sea funa función en conjuntos de puntos 2D definidos por lo siguiente:

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

    Entonces el triángulo de Sierpinski derecho es el cierre topológico del punto menos fijo (por contención establecida) de f.

  • Deja Sser el cuadrado{(x,y) | 0<=x<=1 and 0<=y<=1}

    Let g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}(donde Tes como se definió anteriormente)

    Entonces el triángulo rectángulo de Sierpinski es el mayor punto fijo de g.

Desafío

Escriba un programa o función que acepte 4 enteros, a,b,c,dy dé un valor verdadero si (a/b,c/d)pertenece al triángulo Sierpinski correcto, y de lo contrario da un valor falsey.

Puntuación

Este es un código de golf. El código más corto en bytes gana.

Casos de prueba

Los siguientes están en el triángulo rectángulo de Sierpinski:

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

Los siguientes no están en el triángulo rectángulo de Sierpinski:

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
caja de cartón
fuente
¿Es -1 -3 1 1una entrada válida?
xnor
Sí, esa es una entrada válida. He agregado casos de prueba para aclarar esto.
cartón_box

Respuestas:

5

Pitón 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

Una buena manera de comprobar si la membresía de la junta es fea. Si se nos garantizara que las entradas no son negativas y están en el cuadrado de la unidad, tendríamos 38:

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

La idea es que verifiquemos si un punto se encuentra dentro de la junta comprobando si su fracción binaria se expande bit a bit Y a 0. Para obtener el primer kcarácter de la expansión, desplazamos los kbits del numerador a la izquierda antes de dividirlos por el denominador . Necesitamos hacer lo ksuficientemente grande como para atrapar una repetición. Observamos que la expansión binaria n/dtiene un período como máximo d, por lo que las expansiones conjuntas tienen un período como máximo d*D, por lo que es k=d*Dsuficiente.

El resto es verificar si la fracción está en el cuadro y aislar contra entradas dadas como -1/-3.

xnor
fuente