For questions on arithmetic functions, a real or complex valued function $f(n)$ defined on the set of natural numbers.

learn more… | top users | synonyms

25
votes
1answer
874 views

Primes approximated by eigenvalues?

Consider the infinite matrix starting: $$\displaystyle T = -\left( \begin{array}{ccccccc} +1&+1&+1&+1&+1&+1&+1&\cdots \\ +1&-1&+1&-1&+1&-1&+1 \\...
21
votes
0answers
227 views

Sums of the form $\sum_{d|n} x^d$

Let $$S(x,n) = \sum_{d|n} x^d, n \in \Bbb N$$ Do these sums appear in the literature? What are they called if they do and what is known about them?
19
votes
2answers
201 views

For all $n$ there exists $x$ such that $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$

Let $\varphi$ be the Euler's function, i.e. $\varphi(n)$ stands for the number of integers $m \in \{1,\ldots,n\}$ such that $\text{gcd}(m,n)=1$. Let $n\ge 2$ be a positive integer. Show that there ...
12
votes
1answer
195 views

How to prove that $n\sum_{d\mid n}\frac{|\mu(d)|}{d}=\sum_{d^2\mid n}\mu(d)\sigma\left(\frac{n}{d^2}\right)$?

This is problem 11 part b in chapter 3 of Tom M. Apostol's "Introduction to Analytic Number Theory". A variation on Euler's totient function is defined as $$\varphi_1(n) = n \sum_{d \mid n} \frac{|\mu(...
10
votes
3answers
359 views

Arithmetical Functions Sum, $\sum_{d|n}\sigma(d)\phi(\frac{n}{d})$ and $\sum_{d|n}\tau(d)\phi(\frac{n}{d})$

$$\sum_{d|n}\sigma(d)\phi\left(\frac{n}{d}\right)=n\tau(n) ,\\ \sum_{d|n}\tau(d)\phi\left(\frac{n}{d}\right)=\sigma(n)$$ The problem (7.4.15) of Burton's Elementary Number Theory has been request to ...
10
votes
5answers
585 views

Identity with nested sum taken over divisors of $\gcd$'s

For computational reasons, I want to show that the following holds true: Let $n_1,n_2,N\in \mathbb{N}$. One has $$\Large \sum_{a\mid \gcd(n_1,N)}\sum_{b\mid \gcd(n_2,\frac{n_1N}{a^2})} ab =\sum_{g\...
10
votes
0answers
165 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
9
votes
3answers
1k views

Is there a “nice” formula for $\sum_{d|n}\mu(d)\phi(d)$?

I'm trying to work through Ireland and Rosen's A Classical Introduction to Modern Number Theory as I've heard good things about it. This is Exercise 12 from Chapter 2. Here $\mu$ is the Moebius ...
9
votes
4answers
1k views

How to prove $ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$

how to prove: $$ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$$ $\prod_{d|n} d$ is product of all of distinct positive divisor of $n$, $\tau (n)$ is number (count)of all of positive divisor of $n$
9
votes
1answer
359 views

Proving that $\omega(N)\neq4$ for an odd perfect number $N$ by hand

Let $\omega(n)$ denote the number of distinct prime factors of a positive integer $n$, and let $N$ be an odd perfect number. It is not difficult to show that $\omega(N)\ge3$. In fact, Nocco already ...
8
votes
2answers
1k views

Prove $\sum_{d \leq x} \mu(d)\left\lfloor \frac xd \right\rfloor = 1 $

I am trying to show $$\sum_{d \leq x} \mu(d)\left\lfloor \frac{x}{d} \right\rfloor = 1 \;\;\;\; \forall \; x \in \mathbb{R}, \; x \geq 1 $$ I know that the sum over the divisors $d$ of $n$ is zero if $...
8
votes
1answer
145 views

Comparing average values of an arithmetic function

Suppose $f(n)$ is a positive real-valued arithmetic function such that $$ \frac1n\sum_{k=1}^nf(k)\sim g(n) $$ for $g(x)$ a monotonic increasing function. What can be said about the asymptotic behavior ...
8
votes
1answer
173 views

Intuitive basis of Mobius inversion?

If we're given $f(n)= \sum_{d|n}g\left(\frac{n}{d}\right),n \in \mathbb{N},$ then Mobius inversion gives $$g(n)=\sum_{d|n}\mu \left( d\right) f \left( \frac{n}{d}\right).$$ Also, the generalised ...
7
votes
1answer
207 views

Is there a complex variant of Möbius' function?

When you're dealing with arithmetic functions, you might have come across the classical Möbius' function $$ \mu(n)=\begin{cases} (-1)^{\omega(n)}=(-1)^{\Omega(n)} &\mbox{if }\; \omega(n) = \Omega(...
7
votes
0answers
157 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
6
votes
2answers
199 views

Sum of $n \sigma(n)$

What is known about the asymptotic behavior of $$ -\frac{\pi^2}{18}x^3+\sum_{n\le x}n\sigma(n) ? $$ It seems to be $O(x^{2+\varepsilon})$ but I cannot prove this.
6
votes
1answer
120 views

Lower bound of Euler phi function times sum of divisors

After some work, I got this nice inequality: $$ \frac{n^2}{2} < \phi(n)\cdot \sigma(n) $$ where $\phi(n)$ is Euler's phi function and $\sigma(n)= \sum_{d|n} d$. I know this is true because I'm ...
6
votes
2answers
221 views

Arithmetic Derivatives: Arithmetic Logarithmic Derivative Problem

In Calculus, whenever we see a constant and want to take the derivative of it, it always is 0. However in Number Theory, we have something called the arithmetic derivative in which we can ...
6
votes
2answers
97 views

$\varphi(N)>\pi(N)$?

Is it trivial that $\varphi(N)>\pi(N)$ for sufficiently big integers $N$, where $\varphi$ is Euler's totient function and $\pi$ is the prime-counting function? The only exceptions less than $1.000....
6
votes
1answer
119 views

How many numbers are products of $p^p$?

Consider the set $\mathcal{S}=\{1,4,16,27,\ldots\}$ of numbers which are products of numbers of the form $p^p$ for $p$ prime. ($\mathcal{S}$ is A072873 in the OEIS.) Note that multiple primes are ...
6
votes
0answers
174 views

Are known these identities, that I've deduce using Mobius inversion formula?

I would to know if this formula is right and know (these formula are the same by exponentiation), since I deduce this easily by a standar way (perhaps there are mistakes) using Mobius inversion from $$...
5
votes
1answer
90 views

A question about Euler's totient function

Prove that for every natural number $m$, there exists a natural number $n$ such that $$\phi(n)=\phi(n+m)$$ For odd numbers $m$, we can choose $n=m$ and use the identity $\phi(2m)=\phi(m)$.
5
votes
0answers
180 views

Summation of a function 2

Let $n$ is a positive integer. $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the complete prime factorization of $n$. Let me define a function $f(n)$ $f(n) = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ where ...
5
votes
0answers
138 views

Is the application of $\mu$ on $P_x(s)^k$ analogous to the differentiation $\frac{d^k f(\lambda) }{d\lambda^k}\biggr|_{\lambda=0}$?

Let me start with the following on elementary symmetric polynomials: The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity ...
4
votes
1answer
129 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
4
votes
2answers
399 views

Ramanujan 1918 paper

Does anybody know where I can find Ramanujan's paper from 1918 titled "On Certain Arithmetical Functions." It is referenced in wikipedia, under the Ramanujan Summation section, but I cannot find a ...
4
votes
2answers
279 views

Which natural number predicates can be defined in Robinson arithmetic?

I'm especially wondering about the order relation, subtraction, division and exponentiation here: $x \leq y \quad \Leftrightarrow \quad \exists u\ y=x+u$ $z= x-y \quad \Leftrightarrow \quad x=y+z\...
4
votes
2answers
154 views

Limiting value of $\lim \frac{1}{k}\sum_{n=1}^k \frac{p(n+1)-p(n)}{\log p(n)}$

Empirically it seems $$\lim_{k\to \infty} \frac{1}{k}\sum_{n=1}^k \frac{g(n)}{\log p(n)} = 1\tag{1} $$ in which p(n) is the nth prime and g(n) is the prime gap $p(n+1)-p(n).$ Cramer conjectured ...
4
votes
1answer
574 views

On sums involving Euler's totient function

I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated: Let $\varphi(n)$ be Euler's totient function. Show that there is a constant $0&...
4
votes
3answers
517 views

Prove there are k consecutive non-squarefree integers

So, I've got a question for class that asks me to prove the existence of arbitrarily long runs of consecutive integers where $\mu(n)$ is zero. I've started the proof, but I need a bit of help midway ...
4
votes
1answer
130 views

Decidable & Recursive predicates

Let $C$ be a decidable predicate in the language of arithmetic HA, that is $$ \vdash (\forall \underline x)\: C(x) \vee \neg C(x).$$ $C$ is recursive if there exists a computable characteristic ...
4
votes
1answer
234 views

Euler phi function, number theory

I am trying to find the value of $$\sum_{n=1}^{N}\sum_{d|n}d*\phi(d)$$ Is there a method to evaluate this for large N? $\phi(d)$ is the Euler phi function.
4
votes
3answers
534 views

Question about $T_n = n + (n-1)(n-2)(n-3)(n-4)$

The formula $T_n = n + (n-1)(n-2)(n-3)(n-4)$ will produce an arithmetic sequence for $n < 5$ but not for $n \ge 5$. Explain why. I think it is because if n is less than five the term with ...
4
votes
1answer
218 views

Image of the Euler phi function

I was reading a text about arithmetic functions, which ofcourse mentioned the Euler phi function. I was wondering whether $\phi(n)$ takes on all positive integer values. The answer doesn't seem so ...
4
votes
2answers
94 views

An uncountable well-ordered subordering of asymptotic growth rates?

Define the following relation $\le$ between arithmetic functions $f$ and $g$ (mappings from $\mathbb{N} \rightarrow \mathbb{N}$): $f \le g := \exists n_0, k: \forall n: n \gt n_0 \implies f(n) \lt k \...
4
votes
1answer
119 views

Infinite exponentiation $n^{n^{n^{…^n}}} \equiv m \pmod q$ , find m?

let $(n,q) \in \mathbb N^{*^2}$ I was wondering if it was possible to find a function $f_q$ such that : $f_q(n)=m$ where $m$ is such that $n^{n^{...^n}} \equiv m \mod q$ or at least an easy way to ...
4
votes
1answer
50 views

Number of Divisors of most numbers

In the book A Comprehensive Course in Number Theory by Alan Baker. The author mentions that even though the average order of $\tau(n)$ is $\log n$, almost all numbers have about $(\log n)^{\log 2}$ ...
4
votes
1answer
160 views

Prove $\sum_{k = 1}^n \mu(k)\left[ \frac nk \right] = 1$ [duplicate]

I need to prove the identity $$\sum_{k = 1}^n \mu(k)\left[ \frac{n}{k} \right] = 1$$ where $n$ is a natural number, and $[n]$ denotes the floor function. The proof also should not use the Möbius ...
4
votes
2answers
231 views

prove that $\phi(xy) =\phi(x)\phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. [duplicate]

Prove that $\phi(xy) = \phi(x) \phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. I understand the concept, and have done several examples proofing this but cannot put it in "proof form" because unless ...
4
votes
1answer
106 views

Properties of Arithmetic Functions

I was recently working on arithmetic functions and using Perron's formula to obtain asymptotic estimates. One observation I made was that the Dirichlet series often can be written in terms of the ...
4
votes
2answers
100 views

Prove: $\sum_{k<n, (k,n)=1} k= \frac{1}{2}n \varphi (n)$

Prove: $\sum_{k<n, (k,n)=1}k = \frac{1}{2}n \varphi (n)$ I have had strep throat and missed the lecture discussing properties of the Euler function. Any help in solving this is appreciated. Thank ...
4
votes
2answers
283 views

Elements of finite order in the group of arithmetic functions under Dirichlet convolution.

Let $(G, ∗)$ be the group of arithmetic functions $f : N \to C$ that satisfy $f (1)\neq 0$, with group operation given by the Dirichlet product $∗$. The identity function $I$ is the identity element ...
4
votes
1answer
49 views

On a generalization for $\sum_{d|n}rad(d)\phi(\frac{n}{d})$ and related questions

Let $\phi(m)$ Euler's totient function and $rad(m)$ the multiplicative function defined by $rad(1)=1$ and, for integers $m>1$ by $rad(m)=\prod_{p\mid m}p$ the product of distinct primes dividing $...
4
votes
2answers
122 views

Closed-Form Modular Arithmetic

Is there a way to define modulo division (or functions of modular arithmetic in general) as superposition of (elementary?) functions? For example, the multiplication is first introduced as summation,...
4
votes
1answer
97 views

Asymptotics for almost all $x$

Theorem 2.2 in Shparlinski 2006 says: For all positive integers $n\le x$ except possibly $o(x)$ of them, the bound $$M(x)\ll\frac{x}{\log x}\exp\left((C+o(1))(\log\log\log x)^2\right)$$ holds. ...
4
votes
1answer
34 views

What about $\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n$ when $y=[x]\to\infty$?

For a real $x\geq 2$ and when we take $y= [x]$ its integer part, I am trying to study the asymptotic size or growth of $$\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n,$$ I believe that ...
4
votes
2answers
137 views

Was this arithmetic Möbius/Mangoldt function ever used for something?

Definition: Let $n=\prod_k p_k^{c_k}$, with $p_k \in \mathbb P$ and $$ A(n)=\sum_{d|n} \mu(d)\Lambda(d)=\sum_\limits{c_k\neq 0} \log p_k , $$ with the Möbius function $\mu(n)$, which is: $...
4
votes
2answers
154 views

Estimating $\sum_{p_2 \leq x} (\log p_2)^2$

This was an exercise to use the approach here to estimate the sum $\sum_{p_2 \leq x} \log (p_2)^2,$ in which $p_2$ are numbers containing two prime factors (repetitions allowed). $\pi_2(x)$ is the ...
4
votes
0answers
146 views

Arithmetic Derivative

In Calculus, whenever we see a constant and want to take the derivative of it, it always is $0$. However in Number Theory, we have something called the arithmetic derivative in which we can ...
4
votes
0answers
332 views

LCM of binomial coefficients and related functions

I know about the following identity: $$\displaystyle \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \frac{\text{lcm}(1, 2, ... n+1)}{n+1}$$ 1) Is there any method to find $...