I need help in the problem 2029E - Common Generator. My submission is 291934025. I spent 4 hours on this and came up with proofs of all the steps I took. If any of them are wrong please point them out.
Let's start by dividing it into cases. It is obvious that for n = 1, there is only 1 number and every number is a generator of itself so we can just print that number.
Else, we will be having 3 cases. But before that, let's make and prove some claims.
Claim 1 — Prime Numbers can't have any generators.
Proof: ======
Consider a prime P. According to the problem, for a number a to be a generator of P, it must satisfy a + d = P. But since d is also a factor of a, we can say a = bd for any b != 1. So we get bd + d = P, implying d(b+1) = P and since both d and b are > 1, P has two factors not equal to each other and > 1. So P must not be a prime. Proof by contradiction, primes can only be self generated.
Claim 2: Every composite number can be generated from 2.
Proof:
We can see every even number is generated from 2 because every even number has 2 as a factor. So every multiple M of 2 can also generate M + 2, thus generating every even number. Since any prime P can only be self generated and doesn't have any valid factors (since we can not use 1), the only immediate number it can generate is 2*P (Here from immediate generators I mean if a is a generator of b then there must exist a divisor d of a such that a + d = b. This should happen in a single step and not repeated ones. For example, 2 is an immediate generator of 4 because 2 + 2 = 4 but it isn't an immediate generator of 8 because 8 = 6 + 2, 6 = 4 + 2, 4 = 2 + 2 so we are taking multiple steps to reach there). Since 2*P is a multiple of P, 2 is it's generator. Also, 2*P can generate every multiple of P because P is a divisor of every multiple M of P so every multiple of P can generate M + P and since M is a multiple of P, we can say M = kP thus generating (k+1)P from kP (similar to what we did to prove all even numbers can be generated from 2). And since we can generate any number of the form 2*P from 2 where P is a prime, the number would generate all the other multiples of P thus we can have all the multiples of P except P itself. Hence, 2 can generate every composite number.
Further Cases for n != 1:
Now let's try to find the number of primes present in our array. From here, we can further make 3 cases-
Case 1:
If the number of primes is 0, that means all the numbers in our array are composite and we already proved in claim 2 that 2 can generate every composite number. So we can just print 2.
Case 2:
We already saw from Claim 1 that all prime numbers can only be self generated i.e. we can't have any number that can generate a prime except itself. This implies if we have 2 or more primes in our array it is impossible to generate them from a single number because all of them can only be generated from themselves. So we just print -1 in this case.
Case 3:
When we have just 1 prime number in the array, we need to check if we can generate every other number from it or not. Here are a few observations:
Whenever we are generating a number, we are doing it via an addition operation. Thus, we can never generate a smaller number from a number no matter how many steps we take. So if any number less than our prime is present, we can't generate it and hence print -1.
The next number we can generate from any prime P is 2*P because a prime number only has itself as a factor. So if we have any numbers less that 2*P other than P in our array, we can't generate them and hence print -1.
Now time for a few more proofs.
Claim 3: For two primes P1 and P2, we can always generate every multiple of P2 from P1 if P2 > P1.
Proof: ======
We can always generate 2*P1 from P1. Using similar logic as in Claim 2, I can say I can generate every even number > 2*P1 from 2*P1 because 2 is a factor of it. In general, 2*K can always generate 2*(K+1). Since P2 > P1, 2*P2 > 2*P1 implying I can always generate 2*P2 from P1. Using the logic I proved in Claim 2, I can generate every multiple of P2 except p2 from 2*P2 so if I can generate 2*P2 from P1, I can also generate every multiple of P2 from it.
Now we just need to check what is the least multiple of a prime P0 < P1 which I can generate from P1.
Claim 4: For the greatest possible value of an integer m such that m*P0 < 2*P1, if m is odd then I can always generate all multiples of P0 which are greater than 2*P1 from P1. ==========================================================================================================================================================
Proof:
Since P0 is a prime other than 2, it has to be odd. So, if m is odd, mP0 must be odd. This implies (m+1)P0 must be even since m+1 would be even. Also, since mP0 was the greatest multiple of P0 less than 2*P1, (m+1)P0 must be greater than 2*P1 and even. Since I can generate every even number greater than 2*P1 from P1 as proved in Claim 3, I can always generate (m+1)P0 from P1 for all odd m. Since I just generated a multiple of P0, from Claim 2 I can also prove I can generate every other multiple of P0 from this.
THE EXPECTED PROBLEM WITH THE CODE:
Now extending Claim 4 for even m, I can say, (m+2)P0 can always be generated from P1 since m+2 would be even in this case and again from claim 2, implying every other multiple of P0 greater than it can also be generated from there. The only fishy case is of (m+1)P0 for even m where I can't prove that it can never be generated from P1. However just taking it on gut feeling does make it work for examples like 7 14 15 18 20 etc. Notice that here we can't generate 15 from 7 because 15 = 5 x 3 and greatest multiple of 5 before 14 was 5 x 2 which was the case for an even m. Well for this particular example I mentioned, this could also be taken care of by adding a condition that 2P+1 can never be generated from P because the least we can generate is 2P and addition by 1 is prohibited and remove that condition for even m altogether. But again I am unable to prove it so need help as to take those even values for m, drop them, or have a mix of both. I feel the problem is arising due to this part of the code.
