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

14
votes
2answers
362 views

A conjecture concerning primes and algebra

A monoid morphism $\psi:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ is defined by an arbitrary function $f:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ and defines a group homomorphism $\varphi:\mathbb ...
14
votes
1answer
254 views

Prime pair points slope approaches 1

Take the list of primes, $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \ldots$$ and create ordered $(x,y)$ pairs by grouping in sequence, $$(2, 3), (5, 7), (11, 13), ...
14
votes
1answer
369 views

Primey Pascal's Triangle

Imagine that we have a triangle that starts with 2,3 and grows like Pascal's triangle but instead uses the smallest prime $\geq$ to the sum of the above two primes. Visually: $$ ...
14
votes
1answer
287 views

Sum of reciprocals of primes factorial: $\sum_{p\;\text{prime}}\frac{1}{p!}$

The series $$\sum_{p\;\text{prime}}\frac{1}{p}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\cdots$$ diverges as is well known. How about the following? ...
14
votes
1answer
334 views

Are all primes Euclid primes?

I was learning Euclid's theorem. If we repeat his construction (properly modified to give only primes) then will we skip any primes? Formally: $p_1 = 2$, and $p_{n + 1} = \text{smallest} \; q \in ...
14
votes
1answer
2k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
14
votes
1answer
180 views

Consequences of the negation of the Riemann hypothesis

There are many sources documenting the consequences of the Riemann hypothesis, but I can't find one discussing the consequences of its negation, particularly concerning the prime distribution. Can ...
14
votes
1answer
306 views

Primes as quotients

I ask this question based on a comment of David Speyer in another question. What primes are of the form $$ \frac{p^2-1}{q^2-1} $$ where $p$ and $q$ are prime? The first prime not apparently of this ...
14
votes
0answers
446 views

Sorting of prime gaps

Let $g_i $ be the $i^{th}$ prime gap $p_{i+1}-p_i.$ If we re-arrange the sequence $ (g_{n,i})_{i=1}^n$ so that for any finite $n$ the gaps are arranged from smallest to largest we have a new sequence ...
14
votes
0answers
398 views

Divergence of the Derivative of the Prime Counting Function

On the one hand, the Prime Counting Function $\pi_0(x)$ maybe be written $$ \pi_0(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) \tag{1} $$ with $ \operatorname{R}(z) = ...
14
votes
2answers
311 views

Is this olympiad-like question about remainders an open problem?

Suppose that we are given two positive integers $x$ and $y$ such that $$x \mod p \leqslant y \mod p$$ for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative ...
13
votes
7answers
3k views
13
votes
5answers
1k views

Is that true that all the prime numbers are of the form $6m \pm 1$?

Is that true that all the prime numbers are of the form $6m \pm 1$ ? If so, can you please provide an example? Thanks in advance.
13
votes
4answers
2k views

Is there a sequence of 5 consecutive positive integers such that none are square free?

Is there a sequence of 5 consecutive positive integers such that none are square free? A number is square free if there is no prime number p such that $p^2 \mid n$ What I've tried doing so far is to ...
13
votes
7answers
11k views

Is a prime factor of a number always less than its square root?

I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for ...
13
votes
8answers
1k views

Does the formula $\sqrt{ 1 + 24n }$ always yield prime?

I did some experiments, using C++, investigating the values of $\sqrt{1+24n}$. ...
13
votes
4answers
1k views

Proof that there are infinitely many prime numbers starting with a given digit string

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they ...
13
votes
1answer
401 views

A simple way to obtain $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s}$

Let $ p_1 <p_2 <\ldots <p_k <\ldots $ the increasing list in set $\mathbb{P}$ of all prime numbers . By Infinite geometric series $\sum_{k=0}^\infty r^k = \frac{1}{1-r}$ for all $s>1$ ...
13
votes
1answer
2k views

Prime with digits reversed is prime?

Well, just another idea came up into my mind and i have no idea how to solve it :D Is there infinitely many prime numbers, which are not repunits and their inverse is also prime? (For example, inverse ...
13
votes
2answers
247 views

Prove that $m^{2013}-m^{20}+m^{13}-2013$ has at least $N$ prime divisors

for positive integer $N>1$,There always exists $m$ such that $$m^{2013}-m^{20}+m^{13}-2013$$ has at least $N$ prime divisors Thank you all, this is good problem, but I don't know how to solve it.
13
votes
1answer
280 views

What is the smallest integer $n$>1 such that $n^{5000}+n^{2013}+1$ is prime?

Which is the smallest integer $n>1$, such that $$n^{5000}+n^{2013}+1$$ is prime ? Since $x^{5000}+x^{2013}+1$ is irreducible over $\mathbb{Q}$ and has value $1$ for $x=0$, there should be ...
13
votes
3answers
204 views

If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The proof is already given in the textbook but I tried other way around. Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So ...
13
votes
2answers
263 views

$x^2+x+1$ is the cube of a prime.

Please help me find all natural numbers $x$ so that $x^2+x+1$ is the cube of a prime number.(Used in here)
13
votes
1answer
551 views

Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
13
votes
2answers
753 views

Ulam spiral: Is there an “unusual amount of clumping” in prime-rich quadratic polynomials?

I was reading Martin Gardner's Mathematical Games column on the Ulam spiral which appeared in the March 1964 issue of Scientific American. (The spiral actually featured on the cover of that issue.) ...
13
votes
2answers
1k views

Twin, cousin, sexy, … primes

Twin, cousin, and sexy primes are of the forms $(p,p+2)$, $(p,p+4)$, $(p,p+6)$ respectively, for $p$ a prime. The Wikipedia article on cousin primes says that, "It follows from the first ...
13
votes
1answer
770 views

What's the probability that a sum of dice is prime?

Prompted by today's Minute Math question on the MAA site (http://amc.maa.org/mathclub/5-0,problems/T-problems/T-web,ia/2005web/tb05-12-ia.shtml), I started thinking about the probability that the sum ...
13
votes
4answers
784 views

Is every prime the average of two other primes?

$\forall {p_1\in\mathbb{P}, p_1>3},\ \exists {p_2\in\mathbb{P},\ p_3\in\mathbb{P}};\ (p_1 \neq p_2) \land (p_1\neq p_3) \land (p_1 = \frac{p_2+p_3}{2})$ Now I'm not a 100% sure about this, but I ...
13
votes
2answers
327 views

Number of digits until a prime is reached

Begin with a random digit from $1$ to $9$. Add a random digit to the right-hand side from $0$ to $9$ until a prime number is reached. How many digits are necessary in the avarage ? More precisely: ...
13
votes
1answer
199 views

Primes in $\lfloor a^{n} \rfloor$

Motivated by the question Is there any result, that says that $\lfloor e^{n} \rfloor$ is never a prime for $n>2$?, take a real number $a>1$ and consider the sequence $\lfloor a^{n} \rfloor$. ...
13
votes
1answer
385 views

Prime spiral distribution into quadrants

Is it known that the primes on the Ulam prime spiral distribute themselves equally in sectors around the origin? To be specific, say the quadrants? (Each quadrant is closed on one axis and open on ...
13
votes
1answer
571 views

Going from $\Lambda$ to a prime count

A 1997 paper of √Čtienne Fouvry and Henryk Iwaniec, Gaussian primes, concerns the prevalence of primes that are of the form $n^2+p^2$ for prime $p$. The asymptotic result is $$\sum_{n^2+p^2\le ...
13
votes
1answer
359 views

An estimate for relatively prime numbers

Fix a finite collection of distinct prime numbers $(p_1, p_2, \dots, p_s)$, denote their product by $N$. For a natural number $n$ let $\beta(n)$ be the number of $k$, $k\leq n$, for which $k$ and $N$ ...
13
votes
0answers
80 views

What other prime numbers have been ruled out as counterexamples to the Feit-Thompson conjecture?

Given distinct primes $p$ and $q$, $$\frac{p^q - 1}{p - 1}$$ is never a divisor of $$\frac{q^p - 1}{q - 1}.$$ Or so we believe. If $p = 2$, then it's clear that no odd prime $q$ can make a ...
13
votes
0answers
176 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
12
votes
5answers
3k views

Why does one counterexample disprove a conjecture?

Can't a conjecture be correct about most solutions except maybe a family of solutions? For example, a few centuries ago it was widely believed that $2^{2^n}+1$ is a prime number for any $n$ . For ...
12
votes
6answers
3k views

Prime factorization of 1

Fundamental Theorem of Arithmetic says every positive number has a unique prime factorisation. Question: If 1 is neither prime nor composite, then how does it fit into this theorem?
12
votes
5answers
2k views

Is there a one-to-one function from the natural numbers to the primes?

Is there a function $f : \mathbb N \rightarrow \mathbb P$, where $\mathbb P = \{p \in \mathbb N \mid \ p$ is prime$\}$, such that $f$ is injective? It is known that no such polynomial function exists. ...
12
votes
6answers
16k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
12
votes
3answers
503 views

Twin primes of form $2^n+3$ and $2^n+5$

How to prove that $2^n+3$ and $2^n+5$ are both prime for only finitely many integers $n$? And how to prove that there are infinitely many primes of the form $2^n+3$ and $2^m+5$
12
votes
3answers
397 views

Are there any Combinatoric proofs of Bertrand's postulate?

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and ...
12
votes
4answers
2k views

Why does “the probability of a random natural number being prime” make no sense?

I read an essay about prime numbers. In it the author suggests that a natural first question to ask is, What is the probability of a random natural number being prime? but proceeds to dismiss ...
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 ...
12
votes
1answer
172 views

Is $\sum\frac1{p^{1+ 1/p}}$ divergent?

Is $\displaystyle\sum\frac1{p^{1+ 1/p}}$ divergent? How can we prove that it is divergent or convergent in analytic number theory? I know what bound of the n-th prime number is, and that its order is ...
12
votes
5answers
461 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
12
votes
1answer
165 views

What is the significance of the power of $3$ in the sequence of primes given by $\lfloor A^{3^n}\rfloor ?$

Mill's constant is a number such that $\lfloor A^{3^n}\rfloor$ is prime for all $n$. The existence of such an $A$ was proven in $1947$. I know little about number theory, but I am curious as to why ...
12
votes
2answers
404 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 ...
12
votes
2answers
873 views

nth powers modulo all primes

Let $a \in \mathbb{Z}$, $n \in \mathbb{N}^*$ be integers, and set $P=X^n - a$. Let us consider the three following statements : 1) $P$ has a root in $\mathbb{Z}$ (i.e. $a$ is an nth power) 2) $P$ ...
12
votes
2answers
238 views

An upper bound for $\log \operatorname{rad}(n!)$

Let $n>1$ be an integer and let $\operatorname{rad}(n!)$ denote the radical of $n$-factorial. (The radical of an integer $m$ being, loosely speaking, the product of the prime divisors of $m$.) Can ...
12
votes
3answers
613 views

Consecutive Prime Gap Sum (Amateur)

List of the first fifty prime gaps: 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4. My ...