1
$\begingroup$

I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $j$ in $\Omega(\log j)$ airthmetic operations.

Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.

Question : How to compute set $A$ in $O(k)$ many arithmetic operations?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Is this homework? $\endgroup$ – Emil Jeřábek Jan 25 '18 at 20:51
  • $\begingroup$ @ Emil Jeřábek No I am currently reading a research paper (finite abelian group isomorphism in linear time) in which they have claimed this result. $\endgroup$ – new Jan 26 '18 at 4:26
3
$\begingroup$

Using a linear sieve like this:

https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html

you can factor every number in range $j=2,3,..,k-1$ in linear time.

From there, you get an array with some prime divisor (the least for example) of each number in the range. Using that you can solve your problem by filling $A$ in order, and for each new number $j$ you just use the prime divisor of it, find it's greater exponent in $a$, and $j$, and use the previously calculated results in $A$ to get your answer. I'm not totally sure this last part it runs in linear time, but it should be possible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It sounds like you’re saying factoring can be done in linear time. That’s not (known to be) true, so I’m having trouble understanding what you’re going for here $\endgroup$ – Stella Biderman Jan 25 '18 at 23:42
  • 1
    $\begingroup$ Reynaldo is saying that all integers from $2$ to $n$ can be labeled with their smallest prime divisor in time $O(n)$ using a simple sieving algorithm. This is quite different from factoring a given integer in time linear in its bit size. $\endgroup$ – Sasho Nikolov Jan 26 '18 at 1:40
  • $\begingroup$ You don't need to bother with exponents. If p[j]$l is the array of prime divisors of the j's: `A[1]:=1; for j=2..k-1 do { if (A[j/p[j]]*p[j] divides j and a) then A[j]:=A[j/p[j]]*p[j] else A[j]:=A[j/p[j]] }. This is clearly linear time. $\endgroup$ – Emil Jeřábek Jan 26 '18 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.