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

0
votes
0answers
21 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 ...
0
votes
1answer
23 views

Composition of analytic function with arithmetic function

Consider an arithmetic function $g$ with codomain $\{a,b\}$ and a function $f$ which is analytic on some domain including $\{a,b\}$. We therefore have $$f(g(n))=\sum_{k=0}^\infty c_k (g(n)-a)^k$$ and ...
3
votes
3answers
163 views

Ramanujan's tau function identity

While studying Ramanujan's tau function, I observed that the function satisfies a beautiful identity that I had not seen previously in the literature. Let $\tau(n)$ be Ramanujan's tau function, such ...
2
votes
1answer
39 views

Closed-Form Modular Arithmetic

Is there a way to define modulo division (or functions of modular arithmetic in general) as superposition of (elementary?) functions? For example, the multiplication is first introduced as ...
7
votes
0answers
127 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 ...
1
vote
1answer
39 views

For all $n\in\Bbb N$ does there exist $n_1$ and $n_2$ such that $d(n_1) +d(n_2)=n$

I am trying to show that for each positive integer, $n$, we can find integers $n_1,n_2$ that satisfy $$d(n_1) +d(n_2)=n$$ where $d(n)$ is the divisor function. I am frustrated because even with easy ...
1
vote
0answers
65 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 ...
0
votes
1answer
24 views

If an arithmetic function has a strong logarithmic mean value, then it has an ordinary mean value.

Say that an arithmetic function f has a strong logarithmic mean value A, and write L(f) = A, if f satis es an estimate of the form \begin{align} \sum\limits_{n=1}^{x}\frac{f(n)}{n} = Alog(x) + B + ...
1
vote
0answers
36 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 : ...
2
votes
1answer
38 views

for which values of the pair of integers $(n,k)$ is $p(n,k) =1+\frac{2^{k}-1}n$ is prime?

let $p(n,k)= 1+\frac{2^{k}-1}{n}$ for a positive integer $n,k$ -for which values of the pair of integers $(n,k)$ : $p(n,k)$ is prime ? Any help is very welcom .Thank you
5
votes
0answers
169 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 ...
4
votes
1answer
44 views

Number of Divisors of most numbers

In the book A Comprehensive Course in Number Theory by Alan Baker. The author mentions that even though the average order of $\tau(n)$ is $\log n$, almost all numbers have about $(\log n)^{\log 2}$ ...
0
votes
1answer
24 views

Multiplicative Function Property

Suppose $f$ is an arithmetic function. Does the property $f(1) = 1$ if $f$ is multiplicative? Or is it only when $f$ is completely multiplicative?
5
votes
1answer
83 views

A question about Euler's totient function

Prove that for every natural number $m$, there exists a natural number $n$ such that $$\phi(n)=\phi(n+m)$$ For odd numbers $m$, we can choose $n=m$ and use the identity $\phi(2m)=\phi(m)$.
3
votes
0answers
124 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 ...
3
votes
1answer
78 views

find all positive integers n such that $\phi(n)+\sigma(n)=2n$.

I'm asked to find all integers n such that $\phi(n)+\sigma(n)=2n.$ I know that when n is a prime, $\phi(n)+\sigma(n)=(n-1)+(n+1)=2n.$ My guess is that n can only be primes, and I want to derive a ...
0
votes
1answer
20 views

On the sets $\{\dfrac {\phi(n+1)}{\phi(n)} : n\in \mathbb Z^+\}$ and $\{\dfrac {\phi(n)}{n} : n\in \mathbb Z^+\}$

How to show that the set $\{\dfrac {\phi(n+1)}{\phi(n)} : n\in \mathbb Z^+\}$ is dense in $\mathbb R^+$ ? Also that the set $\{\dfrac {\phi(n)}{n} : n\in \mathbb Z^+\}$ is dense in $(0,1)$ ?
2
votes
0answers
52 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} ...
1
vote
3answers
62 views

The probability that a random integer is prime to a given integer $m$ is $\frac{\phi(m)}m$?

Let $N_m(x)$ denote the number of positive integers not exceeding $x$ that are relatively prime to $m$ , then how to prove that $\lim_{x \to \infty} \dfrac{N_m(x)}x=\dfrac{\phi (m)}m$ , where ...
3
votes
1answer
57 views

Convolution identity involving the Möbius function $\sum_{d|n,d>0} |\mu(d)| = 2^{\omega(n)}$

I'm learning about the Möbius Inversion Formula but I'm stuck on an exercise which involves the Möbius function. Let $n\in\mathbb{Z}$ with $n>0$ and let $\omega(n)$ denote the number of distinct ...
0
votes
1answer
31 views

Proof involving the Euler phi-function

I'm having trouble approaching the following exercise: Let $n$ and $k$ be positive integers. Prove that $\phi(n^k) = n^{k-1}\phi(n)$. I've tried examining the prime factorization $n^k = (p_1^{a_1} ...
1
vote
2answers
124 views

A proof of $\sum{\mu(n)/n}=0$

I am looking for a proof (or references) of the following statement $$\sum_{n=1}^{\infty}{\frac{\mu(n)}{n}}=0$$ where $\mu$ is the Möbius function. Many thanks !
0
votes
0answers
37 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 ...
3
votes
1answer
71 views

Formula for $\sum_{d|n} \frac {\mu(d)}d$

I feel like I've seen a formula somewhere for $\displaystyle \sum_{d|n} \frac {\mu(d)}d$, but I can't remember what it is and can't find it. Does anybody know of a formula?
10
votes
5answers
528 views

Identity with nested sum taken over divisors of $\gcd$'s

For computational reasons, I want to show that the following holds true: Let $n_1,n_2,N\in \mathbb{N}$. One has $$\Large \sum_{a\mid \gcd(n_1,N)}\sum_{b\mid \gcd(n_2,\frac{n_1N}{a^2})} ab ...
1
vote
0answers
61 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, ...
6
votes
1answer
88 views

Lower bound of Euler phi function times sum of divisors

After some work, I got this nice inequality: $$ \frac{n^2}{2} < \phi(n)\cdot \sigma(n) $$ where $\phi(n)$ is Euler's phi function and $\sigma(n)= \sum_{d|n} d$. I know this is true because I'm ...
4
votes
2answers
74 views

Proving an identity of the Möbius function and Euler’s totient function product

Could anyone kindly help me to prove that $$ \sum_{d|n} \mu(d) \varphi(d) = 0 $$ for all even integers $ n \geq 2 $, where $ \mu $ is the Möbius function and $ \varphi $ is Euler’s totient function? ...
1
vote
1answer
75 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 ...
0
votes
2answers
14 views

Offset a range of numbers

I want to find an equation to offset a range of numbers by a given amount. I'm not sure if I am using the term offset correctly. Lets say the range is from 0 - 1 and I want it to be offset by .25 : 0 ...
2
votes
0answers
24 views

To calculate what is $\sum_{1 \le m<n ;(m,n)=1} m^2$ or what is the remainder when $\sum_{1 \le m<n ;(m,n)=1} m^2$ is divided by $n$? [duplicate]

For an integer $n >1$ , what is the sum of the squares of all the positive integers that are less than $n$ and relatively prime to $n$ that is I am trying to calculate $f(n):=\sum_{1 \le m<n ...
4
votes
3answers
267 views

Prove there are k consecutive non-squarefree integers

So, I've got a question for class that asks me to prove the existence of arbitrarily long runs of consecutive integers where $\mu(n)$ is zero. I've started the proof, but I need a bit of help midway ...
7
votes
2answers
87 views

$\varphi(N)>\pi(N)$?

Is it trivial that $\varphi(N)>\pi(N)$ for sufficiently big integers $N$, where $\varphi$ is Euler's totient function and $\pi$ is the prime-counting function? The only exceptions less than ...
1
vote
0answers
31 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 ...
2
votes
3answers
65 views

Where did the sum-of-divisors function come from?

Doing a research project on a few number-theoretic functions, and I was curious, where does the sum-of-divisors function come from? Surely someone thought it up and made it a possibility. I'm talking ...
5
votes
1answer
115 views

How many numbers are products of $p^p$?

Consider the set $\mathcal{S}=\{1,4,16,27,\ldots\}$ of numbers which are products of numbers of the form $p^p$ for $p$ prime. ($\mathcal{S}$ is A072873 in the OEIS.) Note that multiple primes are ...
2
votes
1answer
77 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 ...
0
votes
0answers
48 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
vote
0answers
26 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
2answers
79 views

About the 'sigma' function.

Is it true that if $n$ divides $m$ , $\sigma(\frac mn) \leq \frac{\sigma(m)}n$. If so this has a bearing on counterexamples to Robin's inequality.
1
vote
0answers
66 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
2answers
140 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
0
votes
2answers
68 views

Are there particular techniques to find the general formula for an arithmetic function, neither multiplicative nor additive?

I was reading about the Euler phi function and the sigma function when I began to wonder how on earth one gets to the general formula for an arithmetic function. I'm not considering trivial formulae ...
2
votes
2answers
79 views

Is there a way to show that $d(n)$, which counts the number of divisors of $n$ is non-increasing? [closed]

Is there a way to show that $d(n)$, which counts the number of divisors of $n$ is non-increasing? I'm trying to use the Cauchy condensation test to show that $\sum_{n\ge{2}}\frac{d(n)}{n\log^2n}$ is ...
2
votes
4answers
75 views

How to show that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ [duplicate]

set $ n, n \in \mathbb{N}$ and prove that $\prod_{d/n} d = n^{\frac{\tau(n)}{2}}$ ¨I have tried this¨ If $n > 1$ then $n = p_{1}^{\alpha_{1}}\cdot p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ ...
1
vote
0answers
84 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
1answer
59 views

How to show that $f(p^{k}) = f(p) \cdot f(p^{k-1}) \Longrightarrow f(p^{k}) = [f(p)]^{k}$ [closed]

If f is an arithmetic function such that $f (1) = 1$ and $p$ is a prime number. Prove that: $\forall k \in \mathbb{N}$ $f(p^{k}) = f(p) \cdot f(p^{k-1}) \Longrightarrow f(p^{k}) = [f(p)]^{k}$
4
votes
1answer
109 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
1answer
209 views

Prove that the Möbius function is multiplicative

I'm studying algebra, and I came across some questions on multiplicative functions (that should be number theory though?). One is: prove that mobius function is multiplicative. But I've not been given ...
1
vote
0answers
40 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.$ ...