All Questions
Tagged with nt.number-theory prime-numbers
1,808 questions
4
votes
2
answers
891
views
Asymptotics for the number of ways to sum primes such that the sum is <= n
Hello!
Given $n$ I would like to find a lower bound (or a tight asymptotics) for the number $s(n)$ of solutions to $$ p_1 + \ldots + p_k \leq n \quad (1) $$ where $k$ is arbitrary and $p_1 \leq \...
- 3,463
3
votes
2
answers
876
views
Asymptotics for the number of partitions of $n$ into odd prime parts
Hello!
I am interested in the asymptotic behavior of the function $p_o(n)$ defined as the number of partitions of $n$ into odd prime parts A099773 - http://oeis.org/A099773 .
I couldn't find any ...
- 3,463
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
10
votes
1
answer
2k
views
Convergence of the series $\sum_p p^{-s}$ ($p$ prime and $s>1$)
I know that $\sum_p p^{-s}$, $s>1$, converges. Now, I define $J(s) = \sum_p p^{-s}$. Are there any "well known" values for $J(2)$, $J(3)$, $J(4)$, etc? We all know that $\zeta(2)= \frac{\pi^2}{6}$, ...
- 101
32
votes
2
answers
2k
views
Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?
This is from the category "problems I cannot believe that are still open". But then again, I don't know whether it is still open; it seems to have escaped the attention of most number theorists and ...
- 33.8k
2
votes
0
answers
292
views
Prime divisors of the difference set
Fix $c\in(0,1)$, and let $N$ be a (large) positive integer. Given a set $A=\{0=a_1<\dots<a_n=N\}$ of density $\alpha:=n/N>c$ with $\gcd(A)=1$, I want to find a prime dividing as few ...
- 23k
7
votes
0
answers
452
views
Primes of the form $x^2+ny^2$ such that when you swap x and y you get another prime
Hello, Im looking at primes of the form $x^2+ny^2$ for $n>1$ where we can swap $x$ and $y$ and get another prime, I have found many such pairs for many values of n, and i wanted to know if there ...
- 787
10
votes
2
answers
2k
views
Abel summation of the alternating series of primes?
Consider the ordinary generating function of the sequence of primes ($2+3x+5x^2+7x^3 + ...$); by the ratio test and the prime number theorem, its radius of convergence is $1$. Thus, we might well ask ...
- 5,827
9
votes
1
answer
1k
views
A general question about strictly non-palindromic numbers
For a definition, see the wikipedia page: http://en.wikipedia.org/wiki/Strictly_non-palindromic_number
So according to the wikipedia page, under properties, all strictly non-palindromic numbers with ...
- 26.9k
13
votes
4
answers
1k
views
What results would follow from or imply "randomness" of the primes?
This question on random versions of deterministic problems reminded me that many conditional results in number theory hold if the primes are in some sense random, and it is common knowledge that the ...
11
votes
2
answers
2k
views
primitive roots and primes
Given a positive integer $n > 1$, is it true that there exists infinitely many primes $p$ such that $n$ is a primitive root modulo $p$.
- 111
2
votes
1
answer
454
views
Subsets of $\mathbb N$ with a finite number of prime factors
We call a subset $A = \{a_1, a_2, a_3, \dots\}$ of $\mathbb N$ with $a_1 < a_2 < \dots $ transparent if $a_{k+1} - a_k$ goes to $\infty$ as $k \rightarrow \infty$. Is the following true? For ...
- 11.9k
5
votes
2
answers
641
views
Asymptotic Distribution of Primes
Given an integer $n$ and let $1\leq m\leq n$ be such that $n$ and $m$ are coprimes define
$$
\mathcal{N_{n,m}}:=\text{the set of primes $p$ such that $p\equiv{m}\hspace{0.1cm}\mathrm{mod}(n)$}.
$$
...
- 3,626
4
votes
1
answer
708
views
Calculating the constant in the Bateman-Horn-Stemmler conjecture
Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials.
The constant ...
- 9,114
2
votes
5
answers
2k
views
Prime Number Theorem w/o Complex Analysis
I know about
"Simple analytic proof of the prime number theorem" Newman, 1980
However, is there a proof of the Prime Number Theorem without the use of complex analysis? (Real analysis is fine).
...
- 663
18
votes
3
answers
6k
views
The multiplicative order of 2 modulo primes
Artin's Conjecture says that any positive integer, which is not a square, is a primitive root modulo infinitely many primes. Christopher Hooley gave in
Hooley, Christopher (1967). "On Artin's ...
- 25.5k
7
votes
1
answer
670
views
Given an odd integer N find the smalletst prime p > N such that (p-1,N)=1
So the title says it all,
>
Q: Given a large odd integer $N>>0$, what can we prove about the smallest prime
$p>N$ such that $gcd(p-1,N)=1$?
Note that such a prime exists: Given an ...
- 7,609
7
votes
1
answer
679
views
looking for a multiplicity one prime in a finite sum
So I'm trying to compute the Galois group of family of polynomials (indexed by their degree) using the technique of the Newton polygon. In order to apply this technique I need to find some good prime ...
- 7,609
4
votes
2
answers
323
views
Multiplicity one prime in the factorisation of p-N
I'm wondering if analytic number theorists can prove results which have the following flavor:
So let $N$ be a large positive integer.
Q: Can you always find a prime number $p$ in the interval $(N, ...
- 7,609
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
8
votes
1
answer
530
views
A partial converse to Bertrand's Postulate
Sloane's A077463 obviously suggests that for any positive integer $n$ there exist $n$ consecutive primes and only them in between $m$ and $2m$ for some natural number $m$.
For instance, for
$n=1$, ...
- 2,855
2
votes
2
answers
583
views
Upper bound on Chen primes in an interval?
I'm well aware of the fact that the number of Chen primes between $N/2$ and $N$ for large enough $N$ is at least
$$\frac{c_1N}{\ln^2(N)}$$
(Green and Tao). My question is: is there possibly an upper ...
- 269
4
votes
5
answers
2k
views
residue classes of primes, covering intervals and bounds on the different ways
Take the first $n$ primes $p_1,...,p_n$ and the primorial $P_n$ .Denote by $p_i$ every prime bigger than $p_n$ and smaller than $P_n$.
1) Is that true that there always be a number in any interval of ...
20
votes
2
answers
1k
views
Median largest-prime-factor
Let $P(n)$ denote the largest prime factor of $n$. For any integer $x\ge2$, define the median
$$
M(x) = \text{the median of the set }\{P(2), P(3), \dots, P(x) \}.
$$
Classical results of Dickman and ...
- 12.8k
8
votes
1
answer
1k
views
Are most primes in a prime arithmetic progression of length at least 3?
Following the following two previous questions on mathoverflow:
Are all primes in a PAP-3?
and
Covering the primes by 3-term APs ?
I have attempted to show that infinitely many primes are in an ...
- 26.9k
5
votes
1
answer
389
views
Thin subbases for the primes?
Hi all,
My question concerns a general problem concern the Erdos-Turan conjecture on additive bases; that of finding thin subbases in a given basis. For a given $A \subset \mathbb{N}$, define $r_{A,h}...
- 26.9k
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
2
answers
1k
views
Recovering n from sigma(n)/n
For any positive integer $n$, we define
$$\sigma(n) := \sum_{d \mid n} d,$$
and
$$\delta(n) := \frac{\sigma(n)}{n} = \sum_{d \mid n} \frac{1}{d}.$$
Is there an (efficient) way to determine $\delta^{-1}...
- 6,614
4
votes
1
answer
493
views
Can we count primes in residue classes quickly?
Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in ...
- 9,114
7
votes
2
answers
1k
views
Lower bound of the number of relatively primes(each-other) in an interval
I am trying to find lower and upper bounds for the number of integers that are coprime in pairs in an interval of length n.
What are the best bounds that we have?
Is that true that in any interval ...
22
votes
1
answer
2k
views
Primes represented by two-variable quadratic polynomials
I'm looking over a paper, "Primes represented by quadratic polynomials in two variables" [1] which attempts to characterize the density of the primes in two-variable quadratic polynomials. ...
- 9,114
5
votes
1
answer
310
views
non-asymptotic Bertrand-type theorems for arithmetic progression
It is well known that primes of form $4k+3$, call them $3=q_1 < q_2 < \dots$ satisfy $q_{n+1}/q_n\rightarrow 1$ (and even $q_n=\frac{n}{2\log n}(1+o(1))$). I would be glad to see results of ...
- 109k
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
2
answers
616
views
Are there any notion of 'almost primes' known to have small gaps?
A notorious question with prime numbers is estimating the gaps between consecutive primes. That is, if $(p_n)_{n \geq 1}$ is the canonical enumeration of the primes, then set $g_n = p_{n+1} - p_n$. It ...
- 26.9k
3
votes
1
answer
453
views
An estimate for 'almost primes'?
In the famous Chen's Theorem which states that every sufficiently large even positive integer $n$ can be written as $n = p + q$, where $p$ is a prime and $q$ is a product of at most two primes. This ...
- 26.9k
4
votes
1
answer
650
views
The minimal Goldbach basis
Let $n \in \mathbb{N}, n \geq 2$. By minimal Goldbach basis $G_{2n}$(if it is nonempty) of $2n$ , I mean the minimal set of primes such that every even number less than or equal to $2n$ can be written ...
- 2,855
3
votes
1
answer
993
views
Whence the k-tuple conjecture?
What is the source of the $k$-tuple conjecture, that every integer tuple $(k_1,\ldots,k_n)$ either contains all members of a congruence class mod a prime or has infinitely many primes amongst $(k_1+c,\...
- 9,114
7
votes
1
answer
616
views
Is there an Infinite increasing sequence of primes with bounded second or larger differences?
The opposite question is if for any infinite increasing sequence of primes and any $k$ the sequence of the $k$-th order differences of the elements of the sequence is unbounded.
But if the question ...
- 854
26
votes
1
answer
2k
views
Nontrivial circular arguments?
There is a famous circular argument for the Prime Number Theorem (PNT). It turns
out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates
that taken together imply ...
- 17.6k
8
votes
3
answers
2k
views
Prime counting - any fast alternatives to the Lagarias-Miller-Odlyzko combinatorial method or the Lagarias-Odlyzko analytical methods?
I guess the question says it all - I'm trying to track down fast algorithms for prime counting to know what's out there.
I'm already familiar with the two algorithms mentioned in the title (...
- 627
7
votes
3
answers
1k
views
Values where infinite products of primes and composites are equal
Highly grateful for your help/steers on the following question (at the end):
Take the infinite product:
$$\displaystyle T(s) = \prod _{n=2}^{\infty } \left( \dfrac{{n}^{s}} {{n}^{s}-1}\right)$$
for ...
- 4,169
18
votes
3
answers
918
views
Can Gauss sums derandomize any heuristic arguments?
I've always been fascinated by the fact that the classical Gauss sum has absolute value $\sqrt p$, which is exactly what we would expect if we were to interpret the Gauss sum as a random walk. In ...
- 82.7k
5
votes
2
answers
713
views
Number Theory Representation of Primes
For a primes $p$ sufficiently large, does there always exists
positive integers $k,a,b\in\mathbb{N}$ such that $p=(k+1)(ab)+k(a+b)$ or equivalently
$p\equiv (ab)\bmod ((a+b)+ab)$?
Please note that ...
7
votes
3
answers
1k
views
Prime constellation conjectures
This is a simple question about terminology and provenance.
I just need to sort out the circle of conjectures that generalize and refine the twin prime conjecture.
I've encountered Polignac's ...
- 17.6k
10
votes
4
answers
1k
views
A question about primes as an additive basis
Let $\mathcal{P}$ denote the set of primes. Define the function $r_2(N)$ to be the number of ways to write $N$ as a sum of two not necessarily distinct primes (where order matters). Then the famous ...
- 26.9k
2
votes
1
answer
1k
views
Covering Systems of infinite sets of residue classes mod primes
Take an infinite set of distinct primes and a (edit: or 2 , etc.) residue class for every prime. For exammple you can take all the primes bigger than some prime or the primes of a specific form (i.e. ...
0
votes
4
answers
556
views
Smallest prime that does not divide the Vandermonde determinant [closed]
Let $V = \Pi_{1 \le i < j \le n} (a_j - a_i)$ be the determinant of the Vandermonde matrix where $1 = a_1 < \cdots < a_n = d$ (with $d >> n$). What is the smallest prime $p$ (or the ...
- 236
7
votes
1
answer
833
views
Primes in arithmetic progressions
Denote by $\pi(x,a,q)$ the number of primes $p\le x$ of the form $p=qk+a$
and $E(x,a,q)=\phi(q)^{-1}\mathrm{Li}(x)-\pi(x,a,q)$.
What is the strongest conjectured bound on $E(x,a,q)$ in terms of $x,q$?
- 661
21
votes
3
answers
6k
views
Did André Weil predict that the Riemann Hypothesis would be settled by prime number theory rather than by analysis?
Did André Weil predict that the Riemann Hypothesis would be settled by prime number theory rather than by analysis? If so, what are a reference and/or a quotation?
- 309
37
votes
5
answers
3k
views
Happy New Prime Year!
It happens that next year 2011 is prime, while outgoing 2010 is
highly composite in the sense that the number of its distinct prime factors
is 4, maximal possible for a year $< 2310$.
Let me ...
- 13.5k