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.
131 questions
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
20
votes
3
answers
913
views
Extending arithmetic functions to groups
Thinking along the lines of Tom Leinster's fascinating recent question, I'm wondering more generally about how to extend questions about natural numbers to groups, with the cyclic groups representing ...
- 6,792
19
votes
3
answers
4k
views
Generalized Euler phi function
Let $n$ be an integer, there is a well-known formula for $\varphi(n)$ where $\varphi$ is the Euler phi function. Essentially, $\varphi(n)$ gives the number of invertible elements in $\mathbb{Z}/n\...
- 337
18
votes
1
answer
593
views
For which $n$ is $\sum_{k=1}^n 1 / \varphi(k)$ an integer?
For which positive integers $n$ is the sum $\sum_{k=1}^n 1 / \varphi(k)$ an integer? Here $\varphi$ is the Euler totient function.
The question is a "totient-analog" of the well-known result ...
- 453
17
votes
2
answers
1k
views
Does 53 diverge to infinity in this Collatz-like sequence?
This function has been explored a bit at MSE (in June 2016):
\begin{eqnarray}
f(n) &=& (n-1)^2 \; \textrm{if} \; (n \bmod 4) = 1\\
f(n) &=& \lfloor n/4 \rfloor \; \textrm{otherwise}
\...
- 151k
15
votes
2
answers
1k
views
Sum of $\sum_{k=1}^nd(k^2)$
There is a literature dealing with
$$
\sum_{k\le x}d(f(k))
$$
where $f$ is an irreducible polynomial and $d(n)$ is the number of divisors of $n$. Erdos 1952 shows that the sum $\asymp x\log x,$ which ...
- 9,114
15
votes
4
answers
2k
views
Square roots and prime numbers
Definitions:
Here I present a novel conjecture using basic mathematical tools like the sum of the
divisors of an integer $n$ called $\sigma(n)$, the sum of the squares of the positive divisors of n ...
- 127
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
2
answers
1k
views
A mystery sequence
This question arose from the recent one, roots of a polynomial linked to mock theta function?. Let
$$
g(x):=\sum_{k=0}^\infty x^k\prod_{j=1}^{k-1}(1 + x^j)^2\\=1+x+x^2+3 x^3+4 x^4+6 x^5+10 x^6+15 x^7+...
- 18.4k
13
votes
1
answer
934
views
Is the set of multiplicatively even numbers thick?
A positive integer is multiplicatively even (odd) if, when decomposed into primes, the sum of the exponents is even (odd).
A subset of the integers is thick if it contains arbitrarily long intervals $\...
- 1,701
13
votes
2
answers
968
views
Have any proposals been advanced for the analytic continuation of the divisor function?
While I was working on the evaluation of a certain series, the following limit came up:
\begin{align} \lim_{n \to 1} \frac{d(n)-1}{n(n-1)} &= \lim_{n \to 1} \frac{d'(n)}{2n-1} \\
&= d'(1) .\...
- 4,829
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
2
answers
1k
views
A question on Euler's totient function
With reference to the Euler's totient function $\phi(\cdot)$, given any $n \in \mathbb{Z}^+$, it's quite straightforward to find $\phi(n)$.
In contrast, given $n \in \mathbb{Z}^+$, even though there ...
- 211
11
votes
3
answers
703
views
Evaluating the sum of $kl^2$ over $p,q,k,l$ such that $pk +ql = n$
I have come across the following sum:
$$\sum_{\substack{p, q, k, l \in \mathbb{N} \\ k > l \\ pk + ql = n}}kl^2$$
and I am trying to simplify it, hoping to get a nice formula in terms of $n$ and ...
- 211
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
9
votes
4
answers
4k
views
Averages of Euler-phi function and similar
What are the odds two numbers are relatively prime? This is known to be $\frac{6}{\pi^2}$. The proof involves calculating averages of the Euler phi function.
\[ \phi(1) + \phi(2) + \dotsb + \phi(n) \...
- 22.8k
9
votes
2
answers
740
views
Asymptotics of product of Euler's totient function (A001088)?
Conjecture:
\begin{align}
\lim_{n\to \infty } \, \frac{\left(\prod _{k=1}^n \phi (k)\right){}^{1/n}}{n}\sim 0.2059\text{...}
\end{align}
The numerical result from 100000 terms is:
My questions are:
...
- 690
8
votes
1
answer
328
views
On the density map of the abundancy index
Let $σ$ be the sum-of-divisors function. Let $σ(n)/n$ be the abundancy index of $n$. Consider the density map $$f(x) = \lim_{N \to \infty} f_N(x) \ \ \text{ with } \ \ f_N(x) = \frac{1}{N} \#\{ 1 \...
8
votes
1
answer
659
views
The importance of relations between automorphic forms and arithmetic functions
As I understand things, one of the classical reasons to care about modular forms was their relation to interesting arithmetic functions/counting questions, i.e. on sums of squares and partitions. When ...
- 164
8
votes
1
answer
205
views
Are there infinite numbers of the form $\sigma_1(n)=\sigma_1(m)=p$, or is there only one?
I put forward a hypothesis in number theory, it is as follows.$ \sigma_1(n)=\sigma_1(m)=p$, where $\sigma_1$ is the divisor sum function, $n,m\in \mathbb N$, and $p$ is prime. I recently noticed and ...
- 125
8
votes
1
answer
427
views
Goldbach's conjecture for the Liouville function
Is it true that for every even integer $N > 2$, there exist positive integers $a,b$ such that $a + b = N$ and $\lambda(a) = \lambda(b) = -1$ ?
Here $\lambda$ is the Liouville function.
- 11.3k
7
votes
3
answers
695
views
The digit sum: $s(na)=s(nb)$
Not that I was serious about the following question, but I think it is a must-to-ask as a follow-up to this MO post.
For integer $n\ge0$, let $s(n)$ denote the sum of the digits in the decimal ...
- 23k
7
votes
2
answers
447
views
Prove that two functions are equal only when $s \equiv \pm r^{\pm 1} \pmod{q}$
Let us fix a positive integer $q$, and let us define a functions $P: \mathbb{Z}\times \mathbb{N} \to \mathbb{Z}$ as follows:
$$ P(s,t) := \sum_{j=1}^t \left\lfloor \frac{j (s-1) + t}{q} \right\rfloor$$...
- 1,889
7
votes
1
answer
365
views
How to explain this property of totient?
I am running a program to search for solutions of $$\varphi(pm+1)=\varphi(pm+p+1).$$
So far, for $m=1,\ldots,327$ solutions have been found (some relatively large).
(in the body of the question, $p$ ...
user153451
7
votes
1
answer
1k
views
Menon’s identity
I also put this question in stackexchange, but remained unanswered. https://math.stackexchange.com/questions/506996/menons-identity
Let $G$ be a group of order $n$. Consider an action of $U_n$, the ...
- 801
7
votes
1
answer
743
views
Generalization of a problem, involving radicals and the floor function, proposed by Ramanujan to the Journal of the Indian Mathematical Society
The section Solved problems from the Wikipedia Floor and ceiling functions shows several problems proposed by Ramanujan ([1]). The purpose of this post, if possible, is try to get the generalization ...
7
votes
1
answer
421
views
On $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$
Euler's totient function $\varphi$ is multiplicative, and it plays important roles in number theory.
QUESTION: Is it true that for each integer $m>6$ we have $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$...
- 15.6k
7
votes
1
answer
231
views
The asymptotic of $|\{1\leq n\leq x|\gcd(n,S(n))=1\}|$, with $S(n)$ the sum of remainders, and get idea for other miscellany problem
Let $n\geq 1$ be an integer. In this post we denote the sum of remainders function as $$S(n)=\sum_{k=1}^n n \bmod k,$$ for example $S(1)=S(2)=0+0$ and $S(5)=0+1+2+1+0=4$. In the literature there are ...
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
2
answers
2k
views
Does this multiplicative function have a name? If so, what is known about it?
It is well-known that the Euler $\phi$-function is multiplicative: that is, for co-prime positive integers $m,n$ we have $\phi(mn) = \phi(m)\phi(n)$. Thus it is defined by its values on prime powers. ...
- 26.9k
6
votes
1
answer
331
views
A question about $(0,1]$-valued multiplicative functions
Suppose $f:\mathbb{N}\to [0,1]$ is a multiplicative function (i.e. $f(nm)=f(n)f(m)$ whenever $m$ and $n$ are coprime). Suppose $f$ has non-zero mean, which means
$$
\lim_{N\to\infty}\frac{1}{N} \sum_{...
- 63
6
votes
1
answer
392
views
Arithmetic properties of positively reduced $2\times 2$-matrices
Call a $2\times 2$ matrix with coefficients in $\{0,1,2,3,\ldots\}$
positively reduced if any row or column reduction (given by replacing a row/column by itself minus the other row/column) produces
at ...
- 17.9k
6
votes
1
answer
213
views
Upper bound on minimum number of prime factors in short intervals
Suppose that $H = H(X)$ is some quantity growing with $X$. Are there any bounds on $$F(X, H) = \min_{X < n\le X + H} \omega(n)?$$
It isn't hard to obtain a lower bound $\max_{x\sim X} F(X, H)\gg \...
- 1,890
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
4
answers
2k
views
Good books on arithmetic functions?
As I was studying the Möbius $\mu$ function and Gram series,
I got myself some pretty nice books:
Ribenboim - The New Book of Prime Number Records
Apostol - Introduction to Analytic Number Theory
...
- 731
5
votes
3
answers
843
views
Is the number of solutions of $\phi(x)=n!$ bounded? If yes, what is its bound?
Pillai showed in 1929 that the function $A(n)$ giving the number solutions of the equation $\phi(x)=n$ is unbounded in (S. Pillai, On some functions connected with $\varphi(n)$, Bull. Amer. Math. Soc. ...
5
votes
2
answers
314
views
Congruences for the non-divisors of Euler's $\phi(n)$
If $n$ is composite, then $\phi(n) < n-1$: hence, there is at least one number $d$ which does not divide $\phi(n)$ but divides$(n-1)$. We shall call $d$ the totient divisor of $n$. The purist will ...
- 5,470
5
votes
1
answer
392
views
Does anyone recognize this exponential sum?
For $a$, $b$ two integers, let $(a,b)$ denotes their gcd. We define the following exponential sum :
$$G_q(n):=\sum_{d|q,~(d,q/d)=1}{e^{2i\pi n\frac{dd'}{q}}}$$
for $n$ a non-negative integer and $q$ ...
- 1,479
5
votes
2
answers
556
views
Are there multiplicative functions which are not rational?
Vaidyanathaswamy calls an arithmetic function rational if it is the convolution of some finite collection of functions which are either completely multiplicative or inverse to a completely ...
- 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
5
votes
1
answer
180
views
Uniformity in Wirsing's Mean Value Theorems
In two important papers of Wirsing, namely "Das asymptotische Verhalten von Summen über multiplikative Funktionen" (1961) and its follow up (1967), several results on mean values of multiplicative ...
- 14.7k
4
votes
1
answer
558
views
A curious conjecture: $\{\varphi(m^2)/\varphi(n^2):\ m,n=1,2,3,\ldots\}=\{r>0:\ r\in\mathbb Q\}$
Let $\varphi$ denote Euler's totient function. It is easy to see that all those numbers
$$\varphi(n^2)=n\varphi(n)\ \ (n=1,2,3,\ldots)$$
are pairwise distinct.
I have the following surprising ...
- 15.6k
4
votes
1
answer
170
views
The number of solutions of the equation $ax_1x_2+by_1y_2=n$
The equation $x_1x_2+y_1y_2=n$ is well-studied (Ingham, Heath-Brown, Deshouillers & Iwaniec, Ismoilov) because it arises in an additive divisor problem. The number of solutions in positive ...
- 12.3k
4
votes
1
answer
175
views
Behavior of $m(x)\sqrt{x}$ where $m(x)=\sum_{n\leq x}\frac{\mu(n)}{n}$
Let $M(x) = \sum_{n\leq x} \mu(n)$ and $m(x) = \sum_{n\leq x} \frac{\mu(n)}{n}$, where $\mu(n)$ is the Möbius function.
We know that (it is not the best known bounds):
$$\limsup_{x \to \infty} M(x)x^{-...
- 611
4
votes
1
answer
291
views
Generalization of the The Liouville Lambda function
Let $n=p^{\alpha_1}_1 \cdots p^{\alpha_m}_m,$ and define
$$\lambda_k(n)= (-1)^{ [\frac{\Omega(n)}{k} ]},$$
where $\Omega(n)= \alpha_1 + \cdots + \alpha_k,$ and $[\cdot]$ is the floor function.
For $...
- 499
4
votes
1
answer
530
views
Reference for inequality for $\sum\limits_{d \mid n}\frac{\log d}{d}.$
Let $f(n)=\sum\limits_{d \mid n}\frac{\log d}{d}.$
It is not hard to see that $f(n)\ll(\log\log n)^2$. Is there any reference for this inequality?
EDT 1: A possible answer is Analysis of the ...
- 12.3k