Wiederholen Sie diesen GCD-Vorgang

19

Aufgabe A3 des Putnam-Wettbewerbs 2008 lautet:

Beginnen Sie mit einer endlichen Folge positiver Ganzzahlen. Wenn möglich, wählen Sie zwei Indizes so dass nicht dividiert , und ersetzen Sie und durch bzw. \ text {lcm} (a_j, a_k) . Beweisen Sie, dass dieser Vorgang, wenn er wiederholt wird, irgendwann beendet werden muss und die endgültige Reihenfolge nicht mehr von den getroffenen Entscheidungen abhängt.ein1,ein2,,einnj<keinjeinkeinjeinkgcd(einj,eink)lcm(einj,eink)

Ihr Ziel bei dieser Herausforderung ist es, eine endliche Folge positiver Ganzzahlen als Eingabe zu verwenden und das Ergebnis der Wiederholung dieses Prozesses auszugeben, bis kein Fortschritt mehr möglich ist. (Das heißt, bis jede Zahl in der resultierenden Folge alle nachfolgenden Zahlen dividiert.) Sie müssen das Putnam-Problem nicht lösen.

Das ist : Die kürzeste Lösung in jeder Programmiersprache gewinnt.

Testfälle

[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]
Mischa Lawrow
quelle
9
Was für ein tolles Problem! Schreiben Sie jede Ganzzahl als und beachten Sie, dass der Prozess die Listen in parallel :)2 α i 3 β i 5 γ i α , β , γ , einich2αi3βi5γiα,β,γ,
Lynn

Antworten:

12

Gelee , 9 Bytes

ÆEz0Ṣ€ZÆẸ

Probieren Sie es online!

Wie es funktioniert

ÆEz0Ṣ€ZÆẸ  Main link. Argument: A (array)

ÆE         For each n in A, compute the exponents of n's prime factorization.
           E.g., 2000000 = 2⁷3⁰5⁶ gets mapped to [7, 0, 6].
  z0       Zip 0; append 0's to shorter exponent arrays to pad them to the same
           length, then read the resulting matrix by columns.
    Ṣ€     Sort the resulting arrays (exponents that correspond to the same prime).
      Z    Zip; read the resulting matrix by columns, re-grouping the exponents by
           the integers they represent.
       ÆẸ  Unexponents; map the exponent arrays back to integers.
Dennis
quelle
5

J , 17 Bytes

/:~"1&.|:&.(_&q:)

Probieren Sie es online!

Wahrscheinlich die erste J-Antwort auf PPCG, die &.zweimal verwendet wurde. Nach diesem und jenem fühle ich mich allmählich wie ein seltsamer J-Hacker.

Grundsätzlich eine Übersetzung aus Dennis 'Jelly Antwort .

Wie es funktioniert

/:~"1&.|:&.(_&q:)  Single monadic verb.
           (_&q:)  Convert each number to prime exponents
                   (automatically zero-filled to the right)
       |:&.        Transpose
/:~"1&.            Sort each row in increasing order
       |:&.        Transpose again (inverse of transpose == transpose)
           (_&q:)  Apply inverse of prime exponents; convert back to integers
Bubbler
quelle
Ein früherer ist hier
FrownyFrog
5

Wolfram Language (Mathematica) , 44 Byte

Table[GCD@@LCM@@@#~Subsets~{i},{i,Tr[1^#]}]&

kk

bk=gcd({lcm(einich1,,einichk)|1ich1<<ichkn})

Probieren Sie es online!

Alephalpha
quelle
Sehr schön! Sie sind zwei für zwei auf seltsame Ansätze, die ich nicht kommen sah :)
Mischa Lawrow
5

Python 3 , 103 Bytes

import math
def f(a,i=0,j=-1):d=math.gcd(a[i],a[j]);a[j]*=a[i]//d;a[i]=d;a[i:j]and f(a,i,j-1)==f(a,i+1)

Probieren Sie es online!

Erläuterung

Dieses Problem ist im Wesentlichen eine parallele Sortierung der Primfaktoren, und (gcd (a, b), lcm (a, b)) ist analog zu (min (a, b), max (a, b)). Reden wir also über das Sortieren.

Wir werden durch Induktion beweisen, dass a [i] nach f (i, j) der kleinste Wert in (dem alten Wert von) L ist, wobei L der Bereich zwischen a [i] und a [j] ist, einschließlich beider Enden . Und wenn j = -1 ist, sortiert f (i, j) den Bereich L.

Der Fall, dass L ein Element enthält, ist trivial. Beachten Sie für die erste Behauptung, dass das kleinste von L nach dem Tausch nicht in a [j] bleiben kann, so dass f (i, j-1) es in a [i] setzt und f (i + 1, - 1) wird es nicht beeinflussen.

Beachten Sie für die zweite Behauptung, dass a [i] der kleinste Wert ist und f (i + 1, -1) die verbleibenden Werte sortiert, sodass L nach f (i, j) sortiert wird.

infmagic2047
quelle
3

Netzhaut , 65 Bytes

\d+
*
+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b
$2$4$5$#3*$5
_+
$.&

Probieren Sie es online! Link enthält die schnelleren Testfälle. Erläuterung:

\d+
*

In Unary konvertieren.

+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b

Wiederholt übereinstimmen: Jede Zahl mit einem Faktor, dann eine spätere Zahl, die nicht durch die erste Zahl, sondern durch den Faktor teilbar ist.

$2$4$5$#3*$5

$1ist die erste Nummer. $2ist der Faktor. Da Regex gierig ist, ist dies der größte Faktor, dh der GCD. $4ist der Teil der Übereinstimmung zwischen den ursprünglichen Zahlen. $5ist die zweite Zahl. $#3(dezimal statt unär) ist eine Zahl $1, durch $2die nicht geteilt wird , da das Original nicht enthalten ist $2. Dies bedeutet, dass wir zur Berechnung der lcm $5mit eins mehr multiplizieren müssen, als $#3am genauesten als die Summe von $5und das Produkt von $#3und geschrieben wird $5.

_+
$.&

In Dezimalzahl konvertieren.

Neil
quelle
Standardmäßig ist Unary für Retina zulässig , daher können Sie dies als 52 Byte zählen.
Dennis
@Dennis Nur drei meiner Retina-Antworten werden unärgerlich eingegeben. Ich habe mich daran gewöhnt, E / A dezimal auszuführen.
Neil
3

05AB1E , 10 Bytes

Kredit für die Annäherung geht an Alephalpha .

εIæN>ù€.¿¿

Probieren Sie es online!

εIæN>ù€.¿¿     Full program. Takes a list from STDIN, outputs another one to STDOUT.
ε              Execute for each element of the input, with N as the index variable.
 Iæ            Powerset of the input.
   N>ù         Only keep the elements of length N+1.
      €.¿      LCM each.
         ¿     Take the GCD of LCMs.
Mr. Xcoder
quelle
3

Perl 6 , 53 Bytes

{map {[gcd] map {[lcm] $_},.combinations: $^i},1..$_}

Probieren Sie es online!

Port of Alephalphas Mathematica Antwort.

nwellnhof
quelle
2

JavaScript (SpiderMonkey) , 69 Byte

a=>a.map((q,i)=>a.map(l=(p,j)=>a[j]=j>i&&(t=p%q)?p/t*l(q,j,q=t):p)|q)

Probieren Sie es online!

  • Funktion lzuweisen lcm(p,q)zu a[j]und zuweisen gcd(p, q)zu qwenn j > i, sonst bleibt alles unverändert.
    • lcm(p,q) = if p%q=0 then p else p*lcm(q,p%q)/(p%q)

Alte Antwort:

JavaScript (SpiderMonkey) , 73 Byte

a=>a.map((u,i)=>a.map((v,j)=>i<j?a[j]*=u/(g=p=>p%u?g(u,u=p%u):u)(v):0)|u)

Probieren Sie es online!

  • Funktion gberechnen gcd(u, v)und Rückgabewert zuweisen u.
tsh
quelle
2

05AB1E , 15 14 13 Bytes

Ó¾ζ€{øεgÅpymP

Port von @ Dennis ♦ 'Jelly Antwort , aber leider hat 05AB1E kein Unexponents-Builtin, so dass das Programm mehr als halbiert wird .. :(
-1 Byte dank @ Mr.Xcoder .
-1 Byte dank @Enigma .

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

Erläuterung:

Ó          # Prime exponents of the (implicit) input-list
 ¾ζ        # Zip, swapping rows and columns, with integer 0 as filler
   €{      # Sort each inner list
     ø     # Zip, swapping rows and columns again
ε          # Map each inner list:
 gÅp       #  Get the first `l` primes, where `l` is the size of the inner list
    ym     #  Take the power of the prime-list and inner list
      P    #  And then take the product of that result
           # (And output implicitly)
Kevin Cruijssen
quelle
1
Oh, ich hatte Ihre Antwort nicht gesehen, bevor ich meine eigene gepostet habe, lol. 14 Bytes durch Verwenden ¾und Entfernen von +1. (Ich habe das schon einmal versucht, weil ich versucht habe, Dennis 'Antwort ebenfalls zu portieren, lol)
Mr. Xcoder,
1
Durch εgÅpymPdie Verwendung von würde ein weiteres Byte gegenüber dem von Mr. Xcoder angegebenen Byte gespeichert
Emigna,
@ Mr.Xcoder Oh, ich wusste nicht, dass es einen Unterschied zwischen dem Füllstoff mit 0und gibt ¾. Muss mich daran erinnern! Tatsächlich werde ich es jetzt zu meinen kleinen 05AB1E-Tipps hinzufügen. :)
Kevin Cruijssen