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
1answer
83 views

Prime Factorization and Number Theory

Prime factorization of $n$ is $$n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$$ Let $f(n) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ where $e_k=a_k$ if $p_k|a_k$, else $e_k=a_k-1$ I want to ...
1
vote
1answer
101 views

Prove $\lambda(n)=\sum_{d^2|n}\mu(n/d)^2$ and $\mu^2(n)=\sum_{d^2|n}\mu(d)$

$\lambda(n)$= $\sum_{d^2|n}$ $\mu(n/d)^2$ and $\mu^2(n)$= $\sum_{d^2|n}$ $\mu(d)$ Having a little bit of trouble here.Can I use the fact that $\sum_{d|n}\lambda(n)$ is a characteristic function for ...
1
vote
1answer
57 views

Arithmetic progressions that generate an infinite number of powers of 2?

For an arithmetic progression of the form $a_i = ki, i \in \mathbb{N}$, the question is trivial - if $k$ is a power of 2, then the progression will generate an infinite number of powers of 2, and no ...
9
votes
0answers
72 views

Sums of the form $\sum_{d|n} x^d$

Let $$S(x,n) = \sum_{d|n} x^d, n \in \Bbb N$$ Do these sums appear in the literature? What are they called if they do and what is known about them?
9
votes
0answers
155 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 ...
7
votes
0answers
145 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
5
votes
0answers
176 views

Summation of a function 2

Let $n$ is a positive integer. $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the complete prime factorization of $n$. Let me define a function $f(n)$ $f(n) = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ where ...
5
votes
0answers
137 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
0answers
108 views

Arithmetic Derivative

In Calculus, whenever we see a constant and want to take the derivative of it, it always is $0$. However in Number Theory, we have something called the arithmetic derivative in which we can ...
4
votes
0answers
316 views

LCM of binomial coefficients and related functions

I know about the following identity: $$\displaystyle \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \frac{\text{lcm}(1, 2, ... n+1)}{n+1}$$ 1) Is there any method to find ...
4
votes
0answers
73 views

Derivatives, discrete and continuous, of $(1/\sqrt{n})\cos (t\log n)$ and $(1/\sqrt{n})\sin (t\log n)$ and Cauchy-Riemann equations

For any arithmetical function $f(n)$, we define its derivative to be $f'(n)=f(n)\cdot \log n$ for $n\geq 1$ (see for example [1], page 45 or Wikipedia). Fact. The functions ...
4
votes
0answers
171 views

To prove $\phi(mn)\phi(d)=\phi(m)\phi(n)d$ without explicitly computing the phi function values

If $m,n$ are positive integers with g.c.d.$(m,n)=d$ , then we can show by explicitly computing respective totients that $\phi(mn)\phi(d)=\phi(m)\phi(n)d$, I want to know, is there any more elegant way ...
4
votes
0answers
347 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
0answers
117 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 ...
3
votes
0answers
82 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?
2
votes
0answers
46 views

Are known these identities, that I've deduce using Mobius inversion formula?

I would to know if this formula is right and know (these formula are the same by exponentiation), since I deduce this easily by a standar way (perhaps there are mistakes) using Mobius inversion from ...
2
votes
0answers
22 views

Characters appearing naturally in arithmetic functions

Let $r_2(n)$ denote the number of representations of $n$ as a sum of 2 squares. It is well-known that $$r_2(n) = 4\sum_{d \mid n} \chi(d),$$ where $\chi$ is the non-principal character modulo $4$. ...
2
votes
0answers
61 views

how to show $\lim \sup_{n \to \infty} \frac{\phi(n+1)}{\phi(n)}= \infty$ and $\lim \inf_{n \to \infty} \frac{\phi(n+1)}{\phi(n)}= 0$?

Let $\phi (n)$ be the Euler's totient function . Thenhow to prove that the set $\{\dfrac{\phi(n+1)}{\phi(n)}: n \in \mathbb Z^+\}$ is unbounded above that is how to show $\lim \sup_{n \to \infty} ...
2
votes
0answers
79 views

A challenge question in elementary number theory!

Find an expression for the following sum: $$\sum_{i:(i,n)=1}(i-1,n)$$ I guess that this sum equals to $\phi(n)d(n).$
2
votes
0answers
149 views

On the indivisibility of odd perfect numbers by small numbers

A good day to everyone! This question is an offshoot of the following MSE posts: Odd perfect number divisors Can an odd perfect number be divisible by $101$? My question is as follows: Is ...
2
votes
0answers
84 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
0answers
38 views

Sketch of a possible equivalence with Riemann hypothesis

From Robin's equivalence (see [1]) and the following trigonometrics identitites, I ask to me if it is feasible write vagues equivalences using this strong result and if these equivalences will be ...
1
vote
0answers
37 views

Numbers $n$ whose prime factors are $2$ and $5$ if and only if $\sum_{k=1}^{rad(n)}\mu(k)k=0$?

In the literature if defined the arithmetical function $rad(n)$ as $1$ if $n=1$ and for $n>1$ by $rad(n)=\prod_{p|n}p$. It is obviously a multiplicative function. Too we know the Mobius function ...
1
vote
0answers
44 views

What happens to the $\color{red}s$ in Möbius' Inversion Formula?

At the end of the Wiki page on Möbius' Inversion Formula, the following relation is given: $$ g(x) = \sum_{m=1}^\infty \frac{f(mx)}{m^\color{red}s}\quad\mbox{ for all } x\ge ...
1
vote
0answers
48 views

Modified arithmetical functions from a modified Möbius function

In this post when $n>1$ we assume that $n=\prod_{k=1}^{\omega(n)}p_{n}^{e_{k}}$ its factorization in prime powers, where $\omega (n)$ is the number of distinct primes. It is well known the ...
1
vote
0answers
70 views

What's is the name of this function?

A function, $f:\mathbb{N}\to\mathbb{N}$, is defined in the following way, \begin{equation} f(n)=\#\{m\mid m\leq n\text{ and there does not exists any integer }m'>m\text{ such that }m\text{ divides ...
1
vote
0answers
61 views

Bezout Coefficient for polynomials in sage?

I want to find the bezout coefficient for those 2 polynomials : $f = 1+x-x^2-x^4+x^5$ and $g = -1+x^2+x^3-x^6$ when I use the gcd function in sage the output is : ...
1
vote
0answers
96 views

Summing the reciprocal of $\phi(n)^2$

I am currently reading Vaughan's book 'The Hardy-Littlewood method' and am working on exercise 3.3 (page 37). I have tried working through a special case but that didn't help either. More concretely, ...
1
vote
0answers
35 views

Number of triples $(a, b, c)$ with $1 \leq a,b,c \leq n$ which are coprime ($gcd(a,b,c)=1$)

Number of ordered triples $(a, b, c)$ with $gcd(a, b, c) = 1$ and $1 \leq a, b, c \leq n$ can be computed using the following formula: $$ C(n) = \sum_{k=1}^n\mu(k) \left \lfloor \frac{n}{k} \right ...
1
vote
0answers
29 views

gcd of product of exponents of prime factors and product of prime factors

Let $n = \prod\limits_i p_i^{k_i}$. I want to express $$ \gcd(\prod\limits_i k_i, \prod\limits_i p_i) $$ as an arithmetic function (i.e get rid of gcd). Is that possible? Thanks!
1
vote
0answers
102 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
1
vote
0answers
54 views

All all hypo-multiplicative functions linear combinations of quasi-multiplicative functions?

A function $f(n)$ is multiplicative if, for all coprime $m$ and $n$, $f(m)f(n)=f(mn).$ It is called quasi-multiplicative by many authors if $f(m)f(n)=f(1)f(mn)$, and the two coincide when $f(1)=1.$ ...
1
vote
0answers
110 views

Multiple Dirichlet convolutions

I have been playing around with Dirichlet convolutions. As a reminder, take two arithmetic functions $f,g$, then their Dirichlet convolution is defined as the arithmetic function with: $(f\star g)(n) ...
1
vote
0answers
71 views

Summation of no. of divisors

Let $d(n)$ = no. of divisors of $n$ and $(d(n))^2$ = square of no. of divisors of n. Let $$S(N) = \sum_{n=1}^{N} d(n)$$ and $$S_2(N) = \sum_{n=1}^{N}(d(n))^2$$ $$S(N) = ...
1
vote
0answers
66 views

Relation between Dirichlet convolution and Bell series and convolution of functions and the Fourier transform?

We define the Dirichlet convolution of two arithmetic functions $a,b:\mathbb{N}\to\mathbb{C}$ to be $$ (a*b)(n)=\sum_{d\mid n}a(d)b\left(\frac{n}{d}\right). $$ Given a prime $p$, we define the Bell ...
1
vote
0answers
248 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 ...
1
vote
0answers
129 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 ...
0
votes
0answers
43 views

Standard name or notation for the “even part” of an integer?

\begin{align} 0 & \mapsto 0 \\ 1 & \mapsto 0 \\[6pt] 2 & \mapsto 2 \\ 3 & \mapsto 2 \\[6pt] 4 & \mapsto 4 \\ 5 & \mapsto 4 \\[6pt] 6 & \mapsto 6 \\ 7 & \mapsto 6 \\ ...
0
votes
0answers
17 views

Odd perfect numbers and $\sum_{\substack{D\mid 2n,D<\sqrt{2n}}}(D+\frac{2n}{D})$

It is known that if $m>1$ isn't a perfect square integer (isn't a square number) then the sum of divisor function can be written as $$\sigma(m)=\sum_{\substack{d\mid ...
0
votes
0answers
16 views

Can you analyze this identity involving the sum of divisors function and $rad(n)=\prod_{p\mid n}p$?

Let $\sigma(n)$ the sum of divisors function, then by Mobius inversion formula $$\sigma(n)=n-\sum_{\substack{d\mid n,d<n}}\sigma(d)\mu\left(\frac{n}{d}\right),$$ and since this function is ...
0
votes
0answers
9 views

Lagarias and Robin theorems versus multiplicative property

If I use for example Robin's theorem, see here in the section Growth of arithmetic functions, or Lagarias equivalence, see (5) here has sense ask us what is the more sharp inequality for ...
0
votes
0answers
13 views

$Φ_n$ is Euler group, $n> 2$ is an integer, and $m$ the number of solutions of the equation $x^2 = 1$ in the ring $Z_n$.

Prove $$\prod_{i ∈ Φ_n} i=(-1)^{\frac{m}{2}}$$ Then what becomes this identity if $n$ is a prime number? I know that if $x^2=1$, we pair the number with its inverse modulo $n$ in the ...
0
votes
0answers
27 views

Is there a name for this discrete version of Jensen, specifically when applied to binomial coefficients?

We have $2k$ integers greater than or equal to $j\geq0$ $a_1+a_2+\dots + a_k=n$ and $b_1+b_2+\dots + b_k=n$. If for all $1\leq i\leq k$ we have $|n/k-a_i|\leq|n/k-b_i|$. Then ...
0
votes
0answers
37 views

Show that if $n$ is even then $\sum_{d|n}\mu(d)\phi(d)=0$ using only Dirichlet Convolution propertys (without multiplicative function concepts)

Show that $\displaystyle\sum_{d|n}\mu(d)\phi(d)=0$ using only Dirichlet Convolution propertys (without multiplicative function concepts). I suspect you have to use that $1\ast \mu=I$ and $f\ast ...
0
votes
0answers
29 views

On $\sum_{k\nmid n}k$, where the sum is over the integers $1\leq k\leq n$ such that $k\nmid n$, and perfect numbers

If we define the arithmetic function $\delta(n)$ as the sum of integers $1\leq k\leq n$ such that $k\nmid n$, we have by Gauss statement $\sum_{k=1}^n k=n(n+1)/2$, that ...
0
votes
0answers
35 views

Partial GCD - Sum

$\sum\limits_{n = 2}^{M} \sum\limits_{m = 1}^{R} GCD(m,n) $ $R = (\lfloor\dfrac{N}{n}\rfloor-n) \% n $ $M = \lfloor\sqrt{N}\rfloor $ I calculated that - For N=10 the sum is 1 For N = 100 the ...
0
votes
0answers
24 views

On $\sum_{d|n}(\mu(n/d)\sigma_0(d)/2)\log d$, where $\sigma_0(n)$ and $\mu(n)$ are, respectively, the number of divisors and Möbius functions

Let $f(n)=\sum_{d\mid n}\log d$. Then using Möbius inversion formula (see Wikipedia) and $\prod_{d\mid n}d=n^{\sigma_{0}/2}$ (see [1], page 47) where $\sigma_{0}(n)$ is the number of positive divisors ...
0
votes
0answers
59 views

Order of operations for log transformation

I am working with a large dataset of positive values with a positive skew. I will be using a Ln transformation in SPSS to normalize my dataset. However, I am not sure of the order of operations. For ...
0
votes
0answers
51 views

What is the inverse of $f(x)=x^{x^x}$?

I'm curious to find the inverse of $ f(x)=x^{x^x} $ As an added extra, I'm already familiar with the Lambert Product Log function.
-1
votes
0answers
19 views

Arithmetic problems with understanding

I'm having problems with understanding qn 22. Part (III) don't really know what are they asking :|