All Questions
Tagged with nt.number-theory prime-numbers
518 questions with no upvoted or accepted answers
4
votes
0
answers
191
views
Overview of Combinatorial Technique of "Selberg’s Symmetry Formula"
In the paper entitled "A Computational History of Prime Numbers and Riemann Zeros" (on page 4, click here) it is written about "Selberg’s symmetry formula" that-
Until 1950 it was widely believed (...
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
4
votes
0
answers
273
views
Kaczorowski's Paper on Distribution of Primes
I am looking for a digital copy of the following paper by Jerzy Kaczorowski: ON THE DISTRIBUTION OF PRIMES (mod4)
https://www.degruyter.com/view/j/anly.1995.15.issue-2/anly.1995.15.2.159/anly.1995.15....
- 41
4
votes
0
answers
275
views
A positive irrational number $\alpha$ such that $\lfloor k^n \alpha \rfloor$ and $M$ are always coprime?
From my previous question:
Is it true that there always exists a positive integer $n$ such that $p | ⌊k^n⋅α⌋$
, I came up with a similar question:
Given a positive integer $k$ such that $k>2$, $...
- 501
4
votes
0
answers
408
views
Can we efficiently factor $n$ given that $n=pq$ where $p,q$ are primes satisfying $p=a^2+b^2, q=2ab+1$ for some $a,b$
Suppose we're given a particular number $n \in \mathbb{N}$.
We're also given that $n=pq$ where $p,q$ are unknown primes satisfying
$$
p=a^2+b^2
$$ and
$$
q=2ab+1
$$
for some $a,b$.
Is there an ...
- 141
4
votes
0
answers
672
views
Euclides' sieve
This is probably a well-known problem. Given a set or multiset of natural numbers let us construct its "Euclides" closure: on each step we take all possible products $P_i$ of the elements in the set, ...
- 5,063
4
votes
0
answers
262
views
Error term for Vinogradov's three prime theorem
It can be shown that $$\sum_{a + b + c = N}\Lambda(a)\Lambda(b)\Lambda(c) = \frac{1}{2}\mathfrak{S}(N)N^2 + O(N^2\log^{-A} N)$$ for some $1\ll \mathfrak S(N)\ll 1$using the circle method. Are there ...
- 1,890
4
votes
0
answers
251
views
What is known about stability of number theoretic statements for Beurling systems which are based on small perturbations of the ordinary primes
Beurling considered a sequence of reals $1<x_1<x_2<\cdots <$ as "primes" and then the ordered sequence of all products of these "primes" as "integers". Let us consider Beurling primes ...
- 24.7k
4
votes
0
answers
318
views
Prime powers between $x$ and $x+x^\theta$
By the result of Baker, Harman, Pintz (http://www.cs.umd.edu/~gasarch/BLOGPAPERS/BakerHarmanPintz.pdf), for any sufficiently large $x$ the interval $[x-x^{21/40},x]$ contains a prime number. This ...
- 41.9k
4
votes
0
answers
176
views
Are there any results about this higher degree Titchmarsh divisor problem?
Does there exist an asymptotic formula for $\sum_{p\le x}\tau(p−1)^n$ ? Here $n$ is an arbitrary positive integer and $\tau$ is the divisor function. The case of $n=1$ was done by Linnik, but when $n$ ...
- 41
4
votes
0
answers
412
views
Effective prime number theorem
The prime number theorem implies that for every $ϵ>0$, there is $n_\epsilon$ such that for all $n≥n_\epsilon$ the number of primes in $[n,cn]$ is at least $\frac{(c−1−\epsilon)n}{\log n}$ and at ...
- 13.9k
4
votes
0
answers
324
views
Asymptotic estimate for a random model of primes
Question
Let
$$
\pi_{rm_c}(x) = \sum_{ \substack{ {n\leq x}\\{(n+a,P(\sqrt{n}))=1}}} 1-1,
$$
where $P(x)$ is the product of all primes less or equal to $x$ and $a$ is a random integer constrained to ...
- 965
4
votes
0
answers
173
views
Are prime gaps of even index essentially larger than those of odd index?
Let $g_{n}:=p_{n+1}-p_{n}$ be the $n$- th prime gap, and let's introduce the following summatory functions:
$$G_{1}(x):=\sum_{1\leq n\leq x}g_{2n-1}$$
$$G_{2}(x):=\sum_{1\leq n\leq x}g_{2n}$$.
Let's ...
- 6,984
4
votes
0
answers
359
views
A problem on prime numbers
Given integers $a,b,c,d\in[2^n,2^m]$ with $m>n>1$, how many primes $p$ are there in $[n^\alpha,n^\beta]$ for some $1<\alpha<\beta$ such that
$$0<a\bmod p<n^{\alpha/k}$$
$$0<b\bmod ...
user76479
4
votes
0
answers
211
views
Behavior of the "mean prime factor" of numbers
This question concerns the behavior of
a function $f(\;)$ that maps each number in $\mathbb{N}$ to
its mean prime factor.
I previously posted premature questions, now deleted, which
explains the cites ...
- 151k
4
votes
0
answers
117
views
Best constant for Maier's theorem?
Maier proved that, for fixed $\lambda>1,$
$$
\limsup_{x\to\infty}\frac{\pi(x+\log^\lambda x)-\pi(x)}{\log^{\lambda-1}x}>1
$$
and in particular
$$
\limsup_{x\to\infty}\frac{\pi(x+\log^\lambda x)-\...
- 9,114
4
votes
0
answers
279
views
Analog of Euler's factoring technique
Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials?
Euler's two squares factoring states that numbers ...
- 13.9k
4
votes
0
answers
624
views
Is there a hidden symmetry in the prime numbers distribution?
Under Goldbach's conjecture, let's consider once again the map $r_0\colon n\mapsto r_{0}(n)$ such that $r_{0}(n)$ is the smallest non negative integer $r$ such that both $n-r$ and $n+r$ are prime.
Let'...
- 6,984
4
votes
0
answers
625
views
A "Take a Square Root When You Can" conjecture related to the prime factorization
I would tend to think that the following has already been investigated.
But as implied from the title, I have no idea how to even start looking for it.
Let $P_n$ denote the sum of the squares of the ...
- 605
4
votes
0
answers
306
views
Effective version of the Bombieri-Vinogradov theorem
Is there an effective version of the Bombieri-Vinogradov Theorem, in that have bounds on the implied constant been found?
- 1,890
4
votes
0
answers
755
views
New proofs of Euclid's theorem of the infinitude of primes?
Playing around with elementary inclusion-exclusion, I arrived at two simple variations of proofs of Euclid's theorem that I thought would be long known in the literature. So far I haven't been able to ...
- 965
4
votes
0
answers
241
views
Can the following quantitative version of Chen's theorem be obtained?
The theorem of the Chinese mathematician Chen Jingrun is currently one of the best results with respect to the binary Goldbach problem. It asserts that every even integer $n$ is in the sumset $P + P_2$...
- 26.9k
4
votes
0
answers
370
views
About sign changes of Li(x)-π(x)
Given a constant $C$, which are the best known upper bounds for the number of sign changes
of the function
$$
f: \mathbb{N} \rightarrow \mathbb{R}, \ \ x \mapsto {\rm Li}(x)-\pi(x)
$$
in the range $...
- 51
4
votes
0
answers
399
views
Efficient ways to count primes satisfying Zhang's theorem
The theorem of Yitang Zhang states that there exist a finite $k \in \mathbb{N}$ such that there exist infinitely pairs of primes $(p,q)$ such that $|p - q| \leq k$. The statement that $k$ can be taken ...
- 26.9k
4
votes
0
answers
159
views
smallest k such that highest prime factor of m(m+1)...(m+k-1) is > n if m > n.
I am fascinated by this entry OEIS A213253 which lists the smallest $k$ such that highest prime factor of $m(m+1)\dots(m+k-1)$ is $> n$ if $m > n$.
The article has references to the algorithm ...
- 1,049
4
votes
0
answers
369
views
Reducing factoring prime products to factoring integer products (in average-case)
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...
- 41
4
votes
0
answers
312
views
Generalization of Tamarkin’s ARO 1993, final round, problem 10/8: part II
Let us use the notations of my previous question about Tamarkin's problem.
Let $\ell\in\left\lbrace 0,1,...,p\right\rbrace$.
An element $f\in \mathbb Z^{\mathbb Z}$ is said to be $\ell$-average-...
- 33.8k
4
votes
0
answers
415
views
Number of $k$-partitions of $n$ into odd prime parts
Browsing through OESIS I have found that if $p_p(n)$ denotes the number of partitions of $n$ into prime parts then $p_p(n) = O(e^{\frac{2 \Pi}{\sqrt{3}}\sqrt{n/\log n}})$.
I am interested in the ...
- 3,463
4
votes
1
answer
324
views
Higher roots modulo prime complexity best algorithm
Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$.
What is the best method to find all such ...
3
votes
0
answers
192
views
What smoothing to use for PNT-like results?
Consider a Dirichlet series $\sum_n a_n n^{-s}$ with desirable analytic properties (e.g., analytic extension to $\Re s>0$); one example would be $a_n=\mu(n)$. Say we want to estimate $\sum_{n\leq x}...
- 20.2k
3
votes
0
answers
153
views
On a theorem by Iwaniec about binary quadratic polynomials representing infinitely many primes
In Theorem 1.1 (i) of http://matwbn.icm.edu.pl/ksiazki/aa/aa24/aa2451.pdf, Iwaniec showed that a certain type of quadratic polynomial $P(x,y)$ represents infinitely many primes, where $(x,y) \in \...
- 333
3
votes
0
answers
1k
views
Formula for $\pi$ involving exponents of Mersenne primes
Can someone provide a proof for the following claim?
$$\pi=\dfrac{S_0S_2}{M_3M_5} \cdot\left(\displaystyle\prod_{p \equiv 1 \pmod{4} } \frac{p}{p-1}\right) \cdot \left(\displaystyle\prod_{p \equiv 3 \...
- 2,661
3
votes
0
answers
175
views
Proof of when 3 is a cubic residue modulo primes
I have recently been learning about cubic characters, and the machinery of Gauss and Jacobi sums used to prove the cubic reciprocity theorem, and using this, I can now determine when any prime is a ...
- 2,811
3
votes
0
answers
330
views
Can you prove and/or generalize this formula involving the Möbius function at n = square free numbers for elliptic curve related sequence in the OEIS?
Let $g(n)$ be the Dirichlet inverse of the Euler totient function:
$$g(n) = \sum\limits_{d|n} d \cdot \mu(d)$$
and let $f(x,y)$ be the elliptic equation:
$$f(x,y)=x^3 - x^2 - y^2 - y$$
Show that the ...
- 1,183
3
votes
0
answers
165
views
What is the density of numbers which have at least two divisors whose sum is a perfect square?
Note: This question was posted in MSE about two years ago but it not receive an answer. Hence posting in MO.
A positive integer is said to have square-sum divisors if it has at least two divisors ...
- 5,470
3
votes
0
answers
328
views
Conjecture about primes and Fibonacci numbers
I posted this conjecture on math.stackexchange, but I received no answer proving or disproving it: if $ m > 4 $ is a positive integer not divisible by $ 2 $ or $ 3 $, it's ever possible to find a ...
- 387
3
votes
0
answers
91
views
Equirepartition of sums for large multisets in subsets of finite fields
Let
$p$ be a prime number and let $\mathcal A$ be a subset of $a\leq p$ distinct
elements in $\mathbb F_p$.
We denote by $\mathcal M_k(\mathcal A)$ the set of all ${k+a-1\choose k}$
multisets ...
- 17.9k
3
votes
0
answers
215
views
Some pending questions about $\sum_{p\leq\sqrt{n}}p=\pi(n)$
Here it was showed that $S(n)\sim \pi(n)$, where $S(n)=\sum_{p\leq\sqrt{n}}p$, $p$ refers to prime numbers, and $\pi(n)$ is the prime counting function. Here it was proved that $S(n)=\pi(n)$ for ...
- 189
3
votes
0
answers
343
views
Square-free Mersenne numbers
Questions about prime numbers are notoriously hard. Let me ask one which may be easier:
QUESTION: are there infinitely many square-free Mersenne numbers
$$ M(n)\ := 2^n-1 $$
where $\ n\in\mathbb N\ $ ...
- 4,786
3
votes
0
answers
158
views
What can be said about the primality of Zsigmondy numbers?
I am cross-posting this from math.stackexchange, as it has received upvotes but no comments/answers after a couple months.
Let $\mathcal{Z}(n,a,b)=\frac{\Phi_n(a,b)}{\gcd (\Phi_n(a,b),n)}$ be the $n$-...
- 101
3
votes
0
answers
429
views
Proof of an explicit formula for $\pi_0(x)$
Let $\pi(x)$ denote the prime counting function and $$\pi_0(x) = \lim_{\epsilon \to 0} \frac{\pi(x+\epsilon)+\pi(x-\epsilon)}{2}.$$
I've seen noted in a few references the explicit formula
$$\pi_0(x) =...
- 4,985
3
votes
0
answers
292
views
A prime generating algorithm
I posted this question in MSE around a month ago, but didn't receive any suitable answers. So, I decided to give it a try here as well-
I was trying to explain the famous proof of infinitude of primes ...
- 791
3
votes
0
answers
232
views
Numbers made up of primes from a given set
Take a set $\mathcal P$ of primes and denote by $\langle \mathcal P\rangle $ the set of all natural numbers composed of primes from $\mathcal P$. If
\[ \sum _{p\in \mathcal P}\frac {1}{p}\]
converges ...
- 1,381
3
votes
0
answers
117
views
On the Carmichael Lambda function
Let Carmichael function be denoted by $\lambda(n)$.
Consider the set $I_m=\{n:\lambda(n)=m\}$.
What is known about the cardinality of $I_m$?
Let $P_m=\{p\in Primes: p|\ell \mbox{ for some }\ell\in ...
- 13.9k
3
votes
0
answers
151
views
On an inequality for the arithmetic function counting the number of primes $\lfloor n^c\rfloor$ in the spirit of Ramanujan's prime counting inequality
In page 3 of [1] (please see if you need it the book by Berndt) Axler refers an inequality that involves the prime-counting function $\pi(x)$ and that was deduced by Ramanujan. I'm curious to know if ...
3
votes
0
answers
252
views
Counting twin primes with a sieve-like algorithm
The sequence A002822, denoted as $S$, represents all the twin primes except $\{3, 5\}$. Other than that exception, $k$ and $k+2$ are twin primes iff $(k+1)/6\in S$. Let $S(N)$ be the subset of $S$ ...
- 3,098
3
votes
0
answers
154
views
Reference request for the following results
I am looking for references on the following results. In what follows $\pi(x)$ denotes the prime counting function.
Result 1. For all real $k>1$ there exists $x^k_0 \in \mathbb{R}$ such that for ...
- 31
3
votes
0
answers
415
views
Selberg's elementary proof of the prime number theorem
I tried to follow the argument in the Selberg's proof of the elementary proof from the Selberg symmetry formula
$$L\Lambda + \Lambda*\Lambda =L^2*\mu $$
as presented in the book The Prime Number ...
3
votes
0
answers
147
views
The bias of consecutive prime numbers towards being incongruent modulo 3
Given a positive integer $n$, let $f_1(n)$ denote the number of pairs of
consecutive prime numbers $\leq n$ which are incongruent modulo 3, and let
$f_2(n)$ denote the number of pairs of consecutive ...
- 19.6k
3
votes
0
answers
301
views
Are there infinitely many primes of the form $x^2+(x+y)y^2$?
Heath-Brown [Acta Math. 186(2001), 1-84] proved in 2001 that there are infinitely many primes of the form $x^3+2y^3$ with $x,y\in\mathbb Z^+=\{1,2,3,\ldots\}$.
In contrast, here I ask the following ...
- 15.6k