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 ...
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 ...
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 ...
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$. ...
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 ...
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} = ...
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 ...
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 ...
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 ...
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} \...
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 ...
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},...
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, "...
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 ...
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)/...
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 ...
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\|...
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 $$\...
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}^{...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
divisors-multiples × 225nt.number-theory × 209
analytic-number-theory × 67
perfect-numbers × 46
prime-numbers × 41
reference-request × 24
arithmetic-functions × 18
diophantine-equations × 14
co.combinatorics × 13
integer-sequences × 13
polynomials × 10
factorization × 10
conjectures × 10
inequalities × 9
asymptotics × 6
open-problems × 6
additive-combinatorics × 5
congruences × 5
probabilistic-number-theory × 5
ds.dynamical-systems × 4
sequences-and-series × 4
riemann-hypothesis × 4
stirling-numbers × 4
ac.commutative-algebra × 3
matrices × 3