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.

• xnor: Does our output need to be the smallest valid one?
• lynn: Maybe this is nitpicky, but "using the Chinese Remainder Theorem" is a non-observable requirement, and a theorem is not an algorithm, so I don't think you can judge whether an answer "uses" the CRT. I think you are better off posing the question as "given pairwise coprime inputs, find the smallest range of consecutive numbers satisfying these conditions", and mentioning only as a footnote that the CRT guarantees the existence of a solution.
• Leo: What should be the output for 8,9? According to the definition in the challenge I believe it should be 8,9 again, but your code and some of the answers are returning 80,81 instead
• vengy: @Leo. All code and answers have been corrected to return 8,9. Thanks for catching that edge case.

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.

• Leo: The concatenation ab of two numbers a and b is equal to a*c+b, where c is the first power of 10 larger than b. Since c>=b+1 we get ab>=a*(b+1)+b=a*b+a+b, so the concatenation of two numbers is always at least as large as their product plus their sum (I think the equality happens when both a and b are 1 less than a power of 10). Your V trick should work fine.
• Jonathan Allan: ...and that then extends to more numbers in the product/concatenation. Thanks, @Leo - I really couldn't think it through so late in the day!
• Jonathan Allan: @vengy Ah, I didn't spot that edge case, I've updated the code to handle it.

Answer 2

Wolfram Language (Mathematica), 67 bytes

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

Try it online!

• ZaMoC: @vengy ok, fixed.

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!

• ceilingcat: 446 bytes