Tauschen Sie die besten Exponenten mit ihren Nachbarn aus

13

(Follow-up zu meiner Frage zum Austausch von Bits mit ihren Nachbarn .)

Aufgabe

Bei einer positiven ganzen Zahl x = (2 a  · 3 b ) · (5 c  · 7 d ) · (11 e  · 13 f ) · ... wird die ganze Zahl gedruckt, die durch Vertauschen der Exponenten in dieser Faktorisierung für jedes aufeinanderfolgende Primpaar erhalten wird. y = (2 b  · 3 a ) · (5 d  · 7 c ) · (11 f  · 13 e ) ·…

A061898 im OEIS. Das ist Code-Golf , also gewinnt das kürzeste Programm (in Bytes)!

Testfälle

1 -> 1
2 -> 3
3 -> 2
10 -> 21
37 -> 31
360 -> 756
12345 -> 11578
67895678 -> 125630871
code-golf primes Lynn
quelle
Können wir True anstelle von 1 zurückgeben ?
Dennis
@ Tennis Nach einiger Überlegung habe ich beschlossen, meine Antwort ist nein. Die Ausgabe muss mindestens wie eine Zahl aussehen .
Lynn

Antworten:

6

Gelee , 10 Bytes

ÆE;0s2UFÆẸ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

ÆE;0s2UFÆẸ  Main link. Argument: n

ÆE          Yield the exponents of n's prime factorization.
  ;0        Append a zero.
    s2      Split into pairs.
      U     Upend; reverse each pair.
       F    Flatten the resulting list of pairs.
        ÆẸ  Convert the prime exponents to integer.
Dennis
quelle
4

Jelly, 17 16 11 Bytes

5 Bytes dank Dennis.

ÆfÆC’^1‘ÆNP

Probieren Sie es online!

Erläuterung

ÆfÆC’^1‘ÆNP   Main monadic chain. Argument: n

Æf            Yield the prime factors of n.
  ÆC          For each factor, count the number of primes below it.
              This effectively yields their indices.
    ’         Decrement [each] by 1.
     ^1       Xor with 1
       ‘      Increment [each] by 1.
        ÆN    Find their corresponding primes.
          P   Yield their product.

Vorherige 16-Byte-Version

ÆnÆRiЀÆf’^1‘ÆNP

Probieren Sie es online!

Erläuterung

ÆnÆRiЀÆf’^1‘ÆNP   Main monadic chain. Argument: n

Æn                 Yield the next prime from n.
  ÆR               Yield all primes from 2 to it.
       Æf          Yield prime factors of n
    iЀ            Yield their index in the prime list.
         ’         Decrement [each] by 1.
          ^1       Xor with 1
            ‘      Increment [each] by 1.
             ÆN    Find their corresponding primes.
               P   Yield their product.

Vorherige 17-Byte-Version:

ÆnÆR©iЀÆf’^1‘ị®P

Probieren Sie es online!

Erläuterung

ÆnÆR©iЀÆf’^1‘ị®P   Main monadic chain. Argument: n

Æn                  Yield the next prime from n.
  ÆR                Yield all primes from 2 to it.
    ©               Store to register.
        Æf          Yield prime factors of n
     iЀ            Yield their index in the prime list.
          ’         Decrement [each] by 1.
           ^1       Xor with 1
             ‘      Increment [each] by 1.
              ị®    Find their corresponding primes in
                    the list in register.
                P   Yield their product.
Undichte Nonne
quelle
3

Mathematica, 70 69 Bytes

1##&@@(Prime[BitXor[PrimePi@#+1,1]-1]^#2&)@@@FactorInteger@#/._@_->1&

Eine unbenannte Funktion, die eine Ganzzahl annimmt und zurückgibt. Bei der Eingabe wird ein Fehler 1ausgegeben, das korrekte Ergebnis wird jedoch berechnet.

Erläuterung

Aufgrund des syntaktischen Zuckers ist die Lesereihenfolge wie immer ein bisschen lustig. Ein &auf der rechten Seite definiert eine unbenannte Funktion und ihre Argumente werden bezeichnet durch #, #2, #3usw.

...FactorInteger@#...

Wir beginnen mit der Berücksichtigung der Eingabe. Dies gibt eine Liste von Paaren an, {prime, exponent}zB 12gibt die Eingabe {{2, 2}, {3, 1}}. Etwas ungünstig, 1gibt {{1, 1}}.

(...&)@@@...

Dies wendet die Funktion auf der linken Seite auf die Liste der Ganzzahlen auf Ebene 1 an, dh, die Funktion wird für jedes Paar aufgerufen, wobei Prim und Exponent als separate Argumente übergeben werden, und gibt dann eine Liste der Ergebnisse zurück. (Dies ähnelt der Zuordnung der Funktion über die Liste, aber das Empfangen von zwei separaten Argumenten ist bequemer als das Empfangen eines Paares.)

...PrimePi@#...

Wir berechnen die Anzahl der Primzahlen bis einschließlich der (Prim) -Eingabe mit Hilfe der eingebauten Funktion PrimePi. Dies gibt uns den Index der Primzahl.

...BitXor[...+1,1]-1...

Das Ergebnis wird inkrementiert, mit XOR verknüpft 1und erneut dekrementiert. Dies sind Swaps 1 <-> 2, 3 <-> 4, 5 <-> 6, ..., also alle 1-basierten Indizes. Man beachte , dass Eingang 1ergeben wird 0für PrimePiwelche dann abgebildet -1in diesem Prozess. Wir werden uns später darum kümmern.

 ...Prime[...]^#2...

Wir erhalten nun die n- te Primzahl (wobei n das Ergebnis der vorherigen Berechnung ist), die die korrekt vertauschte Primzahl ist, und erhöhen sie bei der Faktorisierung der Eingabe auf die Potenz der ursprünglichen Primzahl. An diesem Punkt Prime[-1]wird ein Fehler ausgegeben, der sich jedoch nicht ausgewertet zurückgibt. Die Leistung in diesem Fall ist 1so, dass der gesamte bisherige Prozess {Prime[-1]}für die Eingabe 1und eine Liste der korrekten Primleistungen für alle anderen Eingaben ergibt .

 1##&@@...

Als nächstes multiplizieren wir einfach alle Primkräfte. 1##&ist ein Standard-Golf-Trick für die TimesFunktion. In diesem Tipp (Abschnitt "Folgen von Argumenten") erfahren Sie, wie es funktioniert.

Schließlich müssen wir uns um die Eingabe kümmern, 1für die alle oben genannten Ergebnisse erzielt wurden Prime[-1]. Wir können das mit einer einfachen Ersetzungsregel leicht beheben. Denken Sie daran, das f@xist die Abkürzung für f[x]. Wir wollen nur einen Ausdruck dieser Form zuordnen (da alle anderen Ergebnisse Ganzzahlen sind, dh atomare Ausdrücke) und ihn durch Folgendes ersetzen 1:

.../._@_->1

Hier /.ist kurz für ReplaceAll, _@_ist ein Muster für alles von der Form f[x](dh jeder zusammengesetzte Ausdruck mit einem einzelnen Kind) und ->1sagt "Ersetzen durch 1".

Martin Ender
quelle
3

Python 2, 149 139 Bytes

10 Bytes dank Dennis.

n=input()
p=f=1;w=[2]
while w[-1]<=n:f*=p;p+=1;w+=[p]*(-~f%p<1)
r=p=1;w=w[1:]
while n>1:
    p+=1
    while n%p<1:n/=p;r*=w[w.index(p)^1]
print r
Undichte Nonne
quelle
input()funktioniert in Python 2?
NoOneIsHere
@NoOneIsHere Ja, es ist das Äquivalent zu eval(input())in Python 3.
Mego
2

MATL , 17 Bytes

EZqGYfy&mt2\Eq+)p

Probieren Sie es online!

Erläuterung

Hierbei werden die Exponenten nicht direkt verwendet. Stattdessen wird jeder (möglicherweise wiederholte) Primfaktor durch den nächsten oder den vorhergehenden Prim getauscht.

EZq    % Implicit input. Multiply by 2
Zq     % Array with sequence of primes up to that (this is more than enough)
GYf    % Prime factors of input, with possible repetitions
y      % Duplicate array with sequence of primes
&m     % Indices of prime factors in the sequence of primes
t2\    % Duplicate, modulo 2. Gives 0 for even indices, 1 for odd
Eq     % Multiply by 2, add 1. Transforms 0 / 1 into -1 / 1 
+      % Add. This modifies the indices to perform the swapping
)      % Apply the new indices into the sequence of primes
p      % Product. Implicit display
Luis Mendo
quelle
2

Julia, 64 Bytes

~=primes
!n=prod(t->(~3n)[endof(~t[1])+1$1-1]^t[2],factor(2n))/3

Probieren Sie es online! Der letzte Testfall benötigt zu viel Speicher für TIO, aber ich habe ihn lokal überprüft.

Wie es funktioniert

Um die Eingabe 1 in Groß- und Kleinschreibung zu vermeiden - das Produkt eines leeren Wörterbuchs ist nicht definiert - multiplizieren wir die Eingabe n mit 2 und dividieren das Endergebnis durch das Paar 3 .

factor(2n)gibt alle positiven Exponenten der Primfaktoren von 2n als Wörterbuch an. Beim Durchlaufen des Wörterbuchs erhalten wir Schlüssel-Wert / Prim-Exponenten-Paare. Die Funktion prodübernimmt diese Paare, wendet die anonyme Funktion t->...auf sie an und gibt das Produkt der Ergebnisse zurück.

Für jedes Paar t = (p, e) , endof(~t[1])oder endof(primes(t[1]))Rückkehr k , die Anzahl der Primzahlen , die kleiner oder gleich p , was bedeutet , dass die p ist die k - te Primzahl.

+1$1-1erhöht k , XOR k + 1 um 1 und dekrementiert das Ergebnis. Wenn k ungerade ist, ist k + 1 gerade, so dass das XOR inkrementiert und das Endergebnis k + 1 ist . Wenn k gerade ist, ist k + 1 ungerade, so dass das XOR dekrementiert und das Endergebnis k - 1 ist .

Schließlich berechnen wir alle Primzahlen kleiner oder gleich 3n mit (~3n)oder primes(3n)(der höchste Primfaktor von 2n ist kleiner oder gleich n, wenn n> 2 , und es gibt immer eine Primzahl zwischen n und 2n ). Wählen Sie die Zahl am Index k + aus 1 oder k - 1 , und heben Sie es mit auf die e- te Potenz ^t[2].

Dennis
quelle
2

Python 2, 112 109 108 95 94 Bytes

f=lambda n,k=4,m=6,p=[3,2]:1/n or n%p[1]and f(n,k+1,m*k,m*m%k*[k]+p)or p[len(p)*2%4]*f(n/p[1])

Teste es auf Ideone .

Wie es funktioniert

Wenn f aufgerufen wird, berechnet es zuerst 1 / n . Wenn das Ergebnis nicht Null ist , n ist 1 und f kehrt 1 .

Wenn n> 1 ist , geschieht Folgendes.

  • Ist n nicht durch p [1] teilbar (anfangs 2 ), n%p[1]ergibt sich ein Wahrheitswert und

    f(n,k+1,m*k,m*m%k*[k]+p)

    wird gerufen.

    Diese Verzweigung erzeugt eine Primzahl, bis die vorletzte n gleichmäßig teilt . Zu diesem Zweck wird die folgende Folgerung aus dem Satz von Wilson verwendet .

    Folgerung aus Wilsons Satz

    Zu allen Zeiten, m ist die Fakultäts von gleich k - 1 (zunächst 6 = 3! Und 4 In jeder Iteration das Ergebnis. m*m%k*[k]Wird in der Liste der Primzahlen voran p Durch die logische Folge. m*m%kIst 1 , wenn k eine Primzahl ist und 0 wenn nicht, so dass diese wird vorangestellt k zu p , wenn und nur wenn k eine Primzahl ist.

  • Wenn n durch p [1] teilbar ist , n%p[1]ergibt sich 0 und

    p[len(p)*2%4]*f(n/p[1])

    wird ausgeführt.

    Wenn p eine gerade Anzahl von Primzahlen enthält, len(p)*2%4ergibt sich 0 und der erste Multiplikand nimmt den Wert von p [0] an . Wenn p eine ungerade Anzahl von Primzahlen enthält, len(p)*2%4ergibt sich 2 und der erste Multiplikand nimmt den Wert von p [2] an. .

    In beiden Fällen ist dies die Primzahl, deren Exponenten mit der von p [1] vertauscht werden müssen. Wir teilen also n durch p [1] (Verringern des Exponenten um 1 ) und multiplizieren das Ergebnis f(n/p[1])mit der entsprechenden Primzahl (Erhöhen) der Exponent um 1 ).

    Beachten Sie, dass f(n/p[1])Resets k , m und p auf die Standardwerte. f(n/p[1],k,m,p)Dies würde die Effizienz auf Kosten von sechs zusätzlichen Bytes verbessern.

Dennis
quelle
1

Pyth, 25 Bytes

JfP_TSfP_ThQ*F+1m@Jx1xJdP

Testsuite.

Erläuterung

JfP_TSfP_ThQ*F+1m@Jx1xJdP

           Q    get input
          h     add one
      fP_T      find the first prime after it
     S          range from 1 to that prime
 fP_T           filter for the primes
J               assign to J

                        P  prime factorize input
                m      d   for each factor
                     xJ    find its index in J
                   x1      xor with 1
                 @J        find the corresponding entry in J
            *F+1           product of the whole list
Undichte Nonne
quelle
1

Julia, 155 131 127 Bytes

n->(x=[sort([merge([p=>0for p=primes(n+1)],factor(n))...]);1=>0];prod([x[i-1][1]^x[i][2]*x[i][1]^x[i-1][2]for i=2:2:endof(x)]))

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu. Es ist eine Julia-Version <0.5 erforderlich, da die Hauptfunktionalität von Base in 0.5 entfernt wurde.

Ungolfed:

function f(n::Int)
    # Create an array of pairs by merging the Dict created from factoring n
    # with all primes less than n+1 with a 0 exponent. Append an extra pair
    # to account for 1 and situations where x would otherwise have odd length.
    x = [sort([(merge([p=>0 for p in primes(n+1)], factor(n))...]); 1=>0]

    # Compute a^d * c^b, where a and c are primes with b and d as their
    # respective exponents.
    prod([x[i-1][1]^x[i][2] * x[i][1]^x[i-1][2] for i = 2:2:endof(x)])
end

Probieren Sie es online! (Beinhaltet alle Testfälle)

Alex A.
quelle
1

Eigentlich 15 Bytes

w`i;r♂Pí1^Pn`Mπ

Probieren Sie es online!

Erläuterung:

w`i;r♂Pí1^Pn`Mπ
w                prime factorization
 `          `M   map (for (p,e) in factorization):
  i;               flatten, make a copy of p
    r♂P            [prime[i] for i in range(p)]
       í           index (essentially the 0-based prime index of p)
        1^         XOR with 1
          P        prime[n]
           n       repeat e times
              π  product
Mego
quelle
1

05AB1E, 22 Bytes

Ó¾‚˜2ô€R˜DgL<Ø)øvy`smP

Erklärt

Ó¾‚˜                    # list of primeexponents with a 0 appended: n=10 -> [1,0,1,0] 
    2ô                  # split into pairs: [[1,0],[1,0]]
      €R˜               # reverse each pair and flatten: [0,1,0,1]
         DgL<Ø          # get list of primes corresponding to the exponents: [2,3,5,7]
              )ø        # zip lists: [[0,2],[1,3],[0,5],[1,7]]
                vy`sm   # raise each prime to its new exponent: [1,3,1,7]
                     P  # product: 21

Probieren Sie es online aus

Emigna
quelle
0

J, 21 Bytes

([:,_2|.\,&0)&.(_&q:)

Ruft die Primzahlen von n ab als Primkräfte mit Nullen ab. Partitionieren Sie sie dann in nicht überlappende Unterlisten der Größe 2 und füllen Sie sie mit einer zusätzlichen Null. Kehren Sie dann jede Unterliste um und reduzieren Sie sie zu einer Liste. Schließlich konvertieren Sie zurück von Primzahlen in eine Zahl.

Verwendung

   f =: ([:,_2|.\,&0)&.(_&q:)
   (,.f"0) 1 2 3 10 37 360 12345
    1     1
    2     3
    3     2
   10    21
   37    31
  360   756
12345 11578
   f 67895678x
125630871

Erläuterung

([:,_2|.\,&0)&.(_&q:)  Input: n
                _&q:   Obtain the list of prime exponents
(           )&.        Apply to the list of prime exponenets
         ,&0           Append a zero to the end of the list
    _2  \              Split the list into nonoverlapping sublists of size 2
      |.               Reverse each sublist
 [:,                   Flatten the list of sublists into a list
             &.(    )  Apply the inverse of (Obtain the list of prime exponents)
                       to convert back to a number and return it
Meilen
quelle