Primes dividing consecutive composites

Question

Grimm's conjecture states that, for any set of consecutive composite numbers \$n+1, n+2, ..., n+k\$, there exist \$k\$ distinct primes \$p_i\$, such that \$p_i\$ divides \$n+i\$ for each \$1 \le i \le k\$.

For example, take \$\{24, 25, 26, 27, 28\}\$. We can see that if we take the primes \$2, 5, 13, 3, 7\$, each composite number is divisible by at least one of the primes:

$$ 2 \mid 24 \quad 5 \mid 25 \quad 13 \mid 26 \\ 3 \mid 27 \quad 7 \mid 28 $$

Note that it doesn't matter that \$26\$ is also divisible by \$2\$, so long as, for each composite number, there is a corresponding prime that divides it. For the purposes of this challenge, we'll assume Grimm's conjecture is true.

Given a list of \$n\$ consecutive composite integers \$C\$, in any reasonable format, return a list of \$n\$ distinct prime numbers \$P\$ such that, for each \$c\$ in \$C\$, there is a corresponding \$p\$ in \$P\$ such that \$c\$ is divisible by \$p\$. You may return any such list in any order, and in any reasonable format.

This is code-golf, so the shortest code in bytes wins.

Test cases

[4] -> [2]
[6] -> [2]
[8, 9, 10] -> [2, 3, 5]
[12] -> [2]
[14, 15, 16] -> [7, 3, 2]
[18] -> [2]
[20, 21, 22] -> [2, 3, 11]
[24, 25, 26, 27, 28] -> [2, 5, 13, 3, 7]
[30] -> [2]
[32, 33, 34, 35, 36] -> [2, 11, 17, 5, 3]
[38, 39, 40] -> [2, 3, 5]
[42] -> [2]
[44, 45, 46] -> [2, 3, 23]
[48, 49, 50, 51, 52] -> [2, 7, 5, 3, 13]
[54, 55, 56, 57, 58] -> [2, 5, 7, 3, 29]
[60] -> [2]
[62, 63, 64, 65, 66] -> [31, 3, 2, 5, 11]
[68, 69, 70] -> [2, 3, 5]

Answer 1

Husk, 7 bytes

Try it online!

     mp  -- prime factors of each number
    Π    -- cartesian product of this list of lists
►        -- find the element that maximizes:
 oLu     --   (2 functions composed) the length of the unique values

Answer 2

Jelly, 7 bytes

ÆfŒpQƑƇ

Try it online!

Are brownie points redeemable for actual brownies? Similar to ovs' answer and my Vyxal answer.

Returns a bunch of duplicates because Jelly has no 'distinct prime factors' builtin.

Æf      Prime factors
  Œp    Cartesian product of all
      Ƈ Filter by
     Ƒ  Remains same under
    Q   Uniquify

Answer 3

Brachylog, 6 bytes

ḋᵐ∋ᵐ.d

Try it online!

?ḋᵐ∋ᵐ.d.     # implicit input and output
?ḋᵐ          # prime decompositions of each number in the input
   ∋ᵐ.       # for each prime decomposition one number is in the output
     .d.     # and: the output without duplicates is still the output

Answer 4

Vyxal, 6 bytes

vǏΠ'Þu

Try it Online!

Similar to ovs' answer. Outputs a list of lists of primes.

vǏ     # Prime factors of each
  Π    # Cartesian product
   '   # Filter by
    Þu # All unique

Answer 5

APL(Dyalog Unicode), 22 bytes ^SBCS

(⊢∩∪¨)∘,∘↑(∘.,/3∘pco¨)

Try it on APLgolf!

-7 thanks to people on APLFarm. Requires pco. There is no pco on TryAPL, so you need Dyalog APL installed locally. Outputs all possibilities.

Answer 6

Charcoal, 54 bytes

⊞υ⟦⟧ＦＥＡΦι∧›λ¹¬﹪ιλ«≔υη≔⟦⟧υＦΦι⬤ι∨⁼κμ﹪κμＦη¿¬№λκ⊞υ⁺λ⟦κ⟧»Ｉυ

Try it online! Link is to verbose version of code. Outputs all sets. Explanation:

⊞υ⟦⟧

Start with the empty set for k=0.

ＦＥＡΦι∧›λ¹¬﹪ιλ«

For each input composite number, get its factors.

≔υη≔⟦⟧υ

Make a backup of the sets found so far.

ＦΦι⬤ι∨⁼κμ﹪κμ

For each prime factor of the current composite number, ...

Ｆη

... and for each set, ...

¿¬№λκ

... if the set doesn't have that prime factor yet, then...

⊞υ⁺λ⟦κ⟧

... record a new set that does.

»Ｉυ

Output the sets that managed to acquire a prime factor for each input composite.

Answer 7

JavaScript (ES6), 98 bytes

f=(A,b=[],k=2,[n,...a]=A)=>n?k>n?0:n%k?f(A,b,k+1):!b.includes(k)&&f(a,[...b,k])||f([n/k,...a],b):b

Try it online!

Answer 8

Ruby, 105 bytes

->l,*r{(2..l[0]).map{|x|r.any?{|y|x%y<1}||r<<x};r.permutation(l.size).find{|c|c.zip(l).all?{|a,b|b%a<1}}}

Try it online!

Answer 9

05AB1E, 11 bytes

f˜Igã.ΔÙÖ*Q

Outputs one result.

Try it online or verify all test cases.

Could output all results for the same byte-count by replacing .Δ with Ùʒ, but it's much slower and times out for the larger test cases: try it online or don't verify all test cases.

A port of @ovs' Husk and Brachylog answers, as well as @emanresuA's Vyxal and Jelly answers, would be 13 bytes in 05AB1E... :/ Looks like 05AB1E draws the short straw (or I should say longest..) by far with this approach, primarily because there isn't a clean way to reduce-by-cartesian-product (which is ¯¸š.»â€˜, 8 out of 13 bytes).

f¯¸š.»â€˜ʒDÙQ

Outputs all possible outputs.

Try it online or verify all test cases.

Explanation:

f             # Map each integer in the (implicit) input-list to an inner list of
              # its unique prime factors
 ˜            # Flatten this list of lists
  Ig          # Push the input-length
    ã         # Take the cartesian product
     .Δ       # Find the first result which is truthy for:
       Ù      #  Uniquify the list
        Ö     #  Check for each prime if it evenly divides the (implicit) inputs
              #  at the same positions (1 if truthy; 0 if falsey)
         *    #  Multiply each by the (implicit) inputs at the same positions
          Q   #  And check if it's equal to the (implicit) input-list
              # (after which the found list is output implicitly)

If the inner list we're filtering on becomes smaller in length than the input-list after the Ù, it'll stay that same smaller size at the Ö and *. At the Q after that however, this smaller list can never be equal to the input-list.

f             # Map each integer in the (implicit) input-list to an inner list of
              # its unique prime factors
 ¯¸š          # Prepend [[]] at the front of this list
    .»        # Left-reduce it by:
      â       #  Cartesian product of two lists
       €˜     # After the reduce, flatten each inner list
         ʒ    # Filter it by:
          D   #  Duplicate the list
           Ù  #  Uniquify this copy
            Q #  And check if the lists are still the same
              # (after which the list of lists is output implicitly)

Answer 10

Factor + math.primes.factors, 51 bytes

[ [ factors ] map [ members ] product-map longest ]

Try it online!

Explanation

• [ factors ] map Get the prime factors of each number in the input list.
• [ members ] product-map Get every combination of picking one thing from each list. But remove duplicates.
• longest Get the longest one.

                        ! { 14 15 16 }
[ factors ] map         ! { { 2 7 } { 3 5 } { 2 2 2 2 } }
[ members ] product-map ! {
                            { 2 3 }
                            { 7 3 2 }
                            { 2 5 }
                            { 7 5 2 }
                            { 2 3 }
                            { 7 3 2 }
                            { 2 5 }
                            { 7 5 2 }
                            { 2 3 }
                            { 7 3 2 }
                            { 2 5 }
                            { 7 5 2 }
                            { 2 3 }
                            { 7 3 2 }
                            { 2 5 }
                            { 7 5 2 }
                        }
longest               ! { 7 3 2 }