Summen der Primfaktoren

27

2013 hat die Primfaktorisierung 3*11*61. 2014 hat die Primfaktorisierung 2*19*53. Eine interessante Eigenschaft dieser Faktorisierungen in Bezug auf ist , dass es in den Faktorisierungen von 2013 und 2014 diese Summe auf die gleiche Anzahl verschiedene Primzahlen bestehen: 11+61=19+53=72.

Schreiben Sie ein Programm oder eine Funktion, die zwei positive ganze Zahlen größer als 1 als Eingabe verwendet und einen Wahrheitswert zurückgibt, wenn eine Summe ausgewählter Primfaktoren einer Zahl vorhanden ist, die einer Summe ausgewählter Primfaktoren in der zweiten Zahl entspricht, und a Falscher Wert sonst.


Klarstellungen

  • Es können mehr als zwei Primfaktoren verwendet werden. Nicht alle Primfaktoren der Zahl müssen in der Summe verwendet werden. Es ist nicht erforderlich, dass die Anzahl der Primzahlen aus den beiden Zahlen gleich ist.
  • Selbst wenn eine Primzahl bei der Faktorisierung einer Zahl auf eine Potenz größer als 1 angehoben wird, kann sie in der Summe der Primzahlen für die Zahl nur einmal verwendet werden.
  • 1 ist keine Primzahl.
  • Beide Eingabenummern sind kleiner als 2^32-1.

Testfälle

5,6
    5=5
    6=2*3
    5=2+3
==>True

2013,2014
    2013=3*11*61
    2014=2*19*53
    11+61=19+53
==>True

8,15
    8=2^3
    15=3*5
    No possible sum
==>False

21,25
    21=3*7
    25=5^2
    No possible sum (can't do 3+7=5+5 because of exponent)
==>False

Das ist Code Golf. Es gelten Standardregeln. Kürzester Code in Bytes gewinnt.

Arcturus
quelle
6
Ich mag Herausforderungen wie diese, aber für Golfsprachen wird es eine Kette von eingebauten Elementen sein: Faktor, Eindeutigkeit, Teilmengen, Summen, Überlappung.
xnor
Können wir Eingaben als Array mit zwei Elementen annehmen?
ETHproductions
@ETHproductions Standardmäßig ja.
Lirtosiast
Was ist mit 14 (2 * 7) und 21 (3 * 7) true, da sie den Faktor teilen 7?
Simon Forsberg
@ SimonForsbergMcFeely Ja
Arcturus

Antworten:

10

Julia, 95 93 Bytes

g(x)=reduce(vcat,map(p->map(sum,p),partitions([keys(factor(x))...])))
f(a,b)=g(a)∩g(b)!=[]

Die primäre Funktion ist fund ruft eine Hilfsfunktion auf g.

Ungolfed:

function g(x::Integer)
    # Find the sum of each combination of prime factors of the input
    return reduce(vcat, map(p -> map(sum, p), partitions([keys(factor(x))...])))
end

function f(a::Integer, b::Integer)
    # Determine whether there's a nonzero intersection of the factor
    # sums of a and b
    return !isempty(g(a)  g(b))
end

2 Bytes dank Darth Alephalpha gespeichert

Alex A.
quelle
3
Mir ist aufgefallen, dass dies abgelehnt wurde. Was habe ich übersehen? Wenn es falsch ist, würde ich es gerne beheben, aber so wie es aussieht, funktioniert es einwandfrei für mich und besteht alle Testfälle.
Alex A.
Ich denke map(p->mapist kürzer als (m=map)(p->m.
Alephalpha
@DarthAlephalpha Guter Anruf, danke.
Alex A.
7

Pyth, 11 Bytes

t@FmsMy{PdQ

Eingabe in das Formular 30,7.

t@FmsMy{PdQ     implicit: Q=input tuple
      y         powerset of
       {        unique elements of
        Pd      prime factorizations of d
    sM          Map sum over each element of the powerset
    sMy{Pd      lambda d: all sums of unique prime factors of d
   m      Q     Map over Q. Produces a two-element list.
 @F             Fold list intersection
t               Remove first element, which is a 0.
                If no other common sums, the remaining empty list is falsy.
Lirtosiast
quelle
1
Dies ist jetzt identisch mit der anderen Pyth-Antwort, mit Ausnahme eines verschobenen Buchstabens;)
ETHproductions
@ETHproductions Ich antwortete, bevor Maltysen ihre reparierte; Also werde ich es behalten.
Lirtosiast
7

Pyth - 17 12 11 Bytes

Vielen Dank an @FryAmTheEggman für das Korrigieren meiner Antwort und das Speichern eines Bytes.

@FmsMty{PdQ

Test Suite .

Maltysen
quelle
Ich denke mit tyfunktioniert und spart ein tschüss?
FryAmTheEggman
@FryAmTheEggman danke!
Maltysen
17
@Maltysen Sie haben eine einmalige Gelegenheit verpasst, "ty" zu sagen
undergroundmonorail
4

Haskell, 115 106 Bytes

import Data.Numbers.Primes
import Data.List
p=map sum.tail.subsequences.nub.primeFactors
a#b=p a/=p a\\p b

Anwendungsbeispiel: 2013 # 2014-> True.

perstellt eine Liste aller Primfaktoren des Arguments, entfernt Duplikate, erstellt eine Liste aller Untersequenzen, löscht die erste (die immer die leere Liste ist) und summiert schließlich die Untersequenzen. #prüft, ob p adie Differenz ungleich ist p a \\ p b. Wenn nicht gleich, haben sie mindestens ein gemeinsames Element.

nimi
quelle
3

Japt, 25 Bytes

[UV]=N®k â à mx};Ud@J<VbX

Ausgänge trueoder false. Probieren Sie es online!

Ungolfed und Erklärung

[UV]=N®   k â à mx};Ud@ J<VbX
[UV]=NmZ{Zk â à mx};UdX{J<VbX

          // Implicit: N = list of inputs
[UV]=N    // Set variables U and V to the first to items in N,
mZ{    }  // with each item Z mapped to:
Zk        //  Generate list of Z's factors.
â         //  Keep only the unique items.
à         //  Generate all combinations.
mx        //  Sum each combination.
UdX{      // Check if any item X in U fulfills this condition:
J<VbX     //  -1 is less than V.indexOf(X).
          // Implicit: output last expression

Für ein zusätzliches Byte können Sie den Code für die Faktorisierung, die eindeutige Kombination und die Summe zwischen beiden Eingängen aufteilen. Der zusätzliche Vorteil besteht in der zeitlichen Komplexität von O(O(25-byte version)^2):

Uk â à mx d@J<Vk â à mx bX
ETHproductions
quelle
3

CJam, 23 Bytes

q~{mf_&0a\{1$f++}/}/&0-

Teste es hier.

Der Wahrheitswert sind alle gebräuchlichen zusammengesetzten Summen, der falsche Wert ist die leere Zeichenfolge.

Erläuterung

q~     e# Read and evaluate input.
{      e# For each of the two numbers...
  mf   e# Get the prime factors.
  _&   e# Remove duplicates.
  0a\  e# Put an array containing a 0 below to initialise the list of possible sums.
  {    e# For each prime factor...
    1$ e#   Make a copy of the available sums so far.
    f+ e#   Add the current factor to each of them.
    +  e#   Combine with the list of sums without that factor.
  }/
}/
&      e# Set intersection between the two lists of sums.
0-     e# Remove the 0 which is always in the intersection.
Martin Ender
quelle
3

Brachylog , 10 9 Bytes

{ḋd⊇+ℕ₁}ᵛ

Probieren Sie es online!

Das Prädikat gibt erfolgreich zurück, [the sum, the sum]wenn es vorhanden ist, und schlägt fehl, wenn die Summe nicht vorhanden ist.

{            Start of inline predicate.
 ḋ           The prime factors of the input,
  d          with duplicates removed.
   ⊇         Some subset of the unique prime factors
    +ℕ₁      has a sum greater than 0 which is output.
       }ᵛ    The predicate can have the same output for both elements of the input.

-1 Byte dank Fatalize (dem Schöpfer von Brachylog), der mich daran erinnert, dass das Verify- Meta-Prädikat existiert.

Nicht verwandte Zeichenfolge
quelle
1
Sie können ᵛ - verifyanstelle von ˢ=ein Byte speichern.
Fatalize
2

MATL , 23 Bytes

2:"iYfutn2w^1-:B!Y*]!=z

Verwendet die aktuelle Version 2.0.2 , die älter als diese Herausforderung ist.

Die Nummern werden als zwei separate Eingänge bereitgestellt. Ausgang ist 0oder 1.

Beispiel

>> matl 2:"iYfutn2w^1-:B!Y*]!=z
> 2013
> 2014
1

Erläuterung

2:           % vector of two numbers, to generate two iterations
"            % for loop
  i          % input number                                                 
  Yfu        % get prime factors without repetitions
  tn         % duplicate and get number of elements in array N 
  2w^1-:     % numbers from 1 to 2^N                                        
  B!Y*       % convert to binary, transpose and matrix multiply to produce all sums
]            % end                                                      
!=z          % true if any value is equal to any other
Luis Mendo
quelle
2

Mathematica, 58 Bytes

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&/@IntersectingQ@##&

Erläuterung:

Dies ist eine anonyme Funktion.

Zuerst wird IntersectingQgeprüft , ob zwei Listen schneiden. Die Eingaben sind jedoch Zahlen anstelle von Listen, sodass sie nicht ausgewertet werden. Wenn die Eingaben beispielsweise 2013und sind 2014, wird IntersectingQ@##&zurückgegeben IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&ist eine weitere anonyme Funktion, die eine ganze Zahl annimmt, eine Liste ihrer Primfaktoren ohne Wiederholungen abruft, die Potenzmenge nimmt, die leere Menge entfernt und dann die Summe jeder Menge nimmt. Also Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]kehrt zurück {3, 11, 61, 14, 64, 72, 75}.

Dann Tr/@Rest@Subsets[#&@@@FactorInteger@#]&über den Ausdruck mappen IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]und Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]sind Listen, damit wir dieses Mal das Erfassungsergebnis erhalten können.

Alephalpha
quelle
Der Aufruf IntersectingQerste ist erstaunlich! :)
Martin Ender
Könnten Sie eine Erklärung hinzufügen?
Lynn
2

PARI / GP , 98 Bytes

Factor, grab primes ( [,1]), loop über nicht leere Subsets, sum und uniq, schneiden dann das Ergebnis für die beiden Zahlen. Der zurückgegebene Wert ist die Anzahl der Schnittpunkte, die wahr ist, sofern sie nicht 0 sind.

f(n,v=factor(n)[,1])=Set(vector(2^#v-1,i,vecsum(vecextract(v,i))))
g(m,n)=#setintersect(f(m),f(n))
Charles
quelle
2

APL (Dyalog Extended) , 23 SBCS mit 17 Bytes

-5 danke an ngn

Anonyme stillschweigende Infix-Funktion.

1<≢⍤∩⍥(∊0+⍀.,∪⍤⍭)

Probieren Sie es online!

⍥{} Wenden Sie auf beide Argumente die folgende anonyme Funktion an:

 Primfaktoren

 dann

 die einzigartigen von denen

0+⍀., Additionstabellenreduktion von Null verknüpft mit jedem Faktor

ϵ nlist (Abflachen)

 Der Schnittpunkt

 dann

 die Bilanz von denen

1< gibt es mehr als eine? (Einer, weil die Summe ohne Faktoren)

Adam
quelle
mit nur funktionen von dyalog richtiges: p+.×⊤1↓⍳2*≢p←->1↓∊(⊢,+)/0,⍨
ngn
noch kürzer:1↓∊∘.+/0,¨
ngn
das ist 1↓∊0∘.+.,ein inouter produkt - wie oft siehst du das :)
ngn
wenn ich das richtig verstehe , sollte das auch funktionieren:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
ngn
@ngn Danke. Getan.
Adám
2

05AB1E , 10 8 Bytes

f€æO`å¦à

-2 Bytes dank @Emigna .

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

Erläuterung:

f         # Get all distinct prime factors of both values in the (implicit) input-list
          #  i.e. [2013,2014] → [[3,11,61],[2,19,53]]
 ۾       # Get the powerset for each
          #  → [[[],[3],[11],[3,11],[61],[3,61],[11,61],[3,11,61]],
          #     [[],[2],[19],[2,19],[53],[2,53],[19,53],[2,19,53]]]
   O      # Sum each inner-most list
          #  → [[0,3,11,14,61,64,72,75],[0,2,19,21,53,55,72,74]]
    `     # Push both lists to the stack
     å    # Check for each value in the second list if it's present in the first list
          #  → [1,0,0,0,0,0,1,0]
      ¦   # Remove the first item (since the powerset included empty leading lists)
          #  → [0,0,0,0,0,1,0]
       à  # Check if any are truthy by taking the maximum (which is output implicitly)
          #  → 1
Kevin Cruijssen
quelle
1
f€æO`å¦àsollte für 8 arbeiten.
Emigna
1

Python 3 , 206 Bytes

Dies ist eine Lambda-Funktion (m), die zwei Zahlen aufnimmt und eine Menge zurückgibt, die alle Summen von Primfaktoren enthält, die sie gemeinsam haben. In Python ist dies ein wahrer Wert, wenn er nicht leer ist, und ein falscher Wert, wenn er leer ist.

Bearbeiten: Es stellte sich heraus, dass meine ursprüngliche Antwort für Primzahlen nicht funktioniert hat, wie von @JoKing hervorgehoben. Dies wurde (zusammen mit einigen anderen Fehlern) auf tragische Kosten von 40 Byte behoben.

q=__import__('itertools').permutations
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
m=lambda a,b:s(p(a))&s(p(b))

Schnelle Erklärung mit Kommentaren:

#Alias for permutations function
q=__import__('itertools').permutations
#Returns set of prime factors of n, including n, if prime
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
#Returns all possible sums of 2 or more elements in the given set
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
#Returns any shared possible sums of prime factors of a and b (the intersection of the sets)
m=lambda a,b:s(p(a))&s(p(b))

Probieren Sie es online!

senox13
quelle
Dies funktioniert nicht für den ersten Testfall 5,6, da er keine Primzahlen verarbeitet
Jo King,
@JoKing Danke, dass du das erwischt hast. Die Antwort wurde aktualisiert.
Senox13
1

APL (NARS), 50 Zeichen, 100 Byte

{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}

hier würde π die Reihe von Faktoren in seinem Argument finden;

{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵} 

wäre die funktion, die alle teilmengen findet ... ich muss sagen, dass es so aussieht, als ob {⍵operator itsArguments} ¨ (für jede linke) und ¨ (für jede rechte) loop mit fester zykluszahl imitieren kann und ¨¨ in ok ist um Teilmengen einer Menge zu sehen ... auf diese Weise scheint es, dass Symbole in Beschreibungsschleifen reduziert werden ...; Prüfung

  h←{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}
  h 5 6
1
  h 2013 2014
1
  h 8 15
0
  h 21 25
0

Eine kleine Analyse:

π¨⍵  for each arg apply factor 
∪¨ for each arg apply unique
{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨ for each arg apply subsets
{⍵∼⊂⍬}¨ for each argument subtract Zilde enclosed (that would be the void set)
+/¨¨ for each arg (for each arg apply +/)
⍬≢↑∩/ apply intersection, get the first argument and see if it is Zilde (this it is right because enclosed Zilde it seems is the void set)
RosLuP
quelle
1

Japt , 14 Bytes

®k â ã mx
rf Ê

3 Bytes gespart dank @Shaggy

Versuch es

Verkörperung der Ignoranz
quelle
Die zweite Zeile kann ÎfUÌ loder noch kürzer sein rf l. Das wäre der kürzeste Weg, aber Oliver hat dich geschlagen.
Shaggy
1

Jelly , 18 9 Bytes

ÆfŒPḊ§)f/

Probieren Sie es online!

Vielen Dank an Jonathan Allan für -9 und die tolle Hilfe :).

Übernimmt die Eingabe als Array von zwei Elementen. Code Erklärung:

      )    Call Chain 1 for each integer in the input array

ÆfŒPḊ§     Chain 1:
Æf           Compute a list of the prime factors of the integer
  ŒP         Powerset of P, with duplicates and an empty element
    Ḋ        Drop said empty element
     §       Vectorized sum: sum every combination

       f/  Chain 2:
        /    Reduce (the resulting list of two lists of possible sums) by...
       f     ...removing elements to the left that are not in the right

¹

Ven
quelle
Nehmen Sie die Eingabe als Liste mit zwei Werten und vermeiden Sie das ,. Das ẒƇist überflüssig, es gibt keine Nicht-Primfaktoren. Dann ÆFḢ€ ist es gerecht Æf, mit der Ausnahme, dass letzteres uns die Wiederholungen gibt, die wir zum Beispiel 26=2*13und 125=5*5*5währenddessen tatsächlich benötigen 2+13=5+5+5. Auch das ist jedoch nicht gut genug, zum Beispiel anstatt zu 26verwenden, 182=2*7*13was auch nicht gut genug sein sollte 2+13=5+5+5- stattdessen wollen wir das power-set ( ŒP) ohne das führende, leere Element (das wir verwenden können ). S€hier kann ersetzt werden durch §. - Mit $und Ɗ- können Sie wahrscheinlich Bytes speichern .
Jonathan Allan
Ich brauche die am Ende erwähnten Quicks nicht, die wir verwenden können, )und mit meinen Fixes ist der Code 9 Bytes lang (plus Ersetzen œ&durch f): ÆfŒPḊ§)f/ try-it
Jonathan Allan
Aktualisiert mit einer Erklärung. Danke nochmal :)!
Ven
1
Ich habe deine Erklärung ein wenig aktualisiert.
Jonathan Allan
0

Gaia , 16 11 Bytes

ḍzΣ¦
↑@↑&ỵ!

Probieren Sie es online!

Die obere Funktion (erste Zeile) berechnet die Summen des Potenzsatzes der Primfaktoren und die zweite Funktion ermittelt, ob eines der Elemente der Schnittmenge ungleich Null ist.

Giuseppe
quelle