Ist meine Nummer einzigartig?

21

In dieser Herausforderung haben wir einen Weg gefunden, jede positive ganze Zahl mit Hilfe von Faktorbäumen zu codieren.

So funktioniert es:

  • Die leere Zeichenfolge hat den Wert 1.

  • (S)Wobei Sjeder Ausdruck mit einem Wert von S als S- te Primzahl bewertet wird .

  • ABwobei Aund Bwillkürliche Ausdrücke mit Werten von A bzw. B den Wert A * B haben .

Wenn wir zum Beispiel 7 repräsentieren wollten, würden wir das tun

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

Es stellt sich heraus, dass wir mit dieser Methode jede ganze Zahl darstellen können. In der Tat können einige Zahlen auf verschiedene Arten dargestellt werden. Weil Multiplikation kommutativ ist, ist 10 beides

((()))()

und

()((()))

Gleichzeitig können einige Zahlen nur auf eine Art dargestellt werden. Nimm zum Beispiel 8. 8 kann nur dargestellt werden als

()()()

Und da alle unsere Atome gleich sind, können wir die Kommutivität nicht verwenden, um sie neu zu organisieren.


Die Frage lautet nun "Welche Zahlen können nur auf eine Art dargestellt werden?". Die erste Beobachtung habe ich gerade gemacht. Es scheint, dass perfekte Kräfte einige besondere Eigenschaften haben. Bei weiteren Untersuchungen können wir 36 finden, was 6 2 ist, eine perfekte Potenz, aber mehrere Darstellungen hat.

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

Und das ist sinnvoll, weil 6 bereits umordnungsfähig ist. Jede Zahl, die wir aus 6 machen, muss also auch umordnungsfähig sein.

Nun haben wir also eine Regel:

  • Eine Zahl hat eine eindeutige Darstellung, wenn es sich um eine perfekte Potenz einer Zahl mit einer eindeutigen Darstellung handelt.

Diese Regel kann uns helfen, die Feststellung, ob eine zusammengesetzte Zahl eindeutig ist, auf die Feststellung zu reduzieren, ob eine Primzahl eindeutig ist. Nun, da wir diese Regel haben, wollen wir herausfinden, was eine Primzahl einzigartig macht. Das ist eigentlich ziemlich selbstverständlich. Wenn wir eine eindeutige Zahl in Klammern setzen, muss das Ergebnis eindeutig sein. Wenn n mehrere Darstellungen enthält, muss die n- te Primzahl mehrere Darstellungen enthalten. Dies ergibt die zweite Regel:

  • Die n- te Primzahl ist genau dann eindeutig, wenn n eindeutig ist.

Beide Regeln sind rekursiv, daher benötigen wir einen Basisfall. Was ist die kleinste eindeutige Nummer? Man könnte versucht sein, 2 zu sagen, weil es gerecht ist (), aber 1, die leere Zeichenfolge, ist noch kleiner und einzigartig.

  • 1 ist einzigartig.

Mit diesen drei Regeln können wir bestimmen, ob eine Zahl einen eindeutigen Faktorbaum hat.

Aufgabe

Vielleicht haben Sie es kommen sehen, aber Ihre Aufgabe ist es, eine positive ganze Zahl zu nehmen und festzustellen, ob sie eindeutig ist. Sie sollten entweder ein Programm oder eine Funktion schreiben, die diese Berechnung durchführt. Sie sollten einen von zwei möglichen Werten ausgeben. Was diese Werte sind, liegt bei Ihnen, aber einer sollte "Ja" darstellen. Er wird ausgegeben, wenn die Eingabe eindeutig ist, und einer sollte "Nein" darstellen, wenn er ansonsten ausgegeben wird.

Ihre Antworten sollten in Bytes bewertet werden, wobei weniger Bytes besser sind.

Testfälle

Hier sind die ersten paar eindeutigen Zahlen:

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

Vorgeschlagene Testfälle

5381 -> Unique

Es scheint, dass OEIS A214577 in irgendeiner Weise verwandt ist. Wenn Sie also mehr Testfälle benötigen, versuchen Sie es dort, aber ich weiß nicht, dass sie gleich sind. Verwenden Sie sie daher auf Ihr eigenes Risiko.

Weizen-Assistent
quelle
Ich glaube, dass die Primfaktoren sortiert werden mussten, aber was auch immer.
Nissa
1
@ JonathanAllan Nein, es ist alles hier.
Nissa
Vorgeschlagener Testfall: 5381
Nissa
@StephenLeppik Testfall hinzugefügt, danke.
Wheat Wizard
1
@ H.PWiz Ich werde sagen, dass ein vollständiges Programm als Ausgabe fehlerhaft sein kann, da dies eine Form der Ausgabe für ein Programm ist, aber eine Funktion einen Wert zurückgeben muss.
Wheat Wizard

Antworten:

9

Schale , 11 bis 10 Bytes

Dank Zgarb ein Byte gespart!

Ωεo?oṗ←¬Ep

Rückgabe 1für Unikat, 0ansonsten

Probieren Sie es online! Oder die ersten 50 zurückgeben

Erläuterung:

Ωε              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
quelle
Oh, und deine Erklärung lautet " ȯp←".
Erik der Outgolfer
@EriktheOutgolfer Guter Fang, behoben
H.PWiz
Ich denke ṁ¬kann nur sein, ¬da die Liste in diesem Zweig nicht leer sein muss.
Zgarb
@Zgarb Oh Phantasie, ich denke du hast mir diesen Tipp schon
mal gegeben
7

Gelee , 10 Bytes

Nach vielem Herumspielen!

ÆET0ṪḊ?µl¿

Ein monadischer Link, der eine positive Ganzzahl aufnimmt und zurückgibt, 1ob er eindeutig ist oder 0nicht.

Probieren Sie es online!

Wie?

Æ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

Warten Sie, Logarithmus, was ?!

Lassen Sie uns einige Beispiele der Schleife durchgehen.

If n=31( 31 1 , elfte Primzahl):

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

Wenn 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

If 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
quelle
4

APL (Dyalog) , 42 Bytes

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

Das Verwenden ⎕CY'dfns'mit dfnses ist auf tio nicht sehr durchführbar.

Uriel
quelle
Meine Antwort ist Ihrer sehr ähnlich, obwohl ich die erste Version vor ungefähr 4 Stunden geschrieben habe
H.PWiz
@H.PWiz schau Mann, es ist mir eigentlich egal, wenn Leute in der gleichen Sprache einreichen, obwohl ich es normalerweise vorziehe, nur zu kommentieren, wenn ich eine kürzere Lösung finde, aber das ist fast das gleiche. Es macht mir nichts aus, dass Sie es behalten, aber ich finde Antworten, die genauso ziemlich nutzlos aussehen. Über das Timing - so funktioniert es. Ich ließ Dutzende Antworten fallen, weil jemand anderes an erster Stelle stand. Ich (und ich glaube der Rest) mache es zum Spaß, kein echter Wettbewerb.
Uriel
Tut mir leid, dass ich so lange gebraucht habe, aber ich habe meine Antwort gelöscht. Rückblickend scheint ein Kommentar angemessener gewesen zu sein. Ich denke, da ich zu dieser Zeit noch kein APL-
Neuling
2

Jelly , 11 Bytes

ÆfẋE$ḢÆCµl¿

Probieren Sie es online!

-2 dank eines sehr genialen Tricks von Jonathan Allan .

Verwendung des H.PWiz Husk-Algorithmus.

Erik der Outgolfer
quelle
Da loggen Sie sich auf die Basis eins und Null beide ergeben Nonekönnen Sie ÆfẋE$ḢÆCµl¿für 11 tun :)
Jonathan Allan
@ JonathanAllan Hey, das ist eine Premiere! Nett.
Erik der Outgolfer