10
\$\begingroup\$

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]
\$\endgroup\$
3
  • \$\begingroup\$ Brownie points for beating my 10 byte, brute force Jelly answer \$\endgroup\$ Dec 19, 2021 at 18:32
  • \$\begingroup\$ Can we output multiple sets of primes, or just one? \$\endgroup\$
    – emanresu A
    Dec 19, 2021 at 19:22
  • 1
    \$\begingroup\$ @emanresuA You may output any number of sets of primes that satisfy the requirements \$\endgroup\$ Dec 19, 2021 at 19:25

10 Answers 10

11
\$\begingroup\$

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

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

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

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

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.

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

Charcoal, 54 bytes

⊞υ⟦⟧FEAΦι∧›λ¹¬﹪ιλ«≔υη≔⟦⟧υFΦι⬤ι∨⁼κμ﹪κμFη¿¬№λκ⊞υ⁺λ⟦κ⟧»Iυ

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

⊞υ⟦⟧

Start with the empty set for k=0.

FEAΦι∧›λ¹¬﹪ιλ«

For each input composite number, get its factors.

≔υη≔⟦⟧υ

Make a backup of the sets found so far.

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

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

Fη

... and for each set, ...

¿¬№λκ

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

⊞υ⁺λ⟦κ⟧

... record a new set that does.

»Iυ

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

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

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!

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

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!

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

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

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 }
\$\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.