Está dentro do conjunto Cantor?

20

O desafio

Para esse desafio, você deve determinar se um determinado número está no conjunto Cantor. Então, primeiro, vamos definir o conjunto Cantor.

Primeiro, comece com os números entre 0 e 1. Quaisquer números fora desse intervalo não estão no conjunto Cantor. Agora, vamos dividir os números em três partes iguais: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Quaisquer números fora dos intervalos da primeira e da última parte não estão no conjunto Cantor. Agora, repita esse processo para os segmentos [0,1 / 3] e [2/3, 1]. Então você repete o que resta. Você continua fazendo isso para sempre. No final, todos os números restantes estão no conjunto Cantor. Aqui está um diagrama das seis primeiras iterações:

Diagrama do Cantor


Entrada

Dois inteiros xe y.
0 < y < 2^15
0 <= x <= y
O maior denominador comum de xe yé 1, a menos que x == 0.


Saída

Verdadeiramente se x/yestiver no conjunto Cantor.
Falsy se x/ynão estiver no conjunto Cantor.


Exemplos

Agora, vamos ver alguns exemplos de números que estão no conjunto Cantor.

1/3 -> true  

Está em um limite, e os limites nunca são removidos.

1/4 -> true  

1/4nunca está no terço médio de um segmento, embora também nunca esteja no limite. Se você seguir o caminho, descobrirá que ele alterna entre estar no primeiro e no último terço de uma seção.

1/13 -> true  

1/13 alterna entre a primeira, a primeira e a última seção.

1/5 -> false

1/5 cai no primeiro bloco vazio da terceira linha no diagrama acima, entre 1/9 e 2/9.

Outros casos de teste:

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

Você pode tentar outros números com este trecho:


Objetivo

A pessoa com menos bytes vence.

O número um
fonte
Temos a garantia de que a entrada não é (0,0)? A fração é dada na forma mais simples?
Xnor
1
@xnor veja o intervalo fornecido para y. Eu vou dizer que a fração for na forma mais simples, a menosx == 0
TheNumberOne
Alguns casos de teste em que x! = 1 seriam bons. Além disso, seu snippet diz que 1/3 não está no conjunto de cantor.
Xnor
@xnor Adicionado e corrigido;)
TheNumberOne
6
Cantor pode ser encontrado?
Mbomb007

Respostas:

13

Mathematica, 54 bytes

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

Função sem nome, tendo uma fração x/ycomo entrada, onde y > 0e 0 ≤ x ≤ y, e retornando Trueou False.

Um número real entre 0 e 1 está no conjunto Cantor precisamente quando nenhum dos dígitos em sua expansão base-3 é igual a 1; a exceção é que uma fração cujo denominador é uma potência de 3 (cuja expansão da base 3 termina portanto) pode terminar em 1.

RealDigits[#,3][[1]]fornece todos os dígitos na expansão base-3 da entrada fracionária #, de uma forma como {1, 0, 2, {0, 1, 0, 2}}: a última lista é a parte periódica da expansão, enquanto os números inteiros anteriormente são os dígitos antes do início da periodicidade. Se a expansão da base 3 for periódica imediatamente, a saída será semelhante {{0, 1, 0, 2}}; se a expansão da base 3 terminar, o formulário será semelhante {1, 0, 2}.

Então, queremos verificar, usando ~FreeQ~1, se a lista está livre de 1s ou não. No entanto, devido à expansão da expansão, queremos excluir o último elemento da lista, se for igual 1; é isso que If[Last@#===1,Most@#,#]realiza. (O ===necessário para comparar uma lista potencial com 1: ==sozinho permanece sem avaliação nessa situação.)

Greg Martin
fonte
4
Estou surpreso que o Mathematica não tenha, IsCantorNumbermas tenha uma função para determinar se algo é uma cabra .
Brain Guider
3
Bem, eu não sei, que surgem mais na vida real: cabras ou fractais? ;)
Greg Martin
FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
Ngenisis
Essa regra também excluiria os rastros 1s na parte periódica, o que leva a respostas incorretas. Por exemplo, a expansão base-3 de 7/8 é .21212121 ...., ou {{2,1}}; mas a regra sugerida mudaria isso para {{2}}, que é livre de 1s, mas não deveria ser.
22717 Greg Greg
Touché. Que tal #==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&? Se estiver terminando e diferente de zero RealDigits[#,3]for do formato {{__Integer},-1}e se estiver repetindo, será do formato {{___Integer,{__Integer}},-1}, certo? Estou no celular, por isso é difícil testar agora. Se isso funcionar, o uso da notação infix também RealDigitspode 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;}

Explora a simetria do conjunto Cantor. Interrompe após yiterações para evitar um loop infinito.

Experimente online!

Nwellnhof
fonte
7

Geléia , 22 17 16 15 bytes

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

Imprime 3 por verdade, nada por falsidade.

Experimente online!

fundo

Uma propriedade bem conhecida do conjunto Cantor é que ele contém precisamente aqueles números entre 0 e 1 que podem ser escritos sem 1 na expansão ternária.

Observe que alguns números - precisamente as bordas direitas dos intervalos fechados envolvidos na construção do aparelho - podem ser escritos com um único (final) 1 ou com uma quantidade infinita de 2 finais . Por exemplo, 1 = 1 3 = 0,22222… 3 e 1/3 = 0,1 3 = 0,022222… 3 , assim como 0,5 10 = 0,499999… 10 .

Para evitar especial de carcaça as bordas direitas, podemos verificar a existência de um 'S é a expansão mais curto decimal em ambos x / y e 1 - X / Y = (y - x) / y , onde x / y é um sse borda direita (y - x) / y é uma aresta esquerda. Se pelo menos um deles não contém 1 , x / y pertence ao conjunto Cantor.

Como 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
fonte
3é o verdadeiro true+1.
Octopus Magic Urn
3

JavaScript (ES6), 65 67

Editar 2 bytes salvos thx @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 golfe

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
}

Teste

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
fonte
Eu acho que você pode substituir n=n%d*3por q=n/d|0e, em seguida, substituir z[n]porz[n=n%d*3]
Luke 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

Use currying no denominador primeiro e no numerador segundo. O formulário padrão é um byte mais longo:

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

Explicação

Se uma fração não estiver no conjunto Cantor, ela deverá cair em uma das seções do meio em algum momento; portanto, sua representação na base 3 deve conter um 1 seguido em algum momento por um dígito diferente de zero. É assim que isso funciona:

  • z controla se encontramos 1.
  • q é o dígito atual na base 3.
  • !z|!qé verdadeiro se zfor falso (não encontramos 1) ou qfor falso (o dígito atual é 0).

Se ndescer para zero antes de encontrarmos um dígito diferente de zero em algum lugar após 1, a fração estará no conjunto Cantor e retornaremos 1.

ETHproductions
fonte
2

Utilitários Bash + GNU, 62 bytes

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

Experimente online!

Passe dois argumentos inteiros com arg1 <= arg2 e 0 <arg2.

A saída é retornada no código de saída (0 para falsy, 1 para truthy), conforme permitido pelos métodos de E / S do PPCG .

Eu suspeito que o regex pode ser jogado ainda mais, talvez até mesmo eliminando o comando tr em favor do grep -z, mas esse é o menor tempo que eu consegui. (Infelizmente, grep -z é incompatível com grep -P, e a opção -P para obter expressões regulares no estilo perl é necessária para a sintaxe?!).

Programa e saída do teste:

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

Explicação

parte dc (os argumentos são xey):

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 e grep:

Um problema menor é que, embora o dc lide com números inteiros arbitrariamente grandes, quando o dc imprime um número grande, ele o divide em linhas de 69 caracteres, com cada linha exceto a última que termina com uma barra invertida e com uma nova linha após cada linha.

O comando tr exclui barras invertidas e novas linhas. Isso deixa apenas uma única linha.

O comando grep usa um regex no estilo perl (opção -P, que é uma extensão GNU). A regex corresponde se a linha contiver 1 não seguido por pelo menos y 0 ou pelo menos y 2, que terminam a sequência.

É exatamente isso que é necessário para identificar x / y como não estando no conjunto Cantor, porque a parte repetitiva da representação base-3 do número racional x / y pode ser vista como começando no dígito # y + 1 após o ponto ternário , e tem no máximo y dígitos.

Mitchell Spector
fonte
1

CJam (19 bytes)

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

Conjunto de testes online

Este é um bloco anônimo (função) que recebe dois argumentos na pilha e sai 0ou 1na pilha. Ele funciona convertendo a fração x/yem dígitos ybase 3e retornando true se eles não contêm 1ou a única 1parte de um sufixo 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
fonte
1

Pitão , 14 bytes

gu*3hS,G-QGQE0

Com base na minha solução C. yna primeira linha de entrada, xna 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

Se x/yestiver dentro do conjunto Cantor, xpermanece entre 0e y. Caso contrário, xtorna-se maior que yem um ponto e diverge para o infinito negativo nas iterações restantes.

Experimente online!

Nwellnhof
fonte
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%

Testa os primeiros y-13 dígitos da base x/y. ié a contagem de dígitos testados. né o próximo valor de x. jé verdadeiro se natingir zero (porque a expansão termina) ou testamos y-1dígitos sem encontrar a 1. fé verdadeiro se jfor verdadeiro ou se o próximo dígito for a 1; nesse ponto, paramos o loop e a saída j.

Neil
fonte