IMPORTANT NOTE: =============== I initially asked this problem as a doubt since I couldn't figure the last claim on my own. As a result, I doubted my intial observations on a test case that failed and ended up proving everything rigoursly to be certain. As a result, this became full of proofs that I feel can be understood even by most Pupil/Specialist rated coders since it came from one. However, I decided not to change the original text of my doubts since I feel that gives a better idea about my thiught process and how I was able to come up with the proofs for my claims. Also, I added a 5th claim at the end which handles the case for which the original code was failing (that was the only case I couldn't come up with a proof for before which led me to just buy into the thought that such numbers aren't generated. It kinda taught me that if I can't come up with a proof, getting right is pure luck and not learning). You can find my accepted code here — 292005627
ORIGINAL TEXT
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.
EDIT: I WAS ABLE TO SOLVE IT. BUT SINCE IT IS MORE DETAILED THAN THE EDITORIAL, DECIDED TO KEEP IT AS ONE.
To solve for even m, let's make another claim.
Claim 5: For even m, we first find (m+1)P0 and since it is odd, we check if (m+1)P0 — its spf is greater than 2P1 or not. If it is then it can be generated. Else it can't.
Proof:
Since m was even and P0 is odd, (m+1)P0 must be odd. So we know it's spf can't be 2. Note that the spf of a number is also it's least divisor after one so it's the least possible choice of our d. Now, inorder to create a number X such that X + d = (m+1)P0, d must also divide X. Also, since d is an spf and it isn't 2, it must be odd since all primes except 2 are odd. Now our X is (m+1)P0 — d. Since d is odd and (m+1)P0 is also odd, we know odd- odd gives even. So X must be even. Since we already proved in claim 2 that all even numbers greater than 2P1 can be generated from P1. So only if X is >= 2P1 we can generate it from P1 and thus generate (m+1)P0 from this. Now one might question this choice of picking spf as our d. Well you see if we pick the smallest divisor of (m+1)P0 we are creating the greatest possible value for (m+1)P0 — d (or X). If you go through the previous claims, you can see we already proved any number < 2P1 except P1 can't be generated from P1. Also, in this claim we proved that since X is even, only possible way of it not being generated from P1 is if it is less than 2P1. Since it is the greatest possible generator for (m+1)P0, we can say every other number that can generate (m+1)P0 must be less than X. So if our check fails for X, it fails for every other generator of (m+1)P0 which is less than X.
