Soma de fatores primos

27

2013 tem a fatoração principal 3*11*61. 2014 tem a fatoração principal 2*19*53. Uma propriedade interessante em relação a estes fatorações é que existem números primos distintos nas fatorações de 2013 e 2014 que soma para o mesmo número: 11+61=19+53=72.

Escreva um programa ou função que tenha como entrada dois números inteiros positivos maiores que 1 e retorne um valor verdadeiro se existir uma soma dos fatores primos selecionados de um número que seja igual a uma soma dos fatores primos selecionados no segundo número e um valor falsey caso contrário.


Esclarecimentos

  • Mais de dois fatores principais podem ser usados. Nem todos os fatores primos do número precisam ser usados ​​na soma. Não é necessário que o número de números primos usados ​​nos dois números seja igual.
  • Mesmo que um primo seja elevado a uma potência maior que 1 na fatoração de um número, ele pode ser usado apenas uma vez na soma dos primos do número.
  • 1 não é primo.
  • Os dois números de entrada serão menores que 2^32-1.

Casos de teste

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

Isso é código de golfe. Aplicam-se regras padrão. O menor código em bytes vence.

Arcturus
fonte
6
Gosto de desafios como esse, mas para idiomas de golfe, haverá uma cadeia de itens incorporados: fator, unificação, subconjuntos, somas, sobreposição.
Xnor
Podemos considerar a entrada como uma matriz de dois itens?
ETHproductions
@ETHproductions Por padrão, sim.
lirtosiast
O que dizer de 14 (2 * 7) e 21 (3 * 7), é isso true, pois eles compartilham o fator 7?
Simon Forsberg
@SimonForsbergMcFeely Yes
Arcturus

Respostas:

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

A função principal é fe chama uma função auxiliar 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

Guardado 2 bytes graças a Darth Alephalpha

Alex A.
fonte
3
Percebi que isso foi prejudicado. Existe algo que eu tenha esquecido? Se estiver errado, eu ficaria feliz em corrigi-lo, mas, como está, funciona bem para mim e passa em todos os casos de teste.
Alex A.
Eu acho que map(p->mapé mais curto que (m=map)(p->m.
alephalpha
@DarthAlephalpha Boa chamada, obrigado.
Alex A.
7

Pitão, 11 bytes

t@FmsMy{PdQ

Entrada no formulário 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
fonte
1
Agora isso é idêntico à outra resposta Pyth, com exceção de uma letra movida;)
ETHproductions
@ETHproductions eu respondi antes que Maltysen os consertasse; então eu vou mantê-lo.
lirtosiast
7

Pitão - 17 12 11 bytes

Obrigado a @FryAmTheEggman por corrigir minha resposta e salvar um byte.

@FmsMty{PdQ

Conjunto de Teste .

Maltysen
fonte
Eu acho que usando tyobras e salva um tchau?
FryAmTheEggman
@FryAmTheEggman thanks!
Maltysen
17
@Maltysen você perdeu uma oportunidade de ouro para dizer "ty"
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

Exemplo de uso: 2013 # 2014-> True.

pfaz uma lista de todos os fatores principais de seu argumento, remove duplicatas, faz uma lista de todas as subsequências, descarta a primeira (que é sempre a lista vazia) e finalmente soma as subsequências. #verifica se p anão é igual à diferença p a \\ p b. Se não forem iguais, eles têm pelo menos um elemento comum.

nimi
fonte
3

Japt, 25 bytes

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

Saídas trueou false. Experimente online!

Ungolfed e explicação

[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 um byte extra, é possível dividir o código fatorize-unique-combine-sum entre as duas entradas, com a vantagem adicional de ter uma complexidade de tempo de O(O(25-byte version)^2):

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

CJam, 23 bytes

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

Teste aqui.

O valor verdadeiro será todas as somas comuns concatenadas, o valor falso é a sequência vazia.

Explicação

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

Braquilog , 10 9 bytes

{ḋd⊇+ℕ₁}ᵛ

Experimente online!

O predicado consegue retornar, [the sum, the sum]se existir, e falha se a soma não existir.

{            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 graças a Fatalize (o criador do Brachylog), lembrando-me que o meta-predicado de verificação existe.

String não relacionada
fonte
1
Você pode usar em ᵛ - verifyvez de ˢ=salvar um byte.
Fatalize
2

MATL , 23 bytes

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

Usa a versão atual, 2.0.2 , anterior a esse desafio.

Os números são fornecidos como duas entradas separadas. A saída é 0ou 1.

Exemplo

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

Explicação

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

Mathematica, 58 bytes

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

Explicação:

Esta é uma função anônima.

Primeiro, IntersectingQverifica se duas listas estão se cruzando. Mas as entradas são números em vez de listas, portanto, não são avaliadas. Por exemplo, se as entradas forem 2013e 2014, então IntersectingQ@##&retornará IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&é outra função anônima que pega um número inteiro, obtém uma lista de seus fatores primos sem repetições, pega o conjunto de potência, remove o conjunto vazio e, em seguida, pega a soma de cada conjunto. Então Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]retorna {3, 11, 61, 14, 64, 72, 75}.

Em seguida, mapeie Tr/@Rest@Subsets[#&@@@FactorInteger@#]&a expressão IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]e Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]são listas, para que possamos obter o resultado da coleta neste momento.

alefalpha
fonte
Ligar IntersectingQprimeiro é incrível! :)
Martin Ender
Você poderia adicionar uma explicação?
Lynn
2

PARI / GP , 98 bytes

Fatore, pegue primes ( [,1]), faça um loop sobre subconjuntos não vazios, soma e uniq e, em seguida, intercepte o resultado disso para os dois números. O valor retornado é o número de interseções, que é verdade, a menos que sejam 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
fonte
2

APL (Dyalog Extended) , 23 17 bytes SBCS

-5 graças a ngn

Função de infixo tácito anônimo.

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

Experimente online!

⍥{} Aplique a seguinte função anônima aos dois argumentos:

 fatores principais

 então

 os únicos daqueles

0+⍀., redução da tabela de adição de zero concatenada para cada fator

ε nlist (achatar)

 o cruzamento

 então

 a contagem daqueles

1< Existe mais de um? (um porque a soma de nenhum fator)

Adão
fonte
usando apenas recursos do dyalog apropriado: p+.×⊤1↓⍳2*≢p←->1↓∊(⊢,+)/0,⍨
ngn 28/02
ainda mais curto:1↓∊∘.+/0,¨
ngn 28/02
que é 1↓∊0∘.+.,um produto inouter - com que frequência você vê isso :)
ngn 28/02
se eu entendi corretamente, isso deve funcionar também:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
ngn 28/02
@ngn Obrigado. Feito.
Adám 02/03
2

05AB1E , 10 8 bytes

f€æO`å¦à

-2 bytes graças a @Emigna .

Experimente online ou verifique todos os casos de teste .

Explicação:

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
fonte
1
f€æO`å¦àdeve funcionar para 8.
Emigna
1

Python 3 , 206 bytes

Essa é uma função lambda (m), que recebe 2 números e retorna um conjunto que contém somas de fatores primos que eles têm em comum. Em Python, esse é um valor verdadeiro quando não vazio e um valor falsey quando vazio.

Edit: Acontece que minha resposta original não funcionou para entradas principais, como apontado por @JoKing. Isso foi corrigido (junto com alguns outros bugs) pelo custo 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))

Explicação rápida usando comentários:

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

Experimente online!

senox13
fonte
Isso não funciona para o primeiro caso de teste 5,6, pois não trata de entradas principais
Jo King
@JoKing Obrigado por capturar isso. A resposta foi atualizada.
senox13 28/02
1

APL (NARS), 50 caracteres, 100 bytes

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

aqui π encontraria a matriz de fatores em seu argumento;

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

seria a função que encontra todos os subconjuntos ... eu tenho que dizer que parece {operador itsArguments} ¨ (para cada esquerda) e ¨ (para cada direita) podem imitar um loop com número fixo de ciclos e ¨¨ está ok em ver subconjuntos de um conjunto ... dessa maneira, parece reduzir símbolos nos loops de descrição ...; teste

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

Uma pequena análise:

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

Japonês , 14 bytes

®k â ã mx
rf Ê

Guardado 3 bytes graças a @Shaggy

Tente

Modalidade de ignorância
fonte
A segunda linha pode ser ÎfUÌ lou, mais curta ainda rf l,. seria a maneira mais curta de fazer isso, mas Oliver venceu você.
Shaggy
1

Geléia , 18 9 bytes

ÆfŒPḊ§)f/

Experimente online!

Obrigado a Jonathan Allan por -9 e pela incrível ajuda :).

Recebe entrada como uma matriz de dois elementos. Explicação do 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
fonte
Tome entrada como uma lista de dois valores e evite o ,. O ẒƇé redundante, não há fatores primos não primos. Então ÆFḢ€ é justo Æf, exceto que o último nos dá as repetições que realmente precisamos, por exemplo 26=2*13e por 125=5*5*5enquanto 2+13=5+5+5. Mesmo com isso, porém, não é bom o suficiente, por exemplo, em vez de 26usar, o 182=2*7*13que também deve achar isso, 2+13=5+5+5mas não o faz - em vez disso, queremos o power-set ( ŒP) sem o elemento inicial, vazio, (podemos usar ). S€aqui pode ser substituído por §. - Você provavelmente pode salvar bytes com $e Ɗ-.
Jonathan Allan
Não há necessidade das rápidas que eu mencionei no final, podemos usar )e com minhas correções para fazê-lo funcionar corretamente (mais substituindo œ&por f) o código é de 9 bytes: ÆfŒPḊ§)f/ try-it
Jonathan Allan
Atualizado com uma explicação. Mais uma vez obrigado :)!
Ven
1
Eu atualizei sua explicação um pouco.
Jonathan Allan
0

Gaia , 16 11 bytes

ḍzΣ¦
↑@↑&ỵ!

Experimente online!

A função superior (primeira linha) calcula as somas do conjunto de potências de fatores primos e a segunda função descobre se algum dos elementos da interseção é diferente de zero.

Giuseppe
fonte