Sieve of Eratosthenes, Number-Theory and Constructive Algorithms.
Given an integer N \geq 3, find N distinct numbers such that every pair of consecutive numbers have a common factor > 1 and all possible consecutive three elements have no common factor > 1. Also, all numbers found should be between 1 and 10^9. First and Last elements are also considered adjacent here.
SUPER QUICK EXPLANATION
- A simple way to generate N such distinct numbers is to take a prime and multiply two consecutive elements by this number. This way, the condition of co-primes is handled, but the numbers generated go beyond 10^9.
- A better way would be to reuse smaller primes while ensuring all the generated numbers are distinct.
This is a constructive problem, and hence, have multiple solutions. Feel free to share your solution in comments.
Note: If we represent a number as the product of prime numbers, Prime factorization of a common factor of the pair of numbers is the common part of prime factorization. If we consider prime values or product of few primes, they have relatively lesser factors as compared to composite numbers. So, for most of the problems involving prime factors/factorization/divisibility, prime numbers bear special importance.
Let us try similar problems first.
Try solving the same problem assuming there’s no upper bound on maximum values. Now, we can just multiply a distinct prime number to every pair of consecutive numbers. This way, every two consecutive numbers are not co-prime while every three consecutive numbers are coprime.
The above solution is sufficient to solve the first subtask, but in the second subtask, the values exceed 10^9, so we need something better.
Try solving the same problem, assuming we are allowed repeated values. Here, we can choose prime numbers and multiplying each position by exactly two primes such that every two consecutive positions share prime factor while every three consecutive numbers do not share any prime factor, taking special care to choose a different prime number when reaching the end of the array.
Now, let us solve the original problem.
Think up and try to mix the above solutions so as to reduce the magnitude of generated numbers while keeping each number distinct.
The construction used in my solution is to reserve the first few primes and then multiply the first two positions by a non-reserved prime, next two positions by another prime and so on. Now, We can multiply Last and first position by a reserved prime, second and third position by different reserved prime, and so on. This way, we are guaranteed to have every pair of consecutive positions divisible by that particular prime number, and every three consecutive positions are coprime since no prime is multiplied to three consecutive positions.
For this problem, we can preprocess and calculate a list of primes beforehand using the sieve of Eratosthenes and then for every test case, use primes from the list instead of recomputing.
This problem can also be approached as a challenge problem where we need to minimize the maximum value generated in sequence. Can you minimize? Say for N = 50000
Time complexity is O(MX*log(log(MX)) + \sum N) per test case where MX is the upper limit till primes are found. Finding primes up to 10^6 suffices for this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.