All Questions
Tagged with nt.number-theory prime-numbers
315 questions
24
votes
1
answer
2k
views
When is the product $(1+1)(1+4)…(1+n^2)$ a perfect square?
This is a modification of an unanswered problem on the math StackExchange.
When is the product $(1+1)(1+4)…(1+n^2)$ a perfect square?
If $(1+1)(1+4)…(1+n^2)=k^2$ then one possibility is $n=3$, $k=...
- 1,021
19
votes
3
answers
2k
views
Stronger versions of Wilson's Theorem
Problem
Let $c \in \mathbb{N}$ $;$ $\exists$ a prime $p$ for which:
$$p^c \mid (p-1)!+1$$
Does $\exists$ $M$ $\in$ $\mathbb{N}$ $;$ $\forall$ $c \geqslant M$
$;$ $\nexists$ $p$ ...
- 371
19
votes
1
answer
3k
views
Sums of primes that are themselves prime
I'm not a math expert so this may be a trivial question; if $p_i$ is the $i$-th prime, let:
$$S(n) = \sum_{i=1}^n p_i$$
be the sum of the first $n$ primes and
$$P(n) = | \{1 \leq i \leq n \mid S(...
- 1,602
19
votes
2
answers
1k
views
Floors of rationals to powers: Infinite number of primes?
Let $r=a/b$ be a rational number in lowest terms, larger than $1$,
and not an integer (so $b > 1$).
Q. Does the sequence
$$ \lfloor r \rfloor, \lfloor r^2 \rfloor, \lfloor r^3 \rfloor,
\...
- 151k
17
votes
3
answers
2k
views
About the prime divisors of values of polynomials
Let $P$ be a polynomial having integer coefficients (and degree $\geq 3$), and let $\mathscr P_P$ be the set of prime numbers dividing some value $P(n)$ with $n \in \mathbb Z$.
Is it true that $\...
- 3,866
16
votes
1
answer
1k
views
Elementary Proof of Infinitely many primes $\mathfrak{p} \in \mathbb{Z}[i]$ in the sector $\theta < \arg \mathfrak{p} <\phi $
A quick look at the primes in $\mathbb{Z}[i]$ suggests they might be evenly distributed by angle if we zoom out on a coarse enough scale.
I would like ask about the much weaker statement forgetting ...
- 22.8k
15
votes
6
answers
7k
views
Prime factorization of n+1
If $n=\prod_{i=1}^{k} p_i^{e_i}$ is a prime factorization of integer $n$.
Is there a quick way to find the prime factorization of $n+1$?
Or the only way to do it is recalculating the whole ...
- 342
12
votes
1
answer
869
views
Analytic lower bounds on the first sign change of pi(x) - li(x)?
There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...
- 9,114
12
votes
1
answer
547
views
Seeking references for finding primes infinitely often
I've been pondering this weakened version of the finding primes problem for a while:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?
This differs from ...
- 2,302
12
votes
3
answers
929
views
Mertens-like sum in arithmetic progressions
I find myself needing a good estimate for $\sum_{p\le x,\, p\equiv a\bmod q} 1/p$, perhaps something like
$$
\sum_{p\le x,\, p\equiv a\bmod q} \frac1p = \frac{\log\log x}{\phi(q)} + b(q,a) + O\big(\...
- 12.8k
12
votes
3
answers
3k
views
111...11 base p = 111...11 base q
Feels like I am probably missing something obvious.
Are there distinct primes $p,q$ and positive integers $m,n$ such that
$$ \sum_{i=0}^{n} p^i = \sum_{j=0}^{m} q^j$$
Guessing the answer is no, but ...
- 129
12
votes
1
answer
1k
views
Why do the Maynard-Tao weights work so well?
I am looking for an intuitive reason for why the Maynard-Tao weights work well to capture many primes of the form $n+h_1, \ldots , n+h_k$, where $(h_1, \ldots , h_k)$ is any admissible $k$-tuple.
For ...
- 2,283
12
votes
1
answer
1k
views
Prime Power Gaps
In 2000, Baker, Harman and Pintz proved that there is always a prime in
the interval $(n-n^{0.525}, n)$. There are also conditional results
implying smaller intervals. Nevertheless, I could not find ...
- 385
11
votes
1
answer
2k
views
Distribution of the number of prime factors
Count the number of prime factors of a number $n$
to include multiplicity,
so that
$$n=24=2^3 \cdot 3 = 2 \cdot 2 \cdot 2 \cdot 3$$
has $4$ prime factors, and
$$n =
6500 =
2^2 \cdot 5^3 \cdot 13 =
2 \...
- 151k
11
votes
2
answers
1k
views
Update for 2015: least prime of form nq+1, with q prime?
I have received a complaint about my 2011 answer
least prime in a arithmetic progression
which, indeed, gives conflicting reports about this:
given a prime $q,$ what can we say about an upper ...
- 25.7k
11
votes
1
answer
700
views
Squarefree numbers $n$ such that $432n+1$ is also squarefree
This is a second attempt (see Primes $p$ such that $432 p +1$ is prime)
Is the set of squarefree numbers $n$ such that $n(432 n+1)$ is also squarefree known to be infinite?
Fact: the number of such ...
- 123
11
votes
1
answer
1k
views
The Bombieri Vinogradov Theorem restricted to moduli divisible by $k$
The Bombieri-Vinogradov Theorem states that given $A>0$, there exists $B>0$ such that for $Q=\sqrt{x}\left(\log x\right)^{-B},$ we have $$\sum_{q\leq Q}\max_{y\leq x}\max_{\begin{array}{c}
a\...
- 11.4k
10
votes
1
answer
694
views
Set of prime numbers $q$ such that $\sum\limits_{p\leq\sqrt{q}}p=\pi(q)$, where $p$ are prime numbers
The question is: does the set of prime numbers $q$ such that $\sum\limits_{p\leq\sqrt{q}}p=\pi(q)$, where $p$ are prime numbers, contain infinitely many elements? You can find the first elements here (...
- 189
10
votes
1
answer
708
views
Primes dividing $2^a+2^b-1$
From Fermat's little theorem we know that every odd prime $p$ divides $2^a-1$ with $a=p-1$.
Is it possible to prove that there are infinitely many primes not
dividing $2^a+2^b-1$?
(With $2^a,2^...
- 3,866
10
votes
1
answer
469
views
Asymptotic behavior of a certain sum of ratios of consecutives primes
I am looking for the asymptotic growth of the following sum
$$\sum_{k=1}^{n}\frac{p_{k+1}+p_k}{p_{k+1}-p_k}$$
where $p_k$ stands for the prime of index $k$.
Manual computations show, for small values ...
- 1,008
9
votes
1
answer
527
views
Infinitely many primes coming from Euclid's proof
When teaching Euclid's classic proof of the infinitude of primes today, the following question appeared to me. Let $p_1,p_2,p_3,\ldots$ be the prime numbers, listed in increasing order. Set
$$k_n = ...
- 91
8
votes
1
answer
1k
views
Number field analogue of the Goldbach Conjecture
Is there a generalization of Goldbachs conjecture for prime ideals in number fields?
- 81
7
votes
1
answer
531
views
Primes arising from permutations
Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...
- 15.6k
7
votes
2
answers
679
views
What is wrong with this deterministic algorithm efficiently generating large primes?
According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. ...
- 25.4k
7
votes
1
answer
1k
views
Heuristic for Montgomery's conjecture
This is my third question on this site regarding Montgomery's conjecture -- and I apologize
if this is too much -- but I am still not understanding well why this conjecture is believed to be true.
...
- 26k
7
votes
1
answer
1k
views
What would be the consequences of $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log k}$?
The question is in the title: what would be the number theoretic consequences if we managed to establish the conjectured asymptotic equality $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log ...
- 6,984
6
votes
2
answers
804
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 25.4k
6
votes
5
answers
530
views
Arbitrarily long composite anti-diagonals?
Plot points $(a,b) \in \mathbb{N}^2$ if gcd$(a,b) \neq 1$.
Call such points composite points.
Call a sequence of points $(a+i,b-i), i=0,\ldots,k$
a composite anti-diagonal if all are composite points.
...
- 151k
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
5
votes
1
answer
434
views
consecutive prime gaps and explicit bound
I am aware of the theorem that $p_{n+1}- p_n \leq n^{0.525}$ which is true for all sufficiently large numbers due to Baker, but if i want to make the implicit "for all sufficiently large numbers" ...
user95470
4
votes
0
answers
238
views
On the values of $\prod_{k=1}^{(p-1)/2}(e^{2\pi i/12}-e^{2\pi i k^2/p})$ for primes $p>3$
In a recent preprint, I investigated
$$S_p(x):=\prod_{k=1}^{(p-1)/2}(x-e^{2\pi ik^2/p}),$$
where $p$ is an odd prime and $x$ is a root of unity.
Motivated by Question 337879 and Question 338325, ...
- 15.6k
3
votes
0
answers
1k
views
Effective upper bound on large prime gaps; or, what is the first prime after a googolplex?
Question
What is the best known effective upper bound on the prime gap following x?
Motivation
Suppose you needed to show a good bound for the gap between a fixed large constant, say $G=10^{10^{100}...
- 9,114
2
votes
1
answer
379
views
Representation of 2 in sum of powers of positive-negative digits with some base
Define:A set $\mathcal{C}(t)$, a positive integer $n$ is in the $\mathcal{C}(t)$ if $x^t \pmod{n}$ describes a bijection from the set $\{0,1,...,n-1\}$ to itself.
Example table:
\begin{array}{|c|c|}
\...
- 599
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
0
answers
422
views
Sequences with high densities of primes: how to boost them to get even more and larger primes
I propose a methodology to help find large prime numbers with a much higher probability than picking up random numbers and testing them for primality. This would help speed up prime number generators ...
- 3,098
1
vote
1
answer
327
views
Symmetry in Hardy-Littlewood k-tuple conjecture
Assuming Hardy-Littlewood $k$-tuple conjecture, do the "dual" prime constellations $(0,h_1, h_2,\cdots, h_i,\cdots, h_{k-1}=d)$ and $(0, h_{k-1}-h_{k-2}, h_{k-1}-h_{k-3},\cdots,h'_i=h_{k-1}-...
- 6,984
1
vote
0
answers
174
views
A series of conjectures on $\sum_{x=0}^{(p-1)/2}(\frac{x^5+cx^3+dx}p)$ (I)
Let $p$ be an odd prime. Here I introduce the sum
$$S_p(c,d):=\sum_{x=0}^{(p-1)/2}\left(\frac{x^5+cx^3+dx}p\right)$$
with $c,d\in\mathbb Z$, where $(\frac{\cdot}p)$ is the Legendre symbol.
I have a ...
- 15.6k
0
votes
1
answer
669
views
Paradox in additive combinatorics
Let $S$ be an infinite set of positive integers. Let us define the following quantities:
$N_S(z)$ is the number of elements of $S$, less or equal to $z$
$r_S(z)$ if the number of positive integer ...
- 3,098
-3
votes
2
answers
606
views
The number of totatives to the nth primorial, in an interval shorter than the nth primorial
(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.)
Can, and if so when can, we determine the amount of natural numbers which are ...
- 161
65
votes
6
answers
14k
views
What is the simplest proof that the density of primes goes to zero?
By density of primes, I mean the proportion of integers between $1$ and $x$ which are prime. The prime number theorem says that this is asymptotically $1/\log(x)$.
I want something much weaker, namely ...
- 4,164
53
votes
5
answers
4k
views
Distribution of square roots mod 1
I was wondering about the distribution of $\sqrt{p}$ mod $1$ this morning, as one does while brushing one's teeth. I remembered the paper of Elkies and McMullen (Duke Math. J. 123 (2004), no. 1, 95–...
- 13.3k
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
48
votes
4
answers
3k
views
Twin primes conjecture and extrapolation method
Let $(p_1, p_2)$ be a twin prime pair, where we include $(2, 3)$. If $p_1 \equiv 1$ mod $4$ then we let $t_{(p_1, p_2)} := p_1 ^ 2 / p_2 ^ 2$ otherwise, we let $t_{(p_1, p_2)} := p_2 ^ 2 / p_1 ^ 2$.
...
- 1,305
37
votes
3
answers
1k
views
Is there a $c > 1$ such that for all $n \ge 1$ the largest integer $\le c^n$ is prime?
Does there exist a real number $c > 1$ such that for every natural number $n > 0$, the number $\lfloor c^n \rfloor$ is prime?
I doubt such a number $c$ is known to exist, since the best similar ...
- 22.3k
36
votes
8
answers
32k
views
What are the connections between pi and prime numbers?
I watched a video that said the probability for Gaussian integers to be relatively prime is an expression in $\pi$, and I also know about $\zeta(2) = \pi^2/6$ but I am wondering what are more ...
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
34
votes
1
answer
843
views
Can we write each positive rational number as $\frac1{p_1-1}+\ldots+\frac1{p_k-1}$ with $p_1,\ldots,p_k$ distinct primes?
It is well-known that any positive rational number can be written as the sum of finitely many distinct unit fractions. This is easy since
$$\frac1n=\frac1{n+1}+\frac1{n(n+1)}\quad\text{for all}\ n=1,2,...
- 15.6k
32
votes
3
answers
8k
views
Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)
I'm reading the elementary proof of prime number theorem (Selberg / Erdős, around 1949).
One key step is to prove that, with $\vartheta(x) = \sum_{p\leq x} \log p$,
$$(1) \qquad\qquad \vartheta(x) \...
- 587
32
votes
2
answers
2k
views
A Collatz-like problem on prime numbers
Consider the function $f$ on the prime numbers defined by $$ f(p):= \text{ the greatest prime factor of } 2p+1.$$ The iteration of $f$ from any prime $p<10^8$ converges to the cycle $$(3,7,5,11,23,...
29
votes
4
answers
3k
views
Is there an 11-term arithmetic progression of primes beginning with 11?
i.e. does there exist an integer $C > 0$ such that $11, 11 + C, ..., 11 + 10C$ are all prime?
- 4,164