Stellen Sie zwei Zahlen als Ko-Primzahl auf, während Sie das am wenigsten verbreitete Vielfache beibehalten

20

Geben Sie bei zwei positiven Ganzzahlen aund bzwei positive Ganzzahlen aus, cund zwar dso, dass:

  • c teilt a
  • d teilt b
  • cund dsind Co-Prime
  • Das kleinste gemeinsame Vielfache von cund ist dgleich dem kleinsten gemeinsamen Vielfachen von aund b.

Wenn es mehr als eine mögliche Antwort gibt, können Sie nur eine oder alle Antworten ausgeben.

Testfälle:

 a  b  c  d
12 18  4  9
18 12  9  4
 5  7  5  7
 3  6  1  6 or 3 2
 9  9  9  1 or 1 9
 6 15  2 15 or 6 5
 1  1  1  1

Das ist . Kürzeste Antwort in Bytes gewinnt.

Undichte Nonne
quelle
Was hält mich davon ab, zurückzukehren (1, LCM)?
Neil
1
@ Neil Die Anforderung, die dteiltb
Leaky Nun
4
Vielleicht sollten Sie LCM definieren oder zumindest das Akronym nicht verwenden. Ich wusste nicht, wonach gefragt wurde.
Weizen-Assistent

Antworten:

7

Jelly , 21 13 Bytes

ÆEz®0iṂ$¦€ZÆẸ

Probieren Sie es online!

Wenn a = 2 A · 3 B · 5 C ·… und b = 2 α · 3 β · 5 γ ·… , dann berechnen wir

  • c = 2 A> α? A: 0,3 B> β? B: 0,5 C> γ? C: 0

  • d = 2 A> α? 0: α · 3 B> β? 0: β · 5 C> γ? 0: γ ·…

Jetzt ist lcm (c, d) = 2 max (A> α? A: 0, A> α? 0: α) ·… = 2 max (A, α) · 3 max (B, β) ·… = lcm ( a, b)

und gcd (c, d) = 2 min (A> & agr; & agr; A: 0, A> & agr; & agr; 0: & agr;) · ... = 2 0 · 3 0 · 5 0 · ... = 1 .

Mit anderen Worten: Beginnen Sie mit (c, d) = (a, b) . Teilen Sie dann für jede Primzahl diese Primzahl ganz aus der Faktorisierung von c oder d heraus : je nachdem, welcher Wert den kleinsten Exponenten für diese Primzahl hat. (In dieser Implementierung verliert c bei einem Gleichstand seinen Exponenten.)

Also, wenn a = 2250 = 2 1 · 3 2 · 5 3 und b = 360 = 2 3 · 3 2 · 5 1 ,

dann ist c = 2 0 · 3 0 · 5 3 = 125 und d = 2 3 · 3 2 · 5 0 = 72 .

Jonathan Allan hat satte 8 Bytes Golf gespielt! Vielen Dank ~

Lynn
quelle
Dies ist mein ursprünglicher Algorithmus ... Der Perl-Algorithmus ist besser.
Undichte Nonne
Sehr schön. Hier ist es in 12 Bytes
Jonathan Allan
Hier ist ein weiterer 12 byterÆEZ×Ụ’$€$ZÆẸ
Meilen
Das gibt jetzt [1,18]nach [15,18]. Die ursprüngliche Version gab die richtige Antwort zurück ( [5,18]).
Arnauld
1
Ah - ja, wir brauchen einen Null-Füller für die Transponierung. ÆEz®0iṂ$¦€ZÆẸsollte den Trick für 13 tun.
Jonathan Allan
4

R 143 139 123 Bytes

f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")

(Danke an @ Giuseppe für diese 19 Bytes!)

Mit Einrückungen, Zeilenumbrüchen und einigen Erläuterungen:

f=function(a,b,
           q=1:(a*b)) #Defined as function arguments defaults to avoid having to use curly brackets
    for(i in 1:a)
        for(j in 1:b)
            if(!a%%i + b%%j & #Is a divided by c and b divided by d
               max(q[!i%%q+j%%q])<2 & #Are c and d coprimes
               i*j==min(q[!q%%a+q%%b])) #Is this the same lcm
                   cat(i,j,"\n") #Then print

Testfälle:

> f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")
> f(5,7)
5 7 
> f(12,18)
4 9 
> f(6,15)
2 15 
6 5 
> f(1,1)
1 1 
Plannapus
quelle
!hat eine höhere Priorität als &und, |aber eine niedrigere als +und *; Sie sollten in der Lage sein, ein paar Bytes auf diese Weise abzuspielen. dh !i%%q&j%%qsollte gleichbedeutend sein mit!i%%q+j%%q
Giuseppe
1
Okay gut Beobachtung: wenn ja GCD(c,d)==1, dann LCM(c,d)==c*d. So können wir testen GCD(c,d)==1und dann überprüfen, ob es sich bei c*d==a*b/GCD(a,b)letzterem um LCM(a,b)...
Giuseppe
1
Tatsächlich! (obwohl das Rechnen a*b/GCD(a,b)nicht kürzer ist als LCM(a,b)).
Plannapus
120 Bytes - anonyme Funktion + Literal Newline für -3 Bytes
Giuseppe
4

Schale , 10 Bytes

→ÖF§-⌋⌉ΠmḊ

Rohe Gewalt. Nimmt Listen auf und gibt sie zurück und funktioniert auch für mehr als zwei Zahlen. Probieren Sie es online!

Erläuterung

→ÖF§-⌋⌉ΠmḊ  Implicit input, say [6,15]
        mḊ  Map divisors: [[1,2,3,6],[1,3,5,15]]
       Π    Cartesian product:[[1,1],[2,1],[1,3],[2,3],[3,1],[1,5],[3,3],[6,1],[1,15],[2,5],[3,5],[6,3],[2,15],[6,5],[3,15],[6,15]]
 Ö          Sort by
  F         reduce by
     ⌉      lcm
   -⌋       minus gcd: [[1,1],[3,3],[2,1],[1,3],[3,1],[6,3],[1,5],[2,3],[6,1],[2,5],[3,15],[1,15],[3,5],[6,15],[2,15],[6,5]]
→           Get last element: [6,5]
Zgarb
quelle
3

Mathematica, 82 Bytes

#&@@Select[Subsets[Flatten@Divisors[{t=#,r=#2}],{2}],GCD@@#==1&&LCM@@#==t~LCM~r&]&
J42161217
quelle
Ich bin nicht sicher, aber könnten Sie nicht die Listenindizierung Select[...][[1]]verwenden First@Select[...], um ein Byte zu speichern?
Jonathan Frech
ja, aber dann konnte ich verwenden , #&@@anstatt [[1]]ein , mehr zu sparen ;-)
J42161217
3

JavaScript (ES6), 90 84 80 Bytes

Übernimmt Eingaben in der Currying-Syntax (a)(b)und gibt ein Array mit 2 Ganzzahlen zurück.

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]

Testfälle

Wie?

a =>                            // a = first input
  g = (                         // g = recursive function that takes:
    b,                          //   b = second input
    c = 1                       //   c = first output divisor, initially set to 1
  ) =>                          //
    (G = (a, b) =>              // G = function that takes a and b
      b ? G(b, a % b) : a       //     and returns the greatest common divisor
    )(                          // we call it with:
      c,                        //   - c
      d = a * b / G(a, b) / c   //   - d = LCM(a, b) / c = a * b / GCD(a, b) / c
    ) - 1 |                     // if the result is not 1 (i.e. c and d are not coprime)
    a % c |                     // or c does not divide a
    b % d ?                     // or d does not divide b:
      g(b, c + 1)               //   do a recursive call with c + 1
    :                           // else:
      [c, d]                    //   return [c, d], a valid factorization of the LCM
Arnauld
quelle
3

MATL , 17 16 Bytes

&YFt&X>2:!=*^!Xp

Probieren Sie es online!

Gleiche Methode wie Lynn's Jelly-Lösung

Es ist schon eine Weile her, dass ich MATL (oder Matlab für diese Angelegenheit) verwendet habe, so dass wahrscheinlich viele Verbesserungen möglich sind.

B. Mehta
quelle
3

Haskell ,50 48 47 45 42 Bytes

(?)=gcd;a!b|c<-div a$a?b=(c*c?b,div b$c?b)

Idee: Mir ist das aufgefallen c*d = a*b/gcd(a,b). Der Algorithmus führt also zwei Schritte aus:

  1. Beginnen Sie mit c' = a/gcd(a,b)und d' = b. Dies erfüllt alle Anforderungen mit Ausnahme dieser c'und d'muss Co-Prime sein.
  2. Um sie zum Co-Prime zu machen, berechne ich e = gcd(c',d')und setze c = c'*eund d = d'/e. Dies behält alle Eigenschaften bei (da die kombinierten Faktoren gleich bleiben), aber da ich alle gemeinsamen Faktoren von entferne d, mache ich cund dkoprime.

In meiner Implementierung c'heißt das nur c.

Probieren Sie es online!

-3 Bytes dank Laikoni

Sacchan
quelle
Das Binden mit einem Pattern Guard cspart 3 Bytes: Probieren Sie es online aus!
Laikoni
@ Laikoni Ooh, ich wusste nicht einmal diesen Trick. Vielen Dank!
Sacchan
2

05AB1E , 12 Bytes

Ñ`âʒ.¿I.¿Q}н

Probieren Sie es online! oder als Testsuite

Emigna
quelle
Immer noch eine rohe Kraft: c
Leaky Nun
@LeakyNun: Ja, es gibt wahrscheinlich einen mathematischeren Weg, dies zu tun :)
Emigna
2

R , 126 Bytes

function(a,b,g=function(x,y)ifelse(o<-x%%y,g(y,o),y),l=a*b/g(a,b))matrix(c(C<-(1:l)[!l%%1:l],D<-l/C),,2)[g(C,D)<2&!a%%C+b%%D,]

Probieren Sie es online!

Dies erfordert einen anderen (und anscheinend weniger golferischen) Ansatz zum Finden der Werte als die andere R-Antwort .

Erläuterung:

function(a,b){
 G <- function(x,y)ifelse(o<-x%%y,G(y,o),y) #gcd function, vectorized for x,y
 l <- a*b/g(a,b)                            #lcm of a,b
 C <- (1:l)[!l%%1:l]                        #divisors of l
 D <- l/C                                   #l/C is the other half of the pair
 rel_prime <- G(C, D) < 2                   #pairs where C,D are relatively prime, lol, GCD
 a_div <- !a%%C                             #divisors of a
 b_div <- !b%%D                             #divisors of b
 C <- C[rel_prime & a_div & b_div]
 D <- D[rel_prime & a_div & b_div]          #filter out the bad pairs
 matrix(c(C,D),,ncol = 2)                   #matrix of pairs, returned
}

mit der Ausnahme, dass ich alle Definitionen als Standardargumente aufgeschlüsselt und alle Berechnungen für die Golfiness in einer Zeile ausgeführt habe.

Giuseppe
quelle
2

J , 19 Bytes

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

Probieren Sie es online!

Basierend auf @Lynns Lösung .

Erläuterung

(*/:"1)&.|:&.(_&q:)  Input: [a, b]
              _&q:   Get exponenets of each prime
         |:&         Transpose
  /:"1 &             Grade each row
 *                   Multiply elementwise
       &.|:          Transpose
           &. _&q:   Convert exponents back to numbers
Meilen
quelle
2

Haskell , 91 74 Bytes

a!b=[(x,y)|x<-[1..a],y<-[1..b],rem a x+rem b y+gcd x y<2,lcm a b==lcm x y]

Probieren Sie es online!

Gespeichert 17 Bytes dank Laikoni

jferard
quelle
1
u*v`div`gcd u vSpeichert ein Byte.
Lynn
Gibt es einen Grund, die eingebaute lcmFunktion nicht zu verwenden ?
Laikoni
Sollte auch rem a x+rem b y+gcd x y<2funktionieren.
Laikoni
@Laikoni ein sehr guter Grund: Ich wusste nicht einmal, dass das eingebaute lcmexistiert. rem a x+rem b y+gcd x y<2funktioniert, und ich frage mich, ob rem a x+rem b y+gcd x y+lcm a b-lcm x y<2 funktioniert. Es gibt vielleicht eine (mathematische) Garantie dafür lcm a b>=lcm x y.
jferard
1
Tatsächlich lcm a b>=lcm x yweil 1. x=x1*...*xi(Primzerlegung) y=y1*...yj, lcm x y=z1*...*zkwo z1,...,zkgemeinsam sind x1,...,xiund y1,...,yj. 2. a=u1*...*um*x1*...*xi(Primzerlegung) b=v1*...vn*y1*...yj, lcm a b=t1*...*tldie t1,...,tlgemeinsam ist, u1*...*um*x1*...*xiund v1*...vn*y1*...yj. Es ist offensichtlich , dass t1,...,tlenthält z1,...,zk, so lcm a b>=lcm x y. Dies ist jedoch nicht nützlich, um die Bedingung als Summe zu schreiben.
jferard
2

Python 2 , 75 Bytes

def f(x):n=1;exec'n+=1;j=k=1\nwhile x[j]%k<1:k*=n**j;j^=1\nx[j]/=k/n;'*x[0]

Die Eingabe wird als Liste genommen, die die Funktion an Ort und Stelle ändert.

Probieren Sie es online!

Dennis
quelle
1

Python 3 , 129 Bytes

lambda a,b:[[c,d]for c in range(1,-~a)for d in range(1,-~b)if((gcd(c,d)<2)*a*b/gcd(a,b)==c*d/gcd(c,d))>a%c+b%d]
from math import*

Probieren Sie es online! oder Probieren Sie die Testsuite aus.

Gibt alle möglichen Kombinationen in Form einer verschachtelten Liste aus.

Mr. Xcoder
quelle
3
Sie und Ihre bitweise Sachen ... -~aund -~bkönnen einfach umgeschrieben werden a+1und b+1zur besseren Lesbarkeit: P
Stephen
1
@ Stephen Wie Sie sehen, ich bin spezialisiert auf Verschleierung
Mr. Xcoder
Funktioniert nicht für meinen neu hinzugefügten zweiten Testfall.
Undichte Nonne
@LeakyNun Zurückgerollt. Ich hatte keine Zeit, die Gültigkeit des Golfs zu überprüfen.
Mr. Xcoder
1

Jelly ,  19 15  14 Bytes

-4 mit Zeiger von Leaky Nun (Divisor eingebaut verwenden)

Ich bin fast zu 100% sicher, dass dies nicht der richtige Weg ist, aber hier ist ein erster Versuch.
Mal sehen, wer es mit einem Sieben- oder Acht-Byte übertrifft!
Ja ... siehe Lynns Antwort mit Erklärung!

g/־l/
ÆDp/ÇÐṂ

Ein monadischer Link, der eine Liste der beiden Zahlen erstellt und eine Liste der Möglichkeiten zurückgibt.

Probieren Sie es online!

Wie?

g/־l/  - Link: gcd divided by lcm: list [x, y]
g/      - reduce by gcd = gcd(x, y)
   æl/  - reduce by lcm = lcm(x,y)
  ÷     - divide

ÆDp/ÇÐṂ - Main link: list [a, b]    e.g. [160, 90]
ÆD      - divisors (vectorises)          [[1,2,4,5,8,10,16,20,32,40,80,160],[1,2,3,5,6,9,10,15,18,30,45,90]]
  p/    - reduce by Cartesian product    [[1,1],[1,2],...,[1,90],[2,1],[2,2],...,[2,90],....,[160,90]]
     ÐṂ - entries for which this is minimal:
    Ç   -   call the last link (1) as a monad
Jonathan Allan
quelle
Mal sehen, wer es mit einem Sieben- oder Acht-Byte übertrifft! -
Glaube
Du denkst sechs? ...FÜNF?!
Jonathan Allan
: P Nein ... Ich denke nicht weniger als ~ 13-15 ist möglich (Dennis würde natürlich nicht zustimmen!)
Mr. Xcoder
Divisor eingebaut?
Undichte Nonne
Ja, ÆDaber (Achselzucken) Gehirn offensichtlich nicht in Gang ...
Jonathan Allan
1

Perl 6 , 72 Bytes

{([X] map {grep $_%%*,1..$_},@^a).grep:{([lcm] @a)==([lcm] $_)==[*] $_}}

Probieren Sie es online!

Nimmt eine Liste (a, b). Gibt eine Liste aller möglichen Listen zurück (c, d).

Erläuterung:

-> @ab {
    # Generate all pairs (c, d)
    ([X]
         # where c divides a and d divides b.
         map { grep $_%%*, 1..$_ }, @ab)
    # Only keep pairs with lcm(a, b) = lcm(c, d) and lcm(c, d) = c * d.
    # The latter implies gcd(c, d) = 1.
    .grep: { ([lcm] @ab) == ([lcm] $_) == [*] $_ }
}
nwellnhof
quelle
1

Python 2 , 126 121 Bytes

def f(a,b):
 c=[1,1];p=2
 while p<=a*b:
	t=m=1
	while(a*b)%p<1:m*=p;t=b%p<1;a/=p**(a%p<1);b/=p**t
	p+=1;c[t]*=m
 return c

Probieren Sie es online!

Chas Brown
quelle
1

Python 2 + Sympy , 148 Bytes

from sympy import*
a,b=input()
c=d=z=1
while(a/c*c+b/d*d<a+b)+gcd(c,d)-1+(lcm(c,d)!=lcm(a,b)):E=c==d==z;Q=c==z;d=+E or Q+d;c=+Q or-~c;z+=E
print c,d

Probieren Sie es online!

-1 Danke an Jonathan Frech .

Diese Antwort funktioniert in Python 2 (nicht in Python 3) mit sympy.gcdund sympy.lcmanstelle von math.gcdund, math.lcmdie nur in Python 3 verfügbar sind. Und ja, das ist Brute Force :)

Erik der Outgolfer
quelle
Golfen im Gange ...
Erik der Outgolfer
Sie können ein Byte durch die Definition speichern können , Q=c==z;(7 Bytes) zu Beginn der while - Schleife und Ersetzen or(c==z)+dmit or Q+d(-4 Bytes) und c=+(c==z)ormit c=+Q or(-4 Bytes). ( TIO )
Jonathan Frech
Verwenden Sie nur als Frage den +Operator in d=+Eoder c=+(c==z), um einen Booleschen Wert in eine Ganzzahl umzuwandeln?
Jonathan Frech
@ JonathanFrech Ja, ich bin, da Sie nicht Trueund Falseanstelle von 1und 0in Sympy verwenden können.
Erik der Outgolfer
Das ist das erste Mal, dass ich gesehen habe, wo die Vanille +...irgendeinen Nutzen hat.
Jonathan Frech
1

Jelly , 13 Bytes

Ụ€’×
ÆEz0ÇZÆẸ

Probieren Sie es online! Meine erste Gelee Antwort! Bearbeiten: Funktioniert ÆEz0µỤ€’×µZÆẸauch für 13 Bytes. Erläuterung:

ÆE              Get prime factor exponents of both values (vectorises)
  z0            Zip but fill the shorter array with 0
    µ           New monadic link
     Ụ€         Grade up each pair (1-indexed)
       ’        Convert to 0-indexing (vectorises)
        ×       Multiply each pair by its grade (vectorises)
         µ      New monadic link
          Z     Zip back into separate lists of prime factor exponents
           ÆẸ   Turn prime exponent lists back into values (vectorises)
Neil
quelle
1

PARI / GP, 86 Bytes

Das macht genau das, was Lynn in ihrer Antwort sagt:

f(a,b)=forprime(p=2,a*b,v=valuation(a,p);w=valuation(b,p);if(w<v,b/=p^w,a/=p^v));[a,b]

Wenn ich den f(a,b)=Teil nicht zähle , sind es 79 Bytes.

Jeppe Stig Nielsen
quelle
1

05AB1E , 32 26 24 22 20 19 Bytes

Ó0ζεD`›0sǝ}øεā<ØsmP

Probieren Sie es online! Ich habe noch keine Ahnung, wie man in dieser Sprache schreibt, aber es ist zumindest kein Brute-Force-Algorithmus. Erläuterung:

Ó                       Get exponents of prime factors (vectorised)
 0ζ                     Zip, filling with 0
   ε      }             For each prime
    D`                  Extract the pair of exponents
      ›0sǝ              Overwrite the smaller with 0
           ø            Zip back into two lists of prime exponents
            ε           For each list (} implied)
             ā<Ø        Get a list of primes
                sm      Raise each prime to the exponent
                  P     Take the product
Neil
quelle
Was macht es
Lynn
Das Gleiche wie bei Ihnen, aber indem Sie die Exponenten tatsächlich faktorisieren und vergleichen und die Faktoren neu kombinieren.
Neil