Tag Info

New answers tagged

0

The sequence is admissible for all $n$. Given $p$, we only need to consider $j\in[0,p-1]$ to get all residues mod $p$ that are covered by the sequence. Since $(p-j+1)(p-j)\equiv j(j-1)\bmod p$, most of the residues are doubly covered, and hence roughly half are uncovered.


0

$(0,2,4)$ is already inadmissible according to the definition: it contains all residues mod 3. So the answer to the first question is negative. The second sequence is clearly admissible (it contains at most $p-2$ different non-zero residues mod $p$).


0

There is no "simple number theory" proof anywhere and it would be nice if some "elementary" proof was presented. However there is an elementary proof here http://www.jstor.org/stable/1969454?seq=1#page_scan_tab_contents but is extremely complicated....


1

This is a very similar question to Most efficient algorithm for nth prime, deterministic and probabilistic? There are quite a few ways, depending on how much you want to optimize, what your expected range is, and how much code you want to write. If you don't have very large inputs, you can compute (easily) an upper bound, then use a segmented sieve ...


0

The New Book of Prime Number Records by Paulo Ribenboim is very good and will most likely fit best to your need. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics by John Derbyshire. I am currently reading this book and it is a great book which tried to explain Riemann hypothesis to a layman (with basic high school math, not ...


0

This is not complete answer, but this answer is illustrative of one way we could try to attempt to answer the first question posted. Consider $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$. $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$ has possible two forms: $\lbrace 2, ..., 2,3,2,p_x,2,p_{x-1},2,3,2,...,2 \rbrace$ or $\lbrace 2, ..., ...


3

The contraint to have a representation as a sum of distinct primes does not really affect the magnitude of $r_k(n)$, i.e. the number of ways to write $n$ as a sum of $k$ primes. Vinogradov's theorem implies that every sufficiently big odd number is the sum of three primes (since it gives a lower-bound for $r_3(n)$), hence every sufficiently big even number ...


1

Here is a page on twin primes that gives a possible estimate for the probability that $x$ is the lower of a twin prime pair: $$\prod_{p\text{ prime}}\frac{p(p-2)}{(p-1)^2}\frac1{(\log x)^2}\\ \approx\frac{0.66016}{(\log x)^2}$$ https://primes.utm.edu/top20/page.php?id=1 The formula was conjectured by Hardy and Littlewood.


3

Since your question relates to a programming task, here a method I have implemented to compute the $k$th prime (in Pascal for a slightly smaller range): Get a better estimate for the lower bound $L \le p_k$ of $p_k$ e.g. from P. Dusart, 1999, The $k$th prime is greater than $k(\log k + \log \log k - 1)$ for $k\ge 2$, Math.Comp.68, available here. Compute ...


0

Because the twin primes have not (yet!) been proven to be infinite, it's hard to give the ratio between twin primes and all primes. But Brun's theorem gives an upper bound which is conjectured to be within a constant factor of the true ratio. In particular, there are O(x/log^2 x) twin primes up to x, and Theta(x/log x) primes, so the ratio up to x is ...


4

I second Martin's recommendation of Pomerance & Crandall. On the popularizer level we have books like George P. Loweke's The Lore of Prime Numbers and David Wells's Prime Numbers: The Most Mysterious Figures in Math. Somewhere in the middle is Ribenboim's Little Book of Bigger Primes. On a more advanced level there are books like Fine & ...


2

Marcus du sautoy Music of the primes provides a good history and is more recreational (ie no proper theorems or proofs) but does get more technical than your average public maths book.


2

You could try Carl Pomerance Prime numbers, a computational Perspective.


2

First note that the two equations you give are equivalent; $$N-p=q-N\quad\Leftrightarrow\quad 2N=p+q\quad\Leftrightarrow\quad N=\frac{p+q}{2}.$$ The problem you give is slightly stronger than the Goldbach conjecture: Suppose for every natural number $N>3$ there are two distinct prime numbers $p$ and $q$ such that $$N=\frac{p+q}{2},$$ For every even ...


2

Your definition of denizen is a very baroque, confused way to describe an extremely simple concept: you're just asking for the longest interval that can be covered with arithmetic progressions, one for each prime up to $p$. When the same number is covered by multiple progressions, you went to great pains to force the denizen to record only the least ...


4

For every prime $p\le n$, there is at most $1$ number in $S$ divisible by $p$. So taking $S$ to be $1$ together with all the primes $\le n$ maximizes the size of $S$ subject to pairwise coprimality. Now the Prime Number Theorem gives us the asymptotics. Remark: One can characterize all maximum-sized subsets $S$ of $\{1,2,\dots,n\}$ such that any two ...


5

Counterexample : $N=356387\cdot 2^{11}+1=12289\cdot 59393\;$ while $\;3^{N-1}\equiv 1\pmod{N}$ It is interesting to observe $\;2^{N-1}\not\equiv 1\pmod{N}\;$ $\;12289=3\cdot 2^{12}+1\;$ while $\;59393=29\cdot 2^{11}+1\;$ so that both prime factors are (minimal) $2^n$ safe-primes : OEIS A051900.


2

I'm not a mathematician but was intrigued as to whether $37:73$ prime pair are unique. As there's been no answer I wanted to share my answer: Within the first 25 million primes $37:73$ are unique when represented in base 10. However, there are a few other unique prime/emirp pairs in other bases as shown below As a reversible number isn't a property of ...


0

Steve Jessop's answer, on stack overflow and linked by Zev Chonoles, contains your answer. Usually a simple hash function works by taking the "component parts" of the input (characters in the case of a string), and multiplying them by the powers of some constant, and adding them together in some integer type. So for example a typical (although not ...


1

Assume by contradiction that there exists a number $n\in\mathbb{N}$ with two prime factors $p,q>\sqrt{n}$: $p$ and $q$ are prime factors of ${n}\implies\color\red{{p}\cdot{q}\leq{n}}$ $p,q>\sqrt{n}\implies{p}\cdot{q}>\sqrt{n}\cdot\sqrt{n}\implies\color\red{{p}\cdot{q}>{n}}$


6

If $p$ and $q$ are primes that are $>\sqrt{n}$, and such that $n$ is divisible by $q$ and $q$, then $n$ is divisible by $pq$. But $pq>n$, which is a contradiction.


5

THERE HAS BEEN AN EDIT TO THE QUESTION. I NO LONGER KNOW WHAT IS BEING ASKED. ORIGINAL: let $$ P = n+x $$ be prime, as stated. What can you say about $$ n^{P} + x \pmod P? $$ What can you say about $$ n^{2P-1} + x \pmod P? $$ $$ n^{3P-2} + x \pmod P? $$ https://en.wikipedia.org/wiki/Fermat%27s_little_theorem Example: $n=2,x=3,P=5.$ $$ 2 + 3 = 5 ...


3

You can have arbitrary large sequence of $0$'s: Suppose not, there is a period $k$ in the decimal expansion. By Dirichlet's theorem, we have infinitely many prime numbers $p$ in the form $$ p= a 10^{k+2} + 1.$$ Then $p^n \equiv 1$ (mod $10^{k+2}$).


5

By Dirichlet's theorem on primes in arithmetic progressions, for any $k$ there are an infinite number of primes of the form $10^km+1$. If you choose $k$ large enough compared to $n$, there will be an arbitrarily large number of consecutive zeros. Therefore, the number can not repeat, and is therefore irrational.


3

It is unclear what you mean with prime powers. If a prime power is written as $n = p^k$, where $p$ is prime, then it is not true as $$ 2 \times 3 \times 2^2 + 1 = 25 = 5 \times 5. $$ If a prime power is written as $n = p^k$, where $p$ is prime and $k>1$, then it is not true as $$ 2^2 \times 2^3 + 1 = 33 = 3 \times 11. $$ If a prime power is ...


1

I'm not sure what a "prime power integer" is, as no prime can be written in the form $m^n$ with $m,n$ positive integers and $n>1$. Assuming you just mean to say that $p_1,p_2,\ldots,p_n$ are primes, this conjecture is false. What is true is that $p_1p_2\cdots p_n+1$ is relatively prime to $p_1,p_2,\ldots, p_n,$ which is what is needed in Euclid's proof ...


2

$1+2\times3\times5\times7\times11\times13=30031=59\times509$


2

The next-smallest counterexample, as indicated in the links from the comments, is given by $$ R_{19} = \sum_{i=0}^{18}10^i = \overbrace{1 \cdots 1}^{19} $$ it is conjectured (but has not been proven) that there are infinitely many such primes. It is notable that $R_n = \sum_{i=0}^{n-1}10^i$ can be written in the form $$ R_n = \frac{10^{n} - 1}{9} $$ From ...


3

However, for any $\epsilon > 0$, there are infinitely many pairs of primes $p, q$ such that $|\frac{p}{q}-2| < \epsilon $. This is a very special case of the result proved in Hobby, D., D. M. Silbeger, Quotients of primes, Amer. Math. Monthly, Vol. 100, 1993, No. 1, 50–52, that the ratio $\frac{p}{q}$ taken over all pairs of primes is dense in the ...


4

I would like to ammend my previous (edited) estimate to a more conservative one: betwen $1.97\times 10^{19}$ and $7.02\times 10^{22},$ with the most likely value being close to $1.18\times 10^{21},$ based purely on data from @dREaM's link (or equivalently this one), but this is highly speculative. Speculation based on following observations: ...


2

It doesn't go all the way to 2000 but it addresses your problem. Apparently it is hard to do it exhaustively. It has only been done for primes under $10^{18}$ and the gap they found is $1476$ http://primerecords.dk/primegaps/maximal.htm


3

I begin by trying also to answer your question: Why would we exclude $a$ such that $\gcd(a, n) = 1$ when the test works well without such condition? If we know that $\gcd(a, n) \not= 1$, we already that $n$ is not prime, thus the test is pointless. The answer is that we are not excluding those $a$, but the chances of randomly getting a Fermat witness ...


0

I believe you got confused. Also in Fermat's little theorem you must put the condition $\gcd(a,p)=1$, otherwise if $p\mid a$ then $$ a^{p-1}\equiv 0 \mod{p}\;. $$ Of course also in it's generalization, Euler's theorem, only if $\gcd(a,n)=1$ the you can say $$ a^{\varphi(n)}\equiv 1 \mod n\;. $$ I suggest you to look also at this link, ...


3

This occurs because for Carmichael numbers like $N$ we have that, by the Chinese remainder theorem, $\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/p_1\mathbb{Z} \times \mathbb{Z}/p_2\mathbb{Z} \times \dots \times \mathbb{Z}/p_n\mathbb{Z}$ where the $p_i$ are its prime factors, and because for all these primes we have that $p-1|N-1$ we know that any element of this ...


1

Calculating the primes up to $n$ in $O(n)$ time isn't particularly fast, and nor is it particularly slow. A naive Sieve of Eratosthenes works in time $O(n \log n \log \log n)$ and is very easy to implement. It can be sped up to run faster than $O(n)$ using some wheel techniques. I believe one can reduce the time to $O(n/\log n)$. See Paul Pritchard, A ...


3

Suppose that we do not know that all irreducibles are prime. Is there any direct proof that there are infinitely many prime elements in $\mathbb{Z}$? Good question. Euclid's proof that there are infinitely many primes is in fact a proof that there are infinitely many irreducibles, and then elsewhere he uses the Euclidean algorithm to prove that if $p$ ...


0

Since $p$ and $q$ are prime, a number $n$ is coprime to $N$ if and only if $n\ne 0\ (\ mod\ p)$ and $n\ne 0\ (\ mod\ q)$. It is easy to see that $x+kp\ne 0\ (\ mod \ p\ )$ is equivalent to $x\ne 0\ (\ mod\ p\ )$. If this does not hold, $x+pq$ cannot be coprime to $N$. The other condition is simply $x+kp\ne 0\ (\ mod\ q\ )$, giving $k\ne -xp^{-1}\ (\ mod\ q\ ...


3

Certainly not every odd integer $n>1$ is the sum of two primes. Already $27$ is a counterexample. However, every odd $n>1$ is indeed the sum of at most five primes. This is a very nice result, see here. If we consider the other condition whether $n=1+p$ is possible, the situation is not better. In general, $n-1$ need not be prime. Even if we combine ...


5

By Prime Number Theorem and this we get $$ \lim_n \,\frac{np_n}{p_1+\ldots+p_n}=\lim_n\, \frac{n\,(n \ln n)}{\frac{1}{2}n^2\ln n}=2. $$ UPDATE: With regard to the convergence from above, the following would be correct if the upper bound on the sum were exact, but it isn't. Probably a different approach is needed. From quantitative estimate of sum of k ...


1

This is not an answer but it is too long for a comment. I suppose that you could be interested by this paper where the author proposes $$\frac 1{P(n)}=2^n-\big(\frac 43\big)^n+\big(\frac 89\big)^n-\big(\frac 45\big)^n-\big(\frac {16}{27}\big)^n-\big(\frac 47\big)^n+2\big(\frac {8}{15}\big)^n+\big(\frac {32}{81}\big)^n+\cdots$$ For $P(10)$, the expansion ...


3

That equation cannot be solved in terms of the most elementary functions. The Lambert W function can be used for that (though probably your calculator does not include it). Another way is iteratively (assuming $c>3$) : $x_{n+1} = c \ln(x_{n})$, starting with $x_0=c$. Or, much more quickly (Newton–Raphson ) $$x_{n+1} = \frac{\ln (x_{n})-1}{1/c-1/x_n}$$ ...


1

Yes, although it is a capital letter $C.$ Back on page 65, formula (2.9) is followed by where $C$ is Euler's constant. The same is used in the integral table book of Gradshteyn and Ryzhik, especially in section 8.36, pages 952-956 in the fifth edition


3

No. For example, the denominator of $B_{560}$ is $15037922004270$, which is divisible by $561 = 3 \times 11 \times 17$. Hmm: is there a relation to Carmichael numbers? EDIT: By Korselt's criterion, composite positive integer $x$ is a Carmichael number iff $x$ is square-free and $p-1 \mid x-1$ for all primes $p$ dividing $x$. Moreover every Carmichael ...


0

Because $$\zeta\left(\sigma\right)=O\left(\left(\sigma-1\right)^{-1}\right) $$ at $\sigma\longrightarrow1 $, hence $$\zeta^{3}\left(\sigma\right)=O\left(\left(\sigma-1\right)^{-3}\right). $$


4

They are found by reversing the process that was used to come up with the number in the first place: you divide to reverse the multiplications. Presumably you chose these primes and powers of primes and multiplied them together to get this number. So you just divide out the primes or powers of primes. Of course in some cases this is easier said than done. ...


0

First, we note that $p|q_1$ implies $p=q$ (we don't even need Euclid's lemma to see this). Now assume that $p|q_1q_2\ldots q_k\implies p|q_1$ or $p|q_2$ or $\cdots$ or $p|q_k$. Now consider the statement $p|q_1q_2\ldots q_kq_{k+1}$. Using Euclid's lemma, $p$ must divide one of $q_1q_2\ldots q_k$ or $q_{k+1}$. By our inductive hypothesis, we conclude that ...


2

Apart from the obvious criteria (divisibility by a power of $10$, divisibility by $5$), here are a few elementary facts one can use to speed up the trial division approach for relatively small $n$: The smallest prime factor of an integer $n$ is no greater than $\sqrt{n}$.(proof ) If the (base ten) digit sum of $n$ is divisible by $3$ (resp. $9$) then $n$ ...


3

I this case, try dividing $711,000,000$ by $1,000,000$. You get $711$ and $1,000,000$. Let's address $711$ first. $711 = 79 * 9$ Here we see that $79$ is prime, so keep it as a factor. $9$ is not, so let's split it into two primes. $9 = 3 * 3$. Now you have $79*3^2*1,000,000$. All that we have to do now is factor $1,000,000$. $1,000,000 = 2 * 500,000$. ...


3

There are a few different ways to factorize integers, but the simplest to understand (though not always the most efficient) is trial division. If the number is even, you divide it by $2$, giving you $355500000$. You keep dividing by $2$ until you get an odd number, in this case $11109375$. Then you go on to do the same thing with the next prime $3$, and so ...


1

There do exist algorithms to do this, but they run in non-polynomial time (though with a quantum computer you would be able to do it in polynomial time). There do exist some shortcuts for testing if a number $n$ is divisible by a prime $p$ for a few primes. For example: If the last digit of a number is even, then the number is divisible by $2$. If the sum ...



Top 50 recent answers are included