kilobyte136's blog

My 1090 DIV 4, problem D 67th OEIS solution
By kilobyte136, history, 6 weeks ago, In English

Hey there, im back.

this time im with my OEIS solution! the DIV 4 contest had a question known as the 67th OEIS problem, at first i thought why not the $$$2^n$$$ thingy. as powers of two have diffrent unique gcds, then , i saw the constraints and cried for half an hour :[.

then i tried odds, and evens, then primes... PRIMES! but it disappointed me, well you see, primes will always have a gcd of 1 (theyre primes for a reason), but i wanted uniques, what do i do?? what if i square primes?? well, same result.. hm

the time that it actually hit me was when i did a mistake in my primes square calculating loop, missing my index by 1 indice and multiplying the next prime to my curProd (goofy var name). That was the best, it really gave unique gcds, so i wrote another code, with this logic. it worked.. YESS! thats how i got the answer, pretty dramatic, now heres the logic example:

eg: - $$$P_2 = 2 \cdot 3 = 6$$$ - $$$P_3 = 2 \cdot 3 \cdot 5 = 30$$$ - $$$P_4 = 2 \cdot 3 \cdot 5 \cdot 7 = 210$$$

gcd: - $$$\gcd(P_2, P_3) = \gcd(6, 30) = 6 = P_2$$$
- $$$\gcd(P_3, P_4) = \gcd(30, 210) = 30 = P_3$$$

Its Unique!

heres the code for those who want to absolutely destroy me in the face.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;

bool is_prime(int n) {
    if(n<2) return false;
    for (int i = 2; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}

int main() {
    fastio;
    
    vector<int> primes;
    for (int i = 2; primes.size() <= 10001; i++)
        if(is_prime(i))
            primes.push_back(i);
    
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        for (int i = 0; i < n; i++)
            cout << primes[i] * primes[i+1] << " \n";
    }
    return 0;
}

for those who want a detailed explanation, go to the editorial's comments, i have my explanation written there.

OVER AND OUT

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

no bro your code generates the sequence: $$$P = [6, 15, 35, 77, 143, 221, 323]$$$

because you multiply consecutive primes ($$$P = [2 \cdot 3, 5 \cdot 7, 7 \cdot 11, 11 \cdot 13, 13 \cdot 17, 17 \cdot 19]$$$)

Also tip: Faster way to collect primes

Also your explanation (P[i] = product of first $$$i + 1$$$ primes will only get about 20 numbers)

→ Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

There is also an easy way to solve it: if there are some unique GCDs, then any multiple of adjacent values on the number line has a high probability of creating new unique GCDs. So you can iterate from 1 to 2×10⁵ and simply skip any value that produces an already existing GCD.

Example code 1: 369678414 Blind implementation

Example code 2: 369806579 A little smarter using only odds

→ Reply
»
6 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

you can also just print odds or even with the previous element multiplication

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Do you mean like $$$i \cdot (i+1)$$$ for each $$$i$$$? Because that can fail at points, though you can just print $$$i \cdot (i+2)$$$ for all odd $$$i$$$ values from $$$1$$$ to $$$2n-1$$$. Since $$$gcd(i,i+4)$$$ for odds will always be 1, the gcd of any consecutive values $$$i \cdot (i+2)$$$ and $$$(i+2) \cdot (i+4)$$$ will be $$$=(i+2)$$$.

    → Reply
    • »
      »
      »
      6 weeks ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      no i meant like lets say for n = 5

      first five odds are 1, 3, 5 , 7, 9

      then the ans will be 1, 3 * 1 , 5 * 3, 7 * 5, 9 * 7

      gcd -> 1, 3, 5, 7 all odd numbers

      same was done for prime numbers

      → Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Maybe, use Sieve of Erasthostenes for optmization $$$O(N\cdot log(log(N))$$$ (in case)...

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Although your code works, there is an optimization on how to find primes in time complexity of O(n*log(log(n)) Sieve of Erathostenes:

vector<ll> prime(1e7+1),primes;
primes.push_back(1);
for(ll i=2;i<=1e7;i++)
{
    if(prime[i]==0)
    {
         primes.push_back(i);
         for(ll j=i*i;j<=1e7;j+=i)
         {
             prime[j]=1;
         }
    }
}
→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Amazing Community! I learned alot today. I wont be posting any blogs for a while now though, as people downvote blogs alot which costs me rating...

→ Reply