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

3
votes
1answer
48 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
42 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
1answer
43 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 + ...
4
votes
0answers
32 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
22 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
60 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
21 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
17 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 ...
0
votes
1answer
53 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
0answers
34 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
59 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
34 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
68 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
191 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
45 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
19 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
68 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
49 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
38 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 ...
1
vote
1answer
35 views

Induction Proof - Primes and Euclid's Lemma

I'm having some trouble with this proof. Here's the question: Use mathematical induction and Euclid's Lemma to prove that for all positive integers $s$, if $p$ and $q_1, q_2, \dotsc, q_s$ are prime ...
4
votes
2answers
280 views
+100

The longest sequence of numbers with a certain divisibility property

Definition - Denizen A sequence $\lbrace a_k \rbrace$ is a denizen if all of it's members are prime numbers, i.e $a_0, a_1, ... a_n \in \mathbb{P} $; and it satisfies the following condition; ...
5
votes
5answers
84 views

Decomposing an integer into primes raised to different powers

The number $711000000$ can be written as $79^1 \times 2^6 \times 3^2 \times 5^6$. How are these numbers found? I guess the more general question is - given $n \in \mathbb Z $, how can you ...
4
votes
1answer
57 views

number of primes of the form |$n^2 - 6n + 5$|?

How can I find the number of primes of the form $|n^2 - 6n + 5|$ where $n$ is an integer? Through trial and error, I have found $n = 6$ (this one is obvious), and $2$. Are there any more, and what is ...
1
vote
2answers
127 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
-1
votes
0answers
33 views

Lifting quadratic residues

Let $p$ be an odd prime. Show that if $q$ is a quadratic residue modulo $p^x$ for some $x > 0$, then $q$ is a quadratic residue modulo $p^{x+1}$. We have $x^2=q \pmod {p^x}$, and $x^2-q=m ...
8
votes
3answers
73 views

Does the sum of reciprocals of primes congruent to $1 \mod{4}$ diverge?

Let $P$ be the set of primes $p$ greater than $3$ such that $p\equiv1 \pmod{4}$. Does the following sum converge or diverge? $$ \sum_{p\in P}\frac{1}{p} $$
4
votes
2answers
44 views

Is there a Divisibility Metric for Numbers?

Both prime numbers and highly divisible numbers have a common characteristic: divisibility. The former are divisible by as few lower numbers as possible, and the latter by as many as possible, like ...
-1
votes
0answers
38 views

Concatenating the first semiprimes to get a semiprime

The first semiprime numbers are $4,6,9,10,14,15,...$ once alternate them in order from the first semiprime, we see that $46, 469, 469101415$ are also semiprimes(!). After this the largest I've found ...
1
vote
0answers
33 views

What is this quantity?

I wonder whether there is a closed form for $$-\sum_{k=1}^{\infty}\frac{\Delta^{k}\pi(x)}{k!}(-x)_k$$ where $\pi(x)$ is the prime-counting function and $(x)_k$ is the falling factorial. In other ...
0
votes
1answer
44 views

Something related to carmichael numbers.

$a^{n - 1} = 1 \bmod n$ for any prime $n$ and any $a$ prime to $n$. Yet there exists composite $m$ such that $a^{m-1} = 1 \bmod m $ for all $a$ relatively prime to $m$; $m$ being a Carmichael number, ...