¿Está dentro del conjunto de Cantor?

20

El reto

Para este desafío, se supone que debes determinar si un número dado está en el conjunto de Cantor. Primero, definamos el conjunto de Cantor.

Primero, comience con los números entre 0 y 1. Cualquier número fuera de este rango no está en el conjunto de Cantor. Ahora, dividamos los números en tres partes iguales: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Cualquier número que no esté dentro de los rangos de la primera y última parte no está en el conjunto de Cantor. Ahora, repite este proceso para los segmentos [0,1 / 3] y [2/3, 1]. Luego repites lo que sobra. Sigues haciendo esto para siempre. Al final, todos los números restantes están en el conjunto de Cantor. Aquí hay un diagrama de las primeras seis iteraciones:

Diagrama de Cantor


Entrada

Dos enteros xy y.
0 < y < 2^15
0 <= x <= y
El máximo común denominador de xy yes 1, a menos que x == 0.


Salida

Verdad si x/yestá en el conjunto de Cantor.
Falsy si x/yno está en el conjunto de Cantor.


Ejemplos

Ahora, veamos algunos ejemplos de números que están en el conjunto de Cantor.

1/3 -> true  

Está en un límite, y los límites nunca se eliminan.

1/4 -> true  

1/4nunca está en el tercio medio de un segmento, aunque tampoco está en el límite tampoco. Si sigues su camino, en realidad encontrarás que alterna entre estar en el primer y último tercio de una sección.

1/13 -> true  

1/13 alterna entre la primera, primera y última sección.

1/5 -> false

1/5 cae en el primer bloque vacío de la tercera fila en el diagrama anterior, entre 1/9 y 2/9.

Otros casos de prueba:

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

Puedes probar otros números con este fragmento:


Objetivo

La persona con menos bytes gana.

El numero uno
fuente
¿Estamos garantizados de que la entrada no es (0,0)? ¿La fracción se da en la forma más simple?
xnor
1
@xnor mira el rango dado para y. Voy a decir que la fracción está en forma más simple a menos quex == 0
TheNumberOne
Algunos casos de prueba donde x! = 1 sería bueno. Además, su fragmento dice que 1/3 no está en el conjunto de cantor.
xnor
@xnor Agregado y arreglado;)
TheNumberOne
66
Cantor se puede encontrar?
mbomb007 01 de

Respuestas:

13

Mathematica, 54 bytes

If[Last@#===1,Most@#,#]&@RealDigits[#,3][[1]]~FreeQ~1&

Función sin nombre que toma una fracción x/ycomo entrada, donde y > 0y 0 ≤ x ≤ y, y regresa Trueo False.

Un número real entre 0 y 1 está en el conjunto de Cantor precisamente cuando ninguno de los dígitos en su expansión de base 3 es igual a 1; la excepción es que una fracción cuyo denominador es una potencia de 3 (cuya expansión de base-3 por lo tanto termina) puede terminar en 1.

RealDigits[#,3][[1]]da todos los dígitos en la expansión de base 3 de la entrada fraccional #, en una forma como {1, 0, 2, {0, 1, 0, 2}}: la última lista es la parte periódica de la expansión, mientras que los enteros de antemano son los dígitos antes de que comience la periodicidad. Si la expansión de base-3 es periódica de inmediato, la salida es como {{0, 1, 0, 2}}; si la expansión de base 3 termina, la forma es como {1, 0, 2}.

Por lo tanto, queremos verificar, utilizando ~FreeQ~1, si la lista está libre de 1s o no. Sin embargo, debido a la expansión final, queremos eliminar el último elemento de la lista si es igual 1; eso es lo que If[Last@#===1,Most@#,#]logra. (Se ===necesita para comparar una lista potencial con 1: ==solo permanece sin evaluar en esa situación).

Greg Martin
fuente
44
Me sorprende que Mathematica no tenga IsCantorNumberpero tiene una función para determinar si algo es una cabra .
Brain Guider
3
Bueno, no sé, ¿cuáles surgen más en la vida real: cabras o fractales? ;)
Greg Martin
FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
ngenisis
Tal regla también eliminaría los 1s finales en la parte periódica, lo que lleva a respuestas incorrectas. Por ejemplo, la expansión de base 3 de 7/8 es .21212121 ...., o {{2,1}}; pero la regla sugerida cambiaría eso a {{2}}, que está libre de 1s pero no debería serlo.
Greg Martin
Touché ¿Qué tal #==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&? Si está terminando y no RealDigits[#,3]será cero de la forma {{__Integer},-1}y si está repitiendo, será de la forma {{___Integer,{__Integer}},-1}, ¿verdad? Estoy en el móvil, así que es difícil de probar en este momento. Si esto funciona, utilizar la notación infija para también RealDigitspodría funcionar.
ngenisis
9

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;}

Explota la simetría del conjunto de Cantor. Se rompe después de las yiteraciones para evitar un bucle infinito.

Pruébalo en línea!

nwellnhof
fuente
7

Gelatina , 22 17 16 15 bytes

,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ

Huellas dactilares 3 para la verdad, nada para la falsedad.

Pruébalo en línea!

Antecedentes

Una propiedad bien conocida del conjunto de Cantor es que contiene precisamente aquellos números entre 0 y 1 que se pueden escribir sin 1 en su expansión ternaria.

Tenga en cuenta que algunos números, precisamente los bordes derechos de los intervalos cerrados involucrados en la construcción del conjunto, se pueden escribir con un solo (final) 1 o con una cantidad infinita de 2 finales . Por ejemplo, 1 = 1 3 = 0.22222 ... 3 y 1/3 = 0.1 3 = 0.022222 ... 3 , igual que 0.5 10 = 0.499999 ... 10 .

Para evitar el revestimiento especial de los bordes derechos, podemos verificar si 1 es la expansión decimal más corta tanto en x / y como en 1 - x / y = (y - x) / y , donde x / y es un borde derecho si (y - x) / y es un borde izquierdo. Si al menos uno de ellos no contiene 1 , x / y pertenece al conjunto de Cantor.

Cómo funciona

,ạµ%⁹×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].
Dennis
fuente
3es el verdadero true+1.
Urna mágica del pulpo
3

JavaScript (ES6), 65 67

Editar 2 bytes guardados gracias a @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

Menos golf

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
}

Prueba

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

edc65
fuente
Creo que puedes reemplazar n=n%d*3con q=n/d|0y luego reemplazar z[n]conz[n=n%d*3]
Luke
2

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

Úselo al curry primero en el denominador y luego en el numerador. La forma estándar es un byte más largo:

f=(x,y,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,y,z|q==1,n+1):1

Explicación

Si una fracción no está en el conjunto de Cantor, debe caer en una de las secciones centrales en algún momento; por lo tanto, su representación en la base 3 debe contener un 1 seguido en algún punto por un dígito distinto de cero. Así es como funciona esto:

  • z realiza un seguimiento de si hemos encontrado un 1.
  • q es el dígito actual en la base 3.
  • !z|!qes verdadero si zes falso (no hemos encontrado un 1) oq es falso (el dígito actual es 0).

Si nse reduce a cero antes de encontrar un dígito distinto de cero en algún lugar después de un 1, la fracción está en el conjunto de Cantor y regresamos 1.

ETHproducciones
fuente
2

Bash + utilidades GNU, 62 bytes

dc -e3o9d$2^$1*$2/p|tr -cd 012|grep -P "1(?!(0{$2,}|2{$2,})$)"

Pruébalo en línea!

Pásalo dos argumentos enteros con arg1 <= arg2 y 0 <arg2.

La salida se devuelve en el código de salida (0 para falso, 1 para verdadero), según lo permitido por los métodos de E / S PPCG .

Sospecho que la expresión regular se puede jugar más, incluso eliminando el comando tr a favor de usar grep -z, pero este es el más corto que he podido encontrar. (Desafortunadamente, grep -z es incompatible con grep -P, y la opción -P para obtener expresiones regulares de estilo perl es necesaria para la sintaxis?!).

Programa de prueba y salida:

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

Explicación

parte dc (los argumentos son x e 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.

parte tr y grep:

Un problema menor es que, aunque dc maneja enteros arbitrariamente grandes, cuando dc imprime un número grande, lo dividirá en líneas de 69 caracteres, con cada línea excepto la última que termina con una barra diagonal inversa, y con una nueva línea después de cada línea.

El comando tr elimina cualquier barra diagonal inversa y nueva línea. Esto deja solo una línea.

El comando grep luego usa una expresión regular de estilo perl (opción -P, que es una extensión GNU). La expresión regular coincide si la línea contiene un 1 no seguido de al menos y 0 o al menos y 2, que luego finalizan la cadena.

Esto es exactamente lo que se necesita para identificar que x / y no está en el conjunto de Cantor, porque la parte repetida de la representación de base 3 del número racional x / y puede verse como comenzando en el dígito # y + 1 después del punto ternario , y tiene como máximo y dígitos de largo.

Mitchell Spector
fuente
1

CJam (19 bytes)

{_@3@#*\/3b0-W<1&!}

Conjunto de pruebas en línea

Este es un bloque anónimo (función) que toma dos argumentos en la pila y se va 0o 1en la pila. Funciona convirtiendo la fracción x/yen dígitos de ybase 3y devolviendo verdadero si no contienen 1o el único 1es parte de un sufijo 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
}
Peter Taylor
fuente
1

Pyth , 14 bytes

gu*3hS,G-QGQE0

Basado en mi solución C. yen la primera línea de entrada, xen la segunda.

                Q = y
 u         QE   G = x
                loop y times
  *3                x = 3 *
    hS,G                min(x,
        -QG                 y-x)
g            0  return x >= 0

Si x/yestá dentro del conjunto de Cantor, xpermanece entre 0y y. De lo contrario, se xvuelve mayor que yen un punto, luego diverge al infinito negativo en las iteraciones restantes.

Pruébalo en línea!

nwellnhof
fuente
0

Lote, 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%

Prueba la primera y-1base de 3 dígitos de x/y. ies el recuento de dígitos probados. nes el siguiente valor de x. jes cierto si nllega a cero (porque la expansión termina) o hemos probado y-1dígitos sin encontrar a 1. fes verdadero si jes verdadero o si el siguiente dígito es a 1, en cuyo punto dejamos de hacer bucles y de salida j.

Neil
fuente