Questions tagged [arithmetic-functions]
An arithmetic function is one whose domain is the positive integers and whose range is a subset of the complex numbers. There are a number of important number-theoretic examples.
59 questions with no upvoted or accepted answers
30
votes
0
answers
794
views
Is it true that $\left\{\frac{\sigma(n)}{\varphi(n)}:\ n\in\mathbb{Z}_{\geq 1}\right\}=\{r\in\mathbb Q:\ r\ge1\}$?
For any positive integer $n$, let $\sigma(n)$ be the sum of all positive divisors of $n$.
Clearly, $\sigma(n)\ge n\ge \varphi(n)$ for all $n\in\mathbb{Z}_{\geq 1}$, where $\varphi$ is Euler's totient ...
- 15.6k
15
votes
1
answer
956
views
Is the sum $\sum_{d\mid n}\frac1{d+1}$ never integral?
Recall that a positive integer $n$ is a perfect number if and only if
$$\frac{\sigma(n)}n=\sum_{d\mid n}\frac1d=2.$$
QUESTION: Is my following conjecture true?
Conjecture. (i) We have $\sum_{d\mid ...
- 15.6k
13
votes
0
answers
406
views
Is this arithmetic function strictly positive and unbounded?
As requested by Mathphile, since there have been efforts but no complete solutions to some questions raised when this question was asked on MSE, and since we think that here the question is more ...
user153451
12
votes
0
answers
1k
views
Euler's totient function and Riemann hypothesis
I am looking for an upper-bound of the Euler's totient function $\varphi$ which would be equivalent to the Riemann hypothesis (RH). There is the following Nicolas' criterion about primorial numbers $...
11
votes
0
answers
238
views
Strong uniqueness of Euler's totient function
Let $f:\mathbb N\to \mathbb C$ be some arithmetical function. Define $\varphi_f(n)$ by the following formula:
$$
\varphi_f(n)=\sum_{\substack{k\leq n \\ (k,n)=1}}f(k).
$$
In other words, $\varphi_f(...
- 7,193
7
votes
0
answers
332
views
$n\varphi(n)\equiv 2\pmod{\sigma(n)}$ as a primality test
It is known from Subbarao, "On two congruences for primality" that $n>22$ is a prime iff $$n\sigma(n)\equiv 2\pmod{\varphi(n)},$$ where $\varphi(n)$ is Euler's function and $\sigma(n)$ is sum of ...
- 12.3k
6
votes
0
answers
506
views
Does the equation $\sigma(\sigma(x^2))=2x\sigma(x)$ have any odd solutions?
This question was posted in MSE in early August 2020. It did garner several upvotes, but did not receive any responses. I have therefore cross-posted it here, hoping that it gets answered.
Let $\...
6
votes
1
answer
2k
views
If $N = qn^2$ is an odd perfect number with $\gcd(q,n)=1$, is it possible to have $q + 1 = \sigma(n)$?
The title says it all.
Question
If $N = qn^2$ is an odd perfect number with Euler prime $q$ and $\gcd(q,n)=1$, is it possible to have $q + 1 = \sigma(n)$?
Heuristic
From the Descartes spoof, with ...
6
votes
0
answers
333
views
Linear combination of multiplicative functions
Carlitz showed necessary and sufficient conditions for an arithmetic function to be a linear combination of two multiplicative functions. He mentions the possibility of generalizing to $k$ ...
- 9,114
5
votes
0
answers
256
views
Are the numbers $\varphi(n^2)\sigma(n^2)\ (n=1,2,3,\ldots)$ pairwise distinct?
Let $\varphi$ be Euler's totient function, and let $\sigma(n)=\sum_{d\mid n}d$ for $n=1,2,3,\ldots$. Both $\varphi$ and $\sigma$ are multiplicative functions. It is easy to see that the numbers
$$\...
- 15.6k
5
votes
0
answers
229
views
Can we write each positive integer as $x^2+y^2+\varphi(z^2)$?
As odd squares are congruent to $1$ modulo $8$, any integer of the form $4^k(8m+7)$ with $k,m\in\mathbb N=\{0,1,2,\ldots\}$ cannot be written as the sum of three squares.
To avoid such congruence ...
- 15.6k
4
votes
0
answers
151
views
Identities to go from $\sum_{n\leq x} \mu(n) \log \frac{x}{n}$ to $M(x) = \sum_{n\leq x} \mu(n)$?
Let $\mu$ be the Möbius function. Say we have a bound on $\check{M}(x) = \sum_{n\leq x} \mu(n) \log \frac{x}{n}$ of the form $|\check{M}(x)|\leq \epsilon x$ for all $x\geq x_0$.
It is then easy to ...
- 20.2k
4
votes
0
answers
121
views
Do all nonnegative integers appear in A051521?
For every positive integer $n$, $\tau(n)$ is the number of divisors of $n$. If we list the ratio of each positive integer $n$ to $\tau(n)$，they form a rational sequence
1,1,3/2,4/3,5/2,3/2,…
Because $\...
- 321
4
votes
0
answers
86
views
On Carmichael function and aliquot parts of odd perfect numbers
I've asked nine months ago this question on Mathematics Stack Exchange with identifier 4430381 and same title. There is not answer for this question on Mathematics Stack Exchange, I wondered if this ...
4
votes
0
answers
232
views
On the density of a particular subset of integers
Given a positive integer $n$ in the standard form
$$n=\prod_k p_k^{\alpha_k}$$
and the arithmetic function (investigated by Erdős in this paper)
$$A(n)=\sum_k \alpha_k p_k$$
let's define the subset $E$...
- 1,008
4
votes
0
answers
81
views
Joint mean values of arithmetic functions in sequences and families of sequences
This is a bit of a follow up question to this question I asked a couple days ago. The main content of that post can be phrased as asking for a nontrivial lower bound on the sum
$$
\sum_{n\leq x} \...
- 2,000
4
votes
0
answers
465
views
The properties of Pos
Given $n\in\mathbb{N}$, and $f:\mathbb{N}^*\rightarrow \mathbb{N}$, let define $Pos$ as:
$$Pos(f)(n)= |\{x \leq n, f(x)=f(n)\}|$$
When given $n\in\mathbb{N}$, this function gives the 'position' of $...
4
votes
0
answers
275
views
A closed formula for this arithmetic function
The following function comes up in my research as part of a sufficient condition for capability of $p$-group of class two and prime exponent. Given a nonnegative integer $m$, express $m$ as a ...
- 7,217
4
votes
0
answers
413
views
Maximal order of Hooley's Delta function?
There is a large literature on Hooley's
$$
\Delta(n)=\max_u\sum_{d|n,\ e^u\le d< e^{u+1}}1
$$
giving its normal and average order. What is known of its maximal order?
Clearly $\Delta(n)\le d(n)$ ...
- 9,114
3
votes
0
answers
132
views
Is there a way to reduce this problem to two variables through functions coming from arithmetic?
Consider following diophantine equation in $\mathbb Z[x,y,z]$ in three integer variables $x,y,z$
$$x^2+L(y,z)x+L_1(y)L_2(z)=0$$ where $L(y,z)$ is a non-homogeneous linear polynomial in $y,z$ and $L_1(...
- 13.9k
3
votes
0
answers
238
views
Is there a closed form for the discrete convolution of $\sigma_1$ and $\sigma_2$?
I am trying to find a closed form for the following sum:
$$\sum_{k = 1}^{n-1}\sigma_1(k) \sigma_2(n-k)$$
where $\sigma_i$ is the sum of divisors and $\sigma_2$ is the sum of squares of divisors.
...
- 211
3
votes
0
answers
182
views
Mersenne number with small Carmichael function
Let $\lambda(\cdot)$ be the Carmichael function. I'm trying to understand the magnitude of the smallest values of $\lambda(2^n - 1)$, when $n$ runs over the positive integers. Precisely my question is:...
user40023
3
votes
0
answers
443
views
Infinite sums with Mobius Inversion : can we have uniform convergence of inversion formula?
My question is on Mobius inversion formula convergence/properties when used with infinite sums of function.
Lets consider (on $\mathbb{R}^{+}$):
$$S(x)= \sum\limits_{n=1}^{\infty} f(nx)$$
We call $...
- 1,199
2
votes
0
answers
836
views
Polynomials for the indicator function
The (one-variable) indicator function (or characteristic function) is defined as
$f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisfying that
$f_{t^*}(t)=1$ if $t=t^*$ and $f_{t^*}(t)=0$, otherwise. (Here $...
- 31
2
votes
0
answers
358
views
Mertens Bound and the Riemann Hypothesis
Let $M(x)$ denote the Mertens function ($M(x)=\sum_{i=1}^{x}\mu(i)$ where $\mu(i)$ is the Möbius function) and let $\Lambda(i)$ denote the Mangoldt function ($\Lambda(i)$ equals $\log(p)$ if $i=p^{m}$ ...
- 177
2
votes
0
answers
144
views
What is known about absolute convergence of Dirichlet inverses?
Given an arithmetic function $f$ such that the partial sums $\sum_{n \leq x} |f(n)|$ converge as $x$ approaches $\infty$, are there any results concerning the convergence properties of the series of ...
- 121
2
votes
0
answers
76
views
The number of elements with order less than $k$ in a larger cyclic group
I am working on a problem where it has become important to count (or at least bound from above and below) the number of elements of ${\bf Z}/n{\bf Z}$ that have order less than a given $k$, where $2\...
- 807
2
votes
0
answers
110
views
On variations of a claim due to Kaneko in terms of Lehmer means
This post is cross posted from Mathematics Stack Exchange, due that there was a mistake from my part (see the excellent partial answer and my thread of edits of my question on MSE) this post on ...
2
votes
0
answers
71
views
Write large $n$ as $n_1+\ldots+n_k\ (n_1<\ldots<n_k)$ with $\varphi(n_1),\ldots,\varphi(n_k)\in\{x^k:\ x\in\mathbb Z\}$
Let $\varphi$ denote Euler's totient function.
QUESTION. Is it true that for each positive integer $k$ large integers $n$ can be written as $n_1+\ldots+n_k$ with $n_1,\ldots,n_k$ distinct positive ...
- 15.6k
2
votes
0
answers
232
views
If some numbers satisfy this divisibility condition with $\sigma$ and $\varphi$, are they necessarily multiples of $6$?
After doing some computations of the divisibility of $\sigma(n)$ by $n+ \varphi(n)$, mostly with Peter´s help, we found these solutions:
$n=2, 456, 828, 7584 ,33462 , 1357440, 1596048 ,1964544 ,...
user153451
2
votes
0
answers
117
views
Alternating series of arithmetic function values
Some time ago I asked about alternating sums like
$\sum_{n\leq x}(-1)^n \phi(n)$ where $\phi(n)$ is Euler's totient
and the similar sum involving $\sigma(n)$ where $\sigma(n)=\sum_{d|n}d.$
Certain ...
- 112
2
votes
0
answers
100
views
$\varphi(m+n)\mid n$ for some positive integer $n$
Let $\varphi$ be Euler's totient function.
If $p$ is a prime, then $\varphi(1+n)=n$ for $n=p-1$.
Question. Is it true that for each integer $m>1$ there is a positive integer $n\le m^2-m$ such that ...
- 15.6k
2
votes
0
answers
98
views
Discrete "difference" equations that involve changes in both shift and scale
A standard use of the Z-transform ($F(z) = \sum_n (f[n] \cdot z^{-n} )$) is to understand the effect of a difference equation on a signal. For instance:
$y[n] = x[n] + y[n-1]$
$Y(z) = X(z) + Y(z) \...
- 4,907
2
votes
1
answer
349
views
Is there a smallest $r$ such that $n+\varphi(n)=\displaystyle \prod_{i=1}^r q_i$ always has solutions for mutually different odd primes $q_i $?
While discussing with Peter in one of the chatrooms on MSE I proposed an idea to try to find smallest natural number $r$ such that $n+\varphi(n)=\displaystyle \prod_{i=1}^r q_i$ has solutions for ...
user153451
1
vote
0
answers
125
views
Where have you encountered the following arithmetic function?
The following arithmetic function is studied by Zagier in connection with values at odd negative integers of zeta functions of real quadratic fields:
$$e_r (n)=\sum_{\underset{|x|\leq n}{x^{2}\equiv n\...
- 347
1
vote
0
answers
165
views
Relationship between two types of partition functions
Referring to this unanswered question on MS, I'm posting the same question here:
For $s\in \mathbb{C},\Re(s)>1 $, consider:
$$\prod_{k=1}^{\infty}\prod_{n=2}^{\infty}\frac{1}{1-n^{-ks}}= \prod_{k=1}...
- 181
1
vote
0
answers
168
views
On two formulas involving the $k$-fold divisor function $d_k$ and the function $r_k$
I have a puzzle which needs some help form the experts here. Let $d(n)$ be the divisor function, and $d_k(n)$ the $k$-fold divisor function.
I) It is known that, for any positive integer $h$,
$$d(n+h)...
- 563
1
vote
0
answers
153
views
A definition related to pseudoprimes and the Dedekind psi function
In this post we consider that $\psi(k)$ denotes the Dedekind psi function. Wikipedia has an artcle dedicated to this arithmetic function Dedekind psi function defined for a positive integers $m>1$ ...
1
vote
0
answers
174
views
Is $T(n)=\sum_{k=1}^{n}\frac{\lambda(k)\Lambda(k)}{k} \geq 0$ and what is the upper bound of $T(x)=\sum_{n\leq x} \lambda(n)\Lambda(n) $?
Let $\Lambda(n)$ denote the von Mangoldt function: $\Lambda(n)=\log p$ when $n=p^e$ is a prime power ($e\ge 1$) and $\Lambda(n)=0$ otherwise.
and $\lambda(n)$ be Liouville Function, , I'm interested ...
1
vote
0
answers
73
views
On a type of equations that involve certain multiplicative functions and polynomials, in relation to their number of solutions
Past weekend I was interested in the sequence A058891 from the On-Line Encyclopedia of Integer Sequences, from this, inspired by the equation due to Benoit Cloitre (2002) that shows the comments, I ...
1
vote
0
answers
233
views
Primes approximated by eigenvalues?
Let the matrix $T$ be defined by:
$$\displaystyle T(n,k) = -\varphi^{-1}(\operatorname{GCD}(n,k))$$
where $\varphi^{-1}$ is the Dirichlet inverse of the Euler totient function.
$$\varphi^{-1}(n) = \...
- 1,183
1
vote
0
answers
93
views
Existence of equation about the product of the divisor sum function
Let $\sigma_k(n)$ be the sum of the $k$-th powers of the positive divisors of $n$ and $\mu(n)$ be the Möbius function.
As Arithmetic function - Wikipedia mentioned, there is an equation that $$\...
- 123
1
vote
0
answers
90
views
An arithmetic function involving arbitrary (but fixed) number of divisors
I need at least basic information about generating functions of the following class of arithmetic functions, grouped by levels $k$.
Fix some $k$ and some family $\varepsilon_*=(\varepsilon_\sigma)_{\...
- 18.4k
1
vote
0
answers
256
views
On even almost perfect numbers other than powers of two
(Note: This question is an improved version of and has been cross-posted from this MSE post.)
Let $\sigma(x)$ denote the sum of the divisors of $x$. If $\sigma(x) = 2x - 1$, then we call $x$ an ...
1
vote
0
answers
80
views
All all hypo-multiplicative functions linear combinations of quasi-multiplicative functions?
A function is called quasi-multiplicative by many authors if $f(m)f(n)=f(1)f(mn)$, a slight generalization of multiplicativity. (Basically a multiplicative function times a constant is a quasi-...
- 9,114
0
votes
0
answers
193
views
Possible implications of the bound $\sum_{n\leq x}\sum_{m_{1}+m_{2}=n}\lambda\left(m_{1}\right)\lambda\left(m_{2}\right)=O\left(x\right)$
Let $\lambda(n)$ be the Liouville function and consider the Goldbach-type problem $\sum_{m_{1}+m_{2}=n}\lambda\left(m_{1}\right)\lambda\left(m_{2}\right)$. Assume the Riemann hypothesis, the ...
- 1
0
votes
0
answers
68
views
Around similar inequalities than an inequality due to Nicolas, that involve products of consecutive Ramanujan primes
This is cross-posted (and this post is a version to ask just around the veracity of Conjecture 1) as the post with identifier 3594907 and same title), that I've edited on Mathematics Stack Exchange ...
0
votes
0
answers
89
views
A similar inequality for the Dedekind psi function, than an inequality stated by Schinzel
I would like to ask about the next question that seems to me interesting. I know an article that was written by Andrzej Schinzel in which he stated Lemma 2. In this post we denote the Dedekind psi ...
0
votes
0
answers
37
views
Number of different factorizations
I define $\nu(n)$ the number of different factorizations for an integer $n$. I know there are papers about $\delta(n)$ the number of dividers for an integer $n$ (Landau, Euler, Dirichlet) but I still ...
- 111
0
votes
0
answers
132
views
How to estimate sums over arithmetic progressions?
For $x>1$
$$
N(x)=\sum_{0<n<x \\n \equiv 1 \pmod 4\\ n\text{ squarefree}} 1
$$
How to estimate $N(x)$'s order? (Like $N(x) \sim Ax$)
Furthermore, for $n=p_1p_2\cdots p_v$, define $\alpha (n)=...
- 1