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

2
votes
0answers
48 views

Number of primes of type 4*n +1 in a range

I want to find number of primes which are congruent 1 (mod 4) in a range [a, b]. The range can be of order $10^9$ as a and b can be from $1$ to $10^9$. I tried segmented sieve but for a range so ...
2
votes
0answers
162 views

Approximation to $\pi(x)$ conjecture.

A friend conjectured that $\left[\prod_{k=1}^{a_j <\sqrt{x}} \left(1-\frac{1}{a_k}\right)\right] x$ is usually closer to $\pi(x)$ than $\operatorname{Li}(x)$ is for some (fixed) sequence of ...
2
votes
0answers
57 views

Related almost primes

Do there exist positive integers $w, x, y, z$ and an infinite set $A$ such that for all $a \in A$, $a$ is a $w$-almost prime and $b = y \cdot a + z$ is an $x$-almost prime? With $(w,x,y,z) = ...
2
votes
0answers
137 views

How to investigate whether number is prime

Investigate whether 36611 is prime. Show the first few steps of the procedure. This is the question. Is it enough to show its not divisible by 2, 3, 5 ? Surely this must not be enough. But how do i ...
2
votes
0answers
193 views

Prime number finding via polynomials

I try to find approximation polynomial to estimate which number is prime or not. Addtion to this, (If It is possible) To find the closed form of coefficients of the series ($c(n)$) Euler found the ...
2
votes
0answers
31 views

Does the sum over the normed differential of the prime power function equal $2\log2\pi$?

Let $p\in \Bbb P$ a prime and a prime power function: $$\xi_p(x) = p^x$$ with $x \in \Bbb R^+_0$ hence: $$\xi'_p = \frac{d}{dx}\xi_p=\xi_p \log p$$ Taking into account E. Muñoz García and R. ...
2
votes
0answers
109 views

Are there infinitely many primes $p_k$ such that $(p_k-1)!+p_k$ is a also prime?

I am wondering whether there are infinitely many primes $p_k$ such that $(p_k-1)!+p_k$ is also prime. Given that $p_k \equiv 2 \pmod 3$. For a very large prime, I can assume Stirling's ...
2
votes
0answers
55 views

Merthen's third theorem and uncertainty of prime hits

Conjecture(1) Merten's third theorem says: $$\lim_{L\to\infty}\ln L\prod_{p\le L}\left(1-\frac1p\right)=e^{-\gamma}$$ we have a wild discussion here around the table whether it is possible to ...
2
votes
0answers
37 views

Could a determinstic primality test specialized to this form of prime exist?

Is it possible there could be an "efficient" deterministic primality test for prime numbers of the form $$(2^n + 1)^2 - 2$$ or $$(2^n - 1)^2 - 2$$ in the same vein as the Lucas-Lehmer test for ...
2
votes
0answers
68 views

Unique decomposition of $c$ sums of products of $k$ numbers greater than 1, allowing duplicates?

This question differs from Unique decomposition of $c$ sums of products of $k$ prime numbers, allowing duplicates? in that prime number restriction is changed to any number greater than 1. Suppose ...
2
votes
0answers
286 views

Prime numbers with binomial coefficients

Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$ for every $$j\in ...
2
votes
0answers
315 views

Definition of a complex prime

If there would be such a thing as a complex prime number, how would it be defined? A normal prime is defined as a number only dividable by one or itself.. would that be "1+1i" with complex numbers? ...
2
votes
0answers
57 views

Prove $\left(\frac{q(q+1)}{p}\right) =\left(\frac{1+q^{-1}}{p}\right )$ for $p\gt2$ a prime, and any $q \in \mathbb{Z^+} $.

For $p\gt2$ a prime, and any $q \in \mathbb{Z^+} $, Show that $\left(\frac{q(q+1)}{p}\right) =\left(\frac{1+q^{-1}}{p}\right )$ where the terms are legendre terms. I saw this result as part of a ...
2
votes
0answers
137 views

For which positive integers n does there exist a prime whose digits sum to n?

Motivated by this earlier question, I thought of this problem: Question: For which positive integers $n$ does there exist a prime whose decimal digits sum to $n$? We can make two "easy" ...
2
votes
0answers
73 views

$\sum_p z^p$ where $p$ is prime

I've started reading Shakarchi's Complex Analysis, and I thought about something interesting. If I haven't mistaken, for any subsequence $A\subset \mathbb{Z}^+$, $\sum_{n\in A} z^n$ has radius of ...
2
votes
0answers
96 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
2
votes
0answers
185 views

How many co-primes are there for a big integer N over a specified interval?

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
2
votes
0answers
33 views

Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits

I was solving this equation:- $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$ $$ a, m \; are \;coprime $$ I solved it bruteforcely but it ...
2
votes
0answers
82 views

asymtotic ratio of nonsquarefree repunits

Let $R_n:=\frac{10^n-1}{10-1}$ (called a repunit) and $\mu$ be the Moebius function. Also $[n]:=\{1,2,3,\cdots, n\}, A_n:=\{m \in [n]| \mu (R_m)=0\}.$ What is the value of $\lim \limits_{n ...
2
votes
0answers
209 views

Integral with Sums of Prime Counting Functions

I came across the following integral, while working with products of $\zeta$ primes function: $$ \int_{1}^{x}t^{-s-1} \sum_{i=1}^{\pi(t^{1/2})}\left[\pi\left(\frac{t}{p_i}\right)-i+1\right] dt, $$ ...
2
votes
0answers
33 views

What is a good tool for this job involving the prime spiral?

I'm interested in studying the prime spiral interactively. This question talks about some interesting patterns in the spiral involving quadratic equations. The idea I had was, write a program that ...
2
votes
0answers
75 views

Prime numbers of the form: $k\cdot 2^n \pm 1$ , where $k<3n$

Is it true that : For every $n$ there exists a number $k<3n$ such that: $k\cdot 2^n-1$ or $k\cdot 2^n+1$ is prime,where $k,n\in \mathbf{N}$ Maple code that prints least $k$ such that ...
2
votes
0answers
68 views

Prime numbers of the form : $2^{n+a}+2^{n} \pm 1$ , where $0 \leq a < n$ and $n \equiv 0 \pmod 6$

Is it true that : For any positive integer $n$ such that $n \equiv 0 \pmod 6$ there is at least one prime number of the form: $p=2^{n+a}+2^{n} + 1$ , or , $p=2^{n+a}+2^{n} - 1$ with ...
2
votes
0answers
167 views

$n$ by $n$ Primally Magic Squares

(Again copied verbatim from a September 2009 thread I made.) A Primally Magic Square (PMS) is exactly like a traditional magic square with a change of criteria. Where a traditional magic square is ...
1
vote
0answers
80 views

Conjecture: for even n without primitive roots modulo n, the set of $m \in Max(ord_n(k))$ contains one pair of primes $p_1+p_2=n$ (Goldbach)

Conjecture: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes ...
1
vote
0answers
25 views

Estimating the number of elements with a given least prime factor in a sequence of consecutive integers

Let $a,n$ be any positive integers. Let $\varphi(x)$ be the Euler totient function. It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will ...
1
vote
0answers
57 views

Problem with multivaluedness of $(-1)^{\frac 14}$

Assume that $p\equiv3\mod4$ is an odd prime and $k$ an odd number. Then $$m=(-1)^{\frac{p^k-p^{k-1}+2}{4}}$$ seems to be always the value $1$ (?). This would be interesting how one can prove this - I ...
1
vote
0answers
52 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
1
vote
0answers
54 views

the sum of the reciprocals of the primes

The sum of the reciprocals of the primes is $\sum \limits_{p}\frac{1}{p} \approx N \ln\ln(N)$ what about this sum where $p_{3}=3,p_{5}=5,p_{n}=\sum \limits^{N}_{j=5}\frac{1}{p_{j}} \sum ...
1
vote
0answers
37 views

Marking Integers Using a Wheel

Suppose I had a wheel of diameter one meter and I was charged with marking every meter along an infinite stretch of a beach. The strategy is to insert pegs into the wheel so that every point that is a ...
1
vote
0answers
19 views

Is there a standard notation for $(p_i-k)(p_{i-1}-k)(p_{i-2}-k)\cdots$ where $k$ is a small positive integer

For $k=0$, there is: $p_i\# = (p_i)(p_{i-1})(p_{i-2})\cdots(5)(3)(2)$ For $k=1$, there is: $\varphi(p_i\#) = (p_i-1)(p_{i-1}-1)(p_{i-2}-1)\cdots(5-1)(3-1)(2-1)$ Is there any other notation that ...
1
vote
0answers
44 views

Comparative prime number theory with a small tweak

Fix $a, k \in \mathbb{N}$ relatively prime. For $x \in \mathbb{R}$ recall the function $$ \pi(x; k, a) = \sum_{\substack{p \leq x \\ p \equiv a \pmod{k}} } 1 $$ where $p$ denotes the primes. ...
1
vote
0answers
44 views

Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number?

Given some $n \in \mathbb{N}$, is there a name or notation for any/all of the following? The set of all factors $F(n)$ of $n$ (including 1 and $n$). The ascending sequence of non-unique prime ...
1
vote
0answers
55 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
1
vote
0answers
80 views

Euclid's theorem: Paul Erdős's proof on the infinitude of primes

Seemingly simple question: Quote from Wikipedia: First note that every integer $n$ can be uniquely written as $rs^2$ where $r$ is square-free, or not divisible by any square numbers (let ...
1
vote
0answers
27 views

Maier's theorem

I have some questions with Maier's theorem https://en.wikipedia.org/wiki/Maier%27s_theorem If $1 < \lambda < 2$, then what? If $x+(\log x)^\lambda = x^{1+1/\pi(x)}$, then what? In particular, ...
1
vote
0answers
28 views

Question on Newman's proof of the Prime Number Theorem

I am reading through Zagier's exposition of Newman's proof of the prime number theorem and I do not understand one of his arguments when proving his so called Analytic Theorem. This theorem states the ...
1
vote
0answers
34 views

When looking at the mod as binary value

Look at the next value: $$617*947 = 584299$$ 617, 947 are prime values. I want to see what are all the possible solutions for the next equation, for $k=4$: $$(a\mod k)(b\mod k) = 584299\mod k$$ ...
1
vote
0answers
66 views

Reasoning about $z^n = x^m + y^m$

Let $z,n,x,y,m$ be positive integers with $z \ge 5$ and $m \ge 3$ and $m$ odd. Does it follow that: $z$ cannot be prime if $p \ge 5$ and $p | z$, then either $p > m$ or $p|m$ Here is my ...
1
vote
0answers
160 views

Is $\frac{\text{next maximal}}{\text{maximal}} <= 2$ true?

Let $G_n(X)$ denote the $n^{th}$ record largest gap between consecutive primes below $X$, which some call maximal gap. Let $G_{n+1}(Y)$ denote the size of next larger maximal record gap in size from ...
1
vote
0answers
64 views

Can this approach to showing no positive integer solutions to $p^n = x^3 + y^3$ be generalized?

The following problem is a $2000$ Hungarian Olympiad question. Find all primes $p$ such that: $$p^n = x^3 + y^3$$ The answer is that there are only $2$ solutions: $2^1 = 1^3 + 1^3$ $3^2 = 2^3 + ...
1
vote
0answers
39 views

Lucas-Lehmer primality test and numbers form $k^{n}-1$

Is it possible to use Lucas-Lehmer test for testing the primality of numbers of the form $k^{n}-1$, where $k > 2$? For $k = 2$ (Mersenne number) $c_0 = 4$. What would be $c_0$ for $k > 2$?
1
vote
0answers
37 views

Bunyakovsky conjecture for cyclotomic polynomials

This article on Wikipedia: http://en.wikipedia.org/wiki/Bunyakovsky_conjecture says: In fact, it can be shown that if for all natural number $ n $, there exists a natural number $ x > 1 $ such ...
1
vote
0answers
36 views

Is there a better way to search a string so that I don't get false positives?

I've been using this equation to find primes of a specified range, in this example the range is 10 to 10000. Go ahead and try it out, your monitor will not catch fire. The problem I'm now having is ...
1
vote
0answers
98 views

Is every integer $\geq5$ the sum of two primes and a power of a prime?

Is every integer $\geq5$ the sum of two primes and a power of a prime (where $1$ is included in the prime powers)? I don't really expect someone to prove this here, but I wonder if the question has ...
1
vote
0answers
32 views

Solutions $n^2 = -1 \mod (p_n-1)$

Consider the equation $n^2 = -1 \mod (p_n-1)(*)$ where $p_n > n$ and $f(n) = p_n$ is the largest prime that satisfies the equation. $f(n)$ gives $p_n$ assuming there is a solution to the equation ...
1
vote
0answers
42 views

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation?

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation? $2$ is the only prime with $1$ one, the Fermat ...
1
vote
0answers
35 views

On integer $n>1$ and prime $p$ such that $p<n$ , $p$ does not divide $n$ and $n-p$ is a prime

Let $n>1$ be a given integer and $p$ be a prime less than $n$ and not dividing $n$ ; so $p$ and $n$ are co-prime ; hence $n-p$ and $n$ are also co-prime ; I would like to ask when is $n-p$ also is ...
1
vote
0answers
28 views

How quickly can we multiply hypercomplexes?

If we start with a hypercomplex number with $2^n$ entries, how quickly can we multiply it by another hypercomplex number, modulo a prime? EXAMPLE For example, with $n=1$, we get the complex numbers. ...
1
vote
0answers
36 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...