Tag Info

Hot answers tagged

22

Without going into detail what a "random natural number" might be, we could consider the density of such numbers. The possibility to express $n$ depends on the prime factorization of $n$: It may be divisible by $2$ and by primes $\equiv 1\pmod 4$ as much as it likes, but each prime $\equiv 3\pmod 4$ must occur in an even power. The prime $3$ "spoils" all ...


14

You can see : André Weil, Number Theory : An approach through history (1984), Preface, page ix : Fermat, Euler, Lagrange, Legendre. These are the founders of modern number theory. The greatness of Gauss lies in his having brought to completion what his predecessors had initiated, no less than in his inaugurating a new era in the history of the ...


13

Claim. $a+b+c\mid a^{2^n}+b^{2^n}+c^{2^n}$ for all $n\geq0$. Proof. By induction: True for $n=0,1$ $\checkmark$. Suppose it's true for $0,\ldots,n$. Note that ...


10

Yuan-You Fu-Rui Cheng, Explicit estimate on primes between consecutive cubes, showed that for $x\ge\exp(\exp(15))$ there is at least one prime between $x^3$ and $(x+1)^3$. Thus, for sufficiently large $n$ we must have $$\frac{p_{n+1}}{p_n}<\frac{\left(p_n^{1/3}+1\right)^3}{p_n}<1+\frac7{p_n^{2/3}}\;,$$ and $S=1$.


9

Simply divvy up the product nicely. I'll demonstrate how it can be done for the lower bound. $$\begin{align}20!&=(20\cdot15)\cdot(19\cdot 16)\cdot(18\cdot17)\cdot(14\cdot 13\cdot11)\cdot(12\cdot9)\cdot10\cdot 8! \\&=300\cdot304\cdot306\cdot2002\cdot108\cdot10\cdot40320 \\&>3\cdot3\cdot3\cdot2\cdot1\cdot1\cdot4\cdot 10^{2+2+2+3+2+1+4} ...


9

Fermat contributed a lot of results (not so many proofs, unfortunately) to the community, and did lots of work in number theory. For example, both Fermat's Little Theorem and Fermat's Last Theorem are named after him, and they are clearly number theoretic. Fermat is particularly notable in that he worked mostly in isolation (if I remember correctly; if ...


7

There's no need to quote papers on prime gaps - this follows directly from the prime number theorem which states that $$\pi(x)=\sum_{p\leq x} 1=\frac{x}{\log x}+O\left(\frac{x}{\log ^2 x}\right).$$ Indeed, if there existed a $c>1$ such that $p_{n+1}>cp_n$ infinitely often, then we would have $\pi(cx)=\pi(x)$ for infinitely many values of $x$, however ...


7

Though this is not an answer to the original question, I'll write it in answer to VividD's question under Hagen von Eitzen post (and I believe it is not totally unrelated to the question). Let $A_n$ be the number of different pairs $(x,y)$ of non-negative integers solving the equation $x^2 + y^2 = n$. Then it is natural to define the expected number of ...


6

Consider the function $r: \mathbb{N} \to \mathbb{C}$: $$ r(n) = \begin{cases} 1 &n \text{ is the sum of two squares} \\ 0 &n \text{ otherwise}. \end{cases} $$ One way to define the "probability that a random integer is the sum of two squares" would be to consider the distribution on the integers where $n$ selected with probability proportional to ...


6

It follows from the Prime Number Theorem that $$ \lim_n \frac{p_{n+1}}{p_n}=\lim_n\left( \frac{p_{n+1}}{(n+1)\ln(n+1)}\cdot \frac{n\ln(n)}{p_n}\cdot \frac{(n+1)\ln(n+1)}{n\ln(n)}\right)=1 \cdot 1 \cdot 1 $$ Now, since $ \lim_n \frac{p_{n+1}}{p_n}=1$ then the limsup exists and is the same.


6

the limsup is one, see the corollary to Theorem 3 in Rosser and Schoenfeld (1962). The information also allows you to find the maximum of the ratio, which is likely 3/2, but you can find out for sure. In any case, for $n \geq 6,$ $$ \frac{p_{n+1}}{p_n} < 1 + \frac{\log \log n}{\log n}, $$ so the limit is $1.$


6

Here's a counterpart to Peter Woolfitt's answer. $$\begin{align} 20!&=(20\cdot15\cdot10\cdot5\cdot2)(19\cdot7\cdot3)(11\cdot9)(8\cdot6\cdot4)(16\cdot14)(17\cdot13)(18\cdot12)\\ &=(3\cdot10^4)((20-1)(20+1))(99)(192)((15+1)(15-1))((15+2)(15-2))(15+3)(15-3))\\ &\lt(3\cdot10^4)(400)(100)(200)(15^2)(15^2)(15^2)\\ ...


5

$\binom{k}{2}\leq n$ is equivalent to $(2k-1)^2 \leq 8n+1$, hence the largest triangular number $\leq n$ is given by $\binom{k}{2}$ with: $$ k = \left\lfloor \frac{1+\sqrt{8n+1}}{2}\right\rfloor.$$


5

The value is $1$. If $c>1$ is any constant, then $$\pi(nc) - \pi(n) \approx \frac{nc}{\log(nc)} - \frac{n}{\log(n)}$$ converges to $\infty$ when $n\to \infty$ (one can make the "$\approx$" precise). Thus for large enough $n$, there is always a prime between $n$ and $nc$, and so for all sufficiently large $n$, $p_{n+1} < cp_n$. This is enough to show ...


5

Use the fact that: $$ \sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor=\sum_{i=1}^n d(i) $$ where $d(\ )$ is the divisor function (RHS: there are $d(i)$ numbers dividing $i$, LHS: there are $\left\lfloor\frac{n}{i}\right\rfloor$ numbers at most $n$ divisible by $i$). All numbers have even number of divisors, except for the squares, and there are ...


5

the density is zero, and one may be quite precise about it: the count of numbers up to some large real $x$ that are the sum of two squares is asymptotic to $$ \frac{0.7642... \, x}{\sqrt{\log x}} $$ where the logarithm is base $e,$ and the $0.7642...$ is defined by an infinite product. See the last few pages in LeVeque. This is combined volumes 1 and 2, ...


5

What is the units digit of $340274513\times 384759374\,{}$? $$ \begin{array}{ccccccccccccc} & & & & 3 & 4 & 0 & 2 & 7 & 4 & 5 & 1 & 3 \\ & & & \times & 3 & 8 & 4 & 7 & 5 & 9 & 3 & 7 & 4 \\ \hline & & & \cdot & \cdot & \cdot & \cdot & ...


5

The equidistant runner conjecture is false for $3$ runners. For an explicit counterexample, look at a unit circle (radius $1$) with three runner speeds $1,2$, and $4$. This has the advantage of completely resetting at time $2\pi$, since then all runners are at the starting line again. It's not too hard to explicitly check this with a computer. As is pointed ...


5

I think it can be proven using Vieta jumping method that in order for $k=\dfrac{(x+y)(x+y+1)}{xy}$ to be an integer for positive integers $x$ and $y$ the only values $k$ can take are $5, 6$. Ok, we have $x^2+y^2+x+y=(k-2)xy$ Vieta jumping is the key of the solving this problem. The idea of this method is that if $(x_0, y_0)$ is a solution to the ...


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


4

By a domain I will mean a commutative ring without zero divisors. A Furstenberg domain is a domain in which every nonzero nonunit element is divisible by an irreducible element. This is a very weak factorization condition: one has Noetherian $\implies$ ascending chain condition on principal ideals $\implies$ all nonzero nonunits factor into products of ...


4

Since the coefficient of $x$ in $p(x)$ has to be $0$, one has $$3a_1b_1^2+3a_2b_2^2+3a_3b_3^2+3a_4b_4^2=1.$$ Now the LHS is a multiple of $3$ while the RHS is not.


4

Suppose that $a,b\in\mathbb{Z}$. By the binomial theorem $$(10a+b)^k=10^ka^k+\binom{k}{1}10^{k-1}a^{k-1}b+\cdots+\binom{k}{1}10ab^{k-1}+b^k$$ $$=10c+b^k$$ for some $c\in \mathbb{Z}$, so the units digit of $(10a+b)^k$ and $b^k$ are the same. More generally, this follows since multiplication modulo $10$ (or any modulus) is well defined.


4

In the following $p$ will always denote a prime numer. $p_k$ will be the $k$-th prime. Clearly it suffices to show that, given $0\le x_i<y_i\le\alpha$ ($i=0,\dots,n$), we can always find $x$ s.t. $\phi(x+i)\in(x_i,y_i)$ for any $i$. Here $\alpha:=\prod_{p\le n+1}\frac{p-1}{p}$. We first prove this crucial lemma, which in particular gives the thesis for ...


4

We have these estimates for the central binomial coefficient for $n\ge1$: $$ \frac{4^n}{\sqrt{4n}} \leq {2n \choose n} \leq \frac{4^n}{\sqrt{3n+1}} $$ and so $$ (n!)^2\frac{4^n}{\sqrt{4n}} \leq(2n)! \le (n!)^2 \frac{4^n}{\sqrt{3n+1}} $$ Apply this to $n=10$, using that $10!=3628800$, and get $$ 2.19 \times 10^{18} \le 20! \le 2.48 \times 10^{18} $$ I did ...


3

Partial answer: The probability for two points to be visible from each other in $n$ dimensions is $\frac1{\zeta(n)}$. I'll interpret "picking two points at random" as follows. Since we're only interested in the relative position of the two points, I'll take the first one to be the origin. Then for any $R\in\Bbb N$ we count how many points in $[-R,R]^n$ are ...


3

Here's a broad solution in integers. Given, $$\frac{x(x-1)}{y(y-1)}=\frac{p}{q}\tag1$$ All you do is directly solve $(1)$ as a quadratic in $x$ and make its discriminant a square. After some manipulation, I find, $$x = pv(u+qv)$$ $$y = qv(u+pv)$$ and $u,v$ solve, $$u^2-pqv^2 = \color{red}-1\tag2$$ Or, $$x = pv(u+qv)+1$$ $$y = qv(u+pv)+1$$ and ...


3

As taken from my upcoming textbook: There is yet another solution to the Basel problem as proposed by Ritelli (2013). His approach is similar to the one by Apostol (1983), where he arrives at $$\sum_{n\geq1}\frac{1}{n^2}=\frac{\pi^2}{6}\tag1$$ by evaluating the double integral $$\int_0^1\int_0^1\dfrac{\mathrm{d}x\,\mathrm{d}y}{1-xy}.\tag2$$ Ritelli ...


3

First of all, notation: $f(x)\sim g(x)$ means that $$ \lim_{x\to\infty}\frac{f(x)}{g(x)}=1, $$ and $f(x)\approx g(x)$ means that the two functions are 'approximately' equal (which doesn't have a hard and fast definition). Lower-order terms disappear under $\sim,$ so asking if $p_n\sim \frac54 n\log n+\frac12n+\frac{p_1+\cdots+p_{n-1}}{n-1}$ is the same as ...


3

\begin{align} 1^2+2^2+...+&(n-1)^2 \quad\quad= \frac{n(n-1)(2n)}{6} = \frac{n^2(n-1)}{3} &< \frac{n^3}{3} \\ 1^2+2^2+...+&(n-1)^2+n^2 =\frac{n(n+1)(2n+1)}{6} =\frac{2n^3+3n^2+n}{6} =\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6} &>\frac{n^3}{3} \end{align} Cleary our inequality is proven.



Only top voted, non community-wiki answers of a minimum length are eligible