Skip to main content
added 1 characters in body
Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 218

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{\log n} \ll 1. $$$$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{-\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be $\ll 1$.

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be $\ll 1$.

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{-\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be $\ll 1$.

deleted 6 characters in body
Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 218

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be less than $1$$\ll 1$.

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be less than $1$.

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be $\ll 1$.

Source Link
Lucia
  • 43.7k
  • 6
  • 193
  • 218

Your guess that $s(n)$ gets large if $\omega(n)$ is large is not correct.
It is possible for $n$ to have many primes, and for $s(n)$ still to be small.

This can be seen from some of the work in your question. As you note $s(n) =\sum_{d|n} \phi(d) a_d$ where $a_d =\sum_{p\equiv 1\pmod d} p^{-2} \ll 1/d^2$. Therefore $$ s(n) \ll \sum_{d|n} \frac{1}{d} \le \prod_{p|n} \Big(1-\frac 1p\Big)^{-1}. $$ If now every prime factor of $n$ exceeds $\log n$, then (since $\omega(n) \le \log n$ trivially) we have $$ s(n) \ll \Big(1-\frac{1}{\log n} \Big)^{\log n} \ll 1. $$

Thus $n$ can have about $\log n/\log \log n$ prime factors, all larger than $\log n$ and still $s(n)$ would be less than $1$.