Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [arithmetic-functions]

The tag has no usage guidance.

-2
votes
0answers
34 views

Closed Form Formula for Adding two Binary Coded Decimal (BCD) Numbers [on hold]

Formal Verification of decimal arithmetic computations hardware/software requires some sort of function decomposition. None of the numerous decomposition types (Taylor, Horner, Shannon, Davio, etc.) ...
5
votes
0answers
168 views

Can we write each positive integer as $x^2+y^2+\varphi(z^2)$?

As odd squares are congruent to $1$ modulo $8$, any integer of the form $4^k(8m+7)$ with $k,m\in\mathbb N=\{0,1,2,\ldots\}$ cannot be written as the sum of three squares. To avoid such congruence ...
7
votes
1answer
414 views

Is the sum $\sum_{d\mid n}\frac1{d+1}$ never integral?

Recall that a positive integer $n$ is a perfect number if and only if $$\frac{\sigma(n)}n=\sum_{d\mid n}\frac1d=2.$$ QUESTION: Is my following conjecture true? Conjecture. (i) We have $\sum_{d\mid ...
2
votes
0answers
39 views

Uniformity in Wirsing's Mean Value Theorems

In two important papers of Wirsing, namely "Das asymptotische Verhalten von Summen über multiplikative Funktionen" (1961) and its follow up (1967), several results on mean values of multiplicative ...
6
votes
2answers
1k views

Does this multiplicative function have a name? If so, what is known about it?

It is well-known that the Euler $\phi$-function is multiplicative: that is, for co-prime positive integers $m,n$ we have $\phi(mn) = \phi(m)\phi(n)$. Thus it is defined by its values on prime powers. ...
10
votes
0answers
725 views

Euler's totient function and Riemann hypothesis

I am looking for an upper-bound of the Euler's totient function $\varphi$ which would be equivalent to the Riemann hypothesis (RH). There is the following Nicolas' criterion about primorial numbers $...
3
votes
0answers
117 views

Is there a way to reduce this problem to two variables through functions coming from arithmetic?

Consider following diophantine equation in $\mathbb Z[x,y,z]$ in three integer variables $x,y,z$ $$x^2+L(y,z)x+L_1(y)L_2(z)=0$$ where $L(y,z)$ is a non-homogeneous linear polynomial in $y,z$ and $L_1(...
2
votes
0answers
170 views

A conjecture regarding odd perfect numbers

(Note: I asked this question in MSE this June 2018 but did not receive any responses there. I have therefore cross-posted it here, hoping that it gets answered.) Let $\sigma(z)$ denote the sum of ...
8
votes
1answer
335 views

Goldbach's conjecture for the Liouville function

Is it true that for every even integer $N > 2$, there exist positive integers $a,b$ such that $a + b = N$ and $\lambda(a) = \lambda(b) = -1$ ? Here $\lambda$ is the Liouville function.
4
votes
1answer
145 views

The number of solutions of the equation $ax_1x_2+by_1y_2=n$

The equation $x_1x_2+y_1y_2=n$ is well-studied (Ingham, Heath-Brown, Deshouillers & Iwaniec, Ismoilov) because it arises in an additive divisor problem. The number of solutions in positive ...
4
votes
1answer
396 views

Reference for inequality for $\sum\limits_{d \mid n}\frac{\log d}{d}.$

Let $f(n)=\sum\limits_{d \mid n}\frac{\log d}{d}.$ It is not hard to see that $f(n)\ll(\log\log n)^2$. Is there any reference for this inequality? EDT 1: A possible answer is Analysis of the ...
1
vote
0answers
102 views

Primes approximated by eigenvalues?

Let the matrix $T$ be defined by: $$\displaystyle T(n,k) = -\varphi^{-1}(\operatorname{GCD}(n,k))$$ where $\varphi^{-1}$ is the Dirichlet inverse of the Euler totient function. $$\varphi^{-1}(n) = \...
7
votes
1answer
328 views

On $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$

Euler's totient function $\varphi$ is multiplicative, and it plays important roles in number theory. QUESTION: Is it true that for each integer $m>6$ we have $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$...
1
vote
0answers
79 views

Existence of equation about the product of the divisor sum function

Let $\sigma_k(n)$ be the sum of the $k$-th powers of the positive divisors of $n$ and $\mu(n)$ be the Möbius function. As Arithmetic function - Wikipedia mentioned, there is an equation that $$\...
0
votes
1answer
141 views

The Euler's totient function and the product of distinct primes dividing $n$ versus the Heronian means

For integers $n\geq 1$ with $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ we denote the squarefree kernel or radical of an integer $n$ (see if you want this Wikipedia). And $\...
3
votes
0answers
106 views

Is there a closed form for the discrete convolution of $\sigma_1$ and $\sigma_2$?

I am trying to find a closed form for the following sum: $$\sum_{k = 1}^{n-1}\sigma_1(k) \sigma_2(n-k)$$ where $\sigma_i$ is the sum of divisors and $\sigma_2$ is the sum of squares of divisors. ...
11
votes
3answers
408 views

Evaluating the sum of $kl^2$ over $p,q,k,l$ such that $pk +ql = n$

I have come across the following sum: $$\sum_{\substack{p, q, k, l \in \mathbb{N} \\ k > l \\ pk + ql = n}}kl^2$$ and I am trying to simplify it, hoping to get a nice formula in terms of $n$ and ...
4
votes
1answer
294 views

A special kind of multiplicative function $f: \mathbb N \to \mathbb N$ such that $f(p)=p+k$ for all odd prime $p$, where $k>1$ is a fixed odd integer

For which odd positive integer $k$, can we find a multiplicative function $f: \mathbb N \to \mathbb N$ satisfying the following conditions : $f(p)=p+k$ for all large enough odd prime $p$ and the set $...
0
votes
0answers
84 views

Name and theory of multi-valued functions $F:\mathbb{N}^k \rightarrow \mathbb{N}^l$

In computability theory there are considered mostly single-valued functions $f:\mathbb{N}^k \rightarrow \mathbb{N}$. (Let $\mathbb{N}$ be a placeholder for $\mathbb{N}$ or any initial segment $[0,n]$ ...
1
vote
1answer
121 views

Tighter upper bound for $\sum_{i=1}^kA_i\log(\frac{A_i}{e})$

What is the tightest upper bound one can obtain for the following expression $$\sum_{i=1}^kA_i\log(\frac{A_i}{e})$$ subject to $\sum_{i = 1}^k A_i = C$ in terms of $C$ and $k$? A very loose upper ...
6
votes
1answer
297 views

The importance of relations between automorphic forms and arithmetic functions

As I understand things, one of the classical reasons to care about modular forms was their relation to interesting arithmetic functions/counting questions, i.e. on sums of squares and partitions. When ...
13
votes
2answers
920 views

A mystery sequence

This question arose from the recent one, roots of a polynomial linked to mock theta function?. Let $$ g(x):=\sum_{k=0}^\infty x^k\prod_{j=1}^{k-1}(1 + x^j)^2\\=1+x+x^2+3 x^3+4 x^4+6 x^5+10 x^6+15 x^7+...
0
votes
0answers
143 views

Representation of a number as a sum of co-prime numbers

Conventions We will call the following product the canonical expansion of $a$: $$a = \prod\limits_{p_i\in\mathbb{P}}p_i^{\alpha_i}.$$ If $a$ and $b$ are co-prime we write $$a \perp b.$$ $\beth$-...
1
vote
0answers
78 views

An arithmetic function involving arbitrary (but fixed) number of divisors

I need at least basic information about generating functions of the following class of arithmetic functions, grouped by levels $k$. Fix some $k$ and some family $\varepsilon_*=(\varepsilon_\sigma)_{\...
0
votes
0answers
140 views

What is known about Carmichael function distribution and growth?

Let $\lambda(n)$ be the Carmichael Lambda Function of $n$. We know that for every $m$ there is the largest $n_m\in\Bbb N$ such that for every $n>n_m$ we have $\lambda(n)\neq m$ and $\lambda(n_m)=m$...
4
votes
2answers
236 views

Congruences for the non-divisors of Euler's $\phi(n)$

If $n$ is composite, then $\phi(n) < n-1$: hence, there is at least one number $d$ which does not divide $\phi(n)$ but divides$(n-1)$. We shall call $d$ the totient divisor of $n$. The purist will ...
0
votes
0answers
60 views

Counting different residue classes of certain form modulo $4abc-1$?

I posted http://math.stackexchange.com the question and after a while I did not received any reply, so I thought maybe I re-post it here again, maybe some people are interested. I like to calculate ...
3
votes
0answers
133 views

Mersenne number with small Carmichael function

Let $\lambda(\cdot)$ be the Carmichael function. I'm trying to understand the magnitude of the smallest values of $\lambda(2^n - 1)$, when $n$ runs over the positive integers. Precisely my question is:...
16
votes
2answers
871 views

Does 53 diverge to infinity in this Collatz-like sequence?

This function has been explored a bit at MSE (in June 2016): \begin{eqnarray} f(n) &=& (n-1)^2 \; \textrm{if} \; (n \bmod 4) = 1\\ f(n) &=& \lfloor n/4 \rfloor \; \textrm{otherwise} \...
5
votes
1answer
323 views

Does anyone recognize this exponential sum?

For $a$, $b$ two integers, let $(a,b)$ denotes their gcd. We define the following exponential sum : $$G_q(n):=\sum_{d|q,~(d,q/d)=1}{e^{2i\pi n\frac{dd'}{q}}}$$ for $n$ a non-negative integer and $q$ ...
4
votes
0answers
210 views

The properties of Pos

Given $n\in\mathbb{N}$, and $f:\mathbb{N}^*\rightarrow \mathbb{N}$, let define $Pos$ as: $$Pos(f)(n)= |\{x \leq n, f(x)=f(n)\}|$$ When given $n\in\mathbb{N}$, this function gives the 'position' of $...
1
vote
0answers
232 views

On even almost perfect numbers other than powers of two

(Note: This question is an improved version of and has been cross-posted from this MSE post.) Let $\sigma(x)$ denote the sum of the divisors of $x$. If $\sigma(x) = 2x - 1$, then we call $x$ an ...
8
votes
2answers
491 views

Asymptotics of product of Euler's totient function (A001088)?

Conjecture: \begin{align} \lim_{n\to \infty } \, \frac{\left(\prod _{k=1}^n \phi (k)\right){}^{1/n}}{n}\sim 0.2059\text{...} \end{align} The numerical result from 100000 terms is: My questions are: ...
4
votes
2answers
451 views

Are there multiplicative functions which are not rational?

Vaidyanathaswamy calls an arithmetic function rational if it is the convolution of some finite collection of functions which are either completely multiplicative or inverse to a completely ...
0
votes
1answer
338 views

Sum of digits of a power [closed]

Are there any explicit formula for a sum of digits for a power in the given base? A problem to be specific: find a sum of digits for a number $2^{100}$ in the system with a base 5. In the system with ...
6
votes
1answer
278 views

A question about $(0,1]$-valued multiplicative functions

Suppose $f:\mathbb{N}\to [0,1]$ is a multiplicative function (i.e. $f(nm)=f(n)f(m)$ whenever $m$ and $n$ are coprime). Suppose $f$ has non-zero mean, which means $$ \lim_{N\to\infty}\frac{1}{N} \sum_{...
13
votes
1answer
756 views

Is the set of multiplicatively even numbers thick?

A positive integer is multiplicatively even (odd) if, when decomposed into primes, the sum of the exponents is even (odd). A subset of the integers is thick if it contains arbitrarily long intervals $\...
2
votes
0answers
71 views

Discrete “difference” equations that involve changes in both shift and scale

A standard use of the Z-transform ($F(z) = \sum_n (f[n] \cdot z^{-n} )$) is to understand the effect of a difference equation on a signal. For instance: $y[n] = x[n] + y[n-1]$ $Y(z) = X(z) + Y(z) \...
1
vote
1answer
145 views

estimate an sum

I need estimate the following sum: $\sum_{d=1}^{n}\frac{\mu(d)}{d}\sum_{k=1}^{\lfloor n/d\rfloor}\frac{1}{k}\frac{q^k}{1-q^{-kd}}$, where $q>1$ and $\mu$ is the Möbius function. To obtain the ...
2
votes
0answers
273 views

Infinite sums with Mobius Inversion : can we have uniform convergence of inversion formula?

My question is on Mobius inversion formula convergence/properties when used with infinite sums of function. Lets consider (on $\mathbb{R}^{+}$): $$S(x)= \sum\limits_{n=1}^{\infty} f(nx)$$ We call $...
1
vote
1answer
158 views

Existence of arithmetic function satisfying a certain property

I was interested in an arithmetic function satisfying a certain property, I am not sure at the moment if such thing even exists or not. But I was wondering maybe I could get some hint or idea or input ...
2
votes
1answer
231 views

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

This question was also asked on MSE. 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 ...
1
vote
0answers
50 views

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

A function is called quasi-multiplicative by many authors if $f(m)f(n)=f(1)f(mn)$, a slight generalization of multiplicativity. (Basically a multiplicative function times a constant is a quasi-...
4
votes
0answers
250 views

A closed formula for this arithmetic function

The following function comes up in my research as part of a sufficient condition for capability of $p$-group of class two and prime exponent. Given a nonnegative integer $m$, express $m$ as a ...
6
votes
0answers
307 views

$n\varphi(n)\equiv 2\pmod{\sigma(n)}$ as a primality test

It is known from Subbarao, "On two congruences for primality" that $n>22$ is a prime iff $$n\sigma(n)\equiv 2\pmod{\varphi(n)},$$ where $\varphi(n)$ is Euler's function and $\sigma(n)$ is sum of ...
-1
votes
1answer
239 views

Are all known $k$-multiperfect numbers (for $k > 2$) not squarefree?

I asked the following question in MSE four ($4$) days ago, but so far nobody has posted an answer. The gist of the question is as follows: Are all known $k$-multiperfect numbers (for $k > 2$...
1
vote
2answers
185 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 ...
4
votes
1answer
711 views

Menon’s identity

I also put this question in stackexchange, but remained unanswered. https://math.stackexchange.com/questions/506996/menons-identity Let $G$ be a group of order $n$. Consider an action of $U_n$, the ...
2
votes
1answer
282 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
0answers
291 views

Maximal order of Hooley's Delta function?

There is a large literature on Hooley's $$ \Delta(n)=\max_u\sum_{d|n,\ e^u\le d< e^{u+1}}1 $$ giving its normal and average order. What is known of its maximal order? Clearly $\Delta(n)\le d(n)$ ...