Tag Info

New answers tagged

0

Maybe it's more useful to use $$\sum_{k\leq n}\omega\left(k\right)=\sum_{p\leq n}\left\lfloor \frac{n}{p}\right\rfloor $$ to get $$\frac{1}{n}\sum_{k\leq n}\omega\left(k\right)-\sum_{p\leq n}\frac{1}{p}=\frac{1}{n}\sum_{p\leq n}\left\lfloor \frac{n}{p}\right\rfloor -\sum_{p\leq n}\frac{1}{p} $$ $$=\frac{1}{n}\sum_{p\leq n}\frac{n}{p}-\sum_{p\leq ...


1

I'd say no. Many authors state that RH would tell us nothing more (about prime gaps) than $p_{n+1}-p_n \in \text{O}(\sqrt{p_n}\log p_n)$, which obviously doesn't imply TPC, and so it should not be unsafe to say RH doesn't imply TPC.


1

I think that RH does not imply the twin prime conjecture. A couple of quotations from Dan Goldston in his paper here are in favour of this opinion: "While the Riemann Hypothesis is decisive in determining the distribution of primes, it seems to be of little help with regard to twin primes." "The conjecture that the distribution of twin primes satisfies a ...


3

$1024$. P.S.:You will get this sort of answer if you write this sort of question


1

On average, you would expect around $2e/(\log e)^2$ primes. But the $e/\log e$ numbers are a small proportion of the numbers below $e$, and it might happen, for one particular $e$, that none of them are prime.


1

Notation $a \mod k = r$. Then $a = ka_1 + r$ and: $$ ((a \mod k) \cdot k + b) \mod k = ((a-k \cdot a_1) \cdot k + b) \mod k \\= (a\cdot k + b -k \cdot a1 \cdot k) \mod k = (a \cdot k + b) \mod k $$ The last equality is from the fact that $a \mod k = (a + nk) \mod k, \forall n$


1

OP seems to be looking for a simple method that would ensure an easy discovery of all solutions listed. One such simple method is to let $y$ run through $\pm 1, \pm 2, \pm 3, ...$ and calculate $(y−1)(y+1)(y^2+1) = y^4-1$. From the left hand side, we can see that $x$ must be a divisor of $y^4-1$ and we simply check all divisors of $y^4-1$. For $ y = \pm 17$ ...


0

No. For example $x=0, n=2, a_1=1, a_2=-2$: $|x-a_1| + |x-a_2| = |0-1| + |0+2| = 1+2=3$ $|nx - \sum_{i=1}^{n}a_i| = |0 -(1-2)| = |0+1| =1$


0

By assumption $$\mathrm{gcd}(ab)=\frac{|ab|}{\mathrm{lcm}(a,b)}=\mathrm{lcm}(a,b).$$ It implies that $p^A$ divides exactly $a$ and $p^B$ divides exactly $B$, then $\min\{A,B\}=\max\{A,B\}$, i.e. $|a|=|b|$. Similarly, $\min\{kA,kB\}=k \min\{A,B\}$. Let $p^M$ divides exactly $m$. Then $M \ge A$ and $M\ge B$ implies $M\ge \max\{A,B\}$.


5

No, in general you have only have by the triangular inequality $|nx - \sum_{i=1}^{n}a_i| \leq |x-a_1| + |x-a_2| + |x-a_3| + ... + |x-a_n| $ Sometimes you can have equality but to see that this isn't always true, just take, $n=2$, $x=0$, $a_1=1$, $a_2=-1$. On one side you'll get $0$ and on the other you'll get $2$.


2

I'm not really sure what the problem you're having is. What you explain as your objection is in fact just the correct way of interpreting the hint. Maybe it will help if we go through it really carefully: You want to prove that $\operatorname{gcd}(a,b)=1$ and $c\vert a+b$ together imply that $\operatorname{gcd}(c,a)=\operatorname{gcd}(c,b)=1.$ The hint ...


1

The way I see it, you have $3$ conceivable ways for interpreting this question: Count the number of zeros in $((4404_{17})^2)_{17}$ Count the number of zeros in $((4404_{17})^2)_{10}$ Count the number of zeros in $((4404_{10})^2)_{17}$


1

Your partial sum is $H_n-H_{\left\lceil\frac{n}{2}\right\rceil}$, where $H_n$ is the $n^{\rm{th}}$ harmonic number Since $H_n \approx \log n + \gamma,$ this will approach $\log n - \log {\left\lceil\frac{n}{2}\right\rceil}=\log 2$


1

It should be familiar to you that $f_{\omega}(3)\approx\{3,3,3\}=h(3)$. Similiarly, $f_{\omega^2}(4)\approx\{4,4,4,4\}=h(4)$, and in general $$h(n+1) << f_{\omega^\omega}(n) < h(n+2)$$ for $n \geq 3$. See also this answer.


0

Let $n$ be a square-free integer with a minimal number of prime divisors such that $\gcd(n,s)>1$ for all $s\in S$. By the hypothesis, there exists a divisor $d$ of $n$ in $S$. Suppose $d=p_1\cdots p_k$ ($p_1,\ldots,p_k$ are distinct primes). Consider the multiples of $p_1$ that are contained in $S$; call this set $T$. If $\gcd(d,t)>p_1$ for all $t\in ...


1

These notes derive (equation ($4$) on p. $4$) $$ \sum_{k\le n}\frac{\sigma(k)}k=\frac{\pi^2}6n+O(\log n)\;. $$ Thus for your ratio $D(n)$ we have $$ \sum_{k\le n}\frac{\sigma(k)-k-1}k=\left(\frac{\pi^2}6-1\right)n+O(\log n)\;, $$ and dividing by $n$ shows that the average converges to $$ \frac{\pi^2}6-1\approx0.645\;. $$


0

HINT: As $(6a+1,3)=1$ $(6a+1)|(192-2a^2-a)\iff(6a+1)|3(192-2a^2-a)$ Now $\dfrac{3(192-2a^2-a)}{6a+1}=\dfrac{576-2a}{6a+1}-a$ Similarly, $(6a+1)|(576-2a)\iff(6a+1)|3(576-2a)$ $\implies$ we need $3\cdot576+1$ must be divisible by $6a+1$


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$).


4

Elements of $\widehat{\mathbb{Z}}$ are called profinite integers. The profinite integers have a universal property in the category of profinite groups in exactly the same way that the integers have a universal property in the category of groups: namely, $\widehat{\mathbb{Z}}$ is the free profinite group on one generator. This means precisely that elements $g ...


-5

I was trying to get a simple proof and I came up with this one. Let us consider the function f:R->R, f(x)=(x^2) (^ means square; x^2=x*x). Now consider the convex region f(x)>(x^2) and lets call it something say, H. For n>=4, by using induction we can show that n!>(n^2). Therefore for all n belonging to N (N is the set of all natural numbers including 0), ...


2

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 rational root theorem] Given a polynomial $$a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_2 x^2 + a_1 x + a_0$$ with integer coefficients and $a_n \ne 0$, then each rational solution written as $x = \frac pq$, where $\gcd(p,q) = 1$, satisfies $\circ \quad p$ divides $a_0$. $\circ \quad q$ divides $a_n$. $x = \sqrt a$ if and only if $x$ is ...


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

For the first part if you start with $x=c+id$ with integers $c,d$ then of course $2d$ is an integer but I don't see where it comes in. We have simply $ 0=(x-c)^2+d^2=x^2 +x(-2c)+(c^2+d^2)$. And as for the book's statement,"precisely those" means "all and only those" which as your example shows, is incorrect.


0

For 1. we have GCD(a,b) $\le$ min (|a|,|b|) $\le$ max(|a|,|b|) $\le$ LCM(a,b). ... BTW Did you know that LCM(a,b).GCD(a,b)= ab for positive a,b.


1

In particular, this means that $\alpha$ is an algebraic integer if and only if both $2r$ and $r^2 - s^2 m$ are integers. This requires more work than what you've done so far. You need to further know that $x^2 - 2rx + (r^2 - s^2 m)$ is the minimal polynomial of $\alpha$. Fortunately this is clear as long as $s \neq 0$, which is the interesting case ...


1

From Bertrand's postulate , there exist always a prime number between $n$ and $2n$ but for $n>1$, $n!>2n$


8

A (prime) divisor of $n!-1$ can't be a divisor of $n!$ (if it were, it would divide $1$). Furthermore $n!$ is divisible by all of $1, 2, \ldots n$.


2

Show that if $x\in\mathbb Q$ is a root of a monic polynomial with coefficients in $\mathbb Z$, then $x\in\mathbb Z$. $(c+id)^2+a(c+id)+b=0$ leads to $c^2-d^2+ac+b=0$ and $2cd+ad=0$. The last equation writes $(2c+a)d=0$, and then (i) $d=0$; apply 1. (ii) $2c+a=0$; now the first equation becomes $(2d)^2+a^2-4b=0$, so $2d\in\mathbb Z$. Set $e=2d$. Then ...


0

It is called an absolute value sign. Take the following example: $$f(x)=|3x-6|$$ If you plug in any value where $x>2$, then the portion inside the absolute value lines will be positive, and $f(x)$ will be positive. However, if you plug in any value where $x<2$, then the portion within the absolute value lines is negative. With absolute value, you ...


0

The conjecture appears true: For any $a_1,\ldots,a_n\in\mathbb Z$, the determinant of a matrix with them in its first row can be any multiple of their $\gcd$. It clearly suffices to handle the case in which their $\gcd$ is $1$. I found a recursive procedure that seems to work. For $n=2$ we take $$\begin{pmatrix}a_1&a_2\\-b_2&b_1\end{pmatrix}$$ ...


0

Let $d=gcd(a,b)$. $\therefore d|a $ and $d|b$ Again, $ gcd(a,b)=lcm(a,b)=d\space \therefore a|d$ and $b|d$ Now, $d|a\implies a=dk$, where $k \in \mathbb{Z}$ Again, $a|d \implies d=aq=dkq\implies kq=1\implies k=q=±1$, as $k,q\in \mathbb{Z}$. $\therefore d=±a$ $\therefore d=±a=±b$ Hence, $a=±b$ (Proved)


1

$$ I_{m,n}=\frac{1}{n}\int_{0}^{1}(1-x)^m x^{\frac{1}{n}-1}\,dx = \frac{\Gamma(m+1)\,\Gamma\left(\frac{1}{n}\right)}{n\,\Gamma\left(m+1+\frac{1}{n}\right)}=\frac{m!}{\prod_{k=1}^{m}\left(k+\frac{1}{n}\right)}\tag{1}$$ gives: $$ I_{m,n}=\frac{m! n^m}{\prod_{k=1}^{m}(nk+1)}=\prod_{k=1}^{m}\frac{nk}{nk+1} \tag{2}$$ and the problem boils down to proving that ...


2

Assuming the result for smaller $x+y+z$, it is inductively true in the case that any of $x,y,z$ is divisible by 3; this answer is a work in progress. Expand and simplify to obtain: $$\frac{xy+yz+xz}{x^2+y^2+z^2} = \frac{1}{3n}$$ or equivalently $$3n(xy+yz+zx) = x^2+y^2+z^2$$ But the only way a sum of three squares can be a multiple of 3 is if all of ...


1

You might consider the Borodin-Moenck-scheme for computing such a product (see page 372 in "Fast Modular Transforms"). The key idea is to replace $n-1$ successive polynomial multiplications of a degree-1 and a degree-$i$-polynomial by $n-1$ "balanced" multiplications of polynomials of equal degree (or almost equal, if $n$ is not a power of two). That is, in ...


2

If $x^{100}$ is a $31$ digit number, we have $10^{30}\le x^{100}\lt 10^{31}$ Taking logarithms we then have $30\le 100 \log x \lt 31$ so that $0.3\lt \log x \lt 0.31$ If $x$ is an integer, then $x=2$. You should be able to complete the question from there. Logarithms are taken to base ten.


5

$x^{100}$ is 31 digit => $$10^{30}\leq x^{100}< 10^{31} \Rightarrow 10^{300}\leq x^{1000}< 10^{310}.$$ This means that $x^{1000}$ has from 301 t0 310 digits.


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.


4

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 ...


2

Your answer is right. Here is how I do it: As $189=3^3\cdot 7$, $\;185!$ is divisible by $189^n=3^{3n}\cdot7^n$ if and only if $$v_3(185!)\ge 3n\enspace\text{and}\enspace v_7(185!)\ge n$$ (for a prime number $p$, $v_p(n)$ denotes the $p$-adic valuation of $p$ in $n$, i.e. the exponent of $p$ in the decomposition of $n$ into its prime factors) We can use ...


-1

The problem can be analize of a different approach. If we analize $185!$ taking advantage that $7$ is prime, we see that $$ 185!=n(7*14*21*28*35*42*49*56*63*70*77*84*\ldots*175*182). $$ The number of factors that contains $7$ are $[185/7]=26$. But, there others factors that altes our result such that $$ 49,98,147. $$ In summary, there existe ...


3

Well, Prelude> let m = product [1 .. 185] :: Integer Prelude> m `mod` (189^29) 0 Prelude> m `mod` (189^30) 37470960172551150153411831285317353601062526805310229978097429296724 it's not you who is wrong. Your result is correct, the required answer is incorrect. Is there any better approach I can solve this problem? Not really, counting the ...


0

I think a good idea for the problem is using modulos. So, the problem can be written like this $$ z=4-x^2 \text{ }mod(6), $$ We know that $100=96+4=4\quad mod(6)$. So $100^2=(100)*(100)=4*4=16=12+4=4\quad mod(6)$. If $z$ is divisible for $6$, then $z=0\quad mod(6)$. For all of this we have to find $x$ such that $$ x^2=4\quad mod(6). $$ We have to make a ...


3

HINT: $$z=100^2-x^2=(100-x)(100+x)$$ As $(100-x)+(100+x)=200,100\pm x$ have same parity and if one is divisible by $3,$the other is not So if $2|z,100\pm x$ must be even If $3|z,3|(100-x)(100+x)\implies$ either $3|(100-x)\iff x\equiv1\pmod3$ or $3|(100+x)\iff x\equiv-1\pmod3$


0

The constant term is easy to compute, it's just the product of the $a_i$. The coefficient of $x^{n-1}$ is $\sum_i a_i$, so that is also easy. Assume for a moment that $n = 2k$ is even, then the coefficient of $x^k$ is the sum of all possible products consisting of $k$ different $a_i$. There are $\binom{n}{k} \approx 2^n/\sqrt{n} $ such products and there ...


1

The most concise way to expand this is with the use of elementary symmetric polynomials. For each integer $k\in\{0,\ldots,n\}$ the $k$-th elementary symmetric polynomial in $a_1,\ldots,a_n$ is defined as $$e_{n,k}:=\sum_{1\leq j_1<\ldots<j_k\leq n}a_{j_1}\ldots a_{j_k}.$$ In words $e_k$ is the sum of all products of $k$-tuples from $a_1,\ldots,a_n$. ...


2

I find this question somewhat frustrating, ’cause I haven’t been able to answer it to a degree of completeness that satisfies me, but at least I can help. I don’t see any way of doing this in a few lines. First, since you’re interested only in the ramification and splitting of the prime $\mathfrak m=(1+i)$ in your extension $K=k(\pi^{1/4})$, where $k=\Bbb ...


1

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 & ...



Top 50 recent answers are included