Linked Questions

1 vote
1 answer
366 views

Euler's Totient Function [duplicate]

Let $\phi(\cdot)$ be the Euler totient function, and let $n=p_1^{k_1}\cdots p_s^{k_s}$ be the prime factorization of $n\in \mathbb{N}$. The well-known Euler's product formula states that $\phi(n)=n(1-\...
Xueyi Huang's user avatar
2 votes
1 answer
222 views

Bounds for relative totient function for small values

Define $\phi(n,x)= \sum_{m\leq x,\gcd(m,n)=1} 1$, the number of elements in the interval $[1,x]$ that is relatively prime to $n$. $\omega(n)$ is the number of distinct prime factors of $n$. It's not ...
Chao Xu's user avatar
  • 583
0 votes
2 answers
218 views

Results regarding the relative-totient function

Let $\Lambda(x,n)$ be the the number of totatives of $x$ which are less than or equal to $n$, and $\Phi(x)$ be Euler's totient function. For now assume $x>n$. Is there a general formula for $\...
Brad Graham's user avatar
-3 votes
2 answers
594 views

The number of totatives to the nth primorial, in an interval shorter than the nth primorial

(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.) Can, and if so when can, we determine the amount of natural numbers which are ...
Brad Graham's user avatar
1 vote
4 answers
1k views

Distribution of composite numbers

I have moved this question to math.stackexchange.com. People who are interested in this question can discuss at :https://math.stackexchange.com/questions/1272431/distribution-of-composite-numbers ...
Xuexing Lu's user avatar
4 votes
1 answer
446 views

References to proofs of upper and lower bounds on the number of coprimes in an interval?

On the first page of the article "When the sieve works", the authors present upper and lower bounds for $S(T,T+x;\mathcal{E})$; the number of integers in the interval $(T,T+x]$ that are coprime to all ...
user45947's user avatar
  • 955
6 votes
1 answer
717 views

When does Merten's product theorem accurately estimate the number of coprimes in an interval?

Assume an arbitrary $x$ and let $z$ be smaller than $y$, where $y$ is the length of the interval $[x,x+y]$. What I would like to know is: Let $W(z)=\prod_{p\leq z}\left(1-\frac{1}{p}\right)$. For ...
user45947's user avatar
  • 955
6 votes
0 answers
321 views

Should I expect to see numbers this smooth?

I have a sequence $N_k$ of numbers whose growth I wish to determine, or at least approximate nicely. When I look at the ratios of consecutive members, I find some interesting simplifications ...
Gerhard Paseman's user avatar
20 votes
6 answers
4k views

Erik Westzynthius's cool upper bound argument: update?

Version 2 of this writeup is available, and includes a newer and simple upper bound thanks to MathOverflow 88777 as well as indirect references to future writeups. Details of further work ...
Gerhard Paseman's user avatar
13 votes
2 answers
1k views

distribution of coprime integers

Let $0 < a < 1$ be fixed, and integer $n$ tends to infinity. It is not hard to show that the number of integers $k$ coprime to $n$ such that $1\leq k\leq an$ asymtotically equals $(a+o(1))\...
Fedor Petrov's user avatar