Sumy czynników pierwszych

27

Rok 2013 ma zasadnicze znaczenie 3*11*61. 2014 ma pierwszoplanową faktoryzację 2*19*53. Interesująca nieruchomość dotyczące tych factorizations jest to, że istnieją różne liczby pierwsze w factorizations 2013 i 2014, że suma na ten sam numer: 11+61=19+53=72.

Napisz program lub funkcję, która przyjmuje na wejściu dwie dodatnie liczby całkowite większe od 1 i zwraca prawdziwą wartość, jeśli istnieje suma wybranych czynników pierwszych jednej liczby, która jest równa sumie wybranych czynników pierwszych w drugiej liczbie, oraz w przeciwnym razie wartość falsey.


Wyjaśnienia

  • Można użyć więcej niż dwóch głównych czynników. Nie wszystkie czynniki pierwsze liczby muszą być użyte w sumie. Nie jest konieczne, aby liczba liczb pierwszych używanych z dwóch liczb była równa.
  • Nawet jeśli liczba pierwsza zostanie podniesiona do pewnej potęgi większej niż 1 w rozkładzie liczb na liczbę, można jej użyć tylko raz w sumie liczb pierwszych dla liczby.
  • 1 nie jest liczbą pierwszą.
  • Obie liczby wejściowe będą mniejsze niż 2^32-1.

Przypadki testowe

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

To jest kod golfowy. Obowiązują standardowe zasady. Najkrótszy kod w bajtach wygrywa.

Arktur
źródło
6
Lubię takie wyzwania, ale w przypadku języków golfowych będzie to łańcuch wbudowanych elementów: uwzględnianie, unikanie, podzbiory, sumy, nakładanie się.
xnor
Czy możemy brać dane wejściowe jako tablicę dwuelementową?
ETHproductions
@ETHproductions Domyślnie tak.
lirtosiast
Co powiesz na 14 (2 * 7) i 21 (3 * 7), trueponieważ dzielą ten czynnik 7?
Simon Forsberg,
@SimonForsbergMcFeely Tak
Arcturus

Odpowiedzi:

10

Julia, 95 93 bajtów

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

Podstawową funkcją jest fi wywołuje funkcję pomocnika g.

Nie golfowany:

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

Zaoszczędzono 2 bajty dzięki Darth Alephalpha

Alex A.
źródło
3
Zauważyłem, że to zostało przegłosowane. Czy jest coś, co przeoczyłem? Jeśli to źle, chętnie to naprawię, ale w obecnej postaci działa dla mnie dobrze i przechodzi wszystkie testy.
Alex A.,
Myślę, że map(p->mapjest krótszy niż (m=map)(p->m.
alephalpha
@DarthAlephalpha Dobre połączenie, dzięki.
Alex A.,
7

Pyth, 11 bajtów

t@FmsMy{PdQ

Wprowadź w formularzu 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
źródło
1
Jest to teraz identyczna z drugą odpowiedzią Pytha, z wyjątkiem jednej przeniesionej litery;)
ETHproductions
@ETHproductions Odpowiedziałem, zanim Maltysen je naprawił; więc zatrzymam to.
lirtosiast
7

Pyth - 17 12 11 bajtów

Dzięki @FryAmTheEggman za ustalenie mojej odpowiedzi i zapisanie bajtu.

@FmsMty{PdQ

Pakiet testowy .

Maltysen
źródło
Myślę, że korzystanie tydziała i oszczędza do widzenia?
FryAmTheEggman,
@FryAmTheEggman dzięki!
Maltysen,
17
@Maltysen przegapiłaś złotą okazję, by powiedzieć „ty”
podziemny
4

Haskell, 115 106 bajtów

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

Przykład użycia: 2013 # 2014-> True.

ptworzy listę wszystkich głównych czynników argumentu, usuwa duplikaty, tworzy listę wszystkich podsekwencji, upuszcza pierwszą (która zawsze jest pustą listą) i na koniec sumuje podsekwencje. #sprawdza, czy p anie jest równa różnicy p a \\ p b. Jeśli nie są równe, mają co najmniej jeden wspólny element.

nimi
źródło
3

Japt, 25 bajtów

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

Wyjścia truelub false. Wypróbuj online!

Bez golfa i wyjaśnienia

[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

Aby uzyskać dodatkowy bajt, możesz podzielić kod faktoryzujący-unikalny-połączyć-sumę między oba dane wejściowe, z dodatkową zaletą posiadania złożoności czasowej O(O(25-byte version)^2):

Uk â à mx d@J<Vk â à mx bX
ETHprodukcje
źródło
3

CJam, 23 bajty

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

Sprawdź to tutaj.

Prawda będzie sumą wszystkich wspólnych sum, wartość fałsz jest pustym ciągiem.

Wyjaśnienie

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
źródło
3

Brachylog , 10 9 bajtów

{ḋd⊇+ℕ₁}ᵛ

Wypróbuj online!

Predykat pomyślnie zwróci, [the sum, the sum]jeśli istnieje, i nie powiedzie się, jeśli suma nie istnieje.

{            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 bajt dzięki Fatalize (twórcy Brachylog) przypominając mi, że istnieje meta-predykat weryfikacji .

Niepowiązany ciąg
źródło
1
Możesz użyć ᵛ - verifyzamiast ˢ=zapisać jeden bajt.
Fatalize
2

MATL , 23 bajty

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

Wykorzystuje bieżącą wersję 2.0.2 , która jest wcześniejsza niż to wyzwanie.

Liczby podano jako dwa osobne dane wejściowe. Dane wyjściowe to 0lub 1.

Przykład

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

Wyjaśnienie

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
źródło
2

Mathematica, 58 bajtów

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

Wyjaśnienie:

To anonimowa funkcja.

Najpierw IntersectingQsprawdza, czy przecinają się dwie listy. Ale dane wejściowe są liczbami zamiast listami, więc pozostają bezcenne. Na przykład, jeśli dane wejściowe są 2013i 2014, a następnie IntersectingQ@##&wraca IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&to kolejna anonimowa funkcja, która pobiera liczbę całkowitą, pobiera listę czynników pierwszych bez powtórzeń, pobiera zestaw mocy, usuwa pusty zbiór, a następnie pobiera sumę każdego zestawu. Więc Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]wraca {3, 11, 61, 14, 64, 72, 75}.

Następnie odwzoruj Tr/@Rest@Subsets[#&@@@FactorInteger@#]&wyrażenie IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]i Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]są listami, więc tym razem możemy uzyskać wynik zbierania.

alephalpha
źródło
Zadzwoń jako IntersectingQpierwszy jest niesamowity! :)
Martin Ender,
Czy możesz dodać wyjaśnienie?
Lynn,
2

PARI / GP , 98 bajtów

Współczynnik, grab primes ( [,1]), zapętlaj niepuste podzbiory, suma i uniq, a następnie przecinaj wynik tego dla dwóch liczb. Zwrócona wartość to liczba skrzyżowań, co jest prawdą, chyba że są równe 0.

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
źródło
2

APL (Dyalog Extended) , 23 17 bajtów SBCS

-5 dzięki ngn

Anonimowa funkcja ukrytej poprawki.

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

Wypróbuj online!

⍥{} Zastosuj następującą anonimową funkcję do obu argumentów:

 czynniki pierwsze

 następnie

 jedyne w swoim rodzaju

0+⍀., redukcja tabeli dodawania o zero połączona z każdym czynnikiem

ε nlist (spłaszczyć)

 skrzyżowanie

 następnie

 suma tych

1< czy jest więcej niż jeden? (jeden, ponieważ sumy żadnych czynników)

Adám
źródło
używając tylko funkcji z właściwego dyalogu: p+.×⊤1↓⍳2*≢p←->1↓∊(⊢,+)/0,⍨
ngn
jeszcze krótszy:1↓∊∘.+/0,¨
ngn
który jest 1↓∊0∘.+.,produktem inouter - jak często to widzisz :)
ngn
jeśli dobrze rozumiem , to też powinno działać:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
ngn
@ngn Thanks. Gotowy.
Adám
2

05AB1E , 10 8 bajtów

f€æO`å¦à

-2 bajty dzięki @Emigna .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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
źródło
1
f€æO`å¦àpowinien działać dla 8.
Emigna
1

Python 3 , 206 bajtów

Jest to funkcja lambda (m), która przyjmuje 2 liczby i zwraca zestaw zawierający dowolne sumy czynników pierwszych, które mają ze sobą wspólnego. W Pythonie jest to prawdziwa wartość, gdy nie jest pusta, i wartość falsey, gdy jest pusta.

Edycja: Okazało się, że moja pierwotna odpowiedź nie działała dla głównych danych wejściowych, jak wskazał @JoKing. Zostało to naprawione (wraz z kilkoma innymi błędami) przy tragicznym koszcie 40 bajtów.

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))

Szybkie wyjaśnienie za pomocą komentarzy:

#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))

Wypróbuj online!

senox13
źródło
Nie działa to w pierwszym przypadku testowym 5,6, ponieważ nie obsługuje głównych danych wejściowych
Jo King
@JoKing Dzięki za złapanie tego. Odpowiedź została zaktualizowana.
senox13
1

APL (NARS), 50 znaków, 100 bajtów

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

tutaj π znalazłby szereg czynników w swoim argumencie;

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

byłaby funkcja znajdująca wszystkie podzbiory ... muszę powiedzieć, że wydaje się, że {⍵operator itsArguments} ¨ (dla każdego lewego) i ¨ (dla każdego prawego) może imitować pętlę o ustalonej liczbie cykli i ¨¨ jest w porządku aby zobaczyć podzbiory jednego zestawu ... ten sposób widzenia wydaje się redukować symbole w opisie pętli ...; test

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

Jedna mała analiza:

π¨⍵  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
źródło
1

Japt , 14 bajtów

®k â ã mx
rf Ê

Zaoszczędź 3 bajty dzięki @Shaggy

Spróbuj

Wcielenie ignorancji
źródło
Druga linia może być ÎfUÌ lalbo krótszy wciąż rf l. byłby to najkrótszy sposób, ale Oliver cię do tego pobił.
Kudłaty
1

Galaretka , 18 9 bajtów

ÆfŒPḊ§)f/

Wypróbuj online!

Dzięki @Jonathan Allan za -9 i niesamowitą pomoc :).

Pobiera dane wejściowe jako tablicę dwóch elementów. Objaśnienie kodu:

      )    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
źródło
Weź dane wejściowe jako listę dwóch wartości i unikaj ,. ẒƇJest zbędny, nie ma non-prime prime-czynników. To ÆFḢ€ jest po prostu Æf, z tym wyjątkiem, że to drugie daje nam powtórzenia, których moglibyśmy potrzebować, na przykład 26=2*13i na 125=5*5*5chwilę 2+13=5+5+5. Mimo to jednak nie jest wystarczająco dobry, na przykład zamiast 26użycia, 182=2*7*13który również powinien to znaleźć, 2+13=5+5+5ale nie - zamiast tego chcemy power-set ( ŒP) bez wiodącego, pustego elementu (możemy użyć ). S€tutaj można zastąpić §. - Prawdopodobnie możesz zapisać bajty za pomocą $i Ɗ-.
Jonathan Allan
Nie ma potrzeby tych postów, o których wspomniałem na końcu, których możemy użyć, )a wraz z moimi poprawkami, aby działał poprawnie (plus zastąpienie œ&go f), kod ma 9 bajtów: ÆfŒPḊ§)f/ spróbuj
Jonathan Allan
Zaktualizowano z wyjaśnieniem. Jeszcze raz dziękuję :)!
Ven
1
Trochę zaktualizowałem twoje wyjaśnienie.
Jonathan Allan
0

Gaia , 16 11 bajtów

ḍzΣ¦
↑@↑&ỵ!

Wypróbuj online!

Górna funkcja (pierwsza linia) oblicza sumy zestawu mocy czynników pierwszych, a druga funkcja sprawdza, czy którykolwiek z elementów przecięcia jest niezerowy.

Giuseppe
źródło