2
$\begingroup$

I know a little about Euler's totient function that counts integer less than $N$ that are relatively prime to $N$.

But I don't know how to modify the function for perfect square numbers, or maybe there is another formula I don't know about.

Can somebody provide any help? Thanks a lot.

$\endgroup$

1 Answer 1

1
$\begingroup$

We may assume that $$ N=\prod_{l=1}^{k} p_l^{\alpha_l} $$ is the factorization of $N$ and define $\square_N(m)$ as the number of squares $\leq m$ that are coprime with $N$. For our purposes it is enough to compute $\square_N(N^2)-\square_N(N)$, where $\square_N(m)$ accounts for the integers in the range $[1,\sqrt{m}]$ that are coprime with $p_1,p_2,\ldots,p_k$. By the inclusion-exclusion principle $\square_N(m)$ is expected to behave like $$\sqrt{m}\prod_{l=1}^{k}\left(1-\frac{1}{p_l}\right)$$ plus a small error term, hence $\square_N(N^2)-\square_N(N)$ is expected to behave like $$ N\prod_{l=1}^{k}\left(1-\frac{1}{p_l}\right) +O(\sqrt{N}) = \varphi(N)+O(\sqrt{N}).$$

$\endgroup$
2
  • $\begingroup$ thanks a lot for your answer ,, But I am just a beginner and i can't understand your formula well.. can you explain it in general language please? $\endgroup$ Jul 11, 2016 at 3:57
  • $\begingroup$ this is the problem statement sir.. given a number N, you should count how many perfect square numbers bigger than N and smaller than N^2, which has no prime factor exists in number N factorization (i.e. all of the prime factors do not exist in number N factorization) if N = 10 then the output should 2 (49 & 81) if N = 12 then the output should 3 thanks $\endgroup$ Jul 11, 2016 at 4:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .