Determinar se as coordenadas racionais estão no triângulo de Sierpinski certo

9

O triângulo de Sierpinski é um conjunto de pontos no plano que é construído começando com um único triângulo e dividindo repetidamente todos os triângulos em quatro triângulos congruentes e removendo o triângulo central. O triângulo direito de Sierpinski tem cantos em (0,0), (0,1)e (1,0), e fica assim:

Triângulo de Sierpinski

Algumas definições equivalentes deste conjunto são as seguintes:

  • Pontos na niteração do processo descrito acima, para todos n.

  • Pontos (x,y)com 0 <= x <= 1e 0 <= y <= 1tais que, para todos os números inteiros positivos n, o nth bit na expansão binária de x e y não são ambos 1.

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

    Seja fuma função em conjuntos de pontos 2D definidos pelo seguinte:

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

    Então, o triângulo de Sierpinski à direita é o fechamento topológico do ponto menos fixo (por contenção definida) de f.

  • Seja So quadrado{(x,y) | 0<=x<=1 and 0<=y<=1}

    Let g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}(onde Té como definido acima)

    Então o triângulo direito de Sierpinski é o maior ponto fixo de g.

Desafio

Escreva um programa ou função que aceite 4 números inteiros a,b,c,de dê um valor verdadeiro se (a/b,c/d)pertencer ao triângulo de Sierpinski à direita e, caso contrário, dê um valor de falsey.

Pontuação

Este é um código de golfe. O menor código em bytes vence.

Casos de teste

A seguir, estão no triângulo direito 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

O seguinte não está no triângulo direito 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
caixa de papelão
fonte
É -1 -3 1 1uma entrada válida?
Xnor 17/05
Sim, essa é uma entrada válida. Adicionei casos de teste para deixar isso claro.
cardboard_box

Respostas:

5

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

Uma boa maneira de verificar se a associação de vedação está feia. Se tivéssemos a garantia de que as entradas não são negativas e no quadrado da unidade, teríamos 38:

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

A idéia é que verifiquemos se um ponto está dentro da gaxeta, verificando se a sua fração binária se expande bit a bit-AND para 0. Para obter o primeiro kcaractere da expansão, alteramos os kbits do numerador deixados antes da divisão do número inteiro pelo denominador . Precisamos fazer o ksuficiente para capturar uma repetição. Observamos que a expansão binária n/dtem um período no máximo d, portanto as expansões conjuntas têm um período no máximo d*D, o que k=d*Dé suficiente.

O resto é verificar se a fração está na caixa e isolar as entradas fornecidas como -1/-3.

xnor
fonte