Questions tagged [arithmetic-functions]
For questions on arithmetic functions, i.e. real or complex valued functions defined on the set of natural numbers.
625 questions
4
votes
1
answer
117
views
Finding a "Closed Form" Expression for $\sum_{d|n}\mu(n/d)\tau(d)$
I recently got this question on a homework, and after some initial experiments got the hypothesis that $\sum_{d|n}\mu(n/d)\tau(d)=1$. I did prove this, however along the way I also encountered a proof ...
- 79
5
votes
1
answer
71
views
Question on relationship between OEIS entries A020498 and A172407
OEIS entry A020498 is defined as "a(n) is the least number > a(n-1) such that a(1) through a(n) do not contain all residues modulo any prime".
OEIS entry A172407 is defined as "...
- 8,141
0
votes
0
answers
77
views
Proving $\sigma(n) > n + \sqrt{n}$
Question statement, From David Burton's Elementary Number Theory:
For any composite $n$, prove that $\sigma(n)>n+\sqrt{n}$
This question has been resolved here, but I wish to know if the ...
0
votes
0
answers
54
views
about an estimate concerning the Mobius function
I am studying about the zero density estimates of Dirichlet $L$-series, and in a related paper by O. Ramare, he proves the following explicit estimate: for $X \geq 10^{9}$, we have
\begin{equation}
\...
- 1
1
vote
0
answers
84
views
If $a>2b$ then $(a^2)!+b^2≠c^2$
Let $f$ be the arithmetic function $f(x)=\left|a-\frac{x!}{a}\right|$ where $a$ is the divisor of $x!$ which is the closest to $\sqrt{x!}$.
For example, $f(5)=2$ since the divisors of $5!=120$ are: ${...
- 11
1
vote
1
answer
47
views
Linear independence of Ramanujan sums
Let $r$ be a positive integer and define $c(n,r)=\sum_{d \mid (n,r)} \mu\left( \frac{r}{d} \right) d$ for all positive integer $n$ (Ramanujan sums). In the paper A class of Arithmetical Functons by ...
- 113
2
votes
0
answers
121
views
On $\prod_p\frac{p^3 - 2p + 1}{p^3}$
Is there a way to express the product
$$\prod_p\left(\frac{p^3 - 2p + 1}{p^3}\right),$$
where the product is taken over all primes $p$? This product came up in the study of the sum
$$\begin{align*}
\...
- 375
2
votes
1
answer
47
views
Maximal ideal in the ring of formal power series in finitely many variables
Let $k$ be a field, $m \in \mathbb{N}$ and let $\{p_1,p_2,\ldots\}$ be the set of prime numbers in order. Consider the rings $P=k[[x_1,\ldots,x_m]]$ of formal power series in $x_1,\ldots,x_m$ ...
- 113
3
votes
1
answer
209
views
Estimate for a sum over an index set involving divisors
In Iwaniec's paper "Fourier coefficients of modular forms of half-integral weight" (Invent. math. 87, 385-401 (1987)) I came across the following estimate (7.3), which he claims to be ...
- 65
1
vote
0
answers
63
views
Proving $\phi(n) \geq \frac{\sqrt{n}}{2}$ using Dirichlet series
There are already some posts regarding the proof of the following statement:
$$\forall n\geq 1, \phi(n) \geq \dfrac{\sqrt{n}}{2}$$
However, I was wondering if we could find another proof using ...
- 183
0
votes
1
answer
34
views
Calculating the interval of convergence of $G(s)$
Define the function $g: \mathbb{N} \to \mathbb{N}$ as
$$
\begin{equation}
g(n) =
\begin{cases}
1, & n=1\\
2, & n \text{ is composite or } n = 2\\
n, & n \text{ is prime ...
- 893
1
vote
0
answers
39
views
Injective Functions from $\mathbb{N}$ to Finite Subsets of $\mathbb{N}$ with Completely Multiplicative Cardinalities?
Let $\mathcal{F}$ be the set of finite subsets of $\mathbb{N}.$ Can we find all functions $f : \mathbb{N}\to \mathcal{F}$ satisfying following properties:
$f$ is injective
Cardinality of $f$ is ...
- 18.7k
0
votes
0
answers
103
views
When is $\varphi(n)$ one less than $\omega(n)$ [duplicate]
When is $$\varphi(n) = \omega(n)+1$$
for $$1<n<1000$$
where $\varphi(n)$ represents numbers not exceeding $n$ coprime to $n$, and $\omega(n)$ represents numbers not exceeding $n$ that do not ...
user1326973
0
votes
0
answers
33
views
Does the following GCD divisibility constraint imply that $\sigma(m^2)/p^k \mid m$, if $p^k m^2$ is an odd perfect number with special prime $p$?
The topic of odd perfect numbers likely needs no introduction.
In what follows, denote the classical sum of divisors of the positive integer $x$ by $$\sigma(x)=\sigma_1(x).$$
Let $p^k m^2$ be an odd ...
- 8,228
0
votes
0
answers
42
views
Improving $I(m^2)/I(m) < 2^{\log(13/12)/\log(13/9)}$ where $p^k m^2$ is an odd perfect number with special prime $p$
In what follows, let $I(x)=\sigma(x)/x$ denote the abundancy index of the positive integer $x$, where $\sigma(x)=\sigma_1(x)$ is the classical sum of divisors of $x$.
The following is an attempt to ...
- 8,228
4
votes
2
answers
117
views
Proof for formula of sum of factors of $n$
For a given composite number $n=a^pb^qc^r \cdots$. Now the number of factors it has are ${(p+1)(q+1)(r+1)...}$ and the sum of all its factors are ${(a^0+a^1+...+a^p)(b^0+b^1+...+b^q)(c^0+c^1+...+c^r).....
- 115
1
vote
1
answer
105
views
Applying convex multiplicative functions to Brocard's Problem
Brocard's problem asks if there are integer solutions to $n! = (x-1)(x+1)$ other than the cases of $n =$ $4$, $5$, $7$. Knowing the only shared divisor of the factors on the right is 2, would it be ...
- 43
0
votes
0
answers
49
views
Contiguous generalized hypergeometric functions modifying only denominator variables
The standard contiguous relations for the Gaussian Hypergeometric Functions
can be stacked/repeated to relate $_2F_1(a,b;c;z)$ in many ways
to sums of the formats $_2F_1(a\pm,b\pm ; c\pm ;z)$ , see e....
- 3,764
0
votes
0
answers
17
views
How may I show $\sum_{d \mid n} \frac{\mu(d)^2}{\phi(d)} = \frac{n}{\phi(n)}$? [duplicate]
I wish to show the identity
$$\sum_{d \mid n} \frac{\mu(d)^2}{\phi(d)} = \frac{n}{\phi(n)},$$
where $\mu$ is the Möbius function defined by
$$\mu(n) = \begin{cases}(-1)^k & \text{$n=p_1 \dots p_k$,...
- 3,990
0
votes
0
answers
23
views
How to reduce division with uprounding to integer-arithmetic operations with downrounding if the denominator is not necessarily an integer?
Let 𝑖∈ℕ₀ be an unknown variable and 𝑐∈ℚ₊ be a known constant such that 𝑐≥2 and 100𝑐 ∈ ℕ₊. (So we can pre-compute anything regarding 𝑐, e.g., represent 100𝑐 as a product of powers of primes.) We ...
- 101
2
votes
1
answer
69
views
Number of primitive Dirichlet characters of certain order and of bounded conductor
Writing $q(\chi)$ for the conductor of a Dirichlet character $\chi$, one can show using Mobius inversion that
$$\#\{\text{$\chi$ primitive Dirichlet characters}\,:\,q(\chi)\leq Q\}\sim cQ^2.$$
My ...
user1296122
2
votes
0
answers
35
views
Important Subgroups of Arithmetical Functions [closed]
I am taking a course in Analytic Number Theory. The main object of study is arithmetical functions. Moreover, if we look at the arithmetical functions which do not vanish at $1$, then they form a ...
- 259
0
votes
0
answers
60
views
How to make arithmetic function continuous?
Suppose that we have an arithmetic function $f(x)$ defined as follows:
What are the methods in the literature that will make this function continuous and differentiable? However, it should be noted ...
-1
votes
1
answer
152
views
Expressing Numbers Without Any Decimal Presumptions
I have long been uncomfortable with how numbers in alternative bases are expressed. Alternative bases are marketed as transcending our arbitrary base-$10$ conventions, but I wonder if they really ...
- 1,982
2
votes
1
answer
64
views
How to take derivative of an arithmetic function?
Arithmetic functions are defined from natural numbers to complex numbers. Therefore, they are not continuous in the analytic sense and consequently cannot be differentiated analytically. However, we ...
3
votes
2
answers
94
views
Book reference for studying Dirichlet Convolution
Now I am studying elementary number theory, I am interested in arithmetic function, I have studied Burton's Number Theory but I can't find Dirichlet Convolution as a particular topic, I will be highly ...
- 121
4
votes
0
answers
220
views
Relationship between two types of partition functions
After downvoting my previous thread, here is a more detailed explanation of my question. For $s\in \mathbb{C},\Re(s)>1 $, consider:
$$\prod_{k=1}^{\infty}\prod_{n=2}^{\infty}\frac{1}{1-n^{-ks}}= \...
1
vote
1
answer
71
views
$\sum_{k = 1}^{\infty} k\lfloor\frac{n}{k} \rfloor = 1 + \sum_{k = 1}^n \sigma_1(n)$
For any $f: \Bbb{N} \to \Bbb{Z}$ there exists a unique transformed function $F:\Bbb{N} \to \Bbb{Z}$ such that:
$$
f(n) = \sum_{k = 1}^{\infty}F_k\lfloor\frac{n}{k}\rfloor
$$
For example, set $F_1 = f(...
- 21.6k
2
votes
0
answers
231
views
Approximation of partial sum over prime omega function
The prime omega function $\omega(n)$ counts the number of distinct prime factors of a natural number $n$, and can be defined as $\omega(n)=\sum_{p \mid n}1$. Let $S(N)=\sum_{n=1}^{N}n\omega(n)$. Let $\...
- 547
1
vote
0
answers
38
views
Connection between multiplication table $n * k$ and partial sums of the partial sums of the Dirichlet inverse of the Euler totient function.
I am watching this video: L-functions and the Langlands program (RH Saga S1E2)
This reminds me of a recurrence:
Let $c=1$ and a recurrence be:
...
- 7,524
1
vote
2
answers
101
views
Verify if exists $n$ such that $\phi(n)$ equals $\frac{n}{d}$, for a constant $d$
Taking $n$ for $n=p_1^{a_1}...p_k^{a_k}$ (being $p_i$ prime numbers)and applying it to Euler's totient function, we would get $\phi(n) = p_1^{a_1-1}...p_k^{a_k-1}(p_1-1)...(p_k-1)$
If we take $d=2$, ...
- 23
1
vote
1
answer
85
views
How to get the Euler product for $\sum_{n = 1}^{\infty} \mu(n)/\phi(n^k)$.
Let $\mu$ be the Mobius function, and $\phi$ Euler's totient function. I am reading a proof found in this paper (Theorem 2 on page 17), and I can't quite figure why I'm getting something different ...
- 937
5
votes
1
answer
146
views
If an arithmetic function is multiplicative, non-zero at a prime, and "prime-linear", is it the identity?
Let $f:\mathbb{N}\to\mathbb{N}\cup\{0\}$ be a function. Let $f(1)=1,$ and $f(ab)=f(a)f(b)$ whenever $\gcd(a,b)=1.$ Note that I am assuming that $f$ is multiplicative but not completely multiplicative. ...
- 2,539
1
vote
1
answer
127
views
A problem on von Mangoldt function.
Suppose $n$ is odd natural number. Define $r(n)=\sum_{n_1+n_2+n_3=n} \Lambda(n_1)\Lambda(n_2)\Lambda(n_3)$ and
$r'(n)=\sum_{p_1+p_2+p_3=n}(\log p_1)(\log p_2)(\log p_3)$ where $p_1,p_2,p_3$ are ...
2
votes
2
answers
193
views
Does an odd perfect number have a divisor (other than $1$) which must necessarily be almost perfect?
Let $\sigma(x)=\sigma_1(x)$ be the classical sum of divisors of the positive integer $x$. Denote the aliquot sum of $x$ by $s(x)=\sigma(x)-x$ and the deficiency of $x$ by $d(x)=2x-\sigma(x)$. ...
- 8,228
12
votes
1
answer
914
views
Almost exact formula for sum of Euler Phi function $\sum_{k=1}^n \varphi(k)$
Solving a problem, I needed a formula for $\Phi(n)=\sum_{k=1}^n \varphi(k)$, where $\varphi(k)$ is Euler's notorious totient function, that counts the number of numbers between $1$ and $k$ that are ...
- 3,824
1
vote
0
answers
58
views
Pointwise Extension of Multiplicativity
A standard exercise in elementary number theory is to prove that if two multiplicative functions agree on the set of prime powers, then they are identical arithmetic functions.
Consider the following ...
- 17.3k
1
vote
0
answers
54
views
Is there an algorithm to solve number manipulation problems?
There are this kind of problems where, given a certain amount of the same numbers, it's needed to manipulate them with functions or operators in a way to get a certain result. It's allowed to glue ...
- 1,050
0
votes
0
answers
27
views
Arithmetic Progression/Sequence | Does it include terms prior to the initial term?
I’m trying to find the right term to describe points along a linear equation f(x) = mx + b, but where the domain is restricted to the set of integers. EDIT: Also the slope and y-intercept are integers....
1
vote
1
answer
122
views
Is this disproof for the Descartes-Frenicle-Sorli Conjecture that $k=1$, if $p^k m^2$ is an odd perfect number, valid?
Let $N = p^k m^2$ be an odd perfect number with special prime $p$ satisfying $p \equiv k \equiv 1 \pmod 4$ and $\gcd(p,m)=1$.
It is known that
$$D(p^k)D(m^2)=2s(p^k)s(m^2) \tag{0}$$
where $D(x)=2x-\...
- 8,228
4
votes
1
answer
72
views
Weird arithmetics with prime numbers...
Hello here is a problem with which I struggle quite a bit:
For any integer $n \geq 2$, with prime factor decomposition $n = p_1^{α_1}\times p_2^{α_2}\times ... p_k^{a_k}$, let $f(n) = α_1^{p_1}\times ...
- 107
1
vote
0
answers
55
views
Is the set of divisor indicator functions at $x^2 - 1$: $B' = \{(d \mid x^2 - 1) : d \in \Bbb{N}\}$ a $\Bbb{Z}$-linearly independent set?
We know that the set $B = \{(d \mid x) = \begin{cases} 1, d \mid x \\ 0, \text{ otherwise} \end{cases}, \ d \in \Bbb{N}\}$ forms a $\Bbb{Z}$-module Schauder basis for the module $M =\{ \Bbb{N} \to \...
- 21.6k
0
votes
2
answers
102
views
Is there an analytical solution to the inequality $\frac{1 + k({p}^{(k+1)/2)})}{p^k} < \frac{p}{p - 1}$ if one were to bound $k$ in terms of $p$?
My question is as is in the title:
Is there an analytical solution to the inequality
$$\frac{1 + k({p}^{(k+1)/2)})}{p^k} < \frac{p}{p - 1}$$ if one were to bound $k$ in terms of $p$?
Here, $p \...
- 8,228
1
vote
0
answers
153
views
Why is it that, if there are no odd perfect numbers, then there are no other $3$-perfect numbers, apart from the six known, as of the year $1643$?
Let $\sigma(x)=\sigma_1(x)$ denote the classical sum of divisors of the positive integer $x$.
A number $N$ is said to be $k$-perfect if $\sigma(N)=kN$ where $k$ is a positive integer.
The number $1$ ...
- 8,228
0
votes
1
answer
52
views
What is the Dirichlet serie of The function $A$ (OEIS A001414) which gives the sum of prime factors (with repetition) of a number $n$?
The function $A$ (OEIS A001414) which gives the sum of prime factors (with repetition) of a number $n$ and defined by
$$
A(n)=\sum \limits_{p^{\alpha}\parallel n}\alpha p
$$
is this serie calculated ...
1
vote
0
answers
54
views
Characterization of Möbius-monotonicity
We say that an arithmetic function $f:\mathbb{Z}^+\to\mathbb{C}$ is Möbius-monotone if $\forall n\geq1:(\mu*f)(n)\geq0$ (where $*$ denotes de Dirichlet convolution), i.e. if there exists a non-...
- 1,810
0
votes
1
answer
70
views
On the prime factorization of $n$ and the quantity $J = \frac{n}{\gcd(n,\sigma(q^k)/2)}$, where $q^k n^2$ is an odd perfect number
Let $N = q^k n^2$ be an odd perfect number with special prime $q$ satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$. Denote the classical sum of divisors of the positive integer $x$ by $\...
- 8,228
-1
votes
1
answer
99
views
On a consequence of $G \mid I \iff \gcd(G, I) = G$ (Re: Odd Perfect Numbers and GCDs)
Let $N = q^k n^2$ be an odd perfect number given in the so-called Eulerian form, where $q$ is the special prime satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$. Denote the classical sum of ...
- 8,228
1
vote
1
answer
154
views
Show the function for which the Dirichlet generating series is $\zeta(2s)$ using only $\tau,\varphi,\sigma\text{ and }\mu$ or some explicit formula.
I'm trying to find the function with Dirichlet generating series $\zeta(2s)$, I know that this relates somehow to the Liouville function but I am trying to express it in terms of only the standard ...
- 301
3
votes
1
answer
85
views
Generating function for the "two variable totient"?
Recall that Euler's totient function $\varphi(n)$ is defined as the number of natural numbers $<n$ which are coprime to $n$.
The Dirichlet series generating function for $\varphi(n)$ is
$$
\sum_{n\...
- 1,683