43 votes

Expressing the Riemann Zeta function in terms of GCD and LCM

Let me denote your LHS by $f(n,s)$. For fixed even $n$ I shall show that $f(n,s)-1\sim\zeta(s+1)-1$ as $s\to\infty$, that is, $$\lim_{s\to\infty}\frac{f(n,s)-1}{\zeta(s+1)-1}=1.$$ This result nicely ...
Wojowu's user avatar
  • 27.4k
39 votes

Expressing the Riemann Zeta function in terms of GCD and LCM

A variety of formulas of this type (in the sense of a relation between $\zeta(s)$ and a sum over gcd or lcm) has been derived by Titus Hilberdink and László Tóth in On the average value of the least ...
Carlo Beenakker's user avatar
24 votes
Accepted

Find all $m$ such $2^m+1\mid5^m-1$

Here is a proof. Theorem. $2^m+1$ never divides $5^m-1$. Assume that there is some $m$ such that $2^m+1$ divides $5^m-1$. We already know that $m$ must be divisible by $4$. Let $m = 2^n a$ with an ...
Michael Stoll's user avatar
22 votes

Find all positive integers $n$ such that $n+\tau{(n)}=2\varphi{(n)}$

First of all, if $n$ is even, then $\varphi(n)\leq n/2$, so $n\geq 2\varphi(n)$. Therefore, $n$ is always odd and so is $\tau(n)$. Thus, as Gerhard noticed, $n=m^2$ for some odd integer $m$. ...
Alexander Kalmynin's user avatar
19 votes

$\frac{\sigma(n)}{n} < e \ln \ln (n)$ is true?

Wikipedia says Robin proved unconditionally that the inequality $${\sigma(n)\over n}<e^{\gamma}\log\log n+{0.6483\over\log\log n}$$ holds for all $n\ge3$. I believe this is in the same paper as the ...
Gerry Myerson's user avatar
18 votes
Accepted

Does the Prime Number Theorem have anything to do with Erdos-Kac law or vice versa?

Yes. The number of prime factors of a number is distributed roughly like a Poisson process of expectation $\log \log n$, so the probability of exactly one prime factor is roughly $e^{- \log \log n} = ...
Will Sawin's user avatar
  • 135k
17 votes
Accepted

Is the divisor counting function equidistributed mod $p$?

$\newcommand{\Y}{\mathfrak{X}_p(X)}$I haven't checked all the details on the application of Selberg–Delange below, so it's possible something I am saying is nonsense, but even after accounting for the ...
Anurag Sahay's user avatar
  • 1,191
14 votes
Accepted

Number of matrices with bounded products of rows and columns

This problem was considered in passing in the proof of Theorem 4.1 in Granville and Soundararajan, see the argument starting at the bottom of page 17. They show (in your notation) that $M_d(x)$ is of ...
Lucia's user avatar
  • 43.3k
13 votes

Find all $m$ such $2^m+1\mid5^m-1$

There might well be a very elementary argument for this, but in the spirit of taking a hammer to a fly, one can prove that the number of $m$ such that $$ 2^m+1 \mid 5^m-1 $$ is finite by invoking a ...
Mike Bennett's user avatar
  • 2,381
12 votes
Accepted

How to obtain an upper bound for $\prod_{p\mid N} (1 + 1/\sqrt{p})$ where $N$ is square free?

The $N$ for which this product is largest will be of the form $N = \prod_{p<y} p$, so that $\log N \sim y$. For this $N$, $$ \log \prod_{p\mid N} \bigg( 1+\frac1{\sqrt p} \bigg) = \sum_{p\mid N} \...
Greg Martin's user avatar
  • 12.7k
12 votes
Accepted

Greatest common divisor of $(a^n+1,b^n+1)$

I think that this sort of question was originally asked by Ailon and Rudnick, but they use $-1$ instead of $+1$ and asked if $\gcd(2^n-1,3^n-1)=1$ for infinitely many $n$. In this setting, for more ...
Joe Silverman's user avatar
11 votes
Accepted

Sum of divisors below threshold

Put $$ B= C \frac{\log (10\sigma(n)/n)}{\log \log (10 \sigma(n)/n)} $$ for a suitably large positive constant $C$. Then I claim that the desired inequality holds with $$ D = \frac{n}{(\log n)^B},...
Lucia's user avatar
  • 43.3k
11 votes

Has it been proved that odd perfect numbers cannot be triangular?

Curiously enough, I asked myself the same question several days ago... I couldn't settle it; yet, resorting to Jacques Touchard's theorem on the form of odd perfect numbers (cf. J. A. Holdener, "...
José Hdz. Stgo.'s user avatar
11 votes
Accepted

"Oddity" of Fibonacci-Catalan numbers

Let $\alpha=(1+\sqrt{5})/2,\beta=(1-\sqrt{5})/2$, then by Binet formula for Fibonacci numbers we have $F_n=(\alpha^n-\beta^n)/(\alpha-\beta)=:P_n(\alpha,\beta)$. Factorize our Catalan-like expression ...
Fedor Petrov's user avatar
11 votes

$\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)$ Double Summing a (Not Completely) Multiplicative Function

One underappreciated but useful fact about multiplicative functions is the following: if $f(n)$ is multiplicative, and $k$ is any positive integer such that $f(k)\ne0$, then the function $g(n) = f(nk)/...
Greg Martin's user avatar
  • 12.7k
11 votes
Accepted

How many divisors of $n$ are below $n^{1/3}$?

One thing you asked for is a lower bound. Following FusRoDah, I will let $d_k(n)$ be the number of divisors of $n$ of size less than $n^{1/k}$, and $d(n)$ be the number of divisors of $n$. Then I ...
Will Sawin's user avatar
  • 135k
10 votes

Does the Prime Number Theorem have anything to do with Erdos-Kac law or vice versa?

The right context of your question is probably the area of Beurling primes. An arithmetic semigroup is a semigroup $(G,\cdot)$ together with a norm $\|\cdot\|:G\rightarrow[1,\infty)$, such that $\|gh\|...
Jan-Christoph Schlage-Puchta's user avatar
10 votes

Is every prime the largest prime factor in some prime gap?

Heuristically this should be the case. For any prime p greater than 5, consider the set of numbers of the form $2^a3^b5^c p \pm 1$. The "probability" that one of of these is prime should be about $$\...
JoshuaZ's user avatar
  • 6,090
10 votes
Accepted

Is the factorization of $a_m-a_n$ affected by the fact that $\Sigma \frac{1}{a_k}<+\infty$?

No, this is false. Define $a_1=1$, and for all $k \geq 2$ let $a_k = \big\lfloor \frac{k}{2}\big\rfloor^2$. Note that $\sum_{k=1}^\infty \frac{1}{a_k}$ converges since it is equal to $1+2\sum_{k=1}^{...
Tony Huynh's user avatar
  • 31.5k
10 votes
Accepted

On the diophantine equation $x^{m-1}(x+1)=y^{n-1}(y+1)$ with $x>y$, over integers greater or equal than two

You can make a lot of progress if you're willing to assume a deep conjecutre. The $N$-variable generalization of the $abc$-conjecture (https://en.wikipedia.org/wiki/N_conjecture) applied to your ...
Joe Silverman's user avatar
9 votes
Accepted

There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$

The claim is true. Here is the proof, in several steps. Proposition 1: Let $n = 6k + 1$ be composite. If $n$ has less than three non-totient divisors (NTD for short), then $n$ falls in one of the two ...
WhatsUp's user avatar
  • 3,232
9 votes
Accepted

On a problem that equates $\frac{\text{prime}-1}{\operatorname{rad}(\text{prime}-1)}$ with the sequence of primorials

The conjecture is false, and in fact every positive integer $k\geq 1$ lies in $\mathcal{K}$. Here is a proof. Let us fix $k\geq 1$. Let $\pi(x;N_k^3,N_k^2+1)$ be the number of primes $p\leq x$ such ...
GH from MO's user avatar
  • 98.2k
9 votes
Accepted

Do the following binary vectors span $\mathbb{R}^n$?

Let $v_{r,d}$ be an infinite sequence defined in the same way, and let $V_m$ be the span of all corresponding sequences with $d\leq m$. For a fixed $d$, the linear span of all $v_{r,d}$ is the set of ...
Ilya Bogdanov's user avatar
9 votes

Is there a similar formula like Ramanunjan's Eisenstein series identity for $\sum_{k=1}^{n-1}k^2 \sigma(k)\sigma(n-k)$?

All these identities can indeed be proved essentially trivially using modular forms and quasi-modular forms (those involving $E_2$), and the fact that the dimension of such spaces is $1$ for weight 4,...
Henri Cohen's user avatar
  • 11.5k
9 votes
Accepted

On a GCD approach to odd perfect numbers

As I mentioned in another answer, using GCDs and fractions is usually a bad idea. Here is how I would interpret all of this material. Let $N$ be an odd perfect number. Write its prime factorization ...
Pace Nielsen's user avatar
8 votes

Are there an infinite number of integers $n$ such that $n, n+1$, and $n+2$ have the same number of divisors?

I will convert my comment into an answer, since I suspect it is still the state of the art. The version of your question for two consecutive integers was proved in Heath-Brown, D. R. (1984). The ...
Tony Huynh's user avatar
  • 31.5k
8 votes
Accepted

Piltz Divisor Problem

You've discovered some of the primary motivation for the invention of the Dirichlet hyperbola method. Since $\tau_k = \tau_{k-1}*1$ (which you are already using), you can take advantage of the extra ...
Greg Martin's user avatar
  • 12.7k
8 votes
Accepted

Is there a similar formula like Ramanunjan's Eisenstein series identity for $\sum_{k=1}^{n-1}k^2 \sigma(k)\sigma(n-k)$?

Numerical experiments suggest that $$A_2(n) := \sum_{k=1}^{n-1} k^2\sigma(k)\sigma(n-k) = \frac{n^2}{8}\sigma_3(n) - \frac{4n^3-n^2}{24}\sigma(n).$$ PS. In fact, it directly follows from the quoted ...
Max Alekseyev's user avatar
8 votes
Accepted

Divisibility chains and polynomials

Every $P$ is a counterexample. Indeed, given a polynomial $P$ consider the recursive sequence $b_{n+1}=f(b_n)$ where I take $f(x)=x+P(x)$, say. Then $P(b_{n+1}) = P(b_n + P(b_n)) \equiv P(b_n) \equiv ...
Ofir Gorodetsky's user avatar
8 votes
Accepted

Divisibility of Stirling numbers

The Stirling numbers of the first kind satisfy $x^{\underline{n}} = \sum_{k=0}^n s_1(n,k)x^k$. For $n > 0$ we have $s_1(n, 0) = 0$, $s_1(n, 1) = (-1)^{n-1}(n-1)!$, $s_1(n, n) = 1$. If $n > 1$ ...
Peter Taylor's user avatar
  • 6,516

Only top scored, non community-wiki answers of a minimum length are eligible