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

12
votes
5answers
390 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
2answers
771 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
1answer
266 views

The number of prime years in a lifetime

$2013$ is not a prime: $3 \times 11 \times 61$. I was born in a prime year, and if I live as expected according to the statistics for U.S. males, I will just reach another prime year, $2027$. That ...
12
votes
3answers
284 views

Divergence for $p$ prime numbers and convergence for $m$ composite numbers

Does there exist a sequence $(a_n)_{n\in \mathbb N} \in \mathbb C^{\mathbb N}$ such that : For all $p$ prime numbers the series $\displaystyle \sum_{n\in \mathbb{N}} a_n^p$ diverges, and for ...
12
votes
2answers
343 views

Are there Groups of Strictly Primes

Motivation Since Euclid's proof of the infinitude of the primes, the structure and properties of primes has always fascinated mathematicians. This lead to great work in their properties and ...
12
votes
1answer
283 views

Chebyshev: Proof $\prod \limits_{p \leq 2k}{\;} p > 2^k$

How do I prove the following: $$\prod_{p \leq 2k} \; p > 2^k \text{ with } p \in \mathbb{P}$$ I tried induction, but I didn't know how to go on because I don't have a look at all numbers. ...
12
votes
2answers
363 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
12
votes
2answers
463 views

On prime factors of $n^2+1$

It is a well-known conjecture that there are infinitely many primes of the form $n^2+1$. However, there are weaker results that one can prove. For example, There are infinitely many positive ...
12
votes
1answer
335 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: $$ ...
12
votes
2answers
689 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.) ...
12
votes
1answer
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 ...
12
votes
1answer
469 views

What is the probability that some number of the form $10223\cdot 2^n+1$ is prime?

I (David Speyer) took the liberty of doing a fairly major rewrite of this question. I hope I haven't gone too far, but I think there is an interesting question hiding here. Sierpinski proved that ...
12
votes
1answer
259 views

Combinatorial prime problem

Update As Barry Cipra noted in the comments, a better framing of the question might be that I'm looking at absolute differences $|a−b|$ or totals $a+b$ for $5$-smooth numbers $a$ and $b$ satisfying ...
12
votes
1answer
381 views

Prove that $\sum\limits_{i=0}^{k} p^{2i}$ ($p$ is prime) is never a perfect square

Prove that $$ \sum_{i=0}^{k} p^{2i} $$ where $k > 0$ and $p$ is an arbitrary prime, is never a perfect square. I think you can prove it by letting $q = \sum\limits_{i=0}^k a_ip^i$, then expanding ...
12
votes
1answer
331 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$ ...
12
votes
0answers
158 views

Sheldon Cooper Primes

On the $73^{\text{rd}}$ episode of the Big Bang Theory, Dr. Sheldon Cooper, an astrophysicist portrayed by Jim Parsons $(1973 - \stackrel{\text{hopefully}}{2073})$ revealed his favorite number to be ...
11
votes
7answers
775 views

Define an infinite subset of primes such that the sum of reciprocals converges

How can we define an infinite subset of primes such that the sum of reciprocals converges? $S=\{p\in \mathbb{Z}^+ : p\ \text{is prime and some condition on}\ p\}$ s.t. ...
11
votes
4answers
1k views

Is it true that the book 'Calculate Primes' has found the pattern? [closed]

I read about a book called 'Calculate Primes' by James McCanney. It claims to have cracked the pattern for generating families of primes, and also the ability to factorize large numbers. ...
11
votes
3answers
584 views

Irrationality of “primes coded in binary”

For fun, I have been considering the number $$ \ell := \sum_{p} \frac{1}{2^p} $$ It is clear that the sum converges and hence $\ell$ is finite. $\ell$ also has the binary expansion $$ \ell = ...
11
votes
5answers
2k views

Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$? This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
11
votes
3answers
376 views

A prime of the form $38111111\ldots$

Let $z(n)$ denote the number given by $38$ followed by $n 1$'s. What is the least number $n$, such that $z(n)$ is prime ? With brute force, I checked up to $7000$ digits and did not find a prime. ...
11
votes
7answers
8k 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 ...
11
votes
3answers
661 views

How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$?

I saw reference to this result of Chebyshev's: $$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty,$$ and its relation to the Prime Number Theorem. I'm looking into an ...
11
votes
4answers
1k 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 ...
11
votes
3answers
2k views

Cardinality of the set of prime numbers

It was proved by Euclid that there are infinitely many primes. But what is the cardinality of the set of prime numbers ? Cantor showed that the sets $\mathbb{Q}$ and $\mathbb{Z}$ have the same ...
11
votes
6answers
598 views

What are some easy-to-remember prime numbers?

This is a question without much mathematical value, but since I don't immediately see an answer on Google I thought I'd ask anyway ... I'm looking for some largeish (> 10,000) easy-to-remember primes, ...
11
votes
2answers
352 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 ...
11
votes
2answers
578 views

Can you make any number prime by adding some digits to the right?

To ask in another way: Is it guaranteed that any given sequence of digits will be at the beginning of some prime number? We know from Dirichlet's theorem that there are an infinite number of values ...
11
votes
2answers
223 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 ...
11
votes
3answers
430 views

Number Theory or Algebra?

Prove that if $4^m-2^m+1$ is a prime number, then all the prime divisors of $m$ are smaller than $5$ I initially thought about putting $4^m-2^m+1=p$ where $p$ is some prime and after eliminating ...
11
votes
1answer
345 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$ ...
11
votes
1answer
491 views

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square. I tried brute-force method and tried to find some pattern. I got $p=3,7$ as solutions . Apart from these I have tried for ...
11
votes
3answers
394 views

Why are conjectures about the primes so hard to prove?

I recently started learning number theory, and I've noticed there are many conjectures about the prime numbers that are unproven. Some examples would be whether there are infinite Mersenne, ...
11
votes
2answers
433 views

Asymptotics of LCM

Let $\operatorname{LCM}(x_1,x_2,\ldots,x_n)$ be the least common multiple of the integers $x_i$. How can one find the asymptotics of $\operatorname{LCM}(f(1),f(2),\dots,f(n))$ as $n$ approaches ...
11
votes
1answer
517 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, ...
11
votes
2answers
698 views

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis if at all?

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis? What are the connections between both conjectures if any?
11
votes
2answers
262 views

The Fermat prime 257 and binomial sum $\sum_{n=0}^\infty \frac{(-1)^n}{\binom {8n}{4n}}$?

We have, $\begin{aligned} \sum_{n=0}^\infty \frac{(-1)^n}{\binom n{n/2}} &= \frac{4}{27}(9-\pi\sqrt{3}\,)\\[2.5mm] \sum_{n=0}^\infty \frac{(-1)^n}{\binom {2n}n} &= \frac{4}{5} - ...
11
votes
3answers
264 views

Prove or disprove: $99^{100}+100^{101}+101^{99}+1$ is a prime number

Prove or disprove: $$99^{100}+100^{101}+101^{99}+1$$ is a prime number. My idea: let $100^{101}=x^{x+1}$,then $$99^{100}+100^{101}+101^{99}+1=(x-1)^{x}+x^{x+1}+(x+1)^{x-1}+1$$ is prime number? I ...
11
votes
1answer
165 views

For each $n$, does there exist a prime $p$ and integer $k$ such that $p^k - 1$ has exactly $n$ prime divisors?

Let $n \geq 1$ be some integer. Can we always find a prime power $p^k$ such that $p^k - 1$ has exactly $n$ distinct prime divisors? For example: $n = 1$ example: $2^2 - 1 = 3$ $n = 2$ example: $5^2 ...
11
votes
2answers
778 views

crazy problem - does it have a solution? number theory perhaps?

A few researchers are trying to crack a code which involves discovering the values of three integers. They know they are between 1 and 100 (inclusive), and that they may be the same. They each have a ...
11
votes
1answer
416 views

The Goldbach Conjecture and Hardy-Littlewood Asymptotic

A source I am reading refers to the Goldbach conjecture (that every even number is the sum of two primes), and then immediately follows with the "Hardy-Littlewood conjecture" that $\sum ...
11
votes
1answer
717 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 ...
11
votes
1answer
293 views

Is there any theoretical indication that this conjecture of Catalan could be true?

Belgian mathematician Catalan in $1876$ made next conjecture: If we consider the following sequence of Mersenne prime numbers: $2^2-1=3 , 2^3-1=7 , 2^7-1=127 , 2^{127}-1$ then $$2^{2^{127}-1}-1$$ is ...
11
votes
0answers
391 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 ...
11
votes
0answers
114 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 ...
10
votes
5answers
1k views

Decimal form of irrational numbers

In the decimal form of an irrational number like: $$\pi=3.141592653589\ldots$$ Do we have all the numbers from $0$ to $9$. I verified $\pi$ and all the numbers are there. Is this true in general for ...
10
votes
7answers
610 views

Can true randomness come out of mathematical rules?

For example, prime numbers, they seem very random, and they are defined by a simple set of rules. I can't see how real randomness could exist in the real world, but what about mathematics?
10
votes
3answers
1k views

What is wrong with this proposed proof of the twin prime conjecture?

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds ...
10
votes
4answers
882 views

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$ Really speaking, I don't have any clue ...
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, ...