Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

1,829 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
165 views

More on primes $p=u^2+27v^2$ and roots of unity

Given, $$p=u^2+27v^2=6m+1\tag1$$ and the cubic, $$x^3+x^2-2mx+N=0\tag2$$ with its constant expressed in terms of $(1)$ as, $$N = \frac{1}{27}(1-3p\pm2pu)\tag3$$ and the sign $\pm u$ chosen ...
5
votes
0answers
85 views

More primes of the form $6k-1$ than $6k+1$

Let $a_n:= $ number of primes of the form $6k-1$ and $\le n$ and $b_n:= $ number of primes of the form $6k+1$ and $\le n$. I was playing with my computer and noticed that $a_n\ge b_n$ for all $n\...
5
votes
0answers
258 views

Does this prime generating way generate all the prime numbers?

I've thought of the following algorithm to find the entire list of prime numbers: Take a prime number $p$ to your list. $1.$ Multiply all the numbers in your list and call the number you get $...
5
votes
0answers
195 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 4

Following a previous question (here you'll find an introduction): A paper by Maier which refutes Cramer's Model suggests we should replace the heuristic "$\Bbb P(n\in\mathcal P)=1/\log n$" with $$\...
5
votes
1answer
781 views

Euler's proof of divergence of sum of reciprocals of primes

On Wikipedia at link currently is: \begin{align} \ln \left( \sum_{n=1}^\infty \frac{1}{n}\right) & {} = \ln\left( \prod_p \frac{1}{1-p^{-1}}\right) = -\sum_p \ln \left( 1-\frac{1}{p}\right) \\ ...
5
votes
0answers
122 views

Birthday problem & primes

Let $\pi_k(n)$ be the almost prime counting function, then $\pi_k(2^kn)$ reaches a max value, since $\pi_k(2^kn)=\pi_{k+1}(2^{k+1}n)$ for large enough $k$. (eg, $\pi_{5}(272)=\pi_{6}(2\times272)=\...
5
votes
0answers
153 views

How many solutions to $x^2-x+5\equiv 0\pmod{p^2}$

Let $p$ be a prime. How many solutions modulo $p$ has the equation $x^2-x+5\equiv 0\pmod{p^2}$. My thoughts: I first consider equation modulo $p$. I've found: no solutions for $p=2$ one solution for ...
5
votes
0answers
337 views

Logical consequence of Euclid's theorem

Are there any far reaching non-trivial consequences of Euclid's infinitude of primes where theorems make use of it? Wikipedia does not have the list of applications of this theorem, rather modern ...
5
votes
0answers
625 views

Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$. Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: ...
5
votes
0answers
165 views

Primes of the form $\frac{n^2-n+4}{2}$ satisfy Hardy-Littlewood analogue?

Let $n,a,b$ be positive integers with $a<b$. Consider primes of the form $f(n)=\dfrac{n^2-n+4}{2}$. Let $C(a,b)$ denote the amount of primes of the form $f(n)$ between (and including) $f(a)$ and $f(...
5
votes
0answers
269 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
5
votes
0answers
157 views

Is the application of $\mu$ on $P_x(s)^k$ analogous to the differentiation $\frac{d^k f(\lambda) }{d\lambda^k}\biggr|_{\lambda=0}$?

Let me start with the following on elementary symmetric polynomials: The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity $...
5
votes
0answers
131 views

Approach to elliptic curve $y^2=x^3+1/4+p/a^2$

While taking a brute-force look at this question I discovered that it seems that almost every prime (I'll conjecture every prime larger than 20627) can be written as $p=w^2+wc+d$ for $w,c,d\in \mathbb{...
5
votes
0answers
170 views

Proof of infinitude of primes whose reversal in base 10 is also prime

Is there any proof of infinitude of http://oeis.org/A007500 primes. If you want to generate them here is trivial and naive python program. ...
5
votes
0answers
703 views

What does this say about prime numbers?

I was having fun with Sage when I noticed something interesting: ...
5
votes
0answers
353 views

Prime zeta definition, multiplication by zero

Wikipedia has a page about the prime zeta function which is defined as follows: $$P(s)=\sum_{p\;\text{prime}} \frac1{p^s}$$ I entered this additional definition: Define a sequence: $$a_n=\prod_{d\...
5
votes
1answer
234 views

Largest prime factors of two consecutive natural numbers

Let $u(n)$ be the numbers of positive integers $k \le n$ such that the largest prime factor of $k+1$ is greater than the largest prime factor of $k$. Similarly, let $l(n)$ be the numbers of positive ...
4
votes
0answers
145 views
+50

show that $n\Upsilon_{n-1} \equiv -1 (mod\ n)\ \ \ \ \ \iff \ \ n\ is\ prime $

The Bernoulli numbers $B_n$. where all numbers $B_n$ are zero with odd index $n>1$. first values are given by $B_{0} = 1$ , $B_{1} = -1/2$, $B_{2} = 1/6$, $B_{3} = -1/30$. Agoh conjecture: let $...
4
votes
0answers
175 views

Diophantine equation: $n^2=c(4ab-a-b)-b$?

Let $n$ be a positive integer. The Diophantine equation $$ n^2=c(4ab-a-b)-b,\qquad (a,b,c\in\mathbb{Z}^+) $$ is solvable for $n\equiv\pm1\pmod3$, but I stuck for $n\equiv0\pmod3$. Is there any ...
4
votes
0answers
114 views

Is there a finite number of binary-prime loops?

All natural numbers have a unique factorization into primes. I'm interested in a set $Q$ for which all natural numbers have a unique factorization into distinct elements of $Q$. This leads inductively ...
4
votes
0answers
107 views

Are there squares $s$ other than $9$, $121$, and $361$ such that the number of primes $\leq s$ divides the number of composites $\leq s$?

Let $C(n)$ be a function that counts composites $\leq n$ , $P(n)$ be a function that counts primes $\leq n$, and $s$ be a perfect square. How many squares $s$ have the property $C(s)/P(s)$ is an ...
4
votes
0answers
62 views

Primes $p$ which satisfy $p \mid \sum_{i=1}^{p-1} i!$

This question is inspired from @Mathphile's problem: The value$\sum_{i=1}^n i!$ where $n \in \mathbb{N}$, is only semiprime for $n=3,4$ One can easily solve this conjecture by knowing that $9 \mid ...
4
votes
0answers
184 views

Are $3$, $9$ the only natural numbers $n$ for which both $2^n-n$ and $2^n+n$ are prime?

I searched for natural numbers $n$, where $2^n-n$ and $2^n+n$ are both prime for the range of $n \le 10^5$ on PARI/GP and found that 3, 9 are the only solutions in this range. Note that since $2^n-n$...
4
votes
0answers
121 views

A heuristic argument for the Goldbach conjecture?

This question here is purely speculative so be warned if you read on: This question is related to a sequence $b_n$ which is defined here: A series related to prime numbers For the numbers $a_{2n,2}$ ...
4
votes
0answers
281 views

Iterated Twin Prime conjecture

Here is the beginning of the list of sums of twin prime pairs (OEIS A054735): 8, 12, 24, 36, 60, 84, 120, 144, 204, 216, 276, 300, 360, 384, 396, 456, 480, 540, 564, 624, 696, 840, 864, 924,... "...
4
votes
0answers
97 views

Primes of the form $a^n-(a-1)^n$

For a given $n$, consider the assertion: $\exists a \in \Bbb Z : a^n-(a-1)^n\ \text{is prime}\tag*{}$ How can one do one of the following: Prove that the assertion is true for all integer $n > 1$...
4
votes
1answer
96 views

How to approach this sequence? (elementary number theory)

Given is the following sequence: $a_1 = 1$ and $a_n$ equals the biggest prime divisor of $1+ a_1*\dots*a_{n-1}$ . It is then claimed: $11$ does not occur in this sequence. How can one approach this ...
4
votes
0answers
54 views

Non-Chen primes dividing $3^k+3$ and $2^k-3$

A non-Chen prime is a prime $p$ such that $p+2$ is neither a prime nor a semi-prime. $3^6+3=732$ is divisibile by the non-Chen prime $61$. On the other hand, $2^6-3=61$. Are there infinitely many $...
4
votes
0answers
85 views

Are there infintely many primes generated by the recursion $c_{n+1} = \lceil \frac{3}{2} c_{n} \rceil$?

Inspired by a recent discussion (How to solve a ceiling expression or recurrence equation?) I stumbled on the question: Are there infinitely many primes in power ceiling series? If not there must ...
4
votes
0answers
173 views

What is the proportion of primes for which a polynomial has a root

Clearly $ax + b \equiv 0 \pmod{p}$ is solvable for almost all primes $p$. In fact, if $p$ does not divide $a$, then $x \equiv -ba^{-1}$ is a solution. So for any linear polynomial $f(x)$ we get that ...
4
votes
0answers
55 views

Positive integers satisfying: for all odd prime powers $p^k < n$, $n - p^k$ is prime

Given positive integer $k$, define the subset $S(k)$ of positive integers $n$ where for every odd prime power $p^k < n$, $n - p^k$ is prime. In other words, $$S(k) = \{n \in \mathbb{N} \mid \forall ...
4
votes
1answer
200 views

A conjecture on the closeness of twin primes

Let $p_1$ and $p_2$ be twin primes, and let $p_1-1=a_1\times b_1$ and $p_2+1=a_2\times b_2$ be such that $|b_1-a_1|$ and $|b_2-a_2|$ are minimised. Similarly, let $p_1+1=p_2-1=a\times b$ be such that ...
4
votes
0answers
84 views

When does an equation of the form ${1 \over p}{(2^{p-1}-1)} = 2pxy+x+y$ have no integer solutions?

Specific equations of the form below (for different given values of p, a prime number) will either have positive integer solutions for $x$ & $y$, or will not have any integer solutions. $${2^{p-1}...
4
votes
1answer
99 views

Reciprocity of different prime numbers can approximate $1$?

I want to see if there exist $p_1<p_2<p_3<\cdots<p_{1000}$ different prime numbers such that $|1/p_1+\cdots+1/p_{1000}-1|\le ({1\over p_{1000}})^2.$ a) what is my point with this? Nothing....
4
votes
0answers
103 views

Root 2 primes make up 38% of all prime numbers.

It has been conjectured by Emile Artin that the primes of primitive root 2 are infinite. Is it known that their density among all primes is about 1/3 and that this density is constant up to 1 ...
4
votes
0answers
89 views

For what $n$ does there exist $a,b > 0$ such that there are exactly $n$ primes $p$ such that $ap + b$ is a perfect square?

Consider the question: Given positive integers $a,b$, for what primes $p$ is $ap + b$ a perfect square? Denote the solution set by $P(a,b) = \{p \mid p \text{ is prime and } ap + b \text{ is a perfect ...
4
votes
0answers
91 views

Is $p^2+q^2+r^2=3^k$ with primes $p,q,r$ solvable for every odd positive integer $k\ge 3\ $?

For the positive odd integers $3\le k\le 25$, the equation $$p^2+q^2+r^2=3^k$$ with primes $p,q,r$ is solvable. Here is one solution for every exponent , calculated with PARI/GP : ...
4
votes
1answer
109 views

Is the conjecture about prime numbers true?

Let $p_n$ be the $n$-th prime number. Is it true that if $n$ is sufficiently large then will $$p_1×p_2×p_3×...×p_n+1$$ always be a composite number?
4
votes
0answers
422 views

Initial values of Inkeri's primality test for Fermat numbers

Can you provide a proof or a counterexample to the claim given below ? First , we shall give a definition of the Inkeri's primality test for Fermat numbers : Fermat's number $F_m=2^{2^m}+1$ ($m \...
4
votes
0answers
58 views

Greedy Cyclic Group Orders

Any group of order $n$ is cyclic if and only if $n$ is square-free and no prime factor of $n$ is congruent to one modulo any other prime factor of $n$.* Thus, the smallest such $n$ divisible by two ...
4
votes
0answers
233 views

Linear combination of relative primes

I apologise if this question is a duplicate, I couldn't find it anywhere. I came across the following problem: An ordered pair $(x,y)$ of integers is called a primitive point if the greatest ...
4
votes
0answers
106 views

Improving clarity and argumentation with hard-to-describe combinatorial proof

I'm doing undergraduate research and the content of my paper depends on the following lemma. I tried something like a combinatorial proof, but it is clearly not rigorous, partly because my argument is ...
4
votes
0answers
60 views

gaps between square roots of primes

It is well known that the difference $p_{n+1}-p_n$ can be arbitrarily large. What about $\sqrt{p_{n+1}}-\sqrt{p_n}$, or in general, $p_{n+1}^t-p_n^t$ for $t<1$? Has this problem been investigated? ...
4
votes
0answers
95 views

Are there other values of $n$ that generate $p^2$?

I found a pattern that looks quite interesting. $$\begin{align} 2(4 + 2) + 13^3 &= 47^2 \\ 2(4 +5) + 7^3 &= 19^2 \\ 2(4 + 8) + 1^3 &= 5^2.\end{align}$$ It seems at first that if $p$ is ...
4
votes
0answers
96 views

Smallest prime of the form $68^k+k!+1$?

Let $f(n)$ be the smallest integer $k\ge 1$ such that $$n^k+k!+1$$ is prime or undefined if no such $k$ exists. I determined the values $f(n)$ for the even numbers $2,4,6,\cdots $ and $f(56)$ turned ...
4
votes
0answers
97 views

Primes formed by concatenating the mersenne numbers from $2^2-1$ to $2^n-1$

Concatenate the mersenne numbers $2^2-1$ to $2^n-1$ and define $f(n)$ to be the emerging number , for example $$f(6)=\color\red {3}\color\green {7}\color\red {15}\color\green {31}\color\red {63}$$ We ...
4
votes
0answers
135 views

Why do all residues occur in this similar sequence?

A formula similar to this coined in by Enzo Creti is gained as follows : Instead of concatenating the Mersenne numbers $M_n$ and $M_{n-1}$ , we do it in reverse. The formula for this sequence is $$f(...
4
votes
1answer
241 views

A solution using 'Lifting the exponent' lemma to IMO 1990 P3

Question: Find all positive integers $n$ such that $$n^2\mid 2^n+1$$ My solution: Lemma (Lifting the exponent): Let $v_p(n)$ denote the highest power of a prime $p$ that divides $n$. That is, $v_p(...
4
votes
0answers
150 views

2017 was prime. 2018=2 x 1009 is double a prime. What does the future portend?

What is the likelihood in the future that a year will be prime or double a prime? Are these years rare? Dependent on the prime gaps? What's the best proven frequency? Happy New Year! :-)
4
votes
0answers
160 views

What should I do if I wrote an algorithm faster than the Sieve of Atkin?

I have been having fun with prime numbers. I sat down and, following a hunch and after a few weeks of headbanging against the wall, I was able to write an algorithm that, at least on my local, ...