Sumas de factores primos

27

2013 tiene la factorización prima 3*11*61. 2014 tiene la factorización prima 2*19*53. Una propiedad interesante con respecto a estas factorizaciones es que existen números primos distintos en las factorizaciones de 2013 y 2014 que se suma al mismo número: 11+61=19+53=72.

Escriba un programa o función que tome como entrada dos enteros positivos mayores que 1 y devuelva un valor verdadero si existe una suma de factores primos seleccionados de un número que sea igual a una suma de factores primos seleccionados en el segundo número, y un Falsey valor lo contrario.


Aclaraciones

  • Se pueden usar más de dos factores primos. No todos los factores primos del número deben usarse en la suma. No es necesario que el número de primos usados ​​de los dos números sea igual.
  • Incluso si un primo se eleva a una potencia mayor que 1 en la factorización de un número, solo se puede usar una vez en la suma de primos para el número.
  • 1 no es primo.
  • Ambos números de entrada serán menores que 2^32-1.

Casos de prueba

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

Este es el código de golf. Aplican reglas estándar. El código más corto en bytes gana.

Arcturus
fuente
66
Me gustan los desafíos como este, pero para los idiomas de golf, será una cadena de elementos incorporados: factor, uniquify, subconjuntos, sumas, superposición.
xnor
¿Podemos tomar la entrada como una matriz de dos elementos?
ETHproductions
@ETHproductions Por defecto, sí.
lirtosiast
¿Qué pasa con 14 (2 * 7) y 21 (3 * 7) true, ya que comparten el factor 7?
Simon Forsberg
@SimonForsbergMcFeely Sí
Arcturus

Respuestas:

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)!=[]

La función principal es fy llama a una función auxiliar g.

Sin golf:

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

Guardado 2 bytes gracias a Darth Alephalpha

Alex A.
fuente
3
Noté que esto fue rechazado. ¿Hay algo que haya pasado por alto? Si está mal, estaré encantado de solucionarlo, pero tal como está, funciona bien para mí y pasa todos los casos de prueba.
Alex A.
Creo que map(p->mapes más corto que (m=map)(p->m.
alephalpha
@DarthAlephalpha Buena llamada, gracias.
Alex A.
7

Pyth, 11 bytes

t@FmsMy{PdQ

Entrada en el formulario 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
fuente
1
Esto ahora es idéntico a la otra respuesta de Pyth, con la excepción de una letra movida;)
ETHproductions
@ETHproductions respondí antes de que Maltysen arreglara la suya; así que lo guardaré
lirtosiast el
7

Pyth - 17 12 11 bytes

Gracias a @FryAmTheEggman por corregir mi respuesta y guardar un byte.

@FmsMty{PdQ

Test Suite .

Maltysen
fuente
Creo que el uso de tyobras y salva un adiós?
FryAmTheEggman
@FryAmTheEggman gracias!
Maltysen
17
@Maltysen se ha perdido una oportunidad de oro para decir "ty"
undergroundmonorail
4

Haskell, 115106 bytes

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

Ejemplo de uso: 2013 # 2014-> True.

phace una lista de todos los factores primos de su argumento, elimina duplicados, hace una lista de todas las subsecuencias, elimina la primera (que siempre es la lista vacía) y finalmente suma las subsecuencias. #comprueba si p ano es igual a la diferencia p a \\ p b. Si no son iguales, tienen al menos un elemento común.

nimi
fuente
3

Japt, 25 bytes

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

Salidas trueo false. Pruébalo en línea!

Sin golfos y explicación

[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

Para obtener un byte adicional, puede dividir el código factorizar-único-combinar-suma entre ambas entradas, con la ventaja adicional de tener una complejidad de tiempo de O(O(25-byte version)^2):

Uk â à mx d@J<Vk â à mx bX
ETHproducciones
fuente
3

CJam, 23 bytes

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

Pruébalo aquí.

El valor verdadero será concatenado todas las sumas comunes, el valor falso es la cadena vacía.

Explicación

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
fuente
3

Brachylog , 10 9 bytes

{ḋd⊇+ℕ₁}ᵛ

Pruébalo en línea!

El predicado logra regresar [the sum, the sum]si existe, y falla si la suma no existe.

{            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 gracias a Fatalize (el creador de Brachylog) recordándome que existe el meta-predicado de verificación .

Cadena no relacionada
fuente
1
Puede usar en ᵛ - verifylugar de ˢ=guardar un byte.
Fatalize
2

MATL , 23 bytes

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

Utiliza la versión actual, 2.0.2 , que es anterior a este desafío.

Los números se proporcionan como dos entradas separadas. La salida es 0o 1.

Ejemplo

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

Explicación

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
fuente
2

Mathematica, 58 bytes

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

Explicación:

Esta es una función anónima.

Primero, IntersectingQverifica si dos listas se cruzan. Pero las entradas son números en lugar de listas, por lo que permanece sin evaluar. Por ejemplo, si las entradas son 2013y 2014, luego IntersectingQ@##&regresa IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&es otra función anónima que toma un número entero, obtiene una lista de sus factores primos sin repeticiones, toma el conjunto de potencia, elimina el conjunto vacío y luego toma la suma de cada conjunto. Entonces Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]vuelve {3, 11, 61, 14, 64, 72, 75}.

Luego mapea Tr/@Rest@Subsets[#&@@@FactorInteger@#]&sobre la expresión IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]y Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]son listas, para que podamos obtener el resultado de recopilación esta vez.

alephalpha
fuente
¡Llamar IntersectingQprimero es increíble! :)
Martin Ender
¿Podría agregar una explicación?
Lynn
2

PARI / GP , 98 bytes

Factoriza, toma primos ( [,1]), repite sobre subconjuntos no vacíos, suma y uniq, luego intersecta el resultado de esto para los dos números. El valor devuelto es el número de intersecciones, que es verdad a menos que sean 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
fuente
2

APL (Dyalog Extended) , 23 17 bytes SBCS

-5 gracias a ngn

Función de infijo tácito anónimo.

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

Pruébalo en línea!

⍥{... } aplique la siguiente función anónima a ambos argumentos:

 factores primos

 luego

 los únicos de esos

0+⍀., reducción de la tabla de suma de cero concatenada a cada factor

ϵ nlist (aplanar)

 la intersección

 luego

 el recuento de esos

1< ¿hay más de uno? (uno porque las sumas de ningún factor)

Adán
fuente
usando solo características de dyalog propiamente dicho: p+.×⊤1↓⍳2*≢p←->1↓∊(⊢,+)/0,⍨
ngn
aún más corto:1↓∊∘.+/0,¨
NGN
que es 1↓∊0∘.+.,un producto interno - con qué frecuencia ves eso :)
ngn
si entiendo correctamente, esto también debería funcionar:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
ngn
@ngn Gracias. Hecho.
Adám
2

05AB1E , 10 8 bytes

f€æO`å¦à

-2 bytes gracias a @Emigna .

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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
fuente
1
f€æO`å¦àdebería funcionar para 8.
Emigna
1

Python 3 , 206 bytes

Esta es una función lambda (m), que toma 2 números y devuelve un conjunto que contiene cualquier suma de factores primos que tengan en común. En Python, este es un valor verdadero cuando no está vacío, y un valor falso cuando está vacío.

Editar: Resulta que mi respuesta original no funcionó para las entradas principales, como lo señaló @JoKing. Esto se ha solucionado (junto con algunos otros errores) a un costo trágico de 40 bytes.

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

Explicación rápida usando comentarios:

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

Pruébalo en línea!

senox13
fuente
Esto no funciona para el primer caso de prueba 5,6, ya que no maneja entradas principales
Jo King
@JoKing Gracias por atrapar eso. La respuesta ha sido actualizada.
senox13
1

APL (NARS), 50 caracteres, 100 bytes

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

aquí π encontraría la matriz de factores en su argumento;

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

sería la función que encuentra todos los subconjuntos ... tengo que decir que parece {⍵operator itsArguments} ¨ (para cada izquierda) y ¨ (para cada derecha) pueden imitar el bucle con un número fijo de ciclos y ¨¨ está bien en para ver subconjuntos de un conjunto ... esta forma de ver parece reducir los símbolos en los bucles de descripción ...; prueba

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

Un pequeño análisis:

π¨⍵  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
fuente
1

Japt , 14 bytes

®k â ã mx
rf Ê

Guardado 3 bytes gracias a @Shaggy

Intentalo

Encarnación de la ignorancia
fuente
La segunda línea puede ser ÎfUÌ lo, más corto todavía, rf l. sería la forma más corta de hacerlo, pero Oliver te ganó.
Shaggy
1

Jalea , 18 9 bytes

ÆfŒPḊ§)f/

Pruébalo en línea!

Gracias a @Jonathan Allan por -9 y la increíble ayuda :).

Toma la entrada como una matriz de dos elementos. Explicación del código:

      )    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
fuente
Tome la entrada como una lista de dos valores y evite el ,. El ẒƇes redundante, no hay factores primos no primos. Entonces ÆFḢ€ es justo Æf, excepto que este último nos da las repeticiones que realmente podríamos necesitar, por ejemplo 26=2*13y 125=5*5*5mientras 2+13=5+5+5. Sin embargo, incluso con eso, no es lo suficientemente bueno, por ejemplo, en lugar de 26usar, 182=2*7*13que también debería encontrar eso, 2+13=5+5+5pero no lo hace; en su lugar, queremos el conjunto de potencia ( ŒP) sin el elemento inicial, vacío, (podemos usar ). S€aquí puede ser reemplazado con §. - Probablemente pueda guardar bytes con $y Ɗ-.
Jonathan Allan
No hay necesidad de esas quicks que he mencionado al final podemos usar )y con mis correcciones para hacer que funcione correctamente (además de la sustitución œ&con f) el código de bytes es de 9: ÆfŒPḊ§)f/ try-it
Jonathan Allan
Actualizado con una explicación. Gracias de nuevo :)!
Ven el
1
Actualicé un poco tu explicación.
Jonathan Allan
0

Gaia , 16 11 bytes

ḍzΣ¦
↑@↑&ỵ!

Pruébalo en línea!

La función superior (primera línea) calcula las sumas del conjunto de potencia de los factores primos, y la segunda función determina si alguno de los elementos de la intersección no es cero.

Giuseppe
fuente