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

20
votes
2answers
488 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
131 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 ...
8
votes
1answer
234 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 ...
7
votes
1answer
144 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) = ...
5
votes
2answers
171 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.
5
votes
0answers
102 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
5
votes
0answers
134 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 ...
4
votes
2answers
124 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
1answer
408 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
95 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 ...
4
votes
3answers
59 views

Question about $T_n = n + (n-1)(n-2)(n-3)(n-4)$

The formula $T_n = n + (n-1)(n-2)(n-3)(n-4)$ will produce an arithmetic sequence for $n < 5$ but not for $n \ge 5$. Explain why. I think it is because if n is less than five the term with ...
4
votes
1answer
101 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 ...
4
votes
2answers
66 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 ...
4
votes
2answers
86 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. ...
4
votes
1answer
90 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. ...
4
votes
2answers
239 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 ...
4
votes
2answers
127 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 ...
4
votes
0answers
253 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, ...
3
votes
2answers
133 views

Ramanujan 1918 paper

Does anybody know where I can find Ramanujan's paper from 1918 titled "On Certain Arithmetical Functions." It is referenced in wikipedia, under the Ramanujan Summation section, but I cannot find a ...
3
votes
3answers
75 views

Prove that for all $n\in\mathbb{N}$, $\frac{s(n)}{d(n)}\geq \sqrt n$

Prove that for all $n\in\mathbb{N}$ $$\frac{s(n)}{d(n)}\geq \sqrt n$$ where $s(n) = \sum_{d|n} d$ and $d(n) = \sum_{d|n} 1$. Being honest, study some time arithmetic functions, and can not ...
3
votes
1answer
54 views

Is there a friendly pair $\{a, b\}$ where both $a$ and $b$ are odd?

Let $\sigma(x)$ denote the sum of the divisors of a positive integer $x$. $\{y, z\}$ is said to be a friendly pair if $$I(y) = I(z),$$ where $I(x) = \sigma(x)/x$ is the abundancy index of $x$. As ...
3
votes
2answers
101 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.
3
votes
1answer
356 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
76 views

does the surd $\sqrt[p-1]{p}$ for prime $p$ occur in any context?

for any prime $p \in \mathbb{N}$ use the corresponding symbol $q$ to denote the quantity $$q=p^{\frac1{p-1}}$$ and for $n \in \mathbb{N}$ define: $$ Q_n= \prod_{p \le n} q $$ empty products evaluate ...
3
votes
1answer
104 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 ...
3
votes
1answer
24 views

Two sets with the same geometric and arithmetic means

There are two sets A and B with equal geometric mean and arithmetic mean. Each element of both sets is odd integer greater than 1. A = B ? Order of elements isn't important.
3
votes
0answers
97 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
4answers
114 views

Finding the GCD of $50!$ and $2^{50}$

I've been trying to figure out how $n!$ and $x^n$ are related (where x is an integer) for most of the morning - I know it must be the key to unlocking this problem. Up to this point I've only used ...
2
votes
2answers
41 views

how to compute the “Hamming total” of a symmetric group?

The Hamming distance between two binary numbers has an obvious analogue for numbers encoded using a base $\gt 2$. A different analogue is the following. Let $\sigma \in S_n$ be a permutation which ...
2
votes
1answer
100 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, ...
2
votes
4answers
82 views

What's the meaning of this $(m,n) = 1$

I'm reading this pdf http://rutherglen.science.mq.edu.au/wchen/lndpnfolder/dpn01.pdf I understand some of the expression used in this but I don't understand the part $(m,n) = 1$ Is this a cartesian ...
2
votes
1answer
43 views

A closed form for $\sum_{i\cdot j^k=n}(-1)^i$?

$$\alpha_k(n) \stackrel{\text{def.}}{=} \sum_{i\cdot j^k=n}(-1)^i.$$ Does a closed form exist for $\alpha_k(n)$? For low values of $k$: $$\alpha_0(n)=(-1)^n$$ $$\alpha_1(n)=\begin{cases} ...
2
votes
1answer
127 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 $$ ...
2
votes
1answer
64 views

Properties of Arithmetic Functions

I was recently working on arithmetic functions and using Perron's formula to obtain asymptotic estimates. One observation I made was that the Dirichlet series often can be written in terms of the ...
2
votes
1answer
46 views

Finding $m∈\mathbb N$ such that $d^n(m)$ is not a perfect square for any $n\geq1$

Let , for $k ∈\mathbb N$ , $d(k)$ denote the number of positive divisors of $k$ ; define $d^n (k)$ recursively as $d^1(k)=d(k)$ , for $n\geq1$ , $d^{n+1}(k)=d(d^n(k))$ , how do we find those ...
2
votes
1answer
72 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
2
votes
1answer
88 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 ...
2
votes
0answers
65 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 ...
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?
1
vote
3answers
122 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 = ...
1
vote
2answers
74 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
2answers
88 views

If $(m,n)=1$ then $m^{\phi(n)}+n^{\phi(m)}\equiv0\pmod {mn}$

Show that if $(m,n)=1$ then $m^{\phi(n)}+n^{\phi(m)}\equiv0\pmod {mn}$ I tried, $(m,n)=1$ then, Euler theorem we have $m^{\phi (n)}\equiv1\pmod n$ and $n^{\phi (m)}\equiv1\pmod m$. But I could ...
1
vote
1answer
178 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 ...
1
vote
2answers
37 views

Finding root for the segment - found the formula but it doesn't work for some values - wrong formula?

I have the segment, defined as $(x_1, y_1)$, $(x_2, y_2)$. I know that $y_1\ge 0$ and $y_2 < 0$. I want to compute the root point for that segment. I decided to do it that way: ...
1
vote
1answer
160 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 ...
1
vote
1answer
40 views

Farey Sequence Vector Orthogonality Relation Question

Take the Farey sequence $\mathcal{F}_n$ for $n=39$ with values $a_m\in \mathcal{F}_n$ and put them into a vector $$ \vec v_k=\biggr(\exp(2\pi i k a_m)\biggr)_m $$ Since Merten's function for $n=39$ ...
1
vote
1answer
69 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 ...
1
vote
1answer
97 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) ...
1
vote
1answer
103 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}$ $ ...
1
vote
1answer
43 views

Arithmetic function

An arithmetic function is defined as follows:$f(1)=1$, $f(2k)=k$ and $f(2k+1)=f(k)+f(k+1)$. When (for which $k$) is $f(k)$ even? While it is obvious that $f(4n-1)=f(4n)=2n$, therefore $f(k)$ is even ...