Generate a sequence of \$n\$ consecutive composite numbers

Question

Definitions

The common methods to generate consecutive composites are

$$\overbrace{(n+1)! + 2, \ (n+1)! + 3, \ \ldots, \ (n+1)! + (n+1)}^{\text{n composites}}$$

$$\overbrace{n!+2,n!+3,...,n!+n}^{\text{n-1 composites}}$$

$$\overbrace{n\#+2,n\#+3,…n\#+n}^{\text{n-1 composites (Primorials)}}$$

---

A less common method involves the Chinese Remainder Theorem (CRT).

For example, define a list of \$n\$ pairwise coprimes \$p_1, p_2, \ldots, p_n\$.

A set of integers can also be called coprime if its elements share no common positive factor except 1. A stronger condition on a set of integers is pairwise coprime, which means that \$a\$ and \$b\$ are coprime for every pair \$(a, b)\$ of different integers in the set. The set \$\{2, 3, 4\}\$ is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.

Create a set of \$n\$ congruences

\begin{align*} x + 1 &\equiv 0 \pmod{p_1} \\ x + 2 &\equiv 0 \pmod{p_2} \\ &\vdots \\ x + n &\equiv 0 \pmod{p_n} \end{align*}

By CRT, there exists a unique solution \$x\$ which satisfies this sequence of \$n\$ consecutive composite numbers:

$$x + 1, x + 2, \ldots, x + n$$

A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself.

---

Challenge

Given pairwise coprime inputs, find the smallest range of consecutive composite numbers.

Input

A list of \$n\$ pairwise coprimes.

Output

A sequence of \$n\$ consecutive composite numbers.

Test Cases

These cases were derived from this test.

n	pairwise coprimes	consecutive composites
2	2, 3	8,9
3	7, 11, 23	1792, 1793, 1794
4	2, 3, 5, 7	158, 159, 160, 161
5	3, 7, 10, 13, 23	47928, 47929, 47930, 47931, 47932

Added a JavaScript (V8) tool to validate if the input numbers are pairwise coprime.

Answer 1

Jelly, 11 bytes

V+€J%ÞfÞẒƇḢ

A monadic Link that accepts a list of pairwise coprime integers and yields a run of the same number of consecutive composites.

Try it online!

How?

Uses the Chinese Remainder theorem in the most naive way possible, systematic search.

V+€J%ÞfÞẒƇḢ - Link: Coprimes
V           - Digit-smash {Coprimes}
              (e.g. [2, 11, 17] -> 21117 -- N.B. V >= Product+Max so is sufficient*)
   J        - 1-indexed indices {Coprimes} -> [1..n=length(Coprimes)]
  €         - for each {v in [1..2P]}:
 +          -   {v} add {[1..n]} (vectorises)
     Þ      - sort by:
    %       -   modulo {Coprimes} (vectorises)
       Þ    - sort by:
      f     -   keep those which are in:
         Ƈ  -     {Comprimes} for which:
        Ẓ   -       is prime?
         Ḣ - head

---

* Thanks to Leo for this proof that the digit concatenation performed by V is guaranteed to be greater than or equal to the product plus the maximum that we may need to search through:

The concatenation \$a|b\$ of two positive numbers \$a\$ and \$b\$ is equal to \$a\times c + b\$, where \$c\$ is the first power of \$10\$ larger than \$b\$ (i.e. \$c = 10^{\lfloor 1 + \log_{10}{b} \rfloor}\$).

Since \$c \ge b + 1\$ we get \$a|b \ge a \times (b + 1) + b = a \times b + a + b\$.

As such the concatenation of two numbers is always at least as large as their product plus their sum. This then extends to more terms as each of the operations, concatenation and taking a product, may be applied in succession.

Answer 2

Wolfram Language (Mathematica), 67 bytes

((r=Range@Tr[1^#])+ChineseRemainder[-r,#,If[Or@@PrimeQ@#,Tr@#,1]])&

Try it online!

Answer 3

05AB1E, 18 15 bytes

ā∞sδ+ʒp≠P}.ΔIÖP

Try it online or verify all test cases.

Explanation:

ā               # Push a list in the range [1, (implicit) input-length]
 ∞              # Push an infinite positive list: [1,2,3,...]
  s             # Swap so the [1,length] list is at the top again
   δ            # Pop both lists, and apply double-vectorized:
    +           #  Add the values together
     ʒp≠P}      # Filter, and remove all overlapping lists that contain primes
          .Δ    # Then find the first list that's truthy for:
            IÖ  #  Check for each value whether its divisible by the input-value at the
                #  same position
              P #  Check whether this is truthy for all of them
                # (after which the found result is output implicitly)

Answer 4

Retina, 63 bytes

.+
*_,$:&*
/\b((_+)_+),\1*\2\b|,(?!(__+)\3+\b)/+%`$
_
L$`,
$.%'

Try it online! Takes input on separate lines but link is to test suite that converts from and to comma separated for convenience. Explanation: Brute force, so last test case was omitted for speed.

.+
*_,$:&*

Convert each input to unary and append its index.

/\b((_+)_+),\1*\2\b|,(?!(__+)\3+\b)/+`

While there is a non-composite output or an output that isn't divisible by an input, ...

%`$
_

... increment all of the outputs.

L$`,
$.%'

Delete the inputs and convert the outputs to unary.

Answer 5

C (gcc), 563 461 bytes

-102 bytes, thanks to @ceilingcat

The GNU Multiple Precision Arithmetic Library. GMP

#import<gmp.h>
i;f(a,b)int a[];{mpz_t c[b],d[i=b],e,f,g,h,j,k;mpz_inits(e,f,g,h,j,k,0);for(mpz_set_ui(f,1);i--;mpz_mul(f,f,c[i]))mpz_inits(c[i],d[i],0),mpz_set_ui(c[i],a[i]),mpz_set_si(d[i],~i);for(;++i<b;mpz_add(e,e,g))mpz_divexact(j,f,c[i]),mpz_invert(k,j,c[i]),mpz_mul(g,d[i],k),mpz_mul(g,g,j);for(mpz_mod(e,e,f);i--;)mpz_probab_prime_p(c[i],15)?mpz_add_ui(g,e,i+1),i=!mpz_cmp(g,c[i])?mpz_add(e,e,f),0:i:0;for(;b/i;gmp_printf("%Zd ",h))mpz_add_ui(h,e,-i--);}

Try it online!