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

1
vote
1answer
59 views

Sequences of the form : $p_n=2^{p_{n-1}}-a$?

There is known Catalan sequence : $C_n=2^{C_{n-1}}-1$ , with $C_0=2$ I have noticed that following sequence produces prime numbers for the first four terms (I don't know if the fifth term is a prime ...
3
votes
1answer
1k views

Are there infinitely many Mersenne primes?

known facts : $1.$ There are infinitely many Mersenne numbers : $M_p=2^p-1$ $2.$ Every Mersenne number greater than $7$ is of the form : $6k\cdot p +1$ , where $k$ is an odd number $3.$ ...
0
votes
2answers
146 views

Prove a property of divisor function

Let $n$ be a positive natural number whose prime factorization is $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_i$ are natural distinct prime numbers, and $a_i$ are positive natural numbers. ...
12
votes
4answers
2k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
6
votes
2answers
277 views

How do I investigate the metamathematics of Euclid's proof of infinitude of primes?

Is primeness a predicative property? Earlier this year, I jotted down some thoughts in a paper whether Euclid's proof of infinitude of prime numbers is tautological arguing that prime numbers are ...
1
vote
1answer
507 views

Infinitely many primes of the form $6\cdot k+1$ , where $k$ is an odd number?

How to prove that there are infinitely many primes of the form $6k+1$ , where $k$ is an odd number ? Here is a proof that there are infinitely many primes of the form $6k+1$ : We will assume that ...
3
votes
1answer
941 views

Formula for the $n$th prime number: discovered? [closed]

I happened to stumble upon this page. Does anyone know about the validity of this claim?
5
votes
9answers
435 views

Which is the greatest possible natural number that divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$?

Which is the greatest possible natural number that definitely divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$? This one is from my module, comes as a fill in the blanks with ...
6
votes
3answers
172 views

Showing $\pi(ax)/\pi(bx) \sim a/b$ as $x \to \infty$

I'm having a bit of a problem with exercise 4.12 in Apostol's "Introduction to Analytic Number Theory". I don't think it's supposed to be a very hard exercise, it's the first one in its section ...
3
votes
0answers
188 views

Number of integral solutions

Given a prime number $p$, find the number of pairs of integers $(a, b)$ such that $p \lt a$, $p \lt b$ and $ab$ is divisible by $(a-p)(b-p)$.
2
votes
0answers
33 views

What is a good tool for this job involving the prime spiral?

I'm interested in studying the prime spiral interactively. This question talks about some interesting patterns in the spiral involving quadratic equations. The idea I had was, write a program that ...
1
vote
0answers
159 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
5
votes
3answers
252 views

Evaluate $d(n!)$

An exercise: Using the prime number theorem find an asymptotic expression for $d(n!)$ where $d$ is the number of divisors.
0
votes
2answers
227 views

computing primes

As per my knowledge, I have seen the only following functions which will produce primes for $n$: $n^2 - n + 41$ $n^2 + n + 41$ Of course both functions faile for $n = 41$ due to the polynomial ...
1
vote
1answer
272 views

Calculation of prime numbers - why so difficult?

As I read more and more about advanced mathematics, the more complex and obscure topics seem to be tougher to bend the rules of math to describe. However, the simple (and undoubtedly very useful) ...
12
votes
2answers
389 views

How rare are the primes $p$ such that $p$ divides the sum of all primes less than $p$?

This is just for fun! The title pretty much says it all. It's probably a very difficult question. Up to the $40,000^{th}$ prime $(479909)$, I have found only $5$, $71$ and $369119$ with this ...
2
votes
1answer
186 views

Could this $100000004$ digits number be candidate for the record prime number?

Let's observe following number : $ 4517\cdot 2^{332192811}+1$ I have noticed : If $k\cdot 2^{2n+1}+1$ is prime number then $\gcd(k-1,3)=1$ , where $k,n \in Z^{+}$ , so $\gcd(k-1,3)=1$ should ...
0
votes
1answer
63 views

If $P_1P_2…P_{n_0} + 1$ is prime and $2$ divides $P_2P_3…P_{n_0}+1$ is $(P_2P_3…P_{n_0} +1)/2$ prime or composite or both?

If $P_1P_2\cdots P_{n_0} + 1$ is prime, and 2 divides $P_2P_3\cdots P_{n_0}+1$, is $(P_2P_3\cdots P_{n_0} +1)/2$ prime or composite or both? Here $P_i = \{{ 2,3,5,7 \dots\}}$ Composite numbers are ...
1
vote
1answer
268 views

Are there infinitely many primes of the form $p_1\cdot p_2\cdot…p_n+1$? [duplicate]

Possible Duplicate: Is there an infinite number of primes constructed as in Euclid's proof? The question is : Are there infinitely many primes of the form $p_1\cdot ...
2
votes
2answers
169 views

How to prove that this Proth number cannot be a prime number? (without using a computer)

Without using a computer prove that this Proth number cannot be a prime number : $$43373\cdot 2^{49822}+1$$
14
votes
1answer
457 views

Is it possible to assign a value to the sum of primes?

It is possible, by means of zeta function regularization and the Ramanujan summation method, to assign a finite value to the sum of the natural numbers (here $n \to \infty $) : $$ 1 + 2 + 3 + 4 + ...
0
votes
1answer
160 views

Is the set of logarithms of $N$-almost primes equidistributed?

Given the set of all primes. From this one builds subsets of $N$-almost primes according to a certain partition, e.g. $\lambda=(3,1)$, so the set is $$ M=\{2^33,2^35,2^37,...,3^32,3^35,...\}. $$ Is ...
2
votes
2answers
220 views

Shapes and sizes of finite sets of prime numbers

Knowing that $p$ is prime enables us to rule out the possibility that $p+2$ and $p+4$ are both prime, except in the one trivial case that $p=3$, since at least one of $p,\ p+2,\ p+4$ is divisible by ...
5
votes
1answer
153 views

A trivial but maybe nonetheless non-trivial method of inferring primality

The topologist J. H. C. Whitehead (not to be confused with his famous uncle) said it is naive to think a theorem is trivial merely because its proof is trivial. Hence I'm wondering if a certain ...
10
votes
1answer
435 views

Polar Density of a Set of Primes

In Chapter 7 of Marcus' Number Fields, he defines the polar density of a set $A$ of primes of a number field $K$ as follows: Definition: If some $n$th power of the function $$\zeta_{K,A}(s) = ...
1
vote
1answer
107 views

Relations between coefficient and exponent of Proth prime form $k\cdot 2^n+1$?

Definition: Proth number is a number of the form : $$k\cdot 2^n+1$$ where $k$ is an odd positive integer and $n$ is a positive integer such that : $2^n>k$ My question : If Proth number is prime ...
0
votes
1answer
140 views

Integer polynomials with $p$ dividing $f(p)$

If $f \in \mathbb{Z}[x]$ is such that $p \mid f(p)$ for all primes $p$, then $x \mid f(x)$ in $\mathbb{Z}[x]$. This follows by writing $f(x) = \sum \limits_{i=0}^d c_i x^i$ and noting that $c_0 \equiv ...
0
votes
1answer
48 views

How to prove this modular criterion for prime numbers of the form $p=2^n \pm a$?

How to prove following statement : For prime numbers $p$ greater than $3$, it is true that: if $p=2^n-a$ and $a\equiv 1 \pmod 6$ then $p\equiv 1\pmod 3$ if $p=2^n+a$ and $a\equiv 5 \pmod ...
6
votes
3answers
1k views

If the Goldbach Conjecture is True, does it make it easier to find large primes?

I was just reading Is every positive nonprime number at equal distance between two prime numbers? (current hot topic) and was reflecting on the fact that computing security (cryptography) is based ...
16
votes
3answers
2k views

Is every positive nonprime number at equal distance between two prime numbers?

For example $8$ is in the middle of the interval between $5$ and $11$, $9$ is at equal distance between $7$ and $11$; $10$ between $7$ and $13$.
3
votes
2answers
229 views

If $a^n+n^{a}$ is prime number and $a=3k-1$ then $n\equiv 0\pmod 3$?

Is it true that : If $a^n+n^{a}$ is prime number and $a=3k-1$ then $n\equiv 0\pmod 3$ where $a>1,n>1 ; a,n,k \in \mathbb{Z^+}$ I have checked statement for many pairs $(a,n)$ and it ...
14
votes
2answers
825 views

Proof involving induction and primes

I'm looking to prove that: $$p_n \leq 2^{2^{n-1}}$$ Where $p_n$ denotes the $n$th prime in ascending order. The proof method is induction. I've solved my base case, that is: $n=1$ $p_1 = 2$, ...
25
votes
6answers
3k views

Percentage of primes among the natural numbers

How high is the percentage of primes in $\mathbb{N}$? ($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$) The percentage has to be lower ...
3
votes
1answer
108 views

Is this proof about the form $2^n \pm a$ correct?

I want to prove following statement : For prime numbers $p$ greater than $3$, it is true that: $a)$ if $p=2^n-a$ and $a=6k+1$, then $n$ is an odd number. $b)$ if $p=2^n+a$ and $a=6k-1$, ...
6
votes
3answers
404 views

Proof that for all distinct primes $p, q$, there exists $n$ so that $p+n$ is prime, but $q+n$ isn't

Imagine two distinct prime numbers $p$ and $q$. Intuitively, I'd say that there is always a natural number n so that $p+n$ is a prime number, but $q+n$ isn't. I was given two hints: for each ...
3
votes
3answers
385 views

Calculating $\pi(x)$ , a new idea?

I am asking myself if instead of working with the primes in the calculation of $\pi(x)$ up to $x$, we instead work with the composite numbers and then using a simple subtraction to get $\pi(x)$. After ...
2
votes
3answers
188 views

Show there is no prime in a range of numbers

How do I show that except for 5039, there is no prime between 5033 and 5047. I just need a nudge in the right direction, no idea how to start the problem :(
0
votes
1answer
224 views

reliable formulas/algorythms to find approximate number of primes up to a value and fast deterministic ways to check if a number is prime

I'm new to this place and I have two problems. I'm writing a program and I need to know: (A) A formula/algorithm for the approximate number of prime numbers up to a number. Example: let's say that I ...
3
votes
2answers
253 views

Proofs from the BOOK: Bertrand's postulate Part 3: $\frac{2}{3}n<p \leq n \rightarrow$ no p divides $\binom{2n}{n}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 9: I have to show, that for $\frac{2}{3}n<p \leq n$ there is no p which divides ...
2
votes
0answers
75 views

Prime numbers of the form: $k\cdot 2^n \pm 1$ , where $k<3n$

Is it true that : For every $n$ there exists a number $k<3n$ such that: $k\cdot 2^n-1$ or $k\cdot 2^n+1$ is prime,where $k,n\in \mathbf{N}$ Maple code that prints least $k$ such that ...
3
votes
0answers
198 views

How to find $\beta$ and $\alpha$?

$\mathbb{P}$ is the prime numbers set. $p \in \mathbb{P}$ $a,b,c \in \mathbb{N}$ $n=a p^b+c$ where $c= n\bmod p$ $b$ is the highest power of $p$ who divides $n-c$ How to find $\beta$ where ...
2
votes
0answers
68 views

Prime numbers of the form : $2^{n+a}+2^{n} \pm 1$ , where $0 \leq a < n$ and $n \equiv 0 \pmod 6$

Is it true that : For any positive integer $n$ such that $n \equiv 0 \pmod 6$ there is at least one prime number of the form: $p=2^{n+a}+2^{n} + 1$ , or , $p=2^{n+a}+2^{n} - 1$ with ...
3
votes
1answer
181 views

If $2^n+n^2$ is prime number then $n \equiv 0 \pmod 3 $?

Is it true that : $((2^n+n^2) \in \mathbf{P} \land n \geq 3)\Rightarrow n\equiv 0 \pmod 3 $ I have checked this statement for the following consecutive values of $n$ : ...
2
votes
3answers
412 views

Are there infinitely many primes of the form $k\cdot 2^n +1$?

Let's observe following matrix with an infinite number of elements : Elements of the main diagonal are of the form $n\cdot2^n+1$ . These numbers are known as Cullen numbers . It is an open question ...
3
votes
1answer
272 views

If two primes differ by $n$, then infinitely many primes differ by $n$

A proof I'm writing rests on something I can't prove, probably beyond my knowledge, but it seems right: For any two primes $p_k, p_l$ (not necessarily consecutive) such that the distance between ...
1
vote
1answer
222 views

Prime reciprocals sum

Let $a_i$ be a sequence of 1's and 2's and $p_i$ the prime numbers. And let $r=\displaystyle\sum_{i=1}^\infty p_i^{-a_i}$ Can r be rational, and can r be any rational > 1/2 or any real ? ver.2: ...
2
votes
2answers
119 views

Evaluating two limits related to prime numbers

How to find these limits $\displaystyle\lim_{n\to\infty}\left(\ln(\ln(n)) - \sum_{k=2}^n\frac1{k \ln(k)}\right)$ ? and $\displaystyle\lim_{n\to\infty}\left( \ln(\ln(n)) - ...
0
votes
2answers
210 views

Can someone give me a counterexample to disprove this statement?

Claim : For any even number $n$ there is at least one prime number of the form : $$p=k\cdot2^{n}-1$$ with following properties : $k=2^{a-n}+1 , n\leq a < 2n , $ and $a,n\in ...
4
votes
1answer
211 views

Is $k^2+k+1$ prime for infinitely many values of $k$?

Let's define an infinite sequence of positive integers as : $a_n=k^2+(2n-1)k+2n-1 $ , where $ k,n \in \mathbf{Z^{+}}$ Suppose that one can prove that this sequence contains infinitely many ...
1
vote
0answers
132 views

Binary sequences in primes

Is anything known about these problems? If we make a string S of 0's and 1's with 1 in n'th position if the the nth prime $p_n$ is of the form $1+m 2^{9^{9^{9^{9}}}}$, else 0, does every finite string ...