Questions tagged [divisors-multiples]
For questions on divisors and multiples, mainly but not exclusively of integers, and related and derived notions such as sums of divisors, perfect numbers and so on.
39 questions
2
votes
1
answer
516
views
On comparing two almost injective divisor maps
Edit 2018.08.08 This answer https://mathoverflow.net/a/307881 will be updated to give recent information about S, especially a forthcoming preprint. End Edit 2018.08.08
In an introductory post on ...
- 13k
12
votes
1
answer
2k
views
Power of primes
$n$ is a natural number $>1$, $\varphi(n)$ denotes the Euler's totient function, $P_n$ is the $n^\text{th}$ prime number and $\sigma(n)$ is the sum of the divisors of $n$. Consider the expression:
$...
- 45
10
votes
7
answers
2k
views
Getting a bound on the coefficients of the factor polynomial
Suppose $f(x):=a_0+a_1x+\cdots+a_nx^n$ is a polynomial in $\mathbb{Z}[x]$ and $|a_i|\leq M$ for each $i=0,\ldots ,n.$ Now suppose $g(x)$ is a factor of $f(x)$ in $\mathbb{Z}[x]$, then is it possible ...
- 1,305
3
votes
1
answer
356
views
Primitive sequence $a_i$ attaining Pillai's bound on $\sum_{i} 1/a_i$
A primitive sequence $1<a_1<\ldots<a_k\leq n$ is a sequence of integers no one of which divides any other, investigated by Erdos, Behrend and others, over the last 80 years. In fact, $\max k=\...
- 10.4k
9
votes
0
answers
695
views
Van der Pol's identity for the sum of divisors and a quartic polynomial equation for odd perfect numbers
In Touchard (1953) it is mentioned that the sum of divisors $\sigma(n)$ satisfies the following recurrence relation ($n>1$):
$$n^2(n-1) = \frac{6}{\sigma(n)} \sum_{k=1}^{n-1}(3n^2-10k^2)\sigma(k)\...
- 213
8
votes
2
answers
722
views
Is there a similar formula like Ramanunjan's Eisenstein series identity for $\sum_{k=1}^{n-1}k^2 \sigma(k)\sigma(n-k)$?
This question is related to the last question about van der Pol's identity for the sum of divisors.
In Touchard (1953) it is mentioned that the sum of divisors $\sigma(n)$ satisfies the following ...
- 3,124
7
votes
1
answer
303
views
Large gaps between consecutive irreducible polynomials with small heights
For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then $N+2,\...
- 13.4k
5
votes
2
answers
1k
views
A truncated divisor function sum
Let $d(n)$ be the number of divisors function, i.e., $d(n)=\sum_{k\mid n} 1$ of the positive integer $n$. The following estimate is well known
$$
\sum_{n\leq x} d(n)=x \log x + (2 \gamma -1) x +{\cal ...
- 10.4k
5
votes
1
answer
960
views
There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$
If $n$ is composite then $\phi(n) < n-1$ (Euler's totient function) hence there must be one or more divisors of $n-1$ which do not divide $\phi(n)$. For lack of a better terminology, let us call ...
- 5,470
2
votes
1
answer
928
views
Is there a formula that can predict the primes in the sequence of ratios of consecutive superior highly composite numbers? : $2, 3, 2, 5, 2, 3, 7,...$
This is the sequence of prime numbers which are the elementary building blocks for the superior highly composite numbers:
$2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 2, 23, ...$
The $n^{th}$ ...
- 341
2
votes
1
answer
345
views
On odd perfect numbers $q^k n^2$ satisfying $n^2 - q^k = 2^r t$
Let $N = q^k n^2$ be an odd perfect number with special prime $q$, satisfying
$$n^2 - q^k = 2^r t$$
where $r \geq 2$ and $\gcd(2,t)=1$.
We could prove that:
(1) $2^r t > 2n$. (We can modestly ...
2
votes
0
answers
751
views
Does $n \mid \sigma(n^2)$, if $q^k n^2$ is an odd perfect number?
Let $\sigma(x)=\sigma_1(x)$ be the classical sum of divisors of the positive integer $x$.
It is known that
$$\gcd(\sigma(q^k),\sigma(n^2))=\frac{\bigg(\gcd(n,\sigma(n^2))\bigg)^2}{\gcd(n^2,\sigma(n^2))...
2
votes
2
answers
643
views
On the nearest-square function and the quantity $m^2 - p^k$ where $p^k m^2$ is an odd perfect number
This question has been cross-posted from this MSE question and is an offshoot of this other MSE question.
(Note that MSE user mathlove has posted an answer in MSE, which I could not completely ...
1
vote
1
answer
321
views
On odd perfect numbers and a GCD - Part III
Let $m = q^k n^2$ be an odd perfect number with special prime $q$ satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$.
It is known that
$$\gcd(\sigma(q^k),\sigma(n^2)) = \frac{(\gcd(n,\sigma(n^...
49
votes
4
answers
4k
views
Strange (or stupid) arithmetic derivation
Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to ...
- 3,004
36
votes
2
answers
7k
views
Why do primes dislike dividing the sum of all the preceding primes?
I was investigating primes with the property that the sum of the first $n$ primes is divisible by $p_n$. It turns out that these primes are extremely extremely rare. For primes less than $10^9$, I ...
- 5,470
10
votes
4
answers
4k
views
Sum of the sum-of-divisors function
I was looking at the abstract of a paper 1 which claims that [2] and [3] prove
$$
\sum_{n\le x}\sigma(n)-\frac{\pi^2}{12}x^2=\Omega(x\log\log x).
$$
But I cannot find the above—or indeed, ...
- 9,114
9
votes
1
answer
558
views
Is the divisor counting function equidistributed mod $p$?
Let $\sigma_0(n)$ be the divisor counting function:
$$\sigma_0(n) = \sum_{d \vert n} 1.$$
I ran some numerical experiments that showed when $p$ is prime, the function $\sigma_0(n)$ is equidistributed ...
- 1,949
9
votes
1
answer
1k
views
Sum of divisors below threshold
Let $\sigma(n)$ denote the sum of divisors of $n$, that is,
$$
\sigma(n) = \sum_{d | n} d.
$$
It is known that $\sigma$ can have values as large as order $n \log \log n$. However, obviously the sum is ...
- 2,227
8
votes
1
answer
305
views
Identity?: $\frac{\varphi(2^n-1)}{n}=\frac{2^{\varphi(2^n-1)}-1 \bmod (2^n-1)^2}{2^n-1}$
The computer found this.
Let $n$ be a positive integer.
Up to $n=200$ we have:
$$\frac{\varphi(2^n-1)}{n}=\frac{2^{\varphi(2^n-1)}-1 \bmod (2^n-1)^2}{2^n-1}. \tag{1}\label{483144_1}$$
Q1 Is \eqref{...
- 25.4k
6
votes
0
answers
535
views
When is $ \sigma(n!-1) $ a perfect square?
I am looking for pairs of positive integers $(m,n)$ such that $ \sigma(n!-1) =m^2$, where $\sigma$ is the sum of divisors function. Examples occur with $(m,n)=(12,5),(1,2)$.
Question: Are there ...
user99666
6
votes
0
answers
506
views
Does the equation $\sigma(\sigma(x^2))=2x\sigma(x)$ have any odd solutions?
This question was posted in MSE in early August 2020. It did garner several upvotes, but did not receive any responses. I have therefore cross-posted it here, hoping that it gets answered.
Let $\...
6
votes
0
answers
222
views
Growth rate of signed sum of $N \sigma_0(n)-\sigma_1(n)$
Let $\sigma_k(n)=\sum_{d|n} d^k,$ for a positive integer $n$ and $k\geq 0$. A lot is known about the averages for the functions $\sigma_k(n),$ such as the estimates
$$
\sum_{n\leq x} \sigma_0(n)=x \...
- 10.4k
5
votes
0
answers
772
views
The Grimm Machine(s): A Collatz Conjecture Rival?
Edit 2018.08.08 This answer https://mathoverflow.net/a/307881 will be updated to give recent information about S, especially a forthcoming preprint. End Edit 2018.08.08
Just as the Collatz ...
- 13k
5
votes
2
answers
403
views
Estimating $\sum_{n\leq x: n \in A} d(n)^a$ from below for large sets $A\subset \{1,2,\ldots,x\}.$
I apologise for the long-windedness of this question.
Let $a$ be a positive real constant and let $d(n)$ denote the number of divisors of $n.$ Define
$$
S_a(x)=\sum_{n\leq x} d(n)^a.
$$
For $a=1,$ ...
- 10.4k
5
votes
0
answers
171
views
Touchard / van der Pol's identity for the sum of divisors and an elliptic curve for perfect numbers
In Touchard (1953) it is mentioned that the sum of divisors $\sigma(n)$, satisifies the following recurrence relation ($n>1$):
$$n^2(n-1) = \frac{6}{\sigma(n)} \sum_{k=1}^{n-1}(3n^2-10k^2)\sigma(k)\...
- 213
3
votes
0
answers
180
views
Does this Theorem 2 from Dandapat et al. imply that $\gcd(\sigma(p^k),\sigma(a^2)) > 1$?
Write the odd perfect number $m=p^k a^2$ as a product of primes
$$m = p^k {p_1}^{2a_1} \cdots {p_v}^{2a_v}.$$
(Note that it is known that $v \geq 9$ by work of Nielsen.) Let $N(m)$ be the number of ...
3
votes
0
answers
82
views
Estimating from below positive moments of "clipped" divisor function on subsets of $\{1,2,\ldots,x\}$ with positive density
The question here about estimating positive moments of the divisor function on sets of nonzero density $A\subset \{1,2,\ldots,x\}$ was answered giving
$$
S_a(x):=\sum_{n \in A} d(n)^a \geq |A|(\ln x)^{...
- 10.4k
3
votes
1
answer
318
views
Problem related to Frobenius coin problem
Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ good if,
for any $r,s,u,...
- 13.9k
3
votes
4
answers
1k
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 ...
3
votes
2
answers
795
views
Estimate about primes
Can anyone give an estimate (upper bound or lower bound) for the number of divisors $d\mid P_r$ such that $\frac{\sqrt{P_r}}{2}< d < \sqrt{P_r}$, where $P_r$ is the product of the $r$ smallest ...
- 499
2
votes
1
answer
326
views
Does there exist an integer that is both solitary and almost perfect?
This question is an offshoot from the following MSE post. I hope that it is appropriate for this site.
Let $\sigma(x)$ be the sum of the divisors of $x$.
An integer $a$ is said to be solitary if ...
1
vote
1
answer
466
views
Some divisibility constraints in Frobenius coin problem
Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...
- 13.9k
1
vote
0
answers
106
views
Lower bound on a Truncated Divisor Sum
Let $d(n)$ be the number of divisors function, i.e., $d(n)=\sum_{k\mid n} 1$ of the positive integer $n$.
I am interested in estimating, the following sum
$$
A(a,x)=\sum_{n\leq x} \min[ d(n), M]^a
$$
...
- 10.4k
1
vote
2
answers
387
views
Improving the lower bound $I(n^2) > \frac{2(q-1)}{q}$ when $q^k n^2$ is an odd perfect number
Let $N = q^k n^2$ be an odd perfect number with special prime $q$ satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$.
Define the abundancy index
$$I(x)=\frac{\sigma(x)}{x}$$
where $\sigma(x)$ ...
1
vote
0
answers
167
views
On "Euclidean" odd perfect numbers
In what follows, we let $N = r^s u^2$ be an odd perfect number given in Eulerian form, i.e. $r$ is the special prime satisfying $r \equiv s \equiv 1 \pmod 4$ and $\gcd(r,u)=1$. In this preprint, ...
0
votes
0
answers
759
views
On sets of coprime integers in intervals
Briefly,
Question: Is it "good enough" to use least prime factor in choosing a maximal set of coprime integers in an interval?
The post title comes from a 1993 paper of Erdos and Sarkozy. They ...
- 13k
0
votes
1
answer
146
views
On $\mathsf{LCM}$ of a set of integers
For integers $a,b$ define $$\mathcal R(a,b)=\{q\in\mathbb Z\cap[1,\min(a,b)]: a\equiv b\bmod q\}$$ and $\mathsf{LCM}(\mathcal R(a,b))$ to be $\mathsf{LCM}$ of all entries in $\mathcal R(a,b)$.
How ...
- 1,836
-10
votes
1
answer
556
views
Arithmetic billiards, prime numbers and the Goldbach conjecture
I've edited the following post on Mathematics Stack Exchange, (now closed, at that date I'm suspended) with identifier 4510963, please let me to know if you've some doubt or I can improve the post.
On ...
