27
\$\begingroup\$

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.

\$\endgroup\$
5
  • 6
    \$\begingroup\$ I like challenges like this, but for golfing languages, it will be a chain of built-ins: factor, uniquify, subsets, sums, overlap. \$\endgroup\$
    – xnor
    Dec 18, 2015 at 22:20
  • \$\begingroup\$ Can we take input as a two-item array? \$\endgroup\$ Dec 19, 2015 at 0:13
  • \$\begingroup\$ @ETHproductions By default, yes. \$\endgroup\$
    – lirtosiast
    Dec 19, 2015 at 0:32
  • \$\begingroup\$ What about 14 (2*7) and 21 (3*7), is that true, as they share the factor 7 ? \$\endgroup\$ Dec 19, 2015 at 11:07
  • \$\begingroup\$ @SimonForsbergMcFeely Yes \$\endgroup\$
    – Arcturus
    Dec 19, 2015 at 16:23

17 Answers 17

10
\$\begingroup\$

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

\$\endgroup\$
3
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Alex A.
    Dec 18, 2015 at 22:56
  • \$\begingroup\$ I think map(p->map is shorter than (m=map)(p->m. \$\endgroup\$
    – alephalpha
    Dec 22, 2015 at 5:21
  • \$\begingroup\$ @DarthAlephalpha Good call, thanks. \$\endgroup\$
    – Alex A.
    Dec 22, 2015 at 5:25
7
\$\begingroup\$

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.
              
              
              
              
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is now identical to the other Pyth answer, with the exception of one moved letter ;) \$\endgroup\$ Dec 19, 2015 at 1:28
  • \$\begingroup\$ @ETHproductions I answered before Maltysen fixed theirs; so I'll keep it. \$\endgroup\$
    – lirtosiast
    Dec 19, 2015 at 1:57
7
\$\begingroup\$

Pyth - 17 12 11 bytes

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

@FmsMty{PdQ

Test Suite.

\$\endgroup\$
3
  • \$\begingroup\$ I think using ty works and saves a bye? \$\endgroup\$ Dec 19, 2015 at 0:18
  • \$\begingroup\$ @FryAmTheEggman thanks! \$\endgroup\$
    – Maltysen
    Dec 19, 2015 at 0:27
  • 17
    \$\begingroup\$ @Maltysen you missed a golden opportunity to say "ty" \$\endgroup\$ Dec 19, 2015 at 4:27
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 10 9 bytes

{ḋd⊇+ℕ₁}ᵛ

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
    +ℕ₁      has a sum greater than 0 which is output.
       }ᵛ    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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can use ᵛ - verify instead of ˢ= to save one byte. \$\endgroup\$
    – Fatalize
    Feb 27, 2019 at 7:38
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Calling IntersectingQ first is amazing! :) \$\endgroup\$ Dec 19, 2015 at 15:16
  • \$\begingroup\$ Could you add an explanation? \$\endgroup\$
    – Lynn
    Dec 21, 2015 at 3:19
2
\$\begingroup\$

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))
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Extended), 23 17 bytesSBCS

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

\$\endgroup\$
5
  • \$\begingroup\$ using only features from dyalog proper: p+.×⊤1↓⍳2*≢p← -> 1↓∊(⊢,+)/0,⍨ \$\endgroup\$
    – ngn
    Feb 28, 2019 at 16:39
  • \$\begingroup\$ even shorter: 1↓∊∘.+/0,¨ \$\endgroup\$
    – ngn
    Feb 28, 2019 at 16:48
  • \$\begingroup\$ which is 1↓∊0∘.+., an inouter product - how often do you see that :) \$\endgroup\$
    – ngn
    Feb 28, 2019 at 16:57
  • \$\begingroup\$ if i understand correctly, this should work too: 1<∘≢∩⍥{∊0∘.+.,∪⍭⍵} \$\endgroup\$
    – ngn
    Feb 28, 2019 at 17:31
  • \$\begingroup\$ @ngn Thanks. Done. \$\endgroup\$
    – Adám
    Mar 2, 2019 at 20:34
2
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ f€æO`å¦à should work for 8. \$\endgroup\$
    – Emigna
    Mar 5, 2019 at 10:13
1
\$\begingroup\$

Japt, 12 bytes

®k â à mx
rø

Run it online

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ This doesn't work for the first test case 5,6, since it doesn't handle prime inputs \$\endgroup\$
    – Jo King
    Feb 28, 2019 at 0:04
  • \$\begingroup\$ @JoKing Thanks for catching that. Answer has been updated. \$\endgroup\$
    – senox13
    Feb 28, 2019 at 17:05
1
\$\begingroup\$

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)
\$\endgroup\$
1
+300
\$\begingroup\$

Japt , 14 bytes

®k â ã mx
rf Ê

Saved 3 bytes thanks to @Shaggy

Try it

\$\endgroup\$
1
  • \$\begingroup\$ The second line can be ÎfUÌ l or, shorter still, rf l. would be the shortest way of doing that, but Oliver beat you to it. \$\endgroup\$
    – Shaggy
    Apr 3, 2019 at 8:16
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.