Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [arithmetic-functions]

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

0
votes
0answers
12 views

Simplifying expression Mobius Function

Can anybody help me simplify this expression using Mobius Inversion Formula or any other result in order to calculate F(3500) in a simple way?? $$F(n)=\sum_{d\mid n} \mu(d)d$$
1
vote
1answer
26 views

Determine a property of $S_b(n)$, which is the sum of the digits of $n$ when $n$ is expressed in base $b$

The original question Let $S_b(n)$ be the sum of the digits of $n$ when $n$ is expressed in base $b$. was asked by Anson Chan on Jan. 24, 2019. Since it was deemed to not have enough context, it was ...
3
votes
0answers
59 views

On the proof that $\phi(n)/n$ has a limit law

In this question, $\mathbb{N}$ denotes the set of positive integers. Also, $\overline{\mathrm{d}}$, and $\mathrm{d}$ means upper natural density, and natural densitiy respectively. (They are the ...
2
votes
1answer
39 views

$\sum_{d|n, d>0} (\sigma(d)/d)\mu(n/d))=1/n$

We want to show \begin{align} \sum_{d|n,\ d>0}(\sigma(d)/d)\cdot \mu(n/d) =1/n , \end{align} where $\sigma(m)$ denotes the sum of all positive divisors of $m$ and where $\mu$ is the Möbius ...
0
votes
2answers
41 views

Another sum involving totient function or gcd

Motivated by this question, My question pertains to closed form of the sum $$\sum_{d|n}\frac{\phi(d)}{d}$$ There are some formulae and expressions for $\sum_{n}\frac{\phi(n)}{n}$, but what about when ...
1
vote
2answers
50 views

Breaking the barriers at $q=5$ and $q=13$ for $q^k n^2$ an odd perfect number with special prime $q$

Let $\sigma(x)$ be the sum of divisors of the positive integer $x$. If $\sigma(N)=2N$ and $N$ is odd, then $N$ is called an odd perfect number. The question of existence of odd perfect numbers is the ...
1
vote
1answer
41 views

Let a be an multiplicative arithmetic function. Show: either $a(1) = 1$ or $a(1) = 0$. Show that if $a(1) = 0$ then $a(n) = 0$ for all $n$

I am asked to prove Let a be an arithmetic function which is multiplicative. Show that either $a(1) = 1$ or $a(1) = 0$. Show that if $a(1) = 0$ then $a(n) = 0$ for all n. From definition of ...
1
vote
0answers
18 views

Estimating of Big Omega function

Let $\Omega$ be prime big omega function. (Here is description-https://en.wikipedia.org/wiki/Prime_omega_function). Also let $n$ is composite number. Find as good as you can upper bound of number $...
0
votes
0answers
17 views

Finding arithmetic form of XOR function for 2+ bit numbers

There are many different ways to express Exclusive-OR function for 1-bit values (0 or 1). For example: $$ a \oplus b = \left\lvert a - b \right\rvert \tag{1} $$ or $$ a \oplus b = (a + b) \bmod 2 \...
3
votes
2answers
59 views

If $\sigma(n)/n = 5/3$, then $5 \nmid n$. Does it also follow that $3 \nmid \sigma(n)$?

Let $\sigma(x)$ denote the sum of divisors of the positive integer $x$. Denote the abundancy index of $x$ by $I(x)=\sigma(x)/x$. If $\sigma(N)=2N$ (equivalently, when $I(N)=2$) then $N$ is called a ...
0
votes
1answer
45 views

Probability of $f(n) - \varphi(n)$ to be an even number.

Let $f(n)$ denotes the product of all the positive divisors of n, and $\varphi(n)$ denotes the sum of all the positive divisors of $n$. If number $n$ is to be randomly selected from the first $100$ ...
0
votes
2answers
23 views

If $\sigma(n) = 2n - d$ and $d \mid n$, is it true that $d = \gcd(n,\sigma(n))$?

In what follows, assume that $d > 0$. Let $$\sigma(x)=\sum_{e \mid x}{e}$$ denote the classical sum-of-divisors function, and denote the deficiency of $x \in \mathbb{N}$ by $$D(x)=2x-\sigma(x).$$ ...
1
vote
0answers
39 views

How to simplify $2 q^{\frac{k-1}{2}} n^2 - \sigma(q^{\frac{k-1}{2}})\sigma(n^2)$

Let $k$ be a positive integer satisfying $k \equiv 1 \pmod 4$. Let $x \in \mathbb{N}$. Let $q$ be a prime number. If $$\sigma(x) = \sum_{d \mid x}{d}$$ is the classical sum-of-divisors function, ...
2
votes
0answers
59 views

On Basak's “Bounds On Factors Of Odd Perfect Numbers”

Let $N = q^k n^2$ be an odd perfect number given in Eulerian form, i.e. $q$ is the special/Euler prime satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$. In what follows, we denote the ...
1
vote
1answer
48 views

If $q \equiv k \equiv 1 \pmod 4$, is it necessarily true that $\gcd\bigg(\sigma(q^k),\sigma(q^{(k-1)/2})\bigg)=1$?

Let $\sigma$ denote the classical sum-of-divisors function. In what follows, we let $q$ be a prime number. Here is my question: If $q \equiv k \equiv 1 \pmod 4$, is it necessarily true that $\gcd\...
9
votes
1answer
99 views

On $\sup|\varphi^{-1}(n)|=+\infty$

I am trying to find an elementary proof of the following fact: Given some $N\geq 2$, there are $N$ distinct integers $a_1,\ldots,a_N$ such that $\varphi(a_1)=\ldots=\varphi(a_N)$ with $\varphi$ ...
1
vote
2answers
141 views

On Yanqi Xu's 2016 joint undergraduate math research project with Dr. Judy Holdener at Kenyon College

In what follows, we let $\sigma(X)$ denote the sum of the divisors of the positive integer $X$. Denote the abundancy index of $X$ by $I(X)=\sigma(X)/X$, and the deficiency of $X$ by $D(X)=2X-\sigma(X)...
3
votes
2answers
61 views

About The Sum of Positive Divisors of $n$

The question says: Find the smallest positive integer $n$ so that $\sigma(x)=n$ has no solution, exactly two solutions, exactly three solutions. I could not come up with a good way to solve this ...
2
votes
1answer
50 views

What proportion of the positive integers satisfies $\gcd(n^2,\sigma(n^2))>\sigma(n)$, where $\sigma$ is the sum-of-divisors function?

The title says it all. What proportion of the positive integers satisfies $\gcd(n^2,\sigma(n^2))>\sigma(n)$, where $\sigma$ is the sum-of-divisors function? I tried using Sage Cell Server to ...
3
votes
2answers
117 views

A proof of $\sum\limits_{d|n} \sigma(d) = n \sum\limits_{d|n} {\tau(d) \over d}$

I'm trying to proof the following statement: Let $n \in \mathbb{Z}$ and the $\sum$ are on the divisors $d$ of $n$. Show that $$\sum\limits_{d|n} \sigma(d) = n \sum\limits_{d|n} {\tau(d) \over d}.$$ ...
0
votes
1answer
50 views

A question regarding a paper of Ochem and Rao about the radical of an odd perfect number

Let $\operatorname{rad}(n)$ denote the radical or square-free part of the positive integer $n$, that is, $$\operatorname{rad}(n) = \prod_{p \mid n}{p}$$ where $p$ runs over primes. In the paper ...
1
vote
2answers
67 views

How to prove $\sum_{d\mid q}\frac{\mu(d)\log d}{d}=-\frac{\phi(q)}{q}\sum_{p\mid q}\frac{\log p}{p-1}$?

Prove that $$\sum_{d\mid q}\frac{\mu(d)\log d}{d}=-\frac{\phi(q)}{q}\sum_{p\mid q}\frac{\log p}{p-1},$$ where $\mu$ is Möbius function, $\phi$ is Euler's totient function, and $q$ is a positive ...
0
votes
0answers
27 views

Möbius inversion across all natural numbers (no divisors)

EDITED TO ACCOMMODATE COMMENTS: I'm trying (self-taught) to understand more about Möbius inversion. Take two arithmetic functions $f$ and $g$ defined by $$g(n)=\sum_{d|n}f(d)$$ (Presumably $d$ ...
0
votes
1answer
78 views

On the quantity $\sigma(\frac{n^2 \sigma(n^2)}{D(n^2)})$ when $q n^2$ is an odd perfect number with special prime $q$

Denote the sum of the divisors of $x \in \mathbb{N}$ by $\sigma(x)$. Also, denote the deficiency of $x$ by $D(x)=2x-\sigma(x)$. If $m$ is odd and $\sigma(m)=2m$, then $m$ is called an odd perfect ...
4
votes
1answer
99 views

If $x$ and $y$ are solitary numbers satisfying $\gcd(x,y)=1$, under what conditions does it follow that $xy$ is also solitary?

Let $\sigma(z)$ denote the sum of divisors of $z \in \mathbb{N}$. Denote the abundancy index of $z$ by $I(z) = \sigma(z)/z$. If the equation $I(z)=I(a)$ has the lone solution $z=a$, then $a$ is said ...
0
votes
0answers
53 views

Sum of a multiplicative arithmetic function

Prime factorization of $n$ is $\prod p_i^{e_i}$ Then radical of $n$ is defined as $\text{rad}(n)=\prod p_i$ Let $S(N) = \sum_{n=1}^{N}\text{rad}(n)$ I want to calculate $S(N)$ for very large value ...
3
votes
0answers
84 views

Could a Fermat prime divide an odd perfect number?

This question is a follow-up to this earlier post. A positive integer $N$ is said to be perfect if $\sigma(N)=2N$, where $\sigma(x)$ is the sum of divisors of $x \in \mathbb{N}$. If $M$ is odd and $\...
1
vote
0answers
81 views

Does mathlove's answer imply that $D(n^2) \mid n^2$?

In what follows, set $\sigma(x)$ to be the sum of divisors of $x \in \mathbb{N}$, and let $$D(x) = 2x - \sigma(x)$$ be the deficiency of $x$, and let $$s(x) = \sigma(x) - x$$ be the sum of the aliquot ...
2
votes
1answer
60 views

Von Mangoldt function with PARI GP

How to program the Von Mangoldt function: $$\Lambda (n)=\begin{cases}\log p&{\text{if }}n=p^{k}{\text{ for some prime }}p{\text{ and integer }}k\geq 1,\\0&{\text{otherwise.}}\end{cases}$$ ...
3
votes
1answer
106 views

What is the common (and simplified) value for $D(q^k)D(n^2) = 2s(q^k)s(n^2)$ when $q^k n^2$ is an odd perfect number?

In an answer to an earlier question, it is shown that $$D(2^p - 1)D(2^{p-1}) = 2s(2^p - 1)s(2^{p-1}) = 2^p - 2,$$ if $2^{p-1}(2^p - 1)$ is an even perfect number, $D(x) = 2x - \sigma(x)$ is the ...
1
vote
2answers
84 views

Is $(q^k n^2 \text{ is perfect }) \iff (D(q^k)D(n^2) = 2s(q^k)s(n^2))$ only true for odd perfect numbers $q^k n^2$?

(Preamble: This question is an offshoot of this earlier MSE post.) The title says it all. Is $\bigg(q^k n^2 \text{ is perfect }\bigg) \iff \bigg(D(q^k)D(n^2) = 2s(q^k)s(n^2)\bigg)$ only true for ...
0
votes
1answer
37 views

Can you explain the following property for arithmetic functions.

I have trouble understanding the following identity $$\prod_{d|2n} (x^d-1)^{\mu (2n/d)} = \prod_{d|n} (x^d-1)^{\mu (2n/d)} \prod_{d|n} (x^{2d}-1)^{\mu ((2n/d)/2)}$$, $\mu (n)$ is the Mobius function. ...
2
votes
0answers
53 views

Are there any other squares $n^2$ for which $\gcd(n^2, \sigma(n^2)) = 2n^2 - \sigma(n^2)$?

Let $\sigma(x)$ denote the sum of the divisors of the positive integer $x$. Denote the deficiency of $x$ by $$D(x)=2x-\sigma(x).$$ I am interested in solutions to the equation $$\gcd(n^2, \sigma(n^2)...
2
votes
1answer
76 views

Number of pairs $(a,b)$ such that $a+b<n$ and such that $\gcd(a,b,n)=1$

Let $n$ be a positive integer. What is the number of pairs $(a,b)$ of positive integers such that $a+b<n$ and such that $\gcd(a,b,n)=1$? I know that the number of positive integer $a$ such that $\...
1
vote
1answer
47 views

If an arithmetic function $f$ is such that $\sum\limits_{n=1}^Nf(n)=\Theta(N)$ then $f(n)=o(n^\epsilon)$

Consider a positive-valued, arithmetic function $f$ with $f(n)\geq 2$. Suppose that $f$ satisfies the inequality $$c_1N\leq\sum_{n=1}^Nf(n)\leq c_2N$$ where $0<c_1<c_2$ are real constants. ...
1
vote
0answers
43 views

Help proving an equality about arithmetic functions

So I have this equality to prove for any $n \in \mathbb{N}$: $$ \sum_{d|n} \sigma(d) \phi(\frac{n}{d}) = n \tau(n) $$ So I was able to show that left and right side are multiplicative. So how can I ...
4
votes
1answer
285 views

Is it possible to simplify this expression even further?

(Preamble: This question is tangentially related to this earlier one.) Let $\sigma(z)$ denote the sum of the divisors of $z \in \mathbb{N}$, the set of positive integers. Denote the deficiency of $...
9
votes
0answers
282 views

A conjecture regarding odd perfect numbers

(Note: This question has now been cross-posted to MO.) Let $\sigma(z)$ denote the sum of the divisors of $z \in \mathbb{N}$, the set of positive integers. Denote the deficiency of $z$ by $D(z):=2z-\...
-1
votes
3answers
62 views

Is there a lower bound for $\operatorname{rad}(n)$ in terms of $n \in \mathbb{N}$?

For integers $n\geq 1$ we denote the square-free kernel as $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p,$$ that is the product of distinct primes dividing an integer $n>1$ ...
0
votes
4answers
139 views

Do odd numbers $n$ satisfying $\gcd(n, \sigma(n)) > \sqrt{n}$ have a special form?

Let $\sigma(n)$ denote the sum of divisors of the positive integer $n$. Using Sage Cell Server, I was able to get the following odd numbers $n < 5000$ satisfying $\gcd(n, \sigma(n)) > \sqrt{n}$:...
3
votes
1answer
71 views

A bound for a sum over square-free numbers: $\sum_{n \leq X} \frac{\mu(n)^2 \tau_k(n)}{\phi(n)} \ll (\log X)^k$

How can one show that $$\sum_{n \leq X} \frac{\mu(n)^2 \tau_k(n)}{\phi(n)} \ll (\log X)^k \ ?$$ Here, $$\tau_k(n) = \sum_{\substack{d_1,d_2, \dots, d_k \in \mathbb{N} \\ d_1d_2\cdots d_k=n}} 1.$$ I'm ...
0
votes
0answers
34 views

Does $D(n)$ always depend on $\gcd(n,\sigma(n))$ when $\sigma(N)=aN+b$, $N=xn$, and $n$ is a square?

Does $D(n)$ always depend on $\gcd(n,\sigma(n))$ when $\sigma(N)=aN+b$, $N=xn$, and $n$ is a square (with $\gcd(x,n)=1$)? Here, $\sigma$ is the sum of divisors and $D(n) := 2n - \sigma(n)$ is the ...
1
vote
0answers
21 views

Deduce the number of divisors, $d(n)$ is multiplicative and obtain a formula of $d(n)$ in terms of prime decomposition [duplicate]

I have been given a question which begins with me deducing $d(n)$ is multiplicative, I know $d(n)= \sum_{d|n} 1,$ and obtain a formula of $d(n)$ in terms of prime decomposition (once again I know is $...
0
votes
0answers
16 views

Inverting arithmetic functions

I know that if $$F(n)=\sum_{d|n}f(d)$$ then $$f(p^e)=F(p^e)-F(p^{e-1})$$ Let $F(n)=\sum_{d|n}f(d)$ and assume $F(n)$ is multiplicative, so $F(1)=1$. Find the formula for $f(n)$ when $F(n)=1$ for all $...
0
votes
1answer
24 views

Inverse of a Multiplicative Arithmetic Function w/0 Mobius function

So I was given that if $$F(n)=\sum_{d|n}f(d)$$ then $$f(p^e)=F(p^e)-F(p^{e-1})$$ I'm trying to understand how to use this to actually solve specific problems. For example, let $F(n)=\sum_{d|n}f(d)$ ...
1
vote
2answers
71 views

If $f$ is an arithmetic function with $f(1)=1$ then $f$ is multiplicative

I'm studying analytic number theory for undergraduates and I read this theorem in Tom Apostol's book on the second chapter: Theorem 2.12. If $f$ is multiplicative then $f(1)=1$ And under need ...
0
votes
1answer
29 views

Is the average order of a product of arithmetic functions the product of the average orders?

If we have $$\sum_{n \leq x} f(n) \sim \sum_{n \leq x} g(n)$$ $$\sum_{n \leq x} h(n) \sim \sum_{n \leq x} k(n)$$ does it follow that $$\sum_{n \leq x} f(n)h(n) \sim \sum_{n \leq x} g(n)k(n)$$ In ...
7
votes
1answer
157 views

Is it true that $\underbrace{x^{x^{x^{.^{.^{.^x}}}}}}_{k\,\text{times}}\pmod9$ has period $18$ and can never take the values $3$ and $6$?

Is it true that the arithmetical function $f:\mathbb{N}\setminus\{1\}\rightarrow \mathbb{Z}_9$ given by $$f(x\mid k)=\underbrace{x^{x^{x^{.^{.^{.^x}}}}}}_{k\,\text{times}}\pmod9$$ has period $...
2
votes
0answers
30 views

Is feasible a simple inequality as a combination of the Firoozbakht's conjecture and the properties of the Ramanujan tau function?

I would like to know if is feasible a nice/potentially interesting combination of the Firoozbakht's conjecture, this Wikipedia, and the Ramanujan tau function using the so-called Ramanujan conjectures ...
0
votes
1answer
39 views

Multiplicative arithmetic function on the unit disk

Suppose $f$ is a multiplicative arithmetic function that takes values inside the unit disk, and let Re$(s)>1$. We define $F(s) = \sum_{n\ge1}^{}\dfrac{f(n)}{n^s}$. I want to show that $$\text{log } ...