Return to Answer

replaced http://mathoverflow.net/ with https://mathoverflow.net/

Source Link

edited Apr 13, 2017 at 12:58

Let $N$ be the number to be factored. First, use an algorithm to quickly determine if $N$ is a perfect $k$-th power. Daniel Bernstein's papers say this can be done in "essentially linear time" (see this related MO post MO post). Depending on the output of the first algorithm, use $A(\omega(N)) \ge G(\omega(N))$ (i.e. Arithmetic Mean-Geometric Mean Inequality) to reduce the search space:
$$\displaystyle\sum_{p|N}{p} \ge \omega(N)\left({\displaystyle\prod_{p | N}{p}}\right)^{\frac{1}{\omega(N)}}$$ with equality if and only if the previous algorithm gives an affirmative answer. Lastly, use number-theoretic techniques and your knowledge of the "structural properties" of $N$ to give "tight" lower bounds for $\omega(N)$, the number of distinct prime factors of $N$ and the radical $$rad(N) = \displaystyle\prod_{p | N}{p}$$ of $N$. This method will give you a priori knowledge (i.e. an estimate) for the true magnitude of the sum.

Of course, the same method gives you bounds for $\omega(N)$ and $rad(N)$ when either one is known, under the conditions of the problem that you are considering.

Let $N$ be the number to be factored. First, use an algorithm to quickly determine if $N$ is a perfect $k$-th power. Daniel Bernstein's papers say this can be done in "essentially linear time" (see this related MO post). Depending on the output of the first algorithm, use $A(\omega(N)) \ge G(\omega(N))$ (i.e. Arithmetic Mean-Geometric Mean Inequality) to reduce the search space:
$$\displaystyle\sum_{p|N}{p} \ge \omega(N)\left({\displaystyle\prod_{p | N}{p}}\right)^{\frac{1}{\omega(N)}}$$ with equality if and only if the previous algorithm gives an affirmative answer. Lastly, use number-theoretic techniques and your knowledge of the "structural properties" of $N$ to give "tight" lower bounds for $\omega(N)$, the number of distinct prime factors of $N$ and the radical $$rad(N) = \displaystyle\prod_{p | N}{p}$$ of $N$. This method will give you a priori knowledge (i.e. an estimate) for the true magnitude of the sum.

Of course, the same method gives you bounds for $\omega(N)$ and $rad(N)$ when either one is known, under the conditions of the problem that you are considering.

Let $N$ be the number to be factored. First, use an algorithm to quickly determine if $N$ is a perfect $k$-th power. Daniel Bernstein's papers say this can be done in "essentially linear time" (see this related MO post). Depending on the output of the first algorithm, use $A(\omega(N)) \ge G(\omega(N))$ (i.e. Arithmetic Mean-Geometric Mean Inequality) to reduce the search space:
$$\displaystyle\sum_{p|N}{p} \ge \omega(N)\left({\displaystyle\prod_{p | N}{p}}\right)^{\frac{1}{\omega(N)}}$$ with equality if and only if the previous algorithm gives an affirmative answer. Lastly, use number-theoretic techniques and your knowledge of the "structural properties" of $N$ to give "tight" lower bounds for $\omega(N)$, the number of distinct prime factors of $N$ and the radical $$rad(N) = \displaystyle\prod_{p | N}{p}$$ of $N$. This method will give you a priori knowledge (i.e. an estimate) for the true magnitude of the sum.

Of course, the same method gives you bounds for $\omega(N)$ and $rad(N)$ when either one is known, under the conditions of the problem that you are considering.

Source Link

created Mar 7, 2011 at 2:06

Jose Arnaldo Bebita

Let $N$ be the number to be factored. First, use an algorithm to quickly determine if $N$ is a perfect $k$-th power. Daniel Bernstein's papers say this can be done in "essentially linear time" (see this related MO post). Depending on the output of the first algorithm, use $A(\omega(N)) \ge G(\omega(N))$ (i.e. Arithmetic Mean-Geometric Mean Inequality) to reduce the search space:
$$\displaystyle\sum_{p|N}{p} \ge \omega(N)\left({\displaystyle\prod_{p | N}{p}}\right)^{\frac{1}{\omega(N)}}$$ with equality if and only if the previous algorithm gives an affirmative answer. Lastly, use number-theoretic techniques and your knowledge of the "structural properties" of $N$ to give "tight" lower bounds for $\omega(N)$, the number of distinct prime factors of $N$ and the radical $$rad(N) = \displaystyle\prod_{p | N}{p}$$ of $N$. This method will give you a priori knowledge (i.e. an estimate) for the true magnitude of the sum.

Of course, the same method gives you bounds for $\omega(N)$ and $rad(N)$ when either one is known, under the conditions of the problem that you are considering.