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

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 ...
1
vote
1answer
33 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
2answers
36 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: ...
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 ...
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 ...
2
votes
1answer
42 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} ...
-6
votes
1answer
54 views

What are arguments to $\frac 00 = Undefined$?

Now, I understand that dividing by zero in any case is undefined. However, in math, there are always exceptions. I'm just really curious...what are the different cases for different answers? For most ...
5
votes
0answers
101 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 ...
0
votes
1answer
15 views

how to check arithmetic progression of triangle

I solved the problem with the following text: In a rectangle the sides and the diagonal are an arithmetic progression. Calculate the circumference of the rectangle where the longer side is 44 cm ...
20
votes
2answers
487 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 \\ ...
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
1answer
74 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 ...
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, ...
0
votes
1answer
41 views

Evaluate $\sum_{d\mid N}\Lambda(d)$

For a positive integer $n$, define $$\Lambda(n) = \left\{ \begin{array} {ll} \log p & \mbox{if $n = p^r$, $p$ a prime and $r \in \mathbb{N},$ }\\ 0 & \mbox{otherwise.} ...
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 ...
0
votes
5answers
118 views

For every positive integer n greater than $2$, $\phi(n)$ is an even integer.

Theorem: For every positive integer n greater than $2$, then $\phi(n)$ is an even integer. I know this theorem and the same is used much, but I was curious how it would be to demonstrate it, show ...
1
vote
2answers
84 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
votes
5answers
111 views

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$

Solve for $m\in\mathbb{N}$ the equation $\phi (m)=12$ I found (by trial) $m=\{13,21,26,28,36\}$, but do not know if misinterpreted the problem, but actually I suppose I have to find an equation ...
3
votes
2answers
132 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 ...
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. ...
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 ...
1
vote
0answers
111 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
407 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 ...
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 ...
0
votes
1answer
32 views

Demonstration in arithmetic function

I need help to know (in detail) how to prove that the product of two multiplicative arithmetic functions is a multiplicative arithmetic function. $$$$$f(n)$ and $g(n)$ are functions multiplicative, ...
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 ...
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 ...
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) = ...
0
votes
1answer
83 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?
0
votes
0answers
56 views

Does there exist a counterexample to the inequality $I(n) < 2{\left(\frac{n}{n + 1}\right)}^2$, if $n$ is odd and deficient?

If $n$ is odd and deficient, does there exist a counterexample to the inequality $$I(n) < 2{\left(\frac{n}{n + 1}\right)}^2,$$ where $$I(x) = \frac{\sigma(x)}{x}$$ is the abundancy index of ...
0
votes
0answers
42 views

What proportion of the positive integers satisfy $I(n^2) < (1 + \frac{1}{n})I(n)$, where $I(x)$ is the abundancy index of $x$?

Let $\sigma(x)$ denote the classical sum-of-divisors function, and let $$I(x) = \frac{\sigma(x)}{x}$$ be the abundancy index of the positive integer $x$. My question is this: What proportion of ...
0
votes
1answer
38 views

A more elegant version of this function?

I challenged myself. The goal was to find a function $f$ with two variables $x$ and $y$ real, which results $1$ if $x=y$ and results $0$ if $x ≠ y$. But, the fonction can only use additions, ...
0
votes
1answer
83 views

What proportion of the positive integers satisfy $I(n) < \frac{2n}{n + 1} \leq I(n^2)$ < 2?

Let $$I(x) = \frac{\sigma(x)}{x}$$ be the abundancy index of the positive integer $x$. Note that $\sigma(x)$ is the classical sum-of-divisors function. For example, $$\sigma(12) = 1 + 2 + 3 + 4 + ...
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 ...
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 ...
4
votes
2answers
238 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
1answer
100 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
96 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
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 ...
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
102 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
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
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 ...
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.
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 ...
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 ...
1
vote
3answers
121 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 = ...
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