Sums of prime factors

Question

2013 has the prime factorization 3*11*61. 2014 has the prime factorization 2*19*53. An interesting property regarding these factorizations is that there exist distinct primes in the factorizations of 2013 and 2014 that sum to the same number: 11+61=19+53=72.

Write a program or function that takes as its input two positive integers greater than 1 and returns a truthy value if there exist a sum of selected prime factors of one number that is equal to a sum of selected prime factors in the second number, and a falsey value otherwise.

---

Clarifications

• More than two prime factors can be used. Not all of the prime factors of the number need to be used in the sum. It is not necessary for the number of primes used from the two numbers to be equal.
• Even if a prime is raised to some power greater than 1 in the factorization of a number, it can only be used once in the sum of primes for the number.
• 1 is not prime.
• Both input numbers will be less than 2^32-1.

---

Test cases

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

---

This is code golf. Standard rules apply. Shortest code in bytes wins.

• xnor: I like challenges like this, but for golfing languages, it will be a chain of built-ins: factor, uniquify, subsets, sums, overlap.
• ETHproductions: Can we take input as a two-item array?
• lirtosiast: @ETHproductions By default, yes.
• Simon Forsberg: What about 14 (2*7) and 21 (3*7), is that true, as they share the factor 7 ?
• Arcturus: @SimonForsbergMcFeely Yes

Answer 1

Julia, (削除) 95 (削除ここまで) 93 bytes

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

The primary function is f and it calls a helper function 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

Saved 2 bytes thanks to Darth Alephalpha

• Alex A.: I noticed this was downvoted. Is there anything I've overlooked? If it's wrong I'd be happy to fix it, but as it stands it works fine for me and passes all test cases.
• alephalpha: I think map(p->map is shorter than (m=map)(p->m.

Answer 2

Pyth, 11 bytes

t@FmsMy{PdQ

Input in the form 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.
 
 
 
 

• ETHproductions: This is now identical to the other Pyth answer, with the exception of one moved letter ;)
• lirtosiast: @ETHproductions I answered before Maltysen fixed theirs; so I'll keep it.

Answer 3

Pyth - (削除) 17 (削除ここまで) (削除) 12 (削除ここまで) 11 bytes

Thanks to @FryAmTheEggman for fixing my answer and saving a byte.

@FmsMty{PdQ

Test Suite.

• FryAmTheEggman: I think using ty works and saves a bye?
• Maltysen: @FryAmTheEggman thanks!
• undergroundmonorail: @Maltysen you missed a golden opportunity to say "ty"

Answer 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

Usage example: 2013 # 2014 -> True.

p makes a list of all prime factors of it's argument, removes duplicates, makes a list of all subsequences, drops the first one (which is always the empty list) and finally sums the subsequences. # checks whether p a is not equal to the difference p a \\ p b. If not equal, they have at least one common element.

Answer 5

Japt, 25 bytes

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

Outputs true or false. Try it online!

Ungolfed and explanation

[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

For an extra byte, you can split up the factorize-unique-combine-sum code between both inputs, with the added advantage of having a time complexity of O(O(25-byte version)^2):

Uk â à mx d@J<Vk â à mx bX

Answer 6

CJam, 23 bytes

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

Test it here.

The truthy value will be all common sums concatenated, the falsy value is the empty string.

Explanation

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.

Answer 7

Brachylog, (削除) 10 (削除ここまで) 9 bytes

{ḋd⊇+N1}v

Try it online!

The predicate succeeds returning [the sum, the sum] if it exists, and fails if the sum does not exist.

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

-1 byte thanks to Fatalize (the creator of Brachylog) reminding me that the verify meta-predicate exists.

• Fatalize: You can use v - verify instead of s= to save one byte.

Answer 8

MATL, 23 bytes

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

Uses current release, 2.0.2, which is earlier than this challenge.

The numbers are provided as two separate inputs. Output is 0 or 1.

Example

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

Explanation

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

Answer 9

Mathematica, 58 bytes

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

Explanation:

This is an anonymous function.

First, IntersectingQ checks if two lists are intersecting. But the inputs are numbers instead of lists, so it remains unevaluated. For example, if the inputs are 2013 and 2014, then IntersectingQ@##& returns IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]& is another anonymous function that takes an integer, gets a list of its prime factors without repetitions, takes the power set, removes the empty set, and then takes the sum of each set. So Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013] returns {3, 11, 61, 14, 64, 72, 75}.

Then map Tr/@Rest@Subsets[#&@@@FactorInteger@#]& over the expression IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013] and Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]] are lists, so we can get the collect result this time.

• Martin Ender: Calling IntersectingQ first is amazing! :)
• lynn: Could you add an explanation?

Answer 10

PARI/GP, 98 bytes

Factor, grab primes ([,1]), loop over nonempty subsets, sum, and uniq, then intersect the result of this for the two numbers. The returned value is the number of intersections, which is truthy unless they are 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))

Answer 11

APL (Dyalog Extended), (削除) 23 (削除ここまで) 17 bytes ^SBCS

-5 thanks to ngn

Anonymous tacit infix function.

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

Try it online!

⍥{...} apply the following anonymous function to both arguments:

⍭ prime factors

⍤ then

∪ the unique ones of those

0+⍀., addition table reduction of zero concatenated to each factor

∊ εnlist (flatten)

∩ the intersection

⍤ then

≢ the tally of those

1< is there more than one? (one because the sums of no factors)

• ngn: using only features from dyalog proper: p+.×⊤1↓⍳2*≢p← -> 1↓∊(⊢,+)/0,⍨
• ngn: even shorter: 1↓∊∘.+/0,¨
• ngn: which is 1↓∊0∘.+., an inouter product - how often do you see that :)
• ngn: if i understand ⍥ correctly, this should work too: 1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
• Adám: @ngn Thanks. Done.

Answer 12

05AB1E, (削除) 10 (削除ここまで) 8 bytes

f€æO`å¦à

-2 bytes thanks to @Emigna.

Try it online or verify all test cases.

Explanation:

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

• Emigna: f€æO`å¦à should work for 8.

Answer 13

Japt, 12 bytes

®k â à mx
rø

Run it online

Answer 14

Python 3, 206 bytes

This is a lambda function (m), which takes in 2 numbers and returns a set containing any sums of prime factors that they have in common. In Python this is a truthy value when non-empty, and a falsey value when empty.

Edit: Turns out my original answer didn't work for prime inputs, as pointed out by @JoKing. This has been fixed (along with some other bugs) at the tragic cost of 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))

Quick explanation using comments:

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

Try it online!

• Jo King: This doesn't work for the first test case 5,6, since it doesn't handle prime inputs
• senox13: @JoKing Thanks for catching that. Answer has been updated.

Answer 15

APL(NARS), 50 char, 100 bytes

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

here π would find the array of factors on its argument;

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

would be the function that find all subsets... i have to say that it seems {⍵operator itsArguments} ̈ (for each left) and ̈ (for each right) can imitate loop with fixed number of cycles and ̈ ̈ is ok in to see subsets of one set... this way of see it seems reduce symbols in describe loops...; test

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

One little analysis:

π ̈⍵ 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)

Answer 16

Japt -¡, 14 bytes

®k â ã mx
rf Ê

Saved 3 bytes thanks to @Shaggy

Try it

• Shaggy: The second line can be ÎfUÌ l or, shorter still, rf l. rø would be the shortest way of doing that, but Oliver beat you to it.

Answer 17

Gaia, (削除) 16 (削除ここまで) 11 bytes

ḍzΣ¦
↑@↑&ỵ!

Try it online!

The top function (first line) calculates the sums of the powerset of prime factors, and the second function finds if any of the elements of the intersection are nonzero.