Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

0
votes
0answers
10 views

What's the smallest known interval containing at least one prime number?

Wikipedia says that Dusart proved in 2010 that there's at least one prime between $x$ and $\left(1 + \frac{1}{25\ln^2x}\right)x$ for sufficiently large $x$. My question is: is it the smallest known ...
2
votes
0answers
23 views

Which constellations of primes recur forever?

Having derived much joy and learning from the answers I have received to four previous questions, let me ask one more. Let a constellation of primes be a set of primes that stand in certain fixed ...
0
votes
0answers
15 views

Primes and even numbers

Can every even number be written up as the difference of two primes? And in either case could you prove it? $$ e.g.\space 8 = 31-23 \space and \space 10 = 41-31$$
0
votes
0answers
24 views

Ways Of Finding Primes and If they are efficient

I am currently in middle school and love number theory. I try and do a proof every day and today I was working on a relatively simple one involving primes. I proved that every prime above 5 can be ...
2
votes
1answer
70 views

Why is $p_n \sim n\ln(n)$?

I know that the prime number theorem states that the number of primes less than $x$ is approximately $\frac{x}{\ln(x)}$. However, why does this mean that $p_n \sim n\ln(n)$? (where $p_n$ is the $n$-th ...
0
votes
0answers
21 views

Lower bound for $\Pi(n)$ - viability of probabilistic theory

Can somebody check the validity of my arguments below, and tell me why its wrong or right? Consider the sequence of non-negative integers. Let $a_0=0, a_1=1, ..., a_i=i,...$ Divisiblilty of $a_i$ ...
0
votes
0answers
18 views

The distribution of prime and semi-prime.

Let $\alpha$ be an integer and $\rho_1,\rho_2$ some prime such that $\alpha=\rho_1\cdot\rho_2+1$, and $\beta$ the number of all semi-prime less than or equal to $\alpha$. Prove ...
-1
votes
2answers
94 views

How many prime numbers we need? [on hold]

If we have some not prime number $n > 1$ we always can make prime factorization. For this operation we need $m$ prime numbers. Is there any way to prove that for given $n$ we can use no more then ...
2
votes
2answers
45 views

Is the sequence $\{0,2,6,12,20,30,…,n(n+1)\}$ admissible for every natural $n$?

Look here : https://en.wikipedia.org/wiki/Prime_k-tuple for the definition of an admissible sequence. I wonder if the sequence of differences of primes can be $\{0,2,4,6,8,...,2n\}$ for every ...
1
vote
1answer
23 views

Dirichlet theorem

Can anyone give a simple number theory proof for the Dirichlet theorem? Statement of Dirichlet theorem:given any two numbers a and b whose g.c.d is 1,Prove that infinitely many primes exist in the ...
-3
votes
0answers
17 views

what is formula to this eqution [(256)16]1/32+[(169)6]1/12 [on hold]

how to solve this equation [(256)16]1/32+[(169)6]1/12 what is formula of this? What is the closed form expression for this? What is the right domain for this Hamiltonian 2? what is the right ...
4
votes
1answer
54 views

Is every sufficiently large even integer the sum of distinct primes?

Is every sufficiently large even integer the sum of (any number of) distinct primes? No doubt this question has been asked before; does the conjecture/theorem have a name? It is related to ...
1
vote
1answer
53 views

Smallest twin-prime-pair exceeding $10^{1000}$

I found the twin-prime-pair $$\large 10^{1000}+9705092\pm 1$$ with PARI/GP. Is this the smallest twin-prime above $10^{1000}$ ? A general question to the search of twin primes : The prime number ...
2
votes
2answers
62 views

How do I find(isolate) the n-th prime number?

So I wanted to solve this SPOJ problem and I did some research about finding the n-th prime number. This formula came across and it stated that the n-th prime must be in this range: $n \ln n + ...
5
votes
0answers
38 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
1
vote
0answers
26 views

Is there a tighter approximation for the least prime gap of a given length?

This link https://primes.utm.edu/notes/gaps.html gives a definition of the maximal gaps. For a number $g$ , $p(g)$ is the smallest prime $p$ followed by at least $g$ composites. The estimate is ...
0
votes
0answers
22 views

Chebyshev's original proof of Bertrand's postulate

I'm looking for the original Chebyshev's proof of Bertrand's postulate. It would be great if someone could provide me the link to the article. Thank you in advance,
4
votes
4answers
71 views

Books on Prime numbers

I am a graduate student and have just finished Burton's book on number theory. Now I want to read further on prime numbers. Does anyone have any suggestion?
1
vote
1answer
35 views

For every natural integer $N>3$ there are at least two distinct prime numbers $p$ and $q$ such that $\dfrac{p+q}{2}=N$ and $N-p=q-N$, $(p<q)$.

I'm not sure but this problem may be similar or related to Goldbach conjecture? Any proof/disproof, insight and opinion is appreciated, thanks.
-1
votes
1answer
28 views

Is there a number which describes the approaching ratio of twin primes to other primes? Or a formula for the change in density of twin primes?

Could someone shed some light on what we know about the density of twin primes? I find that it seems to be empirically true that the density of prime gaps increases as $\log(x)$ does for any gap. ...
1
vote
1answer
18 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
3
votes
2answers
80 views

New deterministic primality test for numbers of the form $p\cdot 2^n + 1$

Edit: Sorry, there was an error. Old Claim (not true because there is a counter-example): Let $p$ be prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N = p\cdot 2^n+1$ is prime, if and only ...
3
votes
0answers
24 views

Kronecker symbol vs. Koblitz symbol

In Koblitz, Introduction to Elliptic Curves and Modular Forms on page 188 it is defined $$\left( \frac{-1}{j}\right)=0$$ in case $j$ is even. Apart from that definition $\left( \frac{c}{d}\right)$ is ...
0
votes
0answers
35 views

Why does $\frac{x^n}{n^x}$ stop growing at the approximate value of $\pi (n)$?

I noticed while playing around with these functions that $n^x$ will start slow and then speed up really fast in its growth rate. While $x^n$ grows more slowly, but faster than $n^x$ at the start. ...
1
vote
0answers
42 views

Does anyone recognize this graph?

It's a plot of the following: Let $$f_{(n)} = \frac{np_n}{(p_1 + \ldots + p_n)}$$ so that $$g_{(n)} = \left|\space f_{(n)} - f_{(n-k)}\right| $$ where $n > k$ and $k = 5$ in this example. For ...
0
votes
1answer
45 views

Show that there exists $s, t \in S$ such that $\gcd(s, t)$ is a prime

Let $S$ be a set containing finitely many positive integers greater than 1 with property: for all $n \in \mathbb{Z_+}$, there exist $s \in S$ such that $\gcd(s, n) = 1$ or $\gcd(s,n) = s$. Show that ...
1
vote
1answer
33 views

Why hash table size is prime? [on hold]

In computer science, the size of the hash table is recommended to be prime. What is the property of prime number that makes it recommended to be the size of hashtable?
-3
votes
0answers
44 views

If $p$, $q$, and $r$ are all odd primes, which of $p^2-q^2+1$, $pqr+3$, and $(p+2)(r+2)+1$ can be prime? [on hold]

If $p$, $q$, and $r$ are all odd primes, which of the following might also be a prime? a) $p^2-q^2+1$ b) $pqr+3$ c) $(p+2)(r+2)+1$
0
votes
2answers
61 views

Proof that every positive integer has at most one prime factor greater than it's square root?

I read the statement in the title somewhere but I can't find any proof. For a positive integer $n$, why can't there be 4 numbers $a, b, c, d$ ($b$ and $d$ are prime) for which $a < \sqrt{n} < ...
2
votes
0answers
35 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
-1
votes
1answer
59 views

Prove that $n^m+x$ is not prime generally if $n+x$ is (in $\Bbb N$)

If $n + x$ with $n, x \in \Bbb N$ is prime, is it possible to prove generally, that $n^m + x$ with $n, x, m \in \Bbb N$ is not prime for at least one $m$? If yes, how can this be done? EDIT: There ...
5
votes
2answers
74 views

Proving the irrationality of the concatenation of the $n$th powers of primes

Note: The apostrophes are meant to separate different groups of digits. Like, $0.{1^2}'{2^2}'{3^2}'{4^2}'\cdots=0.14916\cdots$. I wasn't able to come up with something better. It is easy to show ...
1
vote
0answers
96 views
+50

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
3answers
37 views

Product of first $n$-th prime power integers $+ 1$

I was just playing with prime numbers and then I accidentally found this pattern. Let $p_1\cdot p_2\cdot p_3\cdots p_n$ is the product of first $n$-th prime power integers. Prove that: $p_1\cdot ...
2
votes
1answer
55 views

Besides 1 and 11, is $\sum_{i=0}^n 10^i$ composite for every $n\in \mathbb{N}$?

Given a number consisting of digits all equal to 1 in base 10 and not equal to 1 or 11, is it necessarily composite? I know that 11 is the smallest non-trivial counter-example, but I would like to ...
2
votes
1answer
62 views

Primes that are approximately twice other primes

Are there infinitely many pairs of primes of the form $p,2p-1$? What about $p,2p+1$?
6
votes
2answers
192 views

What is the smallest prime $p$ such that the next prime is greater than $p+2000\ $?

I studied this site https://en.wikipedia.org/wiki/Prime_gap and wondered if the smallest prime gap greater than $2000$ can still be determined, in other words : Which is the smallest prime $p$, ...
1
vote
0answers
30 views

Equivalent conjecture to Goldbach's conjecture

I'm reading a paper regrading the basis orders. In that paper, I met with the following statement: $$3(\mathbb{P}\cup\{0 \})=\mathbb{Z}_{\geq 2}$$, Which, by definition, states that primes form ...
1
vote
3answers
46 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
3
votes
0answers
84 views

What is the least prime $p$, such that $[p-1000,p+1000]$ does not contain a prime $\ne p$?

I am looking for the least prime number $p$, such that the interval $[p-1000,p+1000]$ contains no prime except $p$. In other words, the prime nearest to $p$ has a distance $>1000$ to $p$. I found ...
1
vote
1answer
43 views

Lunchroom Question: primes adding up to counting numbers?

Our lunchtime group got into another math related discussion. I apologize in advance if this isn't a rigorous question, as none of us are professional mathematicians. This is the question: Is it ...
0
votes
1answer
20 views

What's the condition for (x+kp) and pq being coprime?

Suppose $p$ and $q$ are large primes and $N=pq$. $x$ is an arbitrary integer in $\mathbb{Z}_p$ and $k$ is a random integer. Then what is the condition for $k$ (suppose $x$ is fixed) such that ...
0
votes
1answer
71 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
5
votes
1answer
95 views

Is $\lim_{n\to \infty} \frac{np_n}{\sum_{i=1}^n p_i} = 2$ true?

Noob here. I was playing around with primes in JavaScript and I found that if I divide the nth prime times n to the sum of primes up to n, I get closer to 2 for each n going to infinity: $$\lim_{n\to ...
4
votes
1answer
69 views

Is the relation $P(n) \sim \frac{1}{2^n}$ already known?

Apologies in advance if there is a violation of rules/laws here, as I am not a mathematician. $$ \begin{align} \lim_{n\to\infty} \left( \frac{\pi^{n}}{\zeta(n)}P(n) \right)^{\frac{1}{n}} &= ...
2
votes
1answer
50 views

Solving $x = c\times \ln(x)$

How to solve $x = c\times \ln(x)$ where c is some constant? I'm trying to figure out how to solve the prime number theorem for x, given the number of primes.
1
vote
1answer
29 views

Are the Bernoulli denominators always divisible by these corresponding primes?

I was wondering whether it has been proven/disproven yet or at least conjectured that the bernoulli denominator of $B_{2n}$ is divisible by $2n+1$ if and only if $2n+1$ is prime? If not, must the ...
1
vote
1answer
39 views

Estimates for $1/\zeta(s)$

Recently I am reading Stein's Complex Analysis, and he is going to prove the prime number theorem after estimating the value $1/\zeta(s)$. However, I don't understand the technical details of the ...
1
vote
1answer
22 views

Is the value of $c$ in $\prod_{i=1}^{n}\frac{p_i}{p_i-1}<e^c \cdot (\log p_n) \cdot(1+\frac{1}{\log_2p_n})$ known?

I Recently read this paper by Rosser and Schoenfeld (http://projecteuclid.org/download/pdf_1/euclid.ijm/1255631807) In Theorem 8, corollary 1, they state: $$\prod_{i=1}^{n}\frac{p_i}{p_i-1}<e^c ...
2
votes
0answers
33 views

Finding primes using the Fibonacci sequence in modular form

I was wondering if the following is already a known result in mathematics. I have tested it and it seems to work every single time. If I write the Fibonacci sequence in $\bmod (a)$ form and it ...