Le défi

Pour ce défi, vous êtes censé déterminer si un nombre donné se trouve dans l'ensemble Cantor. Définissons donc d'abord l'ensemble Cantor.

Commencez d'abord par les nombres compris entre 0 et 1. Tout nombre en dehors de cette plage ne se trouve pas dans l'ensemble Cantor. Maintenant, divisons les nombres en trois parties égales: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Tous les nombres ne se trouvant pas dans les plages des première et dernière parties ne sont pas dans l'ensemble Cantor. Maintenant, vous répétez ce processus pour les segments [0,1 / 3] et [2/3, 1]. Ensuite, vous répétez ce qui reste. Vous continuez à faire ça pour toujours. En fin de compte, tous les numéros qui restent sont dans l'ensemble Cantor. Voici un diagramme des six premières itérations:

Contribution

Deux entiers xet y.
0 < y < 2^15
0 <= x <= y
Le plus grand dénominateur commun de xet yest 1, sauf x == 0.

Production

Truthy if x/yest dans l'ensemble Cantor.
Falsy si x/yn'est pas dans l'ensemble Cantor.

Exemples

Voyons maintenant quelques exemples de nombres qui se trouvent dans l'ensemble Cantor.

1/3 -> true  

Il se trouve sur une frontière et les frontières ne sont jamais supprimées.

1/4 -> true  

1/4n'est jamais dans le tiers médian d'un segment, bien qu'il ne soit jamais sur la frontière non plus. Si vous suivez son chemin, vous constaterez qu'il alterne entre le premier et le dernier tiers d'une section.

1/13 -> true  

1/13 alterne entre les première, première et dernière sections.

1/5 -> false

1/5 tombe dans le premier bloc vide de la troisième ligne du diagramme ci-dessus, entre 1/9 et 2/9.

Autres cas de test:

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

Vous pouvez essayer d'autres numéros avec cet extrait:

function isCantor(t,r){var n=new Set;if(0>r)return isCantor(-t,-r);if(0==r)return!1;if(0>t||t>r)return!1;for(;;){if(t%r===0)return!0;if(1===Math.floor(t/r))return!1;if(n.has(t))return!0;n.add(t),t=t%r*3}}$("#test").click(function(){var t=parseInt($("#x").val()),r=parseInt($("#y").val());if(isNaN(t)||isNaN(r)||0==r)return void $("#result").text("Invalid input");var n=isCantor(t,r),i=(n?"I":"Not i")+"n the Cantor set.";$("#result").text(i)});

input{width:30px}button{margin-left:7px}

<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><input id=x>/<input id=y><button id=test>Test</button><p id=result>

Objectif

La personne avec le moins d'octets gagne.

Mathematica, 54 octets

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

Fonction sans nom prenant une fraction x/yen entrée, où y > 0et 0 ≤ x ≤ y, et renvoyant TrueouFalse .

Un nombre réel compris entre 0 et 1 est dans l'ensemble Cantor précisément quand aucun des chiffres de son expansion en base 3 n'est égal à 1; l'exception est qu'une fraction dont le dénominateur est une puissance de 3 (dont l'expansion en base 3 se termine donc) peut se terminer par un 1.

RealDigits[#,3][[1]]donne tous les chiffres de l'expansion en base 3 de l'entrée fractionnelle #, sous une forme comme {1, 0, 2, {0, 1, 0, 2}}: la dernière liste est la partie périodique de l'expansion, tandis que les nombres entiers au préalable sont les chiffres avant le début de la périodicité. Si l'expansion de la base 3 est périodique immédiatement, la sortie est similaire {{0, 1, 0, 2}}; si l'expansion en base 3 se termine, la forme est similaire {1, 0, 2}.

Nous voulons donc vérifier, en utilisant ~FreeQ~1, si la liste est exempte de 1s ou non. Cependant, en raison de la fin de l'extension, nous voulons supprimer le dernier élément de la liste s'il est égal 1; c'est ce qui If[Last@#===1,Most@#,#]accomplit. (Le ===est nécessaire pour comparer une liste potentielle avec 1: ==seul reste non évalué dans cette situation.)

C (gcc) , 61 59 58 octets

f(x,y,i){for(i=y;i--&&x<y;)x=(y-x<x?y-x:x)*3;return x<=y;}

Exploite la symétrie de l'ensemble Cantor. Interrompt les yitérations pour éviter une boucle infinie.

Essayez-le en ligne!

Gelée , 22 17 16 15 octets

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

Imprime 3 pour la vérité, rien pour la fausse.

Essayez-le en ligne!

Contexte

Une propriété bien connue de l'ensemble Cantor est qu'il contient précisément les nombres entre 0 et 1 qui peuvent être écrits sans 1 dans leur expansion ternaire.

Notez que certains nombres - précisément les bords droits des intervalles fermés impliqués dans la construction de l'ensemble - peuvent être écrits soit avec un seul (fin) 1 soit avec une quantité infinie de 2 fin . Par exemple, 1 = 1 ₃ = 0,22222… ₃ et 1/3 = 0,1 ₃ = 0,022222… ₃ , tout comme 0,5 ₁₀ = 0,499999… ₁₀ .

Pour éviter de placer un boîtier spécial sur les bords droits, nous pouvons vérifier que 1 est l'expansion décimale la plus courte à la fois dans x / y et 1 - x / y = (y - x) / y , où x / y est un bord droit ssi (y - x) / y est un bord gauche. Si au moins l'un d'entre eux ne contient aucun 1 , x / y appartient à l'ensemble Cantor.

Comment ça fonctionne

,ạµ%⁹×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].

JavaScript (ES6), 65 67

Modifier 2 octets enregistrés 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

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

Tester

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

JavaScript (ES6), 55 octets

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

À utiliser au curry dans le dénominateur en premier et le numérateur en second. Le formulaire standard est un octet plus long:

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

Explication

Si une fraction n'est pas dans l'ensemble Cantor, elle doit tomber dans l'une des sections centrales à un moment donné; par conséquent, sa représentation dans la base 3 doit contenir un 1 suivi à un moment donné d'un chiffre non nul. Voilà comment cela fonctionne:

• z garde une trace de si nous avons trouvé un 1.
• q est le chiffre actuel de la base 3.
• !z|!qest vrai si zest faux (nous n'avons pas trouvé de 1) ou qest faux (le chiffre actuel est 0).

Si ndescend jusqu'à zéro avant de trouver un chiffre différent de zéro quelque part après un 1, la fraction est dans l'ensemble de Cantor et nous revenons 1.

Utilitaires Bash + GNU, 62 octets

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

Essayez-le en ligne!

Passez-lui deux arguments entiers avec arg1 <= arg2 et 0 <arg2.

La sortie est retournée dans le code de sortie (0 pour la fausse, 1 pour la vérité), comme autorisé par les méthodes d'E / S PPCG .

Je soupçonne que l'expression régulière peut être jouée plus loin, peut-être même en éliminant la commande tr en faveur de l'utilisation de grep -z, mais c'est la plus courte que j'ai pu trouver. (Malheureusement, grep -z n'est pas compatible avec grep -P, et l'option -P pour obtenir des expressions rationnelles de style perl est requise pour la syntaxe?!).

Programme et sortie du banc d'essai:

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

Explication

partie dc (les arguments sont x et 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.

partie tr et grep:

Un problème mineur est que, bien que dc gère des entiers arbitrairement grands, lorsque dc imprime un grand nombre, il le décompose en lignes de 69 caractères, chaque ligne sauf la dernière se terminant par une barre oblique inverse et une nouvelle ligne après chaque ligne.

La commande tr supprime toutes les barres obliques inverses et les sauts de ligne. Cela ne laisse qu'une seule ligne.

La commande grep utilise ensuite une expression régulière de style perl (option -P, qui est une extension GNU). La regex correspond si la ligne contient un 1 non suivi d'au moins y 0 ou au moins y 2 qui terminent ensuite la chaîne.

C'est exactement ce qui est nécessaire pour identifier x / y comme n'étant pas dans l'ensemble de Cantor, car la partie répétitive de la représentation en base 3 du nombre rationnel x / y peut être considérée comme commençant au chiffre # y + 1 après le point ternaire et comporte au plus y chiffres.

CJam (19 octets)

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

Suite de tests en ligne

Il s'agit d'un bloc (fonction) anonyme qui prend deux arguments sur la pile et quitte 0ou 1sur la pile. Il fonctionne par la base convertissant la fraction x/yen ybase de 3chiffres et de retourner vrai ssi ils ne contiennent pas 1ou le seul 1fait partie d'un suffixe 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
}

Pyth , 14 octets

gu*3hS,G-QGQE0

Basé sur ma solution C. ysur la première ligne d'entrée, xsur la seconde.

                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 se x/ytrouve dans l'ensemble Cantor, xreste entre 0et y. Sinon, xdevient plus grand qu'à yun moment donné, puis diverge vers l'infini négatif dans les itérations restantes.

Essayez-le en ligne!

Lot, 91 octets

@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%

Teste les y-13 premiers chiffres de la base x/y. iest le nombre de chiffres testés. nest la prochaine valeur de x. jest vrai si natteint zéro (car l'expansion se termine) ou si nous avons testé des y-1chiffres sans trouver a 1. fest vrai si jest vrai ou si le chiffre suivant est un1 , auquel point nous arrêtons la boucle et la sortie j.