Le triangle de Sierpinski est un ensemble de points sur le plan qui est construit en commençant par un seul triangle et en divisant à plusieurs reprises tous les triangles en quatre triangles congruents et en supprimant le triangle central. Le triangle de Sierpinski droit a des coins à (0,0), (0,1)et (1,0), et ressemble à ceci:

Certaines définitions équivalentes de cet ensemble sont les suivantes:

• Points dans l' nitération du processus décrit ci-dessus, pour tous n.

• Points (x,y)avec 0 <= x <= 1et 0 <= y <= 1tels que pour tous les entiers positifs n, le nbit e dans l'expansion binaire de x et y ne soit pas les deux 1.

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

  Soit fune fonction sur des ensembles de points 2D définis par ce qui suit:

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

  Ensuite, le triangle de Sierpinski droit est la fermeture topologique du point le moins fixe (par confinement défini) de f.

• Soit Sle carré{(x,y) | 0<=x<=1 and 0<=y<=1}

  Soit g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}(où Test tel que défini ci-dessus)

  Ensuite, le triangle de Sierpinski droit est le plus grand point fixe de g.

Défi

Écrivez un programme ou une fonction qui accepte 4 entiers, a,b,c,det donne une valeur vraie si elle (a/b,c/d)appartient au triangle de Sierpinski droit, et sinon donne une valeur de falsey.

Notation

Ceci est un golf de code. Le code le plus court en octets gagne.

Cas de test

Les éléments suivants sont dans le triangle de Sierpinski droit:

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

Les éléments suivants ne sont pas dans le triangle de Sierpinski droit:

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

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

Une belle façon de vérifier que l'adhésion au joint est moche. Si on nous garantissait que les entrées sont non négatives et dans le carré unitaire, nous aurions 38:

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

L'idée est que nous vérifions si un point se trouve dans le joint en vérifiant si leur expansion binaire bit à bit ET à 0. Pour obtenir le premier kcaractère de l'expansion, nous décalons les kbits du numérateur à gauche avant la division entière par le dénominateur . Nous devons faire ksuffisamment grand pour attraper une répétition. Nous notons que l'expansion binaire n/da une période au plus d, donc les expansions conjointes ont une période au plus d*D, donc cela k=d*Dsuffit.

Le reste consiste à vérifier si la fraction est dans la boîte et à l'isoler des entrées données comme -1/-3.