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

0
votes
1answer
35 views

What does “421 is the smallest prime formed by the powers of two in logical order from right to left” mean and if so is it correct?

I've seen this on number gossip and a few other places, but I'm not exactly sure what it means. The only possibilities I have thought of for what they mean are "421 is the smallest center squared ...
1
vote
0answers
27 views

The asymptotic behaviour of triples $n!+q^{n!}=c$, where $q$ is the first prime greater than $n$, and abc conjecture

For a large positive integer $n$, let $q=q(n)$ (below we denote this $q=q(n)$ by $q_{N}$ because we assumed that is the $N$-th prime number) the first prime number which is (strictly) greater that ...
1
vote
1answer
45 views

What does the sum of the reciprocals of composites run along?

This is fairly straight forward: $$\sum_{p\space\text{prime}}^x \frac{1}{p_x} \sim \ln(\ln(x))$$ And if $$\sum_{c\space \text{composite}}^x \frac{1}{c_x}\sim f(x)$$ Then what is $f(x)$?
5
votes
1answer
246 views

Conjectured compositeness tests for $N=k\cdot 2^n \pm 1$ and $N=k\cdot 2^n \pm 3$

How to prove these conjectures ? 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 ~\text{are ...
1
vote
2answers
65 views

Modulus and Fermat's Little Theorem

How do I calculate $ 11^{23} \bmod{163} $ using fermat's little theorem ?
0
votes
1answer
36 views

Counting how many primes exists between square root of a given range?

I am given with a range say l,r(1<=l,r<=10pow14).I am also given with cumulative count of primes no.'s that exists between 1 to 10pow7,e.g for 1,count=0(as no primes exists upto 1),for ...
2
votes
1answer
62 views

What is the smallest “prime” semiprime?

(All dots here means concatenation.) Let $s= ab$ be a semiprime number, then I call s a "prime" semiprime if all these following conditions are satisfied: The reversal of $s$ is a prime The ...
2
votes
0answers
52 views

Beal Conjecture and ($\bmod 3$) operation [closed]

When we apply a ($\bmod 3$) operation on the $A^x +B^y =C^z$ we will see some strange results. For e.g.: Let $A=6m+1$ & $B=6n+1$. Since $A$ & $B$ are odd numbers, $C$ will have to be even. ...
0
votes
2answers
72 views

The number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors

Prove that the number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors, not necessarily distinct. Doing what the hint has suggested, I have done the ...
6
votes
1answer
162 views

Number we know all prime numbers less than [duplicate]

We already know some very big prime numbers. ($2^{257,885,161} − 1$ as of time of writing is the largest known) It is my understanding, that we know it is a prime number but we don't know all prime ...
4
votes
1answer
108 views

Find the integral values for which $\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$

Let $\pi(x)$ be the prime counting function. The problem is, Find all integral values of $x,y$ such that, $$\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$$ I have no idea as to where to begin with. ...
3
votes
2answers
98 views

Is $\frac{2^{n-1}-1}{n}$ an integer only when $n$ is an odd prime?

I have the equation $$k = \frac{2^{n-1}-1}{n}$$ and wonder if $k$ is an integer when $n$ is an odd prime. The numerator is always odd, so even $n$ have no integer solutions. But when I run a test, it ...
4
votes
3answers
118 views

How can $p^{q+1}+q^{p+1}$ be a perfect square?

How can one find all primes $(p,q)$ such that $p^{q+1}+q^{p+1}$ is a perfect square I considered it $\mod 2$ and found a trival solution . Im curious about an eventual answer Diophantine equations ...
1
vote
2answers
157 views

Proof of the reciprocal of all semiprimes diverging?

$$\sum_{\text{semi-primes}}\frac{1}{s}=\frac{1}{4}+\frac{1}{6}+\frac{1}{9}+\frac{1}{10}\cdots$$ I almost positive that this sum diverges, but I would really like to see a very thorough proof. Thank ...
1
vote
2answers
37 views

Is this proof for number of divisors correct?

I'm trying to prove that the number of divisors of any given number is $(a_1+1)(a_2+1)...(a_r+1)$ Where $a_1, a_2 ... a_r$ are from $p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ The problem is that the proof ...
2
votes
1answer
24 views

find least multiple formed only of 1's of given number

The problem states that given a number find the least multiple formed only of 1's. If no such number exists then 0 will be the answer. For example for: ...
2
votes
1answer
58 views

The Sieve of Alice- Number theory Riddle

I am trying to prove the result for a problem which I am unable to do so! The answer is simply $\frac{N}{2}$ when N is even and $\frac{N}{2}+1$ when $N$ is odd. But I do not see why?? Can you give me ...
3
votes
3answers
47 views

primes whose difference is a multiple of $n$

Hello everyone this is my first question here so if there are any suggested edits feel free to participate! Is it true that for every $n$ there two prime numbers $p$ and $q$ with $n\mid p-q$? I have ...
2
votes
1answer
34 views

Understanding Wright's proof of Landau's theorem

I'm reading Wright's A simple proof of a theorem of Landau in which the core argument is a proof by induction and I find myself stuck on a major point. I must be misunderstanding notation or something ...
0
votes
2answers
52 views

Summation of a series of Positive Prime numbers

Is there a way to find the sum for a set of positive prime numbers (e.g., the first $25$ prime numbers) without just arbitrarily adding them up shorthand?
0
votes
1answer
61 views

Out of all the proofs of the PNT, which one is the most accessible?

I have been studying the continuation of the Riemann zeta function $\zeta(s)$ for the past while. I can prove that all the zeroes must lie in the critical strip.I am currently in the process of using ...
6
votes
2answers
96 views

Do the sum of all prime reciprocals with the digit $3$ converge or diverge?

$$\frac{1}{3}+\frac{1}{13}+\frac{1}{23}+\frac{1}{31}+\frac{1}{37}+\frac{1}{43}\cdots$$ Intuitively, I feel that this sum converges, but I really don't know why, (or if I am correct). Can I have a ...
0
votes
0answers
58 views

Prime divisors in Andy Loo's proof…

http://arxiv.org/pdf/1110.2377v1.pdf I have one more question related to that proof. Look at the definition of the symbol ${s \brace r}$ (page 4). Why if $\frac{3n}{4}<p\le \frac{4n}{5}$, then $p$ ...
1
vote
2answers
69 views

$a^4+b^4+c^4+d^4 \neq 2^{2011}$

Prove (elementary, meaning no high level theorems used) that there can not exist 4 prime numbers a,b,c,d $\geq$ 7 such that \begin{equation}a^4+b^4+c^4+d^4=2^{2011}\end{equation} I tried the ...
1
vote
1answer
72 views

Quadratic polynomials describe the diagonal lines in the Ulam-Spiral

I'm trying to understand why is it possible to describe every diagonal line in the Ulam-Spiral with an quadratic polynomial $$2n\cdot(2n+b)+a = 4n^2 + 2nb +a$$ for $a, b \in \mathbb{N}$ and $n \in ...
0
votes
1answer
30 views

For $n$ an even number and $p$ a prime, does $\lfloor {\frac {n}{4}} \rfloor= \frac{1}{\pi (n)-\pi (n/2)} \sum_{n/2<p<n} p-\frac {n}{2}$ hold?

I was playing around with prime numbers and I noticed that for $n$ an even number, the average of the distance between all primes between $n/2$ and $n$ and $n/2$ is equal to $\lfloor {\frac {n}{4}} ...
1
vote
1answer
33 views

Distribution of primes and product of primes

I know for large numbers $\le N$, the distribution of primes is about $N / \ln(N)$. I want to know thet distribution for primes and the product of unique primes ($p_0, ..., p_0 p_1, ..., p_0 p_1 ...
0
votes
2answers
54 views

Analytic continuation of primality function

(There is my initial question, but by advice of @Charles I'm splitting it) For integers we have a primality function: $$ isprime(n)=\begin{cases}1,&\text{$n$ is prime}\\0,&\text{$n$ is not ...
3
votes
1answer
67 views

A few questions about Andy Loo's proof of existence of primes between 3n and 4n…

I have a few questions about Andy Loo's proof (get it here): why, for example, if $2n<p\le3n$, then $p$ does not divide $\binom{4n}{3n}$? Same situation for $\frac{4n}{3}<p\le\frac{3n}{2}$... ...
6
votes
1answer
101 views

Prove for $2p +1$ divides $2^p + 1$

The following theorem is well known and already proven by Lagrange 1775 Let $p = 3$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p - 1$. But how can we prove this: Let ...
0
votes
0answers
57 views

Is there a systematic way of referring to a prime?

Is there a systematic scheme for identifying primes? For small numbers, it is easy to simply reproduce the whole prime, but for larger numbers, it seems like it could get cumbersome. For instance, ...
1
vote
2answers
37 views

How many $2$-Sylow subgroups in $G$ with $|G| = 2^2\cdot 3$?

I have a group $G$ with $|G| = 2^2\cdot 3$. I also know it has $4$ Sylow-$3$ subgroups. I need to show that there is $1$ Sylow-$2$ subgroup. (This is all I have left from the full question.) Any ...
0
votes
1answer
66 views

Sum of primes at minimal $\gt t!$

$$2+3+5+17+97+599\cdots a_t \gt t!$$ What does that mean? Well it is a sum that follows specific rules. For one, the number of terms in the sequence is $t$. Similarly, $a_t$ represents the $t$'th ...
2
votes
1answer
56 views

Solutions of $(2x-1)^x\equiv1\mod\ p$ [closed]

Has the equation $(2x-1)^x\equiv 1\mod{p}$, for $p=1+6qx$, where $p$, $q$ are primes, $x$ is an odd integer and $x<p$ any solutions except $x=1$? Many thanks.
1
vote
1answer
34 views

Weierstrass factorization theorem and primality function

I'm interested in application of the Weierstrass factorization theorem to the primality function. Let $np(x)\colon \mathbb N\to \mathbb N$ is a "not-prime" function: $$ np(x) = \begin{cases}1, & ...
2
votes
2answers
33 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
2
votes
1answer
27 views

A congruence for the prime counting function in Wolfram.What does it actually say?

I saw today in functions.wolfram.com a congruence for the prime counting function which says $\binom {2prime(k)-1} {prime(k)-1} \pmod{prime(k)^3}=1$ (the third congruence at the bottom). What does ...
0
votes
2answers
47 views

On primality of the numbers of the form $10^{2k} - 10^{(k+1)} -1$

Has anyone seen proof that numbers of the form $10^{2k} - 10^{k+1} - 1 \space \forall k \ge 2$ are prime?
6
votes
0answers
135 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
3
votes
3answers
69 views

Number of primes from $n!+1$ to $n!+n$

Why aren't there any primes between $n!+1$ and $n!+n$ for all $n>1$? This question was on AHSME 1969 #23, but the question is trivial because it's multiple choice. However, I have no idea how to ...
4
votes
2answers
71 views

If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then…

Let $a,m\in \mathbb N$ Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m) Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa? I ...
2
votes
3answers
308 views

Statistical observations about primes

Are there statistical observations about prime numbers showing that primes are not random? For example obviously primes are $1$ or $-1$ mod $6$, but are these remainder distributed equally? What I ...
25
votes
5answers
17k views

Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
3
votes
2answers
34 views

Is it known whether there are ever infinitely many primes of the form $\prod_i p_i^{n_i} + 1$ where the $p_i$ are fixed primes but the $n_i$ can vary?

So if we fix finitely many primes $p_i$, where one $p_i$ is $2$, but let the powers $n_i$ on the $p_i$ vary, is it known whether it is ever possible to have infinitely many primes of the form $\prod_i ...
2
votes
1answer
48 views

Comparing $\pi(x)$ and $\pi^{(k)}(x)$

We say a k-almost prime is an integer that results as the product of k prime, counting repetition. For example, $12$ is a $3$-almost prime as $12= 3 \times 2 \times 2$. Additionally, we define ...
0
votes
0answers
10 views

Convenient goedel numbering for finite register machines?

Overview I'm trying to find a goedel numbering for finite register machines, which is convenient in two ways: when ordering machines by their numbering, simple machines shall come first, i.e. ...
2
votes
1answer
72 views

How do computers generate primes so quickly?

From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on ...
7
votes
2answers
178 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
0
votes
1answer
48 views

Time complexity of a simple factoring algorithm?

This has puzzled me for a little. I start off with a list of primes that is sufficiently large. For my number $n$, I do trial division of primes in ascending order until I reach a prime that divides ...
1
vote
2answers
25 views

Distribution of decimal repunit primes

The prime number theorem describes the distribution of prime numbers in positive integers. Is there a similar theorem describing the distribution of primes among positive integers of the form ...