# Primes dividing consecutive composites

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 , 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]

• Brownie points for beating my 10 byte, brute force Jelly answer Dec 19, 2021 at 18:32
• Can we output multiple sets of primes, or just one? Dec 19, 2021 at 19:22
• @emanresuA You may output any number of sets of primes that satisfy the requirements Dec 19, 2021 at 19:25

# 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


# Vyxal, 8 bytes

ǏƒẊvf'Þu


Try it Online!

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

Ǐ        # Prime factors (vectorised)
ƒẊ      # Reduce by cartesian product
vf    # Flatten each
'   # Filter by
Þu # All unique


# 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


# 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


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

• TIO has dfns/pco: razetime.github.io/APLgolf/?h=Uy9Izld/…
– ovs
Mar 21 at 14:32
• Extended, 17 bytes: ∪¨⍛∩⍨∘,∘↑3∘.,/⍤⍭⊢
Mar 21 at 14:44
• Full program, 18 bytes: (⊢∩∪¨),↑∘.,/3pco¨⎕
Mar 21 at 14:47

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

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

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

# 05AB1E, 11 bytes

f˜Igã.ΔÙÖ*Q


Outputs one result.

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.

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)


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