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

4
votes
1answer
104 views

Decidable & Recursive predicates

Let $C$ be a decidable predicate in the language of arithmetic HA, that is $$ \vdash (\forall \underline x)\: C(x) \vee \neg C(x).$$ $C$ is recursive if there exists a computable characteristic ...
1
vote
1answer
72 views

What proportion of the natural numbers satisfy the following inequalities?

Let $\sigma_1(n)$ be the sum of the divisors of $n \in \mathbb{N}$, and let $$I(n) = \frac{\sigma_1(n)}{n}$$ be the abundancy index of $n$. What proportion of the natural numbers satisfy the ...
4
votes
1answer
126 views

Image of the Euler phi function

I was reading a text about arithmetic functions, which ofcourse mentioned the Euler phi function. I was wondering whether $\phi(n)$ takes on all positive integer values. The answer doesn't seem so ...
0
votes
0answers
130 views

Can an odd perfect number be divisible by 101?

Preamble - This question is an offshoot from the following earlier questions here at MSE: Can an odd perfect number be divisible by 825? Can an odd perfect number be divisible by 165? Odd perfect ...
4
votes
2answers
71 views

An uncountable well-ordered subordering of asymptotic growth rates?

Define the following relation $\le$ between arithmetic functions $f$ and $g$ (mappings from $\mathbb{N} \rightarrow \mathbb{N}$): $f \le g := \exists n_0, k: \forall n: n \gt n_0 \implies f(n) \lt k ...
1
vote
1answer
108 views

Attempted exercise using Littlewood's theorem

This was an exercise to try to show we can use Littlewood's theorem$^1$ to prove that $$\lim_{N \to \infty}\frac{1}{N}\sum_{n=1}^{N} \frac{g(n)}{\log p_n} = 1 \hspace{30mm}(1)$$ If $\vartheta(p_k) ...
2
votes
1answer
103 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, ...
1
vote
1answer
140 views

Littlewood's 1914 proof relating to Skewes' number

From Littlewood's 1914 theorem (paraphrase): I propose to show there are arbitrarily large values of x for which successively $\psi(x) - x < - K\sqrt{x}\log\log\log x \tag{A}$ $ ...
4
votes
2answers
139 views

Limiting value of $\lim \frac{1}{k}\sum_{n=1}^k \frac{p(n+1)-p(n)}{\log p(n)}$

Empirically it seems $$\lim_{k\to \infty} \frac{1}{k}\sum_{n=1}^k \frac{g(n)}{\log p(n)} = 1\tag{1} $$ in which p(n) is the nth prime and g(n) is the prime gap $p(n+1)-p(n).$ Cramer conjectured ...
4
votes
2answers
133 views

Estimating $\sum_{p_2 \leq x} (\log p_2)^2$

This was an exercise to use the approach here to estimate the sum $\sum_{p_2 \leq x} \log (p_2)^2,$ in which $p_2$ are numbers containing two prime factors (repetitions allowed). $\pi_2(x)$ is the ...
3
votes
2answers
108 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.
2
votes
0answers
72 views

Smallest prime p with N a quadratic residue mod p

Let $N$ be a square-free number equal to 2 or 3 $(\mod 4)$. Let $P(N)$ be the first odd prime, not a factor of $N$, for which $N$ is a quadratic residue. On average, $N$ would be a non-residue for ...
1
vote
3answers
134 views

Are there any integer solutions to $\gcd(\sigma(n), \sigma(n^2)) = 1$ other than for prime $n$?

A good day to everyone! Are there any integer solutions to $\gcd(\sigma(n), \sigma(n^2)) = 1$ other than for prime $n$ (where $\sigma = \sigma_1$ is the sum-of-divisors function)? Note that, if $n = ...
8
votes
1answer
249 views

Proving that $\omega(N)\neq4$ for an odd perfect number $N$ by hand

Let $\omega(n)$ denote the number of distinct prime factors of a positive integer $n$, and let $N$ be an odd perfect number. It is not difficult to show that $\omega(N)\ge3$. In fact, Nocco already ...
3
votes
0answers
100 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 ...
2
votes
1answer
74 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
6
votes
4answers
201 views

How to prove $ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$

how to prove: $$ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$$ $\prod_{d|n} d$ is product of all of distinct positive divisor of $n$, $\tau (n)$ is number (count)of all of positive divisor of $n$
4
votes
2answers
89 views

Prove: $\sum_{k<n, (k,n)=1} k= \frac{1}{2}n \varphi (n)$

Prove: $\sum_{k<n, (k,n)=1}k = \frac{1}{2}n \varphi (n)$ I have had strep throat and missed the lecture discussing properties of the Euler function. Any help in solving this is appreciated. ...
1
vote
2answers
75 views

Is Wiki wrong on Dirichlet Chararcters Modulo $10$?

Wiki says: Modulus 10 There are $\phi(10)=4$ characters modulo $10$. Note that $χ$ is wholly determined by $\chi(3)$, since $3$ generates the group of units modulo $10$. I can ...
1
vote
1answer
207 views

Function that counts the number of divisors of a natural number?

Let Function $f(n)$ be formally defined for natural numbers such that it gives number of distinct divisors of the number n (n and 1 included) For example, $f (12)=6$, then what is a quick way to ...
7
votes
1answer
158 views

Is there a complex variant of Möbius' function?

When you're dealing with arithmetic functions, you might have come across the classical Möbius' function $$ \mu(n)=\begin{cases} (-1)^{\omega(n)}=(-1)^{\Omega(n)} &\mbox{if }\; \omega(n) = ...
2
votes
1answer
92 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 ...
4
votes
2answers
243 views

Elements of finite order in the group of arithmetic functions under Dirichlet convolution.

Let $(G, ∗)$ be the group of arithmetic functions $f : N \to C$ that satisfy $f (1)\neq 0$, with group operation given by the Dirichlet product $∗$. The identity function $I$ is the identity element ...
0
votes
1answer
87 views

Converting loop to a closed form expression? [duplicate]

Possible Duplicate: How to convert this loop into a closed form expression? I have the following code in Python ...
2
votes
0answers
68 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?
4
votes
0answers
276 views

Numbers $n$ such that Mertens' function is zero.

OEIS (A028442) lists the Numbers n such that Mertens' function $$ M(n)=\sum_{k=1}^n\mu(k) $$ is zero: 2, 39, 40, 58, 65, 93, 101, 145, 149, 150, 159, 160, 163, 164, 166, 214, 231, 232, 235, 236, ...
5
votes
0answers
135 views

Is the application of $\mu$ on $P_x(s)^k$ analogous to the differentiation $\frac{d^k f(\lambda) }{d\lambda^k}\biggr|_{\lambda=0}$?

Let me start with the following on elementary symmetric polynomials: The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity ...
1
vote
1answer
192 views

How can the Möbius function be applied to a series?

Given a series $p_n(s)=\sum_{k=1}^n a_k $. I'd like to get $\hat{p}_n(s)=\sum_{k=1}^n \mu(k)a_k $. Think of $a_k=k^{-s}$ for example. If you let $n$ go to $\infty$, you'll see the well-known relation ...
3
votes
1answer
400 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
1answer
106 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 ...
5
votes
2answers
180 views

Sum of $n \sigma(n)$

What is known about the asymptotic behavior of $$ -\frac{\pi^2}{18}x^3+\sum_{n\le x}n\sigma(n) ? $$ It seems to be $O(x^{2+\varepsilon})$ but I cannot prove this.
21
votes
2answers
549 views

Primes approximated by eigenvalues?

Consider the matrix starting: $$\displaystyle T = -\begin{bmatrix} +1&+1&+1&+1&+1&+1&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ ...
8
votes
1answer
135 views

Comparing average values of an arithmetic function

Suppose $f(n)$ is a positive real-valued arithmetic function such that $$ \frac1n\sum_{k=1}^nf(k)\sim g(n) $$ for $g(x)$ a monotonic increasing function. What can be said about the asymptotic behavior ...
2
votes
1answer
145 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 $$ ...
1
vote
0answers
113 views

Generalizing a result on sums involving Euler's function

Motivation: It's known that there is a constant $0<K$ such that for any natural number $N$, $KN\leq \frac{\varphi(1)}{1}+\frac{\varphi(2)}{2}+\cdots+\frac{\varphi(N)}{N}$ (with $\varphi$ being ...
4
votes
1answer
448 views

On sums involving Euler's totient function

I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated: Let $\varphi(n)$ be Euler's totient function. Show that there is a constant ...
4
votes
1answer
91 views

Asymptotics for almost all $x$

Theorem 2.2 in Shparlinski 2006 says: For all positive integers $n\le x$ except possibly $o(x)$ of them, the bound $$M(x)\ll\frac{x}{\log x}\exp\left((C+o(1))(\log\log\log x)^2\right)$$ holds. ...
0
votes
1answer
89 views

Question about the proof of Theorem 2.19 (Page 38) of the book Introduction to Analytic Number Theory by Apostol

At the last line of the proof: $\lambda^{-1}(n)=\mu(n)\lambda(n)=\mu^2(n)=|\mu(n)|$. Why $\mu(n)\lambda(n)=\mu^2(n)$? How to prove this?