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
0answers
22 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 ...
1
vote
0answers
44 views

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

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? ...
4
votes
3answers
168 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
69 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 ...
0
votes
0answers
17 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
48 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
108 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
55 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
42 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
19 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
69 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
54 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).$
0
votes
2answers
59 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
68 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
65 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
49 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
54 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}$
2
votes
1answer
93 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
1answer
103 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
26 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
38 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) ...
3
votes
0answers
71 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 ...
1
vote
1answer
45 views

Sums involving square of Moebius function

I try to estimate the following sum: $$ \sum_{n \leq x}\mu(n)^2 f(n) $$ where $\mu(n)$ is a Moebius function and $f(n)$ is some multiplicative arithmetic function. If I understand it correctly it is ...
2
votes
1answer
41 views

A Möbius Identity

I need to prove the identity $$\sum_{k = 1}^n \mu(k)\left[ \frac{n}{k} \right] = 1$$ where $n$ is a natural number, and $[n]$ denotes the floor function. The proof also should not use the Möbius ...
0
votes
0answers
29 views

Number of excellent pairs is equal to $\sigma(n)$

Let $\nu$ be an irrational positive number, and let $m$ be a positive integer. A pair of $(a,b)$ of positive integers is called good if $$a \left \lceil b\nu \right \rceil - b \left \lfloor a \nu ...
4
votes
2answers
123 views

Which natural number predicates can be defined in Robinson arithmetic?

I'm especially wondering about the order relation, subtraction, division and exponentiation here: $x \leq y \quad \Leftrightarrow \quad \exists u\ y=x+u$ $z= x-y \quad \Leftrightarrow \quad ...
0
votes
1answer
47 views

Find the term of the G.P.

Find the term of the G.P. $1, 1.2, 1.44, 1.728,... $ which is just greater than $100$. Please somebody explain me the question? All i know is $a=1$ and $r=1.2$ Help :( should it be $T_{n} > ...
4
votes
2answers
83 views

prove that $\phi(xy) =\phi(x)\phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. [duplicate]

Prove that $\phi(xy) = \phi(x) \phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. I understand the concept, and have done several examples proofing this but cannot put it in "proof form" because unless ...
1
vote
1answer
68 views

Finding formulas for sums

I know that $\sum_{d \mid n} \mu(d) = 0$ whenever $n >1$, and I know that $\sum_{d \mid n} \phi(d) = n$. How can I use this in order to give a formula for $\sum_{d \mid n} \mu(d)\phi(d)$?
0
votes
2answers
21 views

Find the numbers; Arithmetic Progression.

The sum of four consecutive numbers in an A.P is $28$. The product of the second and third numbers exceeds that of the first and last by $18$. Find the numbers. I thought of this: $$S_{4} = ...
1
vote
0answers
20 views

An inequality involving Möbius function [duplicate]

For any positive integer $n$ show the inequality holds : $$\left|\sum_{i=1}^{n}\frac{\mu(i)}{i}\right|\le 1$$ I tried induction. when $\mu(n+1)=0$ it is trivial. But what if $\mu(n+1)\ne 0$? I am ...
3
votes
1answer
80 views

A sum regarding prime factorization

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) = \left((p_1^{a_1}+1)(p_2^{a_2}+1)(p_3^{a_3}+1)\cdots(p_k^{a_k}+1)\right)$ I want to find the value of ...
1
vote
0answers
59 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
2answers
24 views

Mean of given Arithmetic function

Find the mean of $a, a+d, a+2d, a+3d,\dots,a+nd$ I have no idea what to do in this question but i have tried the following: $$mean\ \bar{x}= \frac{(a)+(a+d)+(a+2d)+(a+3d)+\cdots+(a+nd)}{n+1} $$ ...
4
votes
1answer
120 views

Euler phi function, number theory

I am trying to find the value of $$\sum_{n=1}^{N}\sum_{d|n}d*\phi(d)$$ Is there a method to evaluate this for large N? $\phi(d)$ is the Euler phi function.
1
vote
1answer
37 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 ...
3
votes
4answers
93 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
57 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$ ...
4
votes
3answers
182 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
2answers
41 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: ...
2
votes
1answer
51 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 ...
-4
votes
1answer
84 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 ...
8
votes
0answers
124 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
17 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 ...
3
votes
1answer
25 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
89 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
60 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 ...
1
vote
1answer
50 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.} ...
3
votes
1answer
77 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
76 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} ...