O9 — Counting distinct prime factors

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Integers are supplied in binary; polynomial time means a polynomial number of classical bit operations in total input length. Define $\omega(n)=|\{p:p\text{ is prime and }p\mid n\}|$ for $n\ge1$, with $\omega(1)=0$.

Statement recorded in the supplied source.

Is there a deterministic polynomial-time algorithm which outputs $\omega(n)$ for every positive integer $n$? [S2]

Short English statement

Can the number of distinct prime divisors be computed deterministically in time polynomial in the binary input length?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8400010 (AMR-083-0010). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Leonard M. Adleman and Kevin S. McCurley, Open Problems in Number Theory Complexity, II, in Algorithmic Number Theory, LNCS 877 (1994), pp. 291--322, C9/O9, manuscript p. 9 (LNCS p. 299). https://mccurley.org/papers/open.ps.gz.