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\$
  • 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 '15 at 22:20
  • \$\begingroup\$ Can we take input as a two-item array? \$\endgroup\$ – ETHproductions Dec 19 '15 at 0:13
  • \$\begingroup\$ @ETHproductions By default, yes. \$\endgroup\$ – lirtosiast Dec 19 '15 at 0:32
  • \$\begingroup\$ What about 14 (2*7) and 21 (3*7), is that true, as they share the factor 7 ? \$\endgroup\$ – Simon Forsberg Dec 19 '15 at 11:07
  • \$\begingroup\$ @SimonForsbergMcFeely Yes \$\endgroup\$ – Arcturus Dec 19 '15 at 16:23

18 Answers 18

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
    \$\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 '15 at 22:56
  • \$\begingroup\$ I think map(p->map is shorter than (m=map)(p->m. \$\endgroup\$ – alephalpha Dec 22 '15 at 5:21
  • \$\begingroup\$ @DarthAlephalpha Good call, thanks. \$\endgroup\$ – Alex A. Dec 22 '15 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\$
  • 1
    \$\begingroup\$ This is now identical to the other Pyth answer, with the exception of one moved letter ;) \$\endgroup\$ – ETHproductions Dec 19 '15 at 1:28
  • \$\begingroup\$ @ETHproductions I answered before Maltysen fixed theirs; so I'll keep it. \$\endgroup\$ – lirtosiast Dec 19 '15 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\$
  • \$\begingroup\$ I think using ty works and saves a bye? \$\endgroup\$ – FryAmTheEggman Dec 19 '15 at 0:18
  • \$\begingroup\$ @FryAmTheEggman thanks! \$\endgroup\$ – Maltysen Dec 19 '15 at 0:27
  • 17
    \$\begingroup\$ @Maltysen you missed a golden opportunity to say "ty" \$\endgroup\$ – undergroundmonorail Dec 19 '15 at 4:27
4
\$\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
    \$\begingroup\$ You can use ᵛ - verify instead of ˢ= to save one byte. \$\endgroup\$ – Fatalize Feb 27 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\$
  • \$\begingroup\$ Calling IntersectingQ first is amazing! :) \$\endgroup\$ – Martin Ender Dec 19 '15 at 15:16
  • \$\begingroup\$ Could you add an explanation? \$\endgroup\$ – Lynn Dec 21 '15 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\$
  • \$\begingroup\$ using only features from dyalog proper: p+.×⊤1↓⍳2*≢p← -> 1↓∊(⊢,+)/0,⍨ \$\endgroup\$ – ngn Feb 28 at 16:39
  • \$\begingroup\$ even shorter: 1↓∊∘.+/0,¨ \$\endgroup\$ – ngn Feb 28 at 16:48
  • \$\begingroup\$ which is 1↓∊0∘.+., an inouter product - how often do you see that :) \$\endgroup\$ – ngn Feb 28 at 16:57
  • \$\begingroup\$ if i understand correctly, this should work too: 1<∘≢∩⍥{∊0∘.+.,∪⍭⍵} \$\endgroup\$ – ngn Feb 28 at 17:31
  • \$\begingroup\$ @ngn Thanks. Done. \$\endgroup\$ – Adám Mar 2 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
    \$\begingroup\$ f€æO`å¦à should work for 8. \$\endgroup\$ – Emigna Mar 5 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\$
  • \$\begingroup\$ This doesn't work for the first test case 5,6, since it doesn't handle prime inputs \$\endgroup\$ – Jo King Feb 28 at 0:04
  • \$\begingroup\$ @JoKing Thanks for catching that. Answer has been updated. \$\endgroup\$ – senox13 Feb 28 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\$
  • \$\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 at 8:16
1
\$\begingroup\$

Jelly, 18 9 bytes

ÆfŒPḊ§)f/

Try it online!

Thanks to @Jonathan Allan for -9 and the amazing help :).

Takes input as an array of two elements. Code explanation:

      )    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

¹

\$\endgroup\$
  • \$\begingroup\$ Take input as a list of two values and avoid the ,. The ẒƇ is redundant, there are no non-prime prime-factors. Then ÆFḢ€ is just Æf, except that the latter gives us the repetitions we might actually need, for example 26=2*13 and 125=5*5*5 while 2+13=5+5+5. Even with that however, is not good enough, for example instead of 26 use 182=2*7*13 which should also find that 2+13=5+5+5 but does not - instead we want the power-set (ŒP) without the leading, empty, element (we can use ). S€ here may be replaced with §. -- You can probably save bytes with $ and Ɗ --. \$\endgroup\$ – Jonathan Allan Apr 1 at 12:19
  • \$\begingroup\$ No need for those quicks I mentioned at the end we can use ) and with my fixes to make it work correctly (plus replacing œ& with f) the code is 9 bytes: ÆfŒPḊ§)f/ try-it \$\endgroup\$ – Jonathan Allan Apr 1 at 12:24
  • \$\begingroup\$ Updated with an explanation. Thank you again :)! \$\endgroup\$ – Ven Apr 1 at 14:25
  • 1
    \$\begingroup\$ I updated your explanation a little. \$\endgroup\$ – Jonathan Allan Apr 1 at 17:14
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, privacy policy and cookie policy

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