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
2answers
72 views

series for $n$-th prime number and prime counting function

"Theoretical Computer Science Cheat Sheet" gives the following: $$p_n = n \ln n + n \ln \ln n - n + n \frac{\ln \ln n}{\ln n} + \mathcal{O}\left( \frac{n}{\ln n}\right)$$ $$\pi (n) = \frac{n}{\ln n} + ...
2
votes
0answers
145 views

Are there infinite many primes p such that 2p-1 is also prime?

I did a search online and found a similar notion called Sophie Germain prime, which by definition is a prime $p$ such that $2p+1$ is also prime. Sophie Germain primes are conjectured to be of infinite ...
1
vote
1answer
31 views

Can the natural numbers be defined in terms of the non-trivial zeta zeros?

Can the natural numbers be defined in terms of the non-trivial zeta zeros? Presumably they can, since $\pi(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^\rho),$ and $\zeta(s)=\sum ...
0
votes
2answers
42 views

If an integer $a$ is coprime with an integer $b$, then will the integer $a$ also be coprime with the integer $9a + b$?

If an integer $a$ is coprime with an integer $b$, then will the integer $a$ also be coprime with the integer $9a + b$ ?
0
votes
1answer
102 views

Prime Number Primality Testing

I've developed a code and method that works in tandem with an earlier prime number algorithm I developed here: ...
4
votes
2answers
59 views

Heuristic for Dirichlet's Theorem on Arithemtic Progression

If we let $\pi_{a,d}(x) = \{p \leq x: p \mbox{ prime, } p \equiv a \mod{d}\}$ then it is a well known result that if $(a,d)=1$ then $$\lim_{x \to \infty} \frac{\pi_{a,d}(x)}{\pi(x)} = ...
1
vote
3answers
106 views

Number theory divisibility - simple way to prove this is prime?

Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z<y$, then let $x=y/z$. Prove that $x$ must be a prime number. Is there a simple way to solve this? It ...
3
votes
1answer
98 views

Is sum of square of primes a square of prime?

I would like to know if it has been proved that : There are no $a$, $b$ and $c$, all prime numbers, such that $a^2 + b^2 = c^2$ There are no $a$, $b$, $c$ and $d$, all prime numbers, such that $a^2 ...
2
votes
1answer
90 views

The Prime Numbers Set is infinite. Is this proof correct?

Proposition: The Prime Numbers Set is infinite. Proof: Suppose we have a finite set of prime numbers $p_{1}, p_{2}, ..., p_{n}$ such that $p_{n}$ is the largest of them. Define $ c := ...
17
votes
4answers
497 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
3
votes
0answers
155 views

Differences between large numbers with many factors has little factors

I apologise beforehand for the informality and lack of precision in this question but it is that way because it comes from only an intuition, nothing more than a heuristic argument. Say one has two ...
1
vote
3answers
44 views

Given all the multiples of a prime number $p \in \mathbb{Z}$, is $p\mathbb{Z}$ an ideal of $\mathbb{Z}$?

So I'm having a little trouble understanding the concept of an ideal. The book gives the "classic example" of $2\mathbb{Z}$, the even integers, saying these form an ideal. Would I be correct in ...
0
votes
1answer
146 views

Is it possible to represent subsets of natural numbers as groups with prime generators?

I'm learning group theory and I'm trying to consider the "symmetry" of a certain group of natural numbers: Here's the idea, all natural numbers are comprised of multiples of primes. So a subset would ...
5
votes
4answers
406 views

Solutions to $p+1=2n^2$ and $p^2+1=2m^2$ in Natural numbers.

$$p+1=2n^2$$$$p^2+1=2m^2$$ Find positive integers $m,n$ and prime $p$ satisfying the above two equations. What would people commonly do? Subtracting both the equations. You get: ...
1
vote
1answer
271 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
10
votes
5answers
2k views

Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16… alternate between prime and composite

I am working through an elementary number theory book and I have come across the following problem. Show the following claims are wrong: Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ...
3
votes
2answers
53 views

Automorphisms of $\langle \mathbb{N}, \cdot \rangle$

It is an elementary fact that multiplication in $\mathbb{N}$ is commutative: $$(\forall n,m)\ n \cdot m = m \cdot n$$ This - among other things - implies that the representation of an $n \in ...
0
votes
1answer
40 views

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$? Would you use $\lim_{x\to \infty}\frac{\pi(x)\log(1-\frac{1}{x})}{\frac{1}{\log x}} = 1$? and how would you show this? Can you ...
1
vote
1answer
95 views

Induction on prime numbers

To dive straight into the question: is there a form of induction which works on prime numbers? I've thought, and while I'm pretty sure it can be done om numbers such as even numbers or numbers ...
1
vote
1answer
95 views

A better way to prime factorize a set of numbers?

Let's say I have a range of numbers starting from 1 to 10^9 and I need to prime factorize each one of them.My basic algorithm is: 1.Use prime-sieve algorithms(Atkins or Eratosthenes(segmented ...
1
vote
1answer
261 views

Implementing a function in PARI/GP

I want to define a function: $$g(n)= \begin{cases} +1 & \text{if $n=1$},\\ +1 & \text{if $n$ is an odd indexed prime}, \\ -1 & \text{if $n$ is an even indexed prime},\\ (-1)^r & ...
1
vote
1answer
170 views

Andrica's conjecture implies Bertrand's Postulate?

Let $p_n$ denote the $n$th prime. Recall Andrica's conjecture, which states that $$\sqrt{p_{n+1}}-\sqrt{p_n}<1\quad\text{ for all }\,n.$$ I think Andrica's conjecture implies Bertrand's postulate. ...
1
vote
2answers
112 views

$2p-2$ as the sum of consecutive prime numbers

Progress: Let $p$ be a prime such that $p≡1$ (mod 6) then $2p-2$ can be written uniquely (up to the order of addends) as the sum of some consecutive prime numbers. These are first ten examples: ...
2
votes
2answers
103 views

Do the ratios of successive primes converge to a value less than 1?

I think it's a pretty straightforward question. Does $\lim_{n \to \infty}{\frac{p_n}{p_{n+1}}} < 1?$ ***$p_n$ denotes the nth prime. Since the average gap increases between successive primes by ...
2
votes
1answer
75 views

Algorithm to identify complex Mersenne primes?

I am thinking on the complex analogue of the Mersenne primes. I think, some like a "complex Mersenne prime" could be a complex prime in the form $$2^{a+b\frac{pi}{2}i}-1$$ Where $a+bi$ is a complex ...
0
votes
1answer
86 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
0
votes
1answer
48 views

How many distinct lists of 14 integers $L=\{v_1,\ldots ,v_{14}\}$ exist satisfying $v_i \geq v_{i+1}\geq 0$ and $\sum _{i=1}^{14}(v_i) \leq 54$

I am trying to solve the following problem: I have an ordered list of integers $L = \{v_1,\ldots ,v_{14}\}$ with fourteen elements, satisfying the following two conditions: $v_i \geq v_{i+1}\geq 0$ ...
3
votes
3answers
396 views

Deterministic random numbers generator using $p^n \mod q$

I figured that I can create a deterministic "random" numbers generator by utilizing a bit of "magic" that I picked up from some cryptography. However I seem to have missed a detail. Basically the ...
2
votes
1answer
44 views

Finding the lowest number (or an upper bound to the lowest number) not congruent to a set of moduli

Note: if finding x is not possible, an upper bound, where there must be at least one number less than said number which is not congruent to the set, would be helpful. The set: For my purposes, the ...
2
votes
1answer
49 views

Is $\sum_{n=1}^N e^{2 \pi p_n z i}$ bounded for irrational $z$?

Let $p_n$ be the $n$th prime number. If $z$ is irrational real, is it known whether the partial sums $\sum_{n=1}^N e^{2 \pi p_n z i}$ are bounded? It seems the partial sums are unbounded if $z$ is ...
1
vote
2answers
48 views

Asymptotic behaviour of $\prod_{p \leq x} (1 + 4/(3p) + C p^{-3/2})$

I'm reading Montgomery and Vaughan and in it they state quite simply \begin{equation} \prod_{p \leq x} \left(1 + \frac{4}{3p} + \frac{C}{p^{3/2}} \right) \ll (\log x)^{4/3} \end{equation} as $x ...
0
votes
1answer
71 views

Is there a 10-digit emirp?

Does a 10-digit emirp exist? Unfortunately, the lists of emirps I could find on the Web are quite small and my programming skills aren't good enough to write a program to check all the primes up to ...
2
votes
2answers
73 views

Diophantine: $px^2+2=y^2$ where $p\in \mathbb{P}$

Solve the Diophantine Equation: $px^2+2=y^2$, where $p$ is a prime number and $x,y$ integers. I tried this for ages but didn't get anywhere, but I don't know any advanced machinery since I am only in ...
0
votes
1answer
98 views

What percent of numbers are primes? [duplicate]

I understand that there are infinitely many primes and (obviously) infinitely many integers, but is there any way to calculate the total percentage of integers that are primes? Thanks
0
votes
1answer
98 views

Infinite Wilson Prime proof

An article I read recently about Wilson Primes stated that, while 5, 13, and 563 are the only known terms, there is an infinite number of Wilson Primes. I was wondering if someone could verify this ...
2
votes
1answer
61 views

Iterated Pi function

Does anyone have any information on iterating the prime counting function. Specifically, $\pi_n(x)$=$\pi(\pi_{n-1}(x))$, and $\pi_1(x)$=$\pi(x)$. I'm looking for anything on this function, what it may ...
1
vote
3answers
381 views

Distribution of prime numbers. Can one find all prime numbers?

I want to know if it is possible to find a formula that gives all the prime numbers? or can one find the distribution of prime numbers? I know that there is a set of ongoing research on prime ...
8
votes
1answer
98 views

What is $\limsup\limits_{n\rightarrow\infty}\left\{\frac{p_{m+1}}{p_m}|m\in \mathbb{N},m\geq n\right\} $?

What is $$\limsup\limits_{n\rightarrow\infty}\left\{\frac{p_{m+1}}{p_m}\middle|m\in \mathbb{N},m\geq n\right\} = ?$$ where $p_i$ is i'th prime number. We know that this limsup exists because of ...
2
votes
2answers
655 views

Prime Number Sum Sequence (Amateur)

SOLVED: This is false Beginning with 3, add the next consecutive prime (2) and then take that sum (5) and add that to next consecutive prime (3) to get (8), and so on... $$ 3 + 2 = 5 $$ $$ 5 + 3 = 8 ...
1
vote
1answer
38 views

Generalizing primality to other operations

(By "number" below I always mean an element of $\mathbb{Z}^+\setminus $$\left\{1\right \}$.) We all know that a number $p$ is prime iff it cannot be represented as $ab$ for any two numbers $a$ and ...
1
vote
2answers
139 views

Property of set of prime numbers

let $\{p_1,p_2,p_2,\cdots ,p_r\}$ be the set of $r$($\ge2$) pair wise distinct prime numbers i.e.., $(i\ne j \implies p_i \ne p_j)$ for all $1\le i,j\le r$ ${Statement}$ : For any such ...
0
votes
1answer
122 views

Computing infinite product over primes

How can I compute $$ \prod_p \left(1+\frac{k}{p}\right)\exp(-k/p) $$ where $0<k<e$ and the product is over all primes $p$? Background L. G. Sathe proved [1] that there are $$ ...
1
vote
4answers
3k views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
5
votes
1answer
88 views

Is any elementary proof important (beside Selberg's work) ?

Is any elementary proof important (beside Selberg's work) ? Plus, why is the elementary proof of prime number theory by Selberg so important ? Selberg was awarded the Field medal is mainly because ...
1
vote
1answer
43 views

Conditions for which $(\sum p_i)(\sum \frac{1}{p_i})$ over an arbitrary $i$ for a set of primes $\{p_i\}$ is unique?

I am looking for conditions (if any are needed beyond properties of primes) for which $(\sum p_i)(\sum \frac{1}{p_i})$ over an arbitrary $i$ for a set of primes $\{p_i\}$ is unique in that there is ...
6
votes
1answer
352 views

Can Fermat's little theorem be used to list primes?

I was reading about Fermat's little Theorem, which states that if p is prime, then for any integer a, $a^p-a$ would be a multiple of p. So, I started wondeing if this could be used to determine ...
-2
votes
2answers
116 views

Why is $y^{x-1}-1$ divisible by $x$?

I wanted to know if there is a way to prove that $y^{x-1}-1$ is divisible by $x$. Where $x$ is a prime number and is not equal to $y$, and $y$ is any positive whole number besides $1$. For example, ...
2
votes
1answer
269 views

Unusual behavior of 210 and 199 regarding prime numbers

Adding 210 to 199 over and over again, you get 8 more primes that can be arranged together into a 3x3 magic square: 1669 199 1249 619 1039 1459 829 1879 409 Is there any other pairs of numbers ...
48
votes
5answers
5k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
3
votes
1answer
527 views

Golden Ratio of Primes (Amateur)

Unable to find information elsewhere, so I'll try here. What two consecutive primes are closest to producing the Golden Ratio? Or two of any Primes? Has this been determined? Thanks!