My Explanation for k=20
Ai and Bi are two numbers. These two numbers must have gcd == 1.
1st we assume that Ai and Bi have gcd != 1. That means Ai and Bi have something in common. if we add 1 to Bi and if still Ai and Bi have gcd!=1.
Similarly,
Ai and Bi → gcd!=1
Ai and Bi +1-> gcd!=1
…
Ai and Bi+20 → gcd!=1
Maximum Output from this observation is that
Ai can be max = (Bi) * (Bi+1) * (Bi*2) * … * (Bi+20);
minimum Ai can be if we take Bi=0;
then ignore the values that are not prime that are Bi+4 (that will be 4 not prime)
So Ai can be minimum = 1 * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9,699,690
when Bi is 0
So Ai goes above the given limit that is 1,000,000
So between 20 numbers Bi to Bi+20 there will at least be 1 number whose gcd with Ai will be 1.