Yet Another Problem About Sequences | Yet Another Unofficial Editorial

eartseq
editorial
eratosthenes
gcd
jan19
long-challenge
prime

#1

Problem Link

Practice

Contest Div. 1

Contest Div. 2

Author: Evgeniy Artemov

Editorialist: Rishabh Dhiman

Problem

Find an integer sequnce A of length n such that

  • \gcd(A_i, A_{i + 1 \mod n}) > 1
  • \gcd(A_i, A_{i + 1 \mod n}, A_{i + 2 \mod n}) = 1

for all 0 \le i \le n - 1.

Constraints:

A_i < 10^9

1 \le \text{test cases} \le 10^3

Subtask 1: 1 \le N \le 3,333

Subtask 2: 1 \le N \le 50,000

Prerequisites

Sieve of Eratosthenes, previous experience with \gcd

Super Quick Solution

\gcd and construction problem, so work with primes, if p_n is the n-th prime, this simple sequence would work, \{p_1p_n, p_1p_2, p_2p_3, \dots, p_{n - 1}p_n\}, this would work for subtask 1 but p_{n - 1}p_n > 10^9 for n = 50,000.

Playing around a bit you get the following sequence that works,

  • A_0 = 35 = p_3p_4
  • A_1 = 15 = p_2p_3
  • A_{4i} = p_1p_{2i + 4}
  • A_{4i + 1} = p_2p_{2i + 4}
  • A_{4i + 2} = p_2p_{2i + 5}
  • A_{4i + 3} = p_1p_{2i + 5}
  • A_{n - 1} \to p_4A_{n - 1}

Explanation

Since, there isn’t much to explain in the way of a solution, I’ll just explain how I came up with such a sequence.

So, the thing with \gcd is that it acts pretty unpredictabily in most circumstances, unless we are dealing with primes. So, a good idea would be to deal with primes and that’s exactly what we do!

Let us ignore the condition, that A_i < 10^9 for a while.
Also, assume all the indices are modulo n.

So, what we would like is that \gcd(A_i, A_{i + 1}) = \text{a prime}, \gcd(A_{i + 1}, A_{i + 2}) = \text{another unrelated prime}. Since, this would imply

\gcd(A_i, A_{i + 1}, A_{i + 2}) = \gcd(\gcd(A_{i}, A_{i + 1}), A_{i + 2}) = \gcd(\text{a prime}, A_{i + 2}) = 1

since \text{a prime} doesn’t divide A_{i + 2}.

Keeping this in mind, we can come up with the very simple solution \{p_1p_n, p_1p_2, \dots \}.

However, this approach does have a drawback, the numbers would be too large in subtask 2.

Let us call our initial solution S.

One thing, we can notice about S is that it is an overkill solution.

What I mean is that rather than having \gcd(S_{i}, S_{i + 1}, S_{i + 2}) = 1, we have \gcd(S_x, S_y, S_z) = 1 for all x, y, z.

This indicates that we can instead repeat some primes, ie, rather than using a new prime for each S_i, we can recycle one.

If we consider the \gcd of two consecutive elements, and force an alternating cycle as such,

2, \text{ a prime }, 2, \text{ another prime }, 2, \dots

we’d be done. You can try a few cases to see that this isn’t really very feasible.

But what if we do it as such,

2, \text{ a prime }, 3, \text{ another prime }, 2, \text{ a third prime }, 3, \dots

we see that yeah, this actually works!

But there’s a small problem, though, it occurs when we are dealing with n - 1, n, 1 and n, 1, 2. So, what can we do to remove, this? Just make sure that the first two elements aren’t divisible by 2, but we still need some primes to link the first two elements. This is actually pretty simple if we use 5 and 7 here.

Implementation

Just use classical Sieve of Eratosthenes to generate the first 25003 primes, because those are all we need.
Also, there’s a faster way to write the 4 cases of A_{4i}, A_{4i + 1}, A_{4i + 2} and A_{4i + 3},

A_i = \left(3 - \left(\left\lfloor\frac{i - 1}{2}\right\rfloor \mod 2\right)\right)\times p\left[\left\lfloor\frac{i}{2}\right\rfloor + 4\right].

Editorialist’s Implementation