Mon numéro est-il unique

21

Dans ce défi, nous avons appris un moyen de coder chaque entier positif en utilisant des arbres de facteurs.

Voici comment cela fonctionne:

  • La chaîne vide a la valeur 1.

  • (S)Sest toute expression avec une valeur de S évaluée au S ème premier.

  • ABAet Bsont des expressions arbirary avec des valeurs de A et B a respectivement la valeur A * B .

Par exemple, si nous voulions représenter 7, nous ferions

  7 -> (4) -> (2*2) -> ((1)(1)) -> (()())

Il s'avère que nous pouvons représenter chaque nombre entier en utilisant cette méthode. En fait, certains chiffres que nous pouvons représenter de plusieurs façons. Parce que la multiplication est commutative, 10 est à la fois

((()))()

et

()((()))

En même temps, certains nombres ne peuvent être représentés que d'une seule manière. Prenez 8 par exemple. 8 ne peut être représenté que

()()()

Et puisque tous nos atomes sont les mêmes, nous ne pouvons pas utiliser la commutativité pour les réorganiser.


Alors maintenant, la question est "Quels nombres ne peuvent être représentés que d'une seule façon?". La première observation est celle que je viens de commencer à faire là-bas. Il semble que les pouvoirs parfaits aient des propriétés spéciales. En approfondissant les recherches, nous pouvons trouver 36, ce qui est 6 2 est une puissance parfaite mais a de multiples représentations.

(())()(())()
(())()()(())
()(())()(())
()(())(())()
()()(())(())

Et cela a du sens parce que 6 est déjà réorganisable, donc tout nombre que nous faisons sur 6 doit également être réorganisable.

Alors maintenant, nous avons une règle:

  • Un nombre a une représentation unique s'il s'agit d'une puissance parfaite d'un nombre avec une représentation unique.

Cette règle peut nous aider à réduire la détermination si un nombre composé est unique à déterminer si un nombre premier est unique. Maintenant que nous avons cette règle, nous voulons comprendre ce qui rend un nombre premier unique. C'est en fait assez évident. Si nous prenons un nombre unique et l'enveloppons entre parenthèses, le résultat doit être unique et, dans le sens contraire si n a plusieurs représentations, le n e premier doit avoir plusieurs représentations. Cela donne la deuxième règle:

  • Le n e premier est unique si et seulement si n est unique.

Ces deux règles sont récursives, nous allons donc avoir besoin d'un cas de base. Quel est le plus petit numéro unique? On pourrait être tenté de dire 2 parce que c'est juste (), mais 1, la chaîne vide, est encore plus petite et unique.

  • 1 est unique.

Avec ces trois règles, nous pouvons déterminer si un nombre a un arbre de facteurs unique.

Tâche

Vous l'avez peut-être vu venir, mais votre tâche consiste à prendre un entier positif et à déterminer s'il est unique. Vous devez écrire un programme ou une fonction qui effectue ce calcul. Vous devez sortir l'une des deux valeurs possibles, ce que ces valeurs sont à vous, mais l'une devrait représenter "oui", étant sortie lorsque l'entrée est unique et l'autre devrait représenter "non" étant sortie autrement.

Vos réponses doivent être notées en octets avec moins d'octets mieux.

Cas de test

Voici les deux premiers numéros uniques:

1
2
3
4
5
7
8
9
11
16
17
19
23
25
27
31

Cas de test suggérés

5381 -> Unique

Il semble que OEIS A214577 soit en quelque sorte lié, donc si vous avez besoin de plus de cas de test, essayez-le, mais je ne sais pas ce sont les mêmes, alors utilisez-le à vos risques et périls.

Assistant de blé
la source
Je crois que les facteurs premiers devaient être triés mais peu importe.
Nissa
1
@JonathanAllan non, tout est là.
Nissa
Cas de test suggéré: 5381
Nissa
@StephenLeppik Test case ajouté, merci.
Wheat Wizard
1
@ H.PWiz Je vais dire qu'un programme complet peut faire une erreur en sortie car c'est une forme de sortie pour un programme, mais une fonction doit retourner une valeur.
Wheat Wizard

Réponses:

9

Husk , 11 10 octets

Un octet enregistré grâce à Zgarb!

Ωεo?oṗ←¬Ep

Retourne 1pour unique, 0sinon

Essayez-le en ligne! Ou retourner les 50 premiers

Explication:

Ωε              Until the result is small (either 1 or 0), we repeat the following
         p     Get the prime factors
  o?           If ...
        E      they are all equal:
    ȯṗ←           Get the index of the first one into the primes
               Else:
       ¬          Not the list (since non-empty lists are truthy, this returns 0)
H.PWiz
la source
Oh, et votre explication dit " ȯp←".
Erik the Outgolfer
@EriktheOutgolfer Good catch, fixed
H.PWiz
Je pense que cela ṁ¬peut être juste ¬car la liste doit être non vide dans cette branche.
Zgarb
@Zgarb Oh fantaisie, je pense que vous m'avez déjà donné cette astuce avant
H.PWiz
7

Gelée , 10 octets

Après BEAUCOUP de tripoter!

ÆET0ṪḊ?µl¿

Un lien monadique prenant un entier positif et retournant 1s'il est unique ou 0sinon.

Essayez-le en ligne!

Comment?

ÆET0ṪḊ?µl¿ - Link: number, n     e.g. 11          or 13            or 20
         ¿ - while:
        l  - ...condition: (left) logarithm with base (right)
           -               note: x log 0 and x log 1 both yield None, which is falsey
       µ   - ...do the monadic chain: (first pass shown)
ÆE         -   prime exponent array   [0,0,0,0,1]    [0,0,0,0,0,1]    [2,0,1]
  T        -   truthy indexes         [5]            [6]              [1,3]
      ?    -   if:
     Ḋ     -   ...condition: dequeue (i.e. if length > 1)
   0       -   ...then: literal zero   -              -               0
    Ṫ      -   ...else: tail           5              6               -
           - end result                1              0               0

Attendez, logarithme, quoi?!

Permet de parcourir quelques exemples de la boucle.

Si n=31( 31 1 , onzième nombre premier):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |       31 |        31 |    1.000 -> continue
         2 |       11 |        31 |    0.698 -> continue
         3 |        5 |        11 |    0.671 -> continue
         4 |        3 |         5 |    0.683 -> continue
         5 |        2 |         3 |    0.631 -> continue
         6 |        1 |         2 |    0.000 -> stop, yielding left = 1

Si n=625( 5 4 ):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |      625 |       625 |    1.000 -> continue
         2 |        3 |       625 |    0.171 -> continue
         3 |        2 |         3 |    0.631 -> continue
         4 |        1 |         2 |    0.000 -> stop, yielding left = 1

Si n=225( 5 2 × 3 2 ):

log test # |  left, x |  right, b |  x log b
-----------+----------+-----------+----------
         1 |      225 |       225 |    1.000 -> continue
         2 |     *  0 |       225 |-inf+nanj -> continue
         3 |     ** 0 |         0 |     None -> stop, yielding left = 0

*The dequeued list was not empty
**Tailing an empty list in Jelly yields 0
Jonathan Allan
la source
4

APL (Dyalog) , 42 octets

CY'dfns'
{1≥⍵:11=≢∪r3pco⍵:∇11pcor0}

L'utilisation ⎕CY'dfns'avec dfnses n'est pas très faisable sur tio.

Uriel
la source
Ma réponse est assez similaire à la vôtre, bien que j'aie écrit la première version il y a environ 4 heures
H.PWiz
@ H.PWiz regarde mec, je m'en fiche vraiment quand les gens soumettent dans la même langue, même si je préfère généralement commenter quand je trouve une solution plus courte, mais c'est presque la même chose. Cela ne me dérange pas que vous le gardiez, mais je trouve les réponses qui semblent les mêmes assez inutiles. À propos du timing - c'est comme ça que ça fonctionne. J'ai laissé tomber des dizaines de réponses parce que quelqu'un d'autre est venu en premier. Je le fais (et je crois le reste) pour le plaisir, pas pour une vraie compétition.
Uriel
Désolé d'avoir mis si longtemps à y arriver, mais j'ai supprimé ma réponse. Avec le recul, un commentaire semble avoir été plus approprié. Je pense que, comme j'étais nouveau à APL à l'époque, une telle réponse nécessitait un effort assez important, et je pensais qu'un commentaire aurait fait en sorte que ce serait un gaspillage
H.PWiz
2

Gelée , 11 octets

ÆfẋE$ḢÆCµl¿

Essayez-le en ligne!

-2 grâce à un tour très génial de Jonathan Allan .

Utilisation de l'algorithme Husk de H.PWiz.

Erik le Outgolfer
la source
Depuis le journal de base et le zéro, Nonevous pouvez faire ÆfẋE$ḢÆCµl¿pour 11 :)
Jonathan Allan
@JonathanAllan Hé, c'est une première! Agréable.
Erik the Outgolfer