Given positive integer $M.$ For any $n\in\mathbb N_+,$ let $h(n)$ be the number of elements in $[n]$ that are coprime to $M.$ Define $\beta :=\frac {h(M)}M.$ Proof: there are at least $\frac M3$ elements $n$ in $[M],$ satisfy $$\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}+1.$$Here $[n]:=\{1,2,\ldots ,n\}$ for all positive integer $n.$ Proposed by Bin Wang
Problem
Source: 2024 Chinese TST P3
Tags: number theory, 2024 CTST
06.03.2024 05:43
I think I might be having extreme reading comprehension issues. If $M=2^{10}$, then $h(n)=\frac n2$ so the right hand side is less than $2$, which means only $n=1,2,3$ works?
06.03.2024 05:48
EDIT: This probably depends on the definition of $\omega(n)$, and Dotted's complaint is valid if $\omega(n)$ is assumed as the prime divisor counting function.
06.03.2024 05:50
TheHazard wrote: $h(n)$ depends on the value of $n$, which isn't always $M = 2^{10}$. Isn't $h(n)=\frac n2$ for $M=1024$?
06.03.2024 09:33
redacted
06.03.2024 16:11
L should be number of distinct prime divisors…. Not the number of divisors
06.03.2024 16:13
DottedCaculator wrote: TheHazard wrote: $h(n)$ depends on the value of $n$, which isn't always $M = 2^{10}$. Isn't $h(n)=\frac n2$ for $M=1024$? So in this case $L=1$ and $\beta =\frac 12$. The statement is true since $h(n)=\lceil \frac n2\rceil$
06.03.2024 19:54
06.03.2024 20:26
08.03.2024 13:14
Actually it is not abstruse by using Markov ine
01.10.2024 11:22
Actually the original problem created by proposer is way more difficult, but since he thought that no one is abled to solve it, at last this problem turns out. Original Problem: Given positive integer $M.$ For any $n\in\mathbb N_+,$ let $h(n)$ be the number of elements in $[n]$ that are coprime to $M.$ Define $\beta :=\frac {h(M)}M.$ Proof: there are at least $\frac {M-h(M)}3$ elements $n$ in $[M]$ that are not coprime to $M,$ satisfy $$\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}.$$
11.01.2025 19:40
Rushery_10 wrote:
Is summation of h(n) - Bㆍn = fraction part of n/d ?