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

3
votes
3answers
294 views

Ramanujan's tau function identity

While studying Ramanujan's tau function, I observed that the function satisfies a beautiful identity that I had not seen previously in the literature. Let $\tau(n)$ be Ramanujan's tau function, such ...
3
votes
5answers
153 views

How can I show that $\phi(m) \mid \phi(n)$? [duplicate]

I want to prove that: $$\text{ if } m,n \geq 1 \text{ and } m \mid n,\text{ then } \phi(m) \mid \phi(n).$$ How can I show this? I thought the following: $$m \mid n \Rightarrow \exists k \in ...
3
votes
1answer
74 views

Looking an asymptotic for $\sum_{k\leq x}\Lambda(k)e^k$, where $\Lambda (n)$ is the von Mangoldt function

Using Abel's identity (see Theorem 4.2 in page 77 of [1]) and Prime Number Theorem (Theorem 4.4 in page 75) I compute $$\frac{1}{x}\sum_{k\leq x}\Lambda(k)e^k\sim 1\cdot e^x-\frac{1}{x}\int_1^x ...
3
votes
1answer
102 views

Formula for $\sum_{d|n} \frac {\mu(d)}d$

I feel like I've seen a formula somewhere for $\displaystyle \sum_{d|n} \frac {\mu(d)}d$, but I can't remember what it is and can't find it. Does anybody know of a formula?
3
votes
1answer
362 views

Prove that the Möbius function is multiplicative

I'm studying algebra, and I came across some questions on multiplicative functions (that should be number theory though?). One is: prove that mobius function is multiplicative. But I've not been given ...
3
votes
3answers
85 views

Prove that for all $n\in\mathbb{N}$, $\frac{s(n)}{d(n)}\geq \sqrt n$

Prove that for all $n\in\mathbb{N}$ $$\frac{s(n)}{d(n)}\geq \sqrt n$$ where $s(n) = \sum_{d|n} d$ and $d(n) = \sum_{d|n} 1$. Being honest, study some time arithmetic functions, and can not ...
3
votes
3answers
77 views

An identity involving $[\sigma(n)]^2$

For a positive integer $n$, let $\sigma(n)$ denote the sum of the divisors of $n$. For example, $\sigma(1)=1$, $\sigma(2)=3$, $\sigma(4)=7$, etc. I would like to prove the following identity: For ...
3
votes
1answer
54 views

Hints to compute if exists $\lim_{n\to\infty}\sum_{k=1}^n\sigma(k^2)/\sum_{k=1}^n\sigma(k)$, which $\sigma(n)=\sum_{d\mid n}d$, and other question

I would like receive hints at least for one of the following problems, these are going from experiments. Can you provide to me hints for at least one of the following problems? I will try put the ...
3
votes
1answer
45 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 ...
3
votes
1answer
39 views

The sum $\sum_{n\leq x}\sum_{\substack{1\leq k\leq n \\ gdc(k,n)=1}}cos^2\pi \frac{k}{n}$ diverges as $x$, when $x$ tends to infitity

I want to know if it is possible find an easy proof (this is without an use of an strong result) of Question. Prove that the following sum diverges as $x\to\infty$ $$\sum_{n\leq ...
3
votes
1answer
105 views

A sum regarding prime factorization

Prime factorization of $n$ is $n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$ Let $f(n) = \left((p_1^{a_1}+1)(p_2^{a_2}+1)(p_3^{a_3}+1)\cdots(p_k^{a_k}+1)\right)$ I want to find the value of ...
3
votes
4answers
122 views

What's the meaning of this $(m,n) = 1$

I'm reading this pdf http://rutherglen.science.mq.edu.au/wchen/lndpnfolder/dpn01.pdf I understand some of the expression used in this but I don't understand the part $(m,n) = 1$ Is this a cartesian ...
3
votes
1answer
85 views

Is there a friendly pair $\{a, b\}$ where both $a$ and $b$ are odd?

Let $\sigma(x)$ denote the sum of the divisors of a positive integer $x$. $\{y, z\}$ is said to be a friendly pair if $$I(y) = I(z),$$ where $I(x) = \sigma(x)/x$ is the abundancy index of $x$. As ...
3
votes
2answers
132 views

Order of a function related to divisors

Let $f(n)=\max(\{d(ab):\ a,b\le n\})$ where $d(m)$ is the number of divisors of $m.$ What is the order of $f$? In particular I'm looking for an asymptotic upper bound.
3
votes
2answers
683 views

Show that $\sigma(n) = \sum_{d|n} \phi(n) d(\frac{n}{d})$

This is a homework question and I am to show that $$\sigma(n) = \sum_{d|n} \phi(n) d\left(\frac{n}{d}\right)$$ where $\sigma(n) = \sum_{d|n}d$, $d(n) = \sum_{d|n} 1 $ and $\phi$ is the Euler Phi ...
3
votes
1answer
52 views

Can you give an understandable strategy to compute the asymptotic behaviour of $\sum_{2\leq n\leq x}\frac{\Lambda(n)Li(n)}{n}$?

First I am looking a discussion about if the statements that I've deduced will find a good asymptotic formula, what of them you can discard as non useful,or one better than other, and ... second my ...
3
votes
1answer
41 views

Can you prove this identity involving the divisor sum function?

Let $$\sigma(n)=\sum_{d\mid n}d$$ the sum of divisor function. I've deduced, but I don't know how prove directly $$\sigma(n)=\sum_{m=1}^{n}\sum_{k=1}^{m}(-1)^{nk}\cos\left(\frac{\pi ...
3
votes
1answer
80 views

What about $\lim_{n\to\infty}\frac{\sum_{k=1}^n s_k\mu(k)}{n}$, for the zeros of Dirichlet eta function $s_k=1+\frac{2\pi k}{\log 2}i$ with $k\geq 1$?

Let for integers $k\geq 1$ the corresponding zeros of Dirichlet eta function of the form $$s_k=1+\frac{2\pi k}{\log 2}i,$$ then we can consider the following puzzle, when we multiply previous ...
3
votes
1answer
197 views

find all positive integers n such that $\phi(n)+\sigma(n)=2n$.

I'm asked to find all integers n such that $\phi(n)+\sigma(n)=2n.$ I know that when n is a prime, $\phi(n)+\sigma(n)=(n-1)+(n+1)=2n.$ My guess is that n can only be primes, and I want to derive a ...
3
votes
1answer
112 views

Convolution identity involving the Möbius function $\sum_{d|n,d>0} |\mu(d)| = 2^{\omega(n)}$

I'm learning about the Möbius Inversion Formula but I'm stuck on an exercise which involves the Möbius function. Let $n\in\mathbb{Z}$ with $n>0$ and let $\omega(n)$ denote the number of distinct ...
3
votes
1answer
554 views

Chebyshev's first $\vartheta(x)$ function question

This was an exercise using the first Chebyshev function, $\vartheta(x)= \sum_{p \leq x} \log p.$ The question is simply how to prove (2) below, the rest is my two thoughts on how to proceed. [Edit: ...
3
votes
2answers
105 views

Proving an identity of the Möbius function and Euler’s totient function product

Could anyone kindly help me to prove that $$ \sum_{d|n} \mu(d) \varphi(d) = 0 $$ for all even integers $ n \geq 2 $, where $ \mu $ is the Möbius function and $ \varphi $ is Euler’s totient function? ...
3
votes
1answer
101 views

does the surd $\sqrt[p-1]{p}$ for prime $p$ occur in any context?

for any prime $p \in \mathbb{N}$ use the corresponding symbol $q$ to denote the quantity $$q=p^{\frac1{p-1}}$$ and for $n \in \mathbb{N}$ define: $$ Q_n= \prod_{p \le n} q $$ empty products evaluate ...
3
votes
1answer
113 views

Minimal $x$ for which $\phi(k) > n$ for all $k > x$

It's well-known that $$ \liminf_n\frac{\varphi(n)\log\log n}{n}=e^{-\gamma} $$ and there exists an effective version $$ \varphi(n)>\frac {n}{e^\gamma\log\log n+\frac{3}{\log\log n}} $$ valid for ...
3
votes
0answers
69 views

how to show $\lim \sup_{n \to \infty} \frac{\phi(n+1)}{\phi(n)}= \infty$ and $\lim \inf_{n \to \infty} \frac{\phi(n+1)}{\phi(n)}= 0$?

Let $\phi (n)$ be the Euler's totient function . Thenhow to prove that the set $\{\dfrac{\phi(n+1)}{\phi(n)}: n \in \mathbb Z^+\}$ is unbounded above that is how to show $\lim \sup_{n \to \infty} ...
3
votes
1answer
28 views

Two sets with the same geometric and arithmetic means

There are two sets A and B with equal geometric mean and arithmetic mean. Each element of both sets is odd integer greater than 1. A = B ? Order of elements isn't important.
3
votes
0answers
117 views

Does the Fourier matrix $F_n$ represent a (tensor) multiplicative function?

At "Complex Hadamard Matrices", I found that, two Kronecker (tensor) products of Fourier matrices $k_1$ and $k_2$ are equivalent, if and only if $k_2$ can be obtained from $k_1$ by a combination of an ...
3
votes
0answers
85 views

Approximate how the Numbers $n$ such that Mertens' function is zero grow.

Is it possible to approximate how the "Numbers $n$ such that Mertens' function is zero" grow?
2
votes
4answers
120 views

Finding the GCD of $50!$ and $2^{50}$

I've been trying to figure out how $n!$ and $x^n$ are related (where x is an integer) for most of the morning - I know it must be the key to unlocking this problem. Up to this point I've only used ...
2
votes
2answers
186 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
2
votes
2answers
69 views

how to compute the “Hamming total” of a symmetric group?

The Hamming distance between two binary numbers has an obvious analogue for numbers encoded using a base $\gt 2$. A different analogue is the following. Let $\sigma \in S_n$ be a permutation which ...
2
votes
2answers
28 views

On $\sigma(n)<n+\frac{n}{2}\log\frac{n+1}{n-1}+\frac{n}{4} \left(\sum_{\substack{d|n,1<d<n}}\log\frac{(n+d)(n+1)}{(n-d)(n-1)}\right)$

I've derived for $n>1$ and $\sigma(n)$ the sum of divisor function $\sum_{d|n}d$ the following inequality $$\sigma(n)<n+\frac{n}{2}\log\frac{n+1}{n-1}+\frac{n}{4} ...
2
votes
1answer
114 views

Definition of “totient”

I had always taken the term "totient" to be defined by saying that the totient of a positive integer $n$ is the number of positive integers less than $n$ that are coprime to $n$. Thus, for example, ...
2
votes
1answer
79 views

A closed form for $\sum_{i\cdot j^k=n}(-1)^i$?

$$\alpha_k(n) \stackrel{\text{def.}}{=} \sum_{i\cdot j^k=n}(-1)^i.$$ Does a closed form exist for $\alpha_k(n)$? For low values of $k$: $$\alpha_0(n)=(-1)^n$$ $$\alpha_1(n)=\begin{cases} ...
2
votes
2answers
89 views

Is there a way to show that $d(n)$, which counts the number of divisors of $n$ is non-increasing? [closed]

Is there a way to show that $d(n)$, which counts the number of divisors of $n$ is non-increasing? I'm trying to use the Cauchy condensation test to show that $\sum_{n\ge{2}}\frac{d(n)}{n\log^2n}$ is ...
2
votes
1answer
178 views

Next asymptotic term of the average order of sigma

$$ \sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+O(n\log n). $$ Is the next asymptotic term known? That is, is there a monotonic increasing function $f(x)$ such that $$ ...
2
votes
1answer
26 views

Perfect numbers of the form $12m+1$ and $\sum_{d\mid n}\frac{1}{\phi(d)}$, where $\phi(m)$ is Euler's totient function

If there are no mistakes combining Exercise 9 a) (Chapter 3, page 71) and Exercise (Chapter2, page 47) of Apostol's Introduction to Analytic Number Theory we can prove easily Lemma. If $n$ is a ...
2
votes
1answer
47 views

What inequalities similar Lagarias' statement are easy to prove?

Let $$H_n=1+\frac{1}{2}+\cdots+\frac{1}{n},$$ the nth harmonic number and $$\sigma(n)=\sum_{d\mid n}d,$$ the sum of divisor function, for example $\sigma(6)=12$. I believe that this could be a nice ...
2
votes
1answer
34 views

On Abel summation $\sum_{e<n\leq x}\left(\mu(n)\cdot\int_2^n\frac{ds}{\log s}\right)$, where $\mu(n)$ is the Möbius function

By Abel's identity for $Li (x)=\int_2^x\frac{ds}{\log s}$, $a(n)=\mu(n)$ the Möbius function and $[y=e,x]$ (see Theorem 4.2, page 77 of [1]) and an application of Fundamental Calculus Theorem we ...
2
votes
1answer
71 views

Infinite sum of a function $g(n)=\sum_{d|n \; d\ne n}g(d)$

Let the function $g:\Bbb{N}\to\Bbb{N}$ be defined as $$g(n)=\sum_{d|n \; d\ne n}g(d)$$ with $g(1)=1$, how can we evaluate a sum like $$\sum_{i=0}^\infty{g(15^i)\over15^i} \tag1$$ Need we find a ...
2
votes
1answer
71 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 ...
2
votes
1answer
45 views

for which values of the pair of integers $(n,k)$ is $p(n,k) =1+\frac{2^{k}-1}n$ is prime?

let $p(n,k)= 1+\frac{2^{k}-1}{n}$ for a positive integer $n,k$ -for which values of the pair of integers $(n,k)$ : $p(n,k)$ is prime ? Any help is very welcom .Thank you
2
votes
4answers
87 views

How to show that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ [duplicate]

set $ n, n \in \mathbb{N}$ and prove that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ ¨I have tried this¨ If $n > 1$ then $n = p_{1}^{\alpha_{1}}\cdot p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ ...
2
votes
1answer
87 views

Sums involving square of Moebius function

I try to estimate the following sum: $$ \sum_{n \leq x}\mu(n)^2 f(n) $$ where $\mu(n)$ is a Moebius function and $f(n)$ is some multiplicative arithmetic function. If I understand it correctly it is ...
2
votes
1answer
47 views

Finding $m∈\mathbb N$ such that $d^n(m)$ is not a perfect square for any $n\geq1$

Let , for $k ∈\mathbb N$ , $d(k)$ denote the number of positive divisors of $k$ ; define $d^n (k)$ recursively as $d^1(k)=d(k)$ , for $n\geq1$ , $d^{n+1}(k)=d(d^n(k))$ , how do we find those ...
2
votes
1answer
93 views

how to prove $f$ is an arithmetic function with this property $\sum_{d\mid n} f(d)=n^2$

how to prove $f$ is an arithmetic function with this property $$\sum_{d\mid n} f(d)=n^2$$ Arithmetic function
2
votes
1answer
106 views

Solving $ f(\log x)$

A generalization of the conjecture $$\pi(x+x^{\theta}) - \pi(x) \sim \frac{x^\theta}{\log x} $$ (Ingham, 1937 or earlier) might be $$\Delta \pi_k = \pi_k((x+1)^2) - \pi_k(x^2)\sim \frac{x}{\log ...
2
votes
0answers
30 views

Any formulæ for products of consecutive cyclotomic polynomials?

I am interested in any information about coefficients of the polynomials $\Psi_n(x):=\prod_{k=1}^n\Phi_k(x)$, where $\Phi_k$ are the cyclotomic polynomials. I realize of course that this is a ...
2
votes
0answers
22 views

Characters appearing naturally in arithmetic functions

Let $r_2(n)$ denote the number of representations of $n$ as a sum of 2 squares. It is well-known that $$r_2(n) = 4\sum_{d \mid n} \chi(d),$$ where $\chi$ is the non-principal character modulo $4$. ...
2
votes
0answers
25 views

To calculate what is $\sum_{1 \le m<n ;(m,n)=1} m^2$ or what is the remainder when $\sum_{1 \le m<n ;(m,n)=1} m^2$ is divided by $n$? [duplicate]

For an integer $n >1$ , what is the sum of the squares of all the positive integers that are less than $n$ and relatively prime to $n$ that is I am trying to calculate $f(n):=\sum_{1 \le m<n ...