Back Matter

Last updated
Save as PDF

Page ID: 26364

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Classical Unsolved Problems

Is every even number > 2 the sum of two primes? (Goldbach)
Is every number of the form \(4n + 2\) (\(n > 1\)) the sum of two primes of the form \(4n + 1\)? (Euler)
Obtain an asymptotic formula for the number of representations of \(2n\) as the sum of two primes.
Can every even number be expressed as the difference of two primes?
Can every even number be expressed as the difference of two primes in infinitely many ways?
In particular, are there infinitely many prime pairs?
Find an asymptotic formula for the number of prime pairs \(\le x\).
Do there exist infinitely many primes of the form \(x^2 + 1\)?
Does any polynomial of degree > 1 represent infinitely many primes?
Are there infinitely many Fermat primes?
Are there infinitely many Mersenne primes (primes of the form \(2^p − 1\))?
Are there infinitely many primes of the form \(2p + 1\), where \(p\) is a prime?
Is there at least one prime between every pair of consecutive squares?
Are there odd perfect numbers?
Are there infinitely many multiply perfect numbers?
Are there infinitely many pairs of amicable numbers?
Let \(f(n) = \sigma (n) - n\). Does the sequence \(f_0 (n) = n\), \(f_{k + 1} (n) = f(f_k(n))\), \(k = 1, 2, 3, ...\) remain bounded for every \(n\)? (Poulet)
Are there infinitely many primes \(p\) for which \(2^{p−1} − 1\) is divisible by \(p^2\)?
Are there infinitely many primes \(p\) for which \((p − 1)! + 1\) is divisible by \(p^2\)?
Is \(x^n + y^n = z^n\) solvable for every \(n > 2\)? (Fermat)
Is \(x_1^n + x_2^n + \cdot\cdot\cdot + x_{n - 1}^n = x_n^n\) solvable for any \(n > 2\)? (Euler)
Is 2 a primitive root of infinitely many primes? (Artin conjectures that 2 is a primitive root of about one third of all primes.)
is Euler's constant \(\gamma\) irrational?
Is \(\pi^{e}\) irrational?
Are 8 and 9 the only powers (exceeding 1) of integers that differ by 1? (Catalan.)
For what values of \(k\) is \(x^2 + k = y^3\)?

Miscellaneous Problems

Show that \(\sum_{d = 1}^n (2d - 1) \lfloor \dfrac{n}{d} \rfloor = \sum_{d = 1}^{n} \lfloor \dfrac{n}{d} \rfloor^2\).
Show that \(\sum_{d\ |\ n} \tau(d)^3 = (\sum_{d\ |\ n} \tau (d))^2\).
Show that \(\sum_{(a, b) = 1} \dfrac{1}{(ab)^2} = \dfrac{5}{2}\).
Show that \(\prod \dfrac{p^2 + 1}{p^2 - 1} = \dfrac{5}{2}\).(The product runs over all primes.)
Generalize the results of Problems 3 and 4 above.
Show that \(\text{lim}_{n \to \infty} \sum_{d\ |\ (n! + 1)} \dfrac{1}{d} = 1\).
Show that \(\text{lim}_{n \to \infty} \sum_{d\ |\ F_n} \dfrac{1}{d} = 1\), where \(F_n = 2^{2^n} + 1\).
Prove that \(\pi(x) = \sum_{n = 1}^x \sum_{j = 1}^n e^{2\pi i ((n - 1)! + 1)j / n}\).
Prove that \((a, b) = \sum_{m = 0}^{a - 1} \sum_{n = 1}^{a - 1} \dfrac{1}{a} e^{2\pi i bmn /a}\).
Show that the least absolute remainder of \(a\) (mod \(b\)) is \(a - b \lfloor \dfrac{2a}{b} \rfloor + b \lfloor \dfrac{a}{b} \rfloor.\)
Prove that \(\sum_{n = 1}^{\infty} \dfrac{\varphi (n)}{n!}\) is irrational.
Prove that \(\sum_{n = 1}^{\infty} \dfrac{\sigma (n)}{n!}\) is irrational.
Prove that \(\sum_{n = 1}^{\infty} \dfrac{\sigma_2 (n)}{n!}\) is irrational.
Show that \(\sum_{n = 1}^x \dfrac{n}{\sigma(n)} \ge x + 1\).
Show that \(\sum_{d^2\ |\ n} \mu (d) = |\mu(n)|\).
Show that for \(g \ne 3, 1 + g + g^2 + g^3 + g^4\) is not a square.
For \(n\) an integer and \(a \ge 0\) prove that \(\sum_{k = 1}^{n - 1} \lfloor a + \dfrac{k}{n} \rfloor = \lfloor na \rfloor\).
Show that \(\dfrac{1}{\phi (n)} = \dfrac{1}{n} \sum_{d\ |\ n} \dfrac{\mu^2 (d)}{\phi (d)}\).
Prove that \(\sum_{n = 1}^{\infty} \dfrac{\mu(n) x^n}{1 + x^n} = x - 2x^2\).
Prove that \(\dfrac{\lambda (n) x^n}{1 - x^n} = \sum_{n = 1}^{\infty} x^{n^2}.\)
Prove that \(F(n) = \prod_{d\ |\ n} f(d)\) if and only if \(f(n) = \prod_{d\ |\ n} F(\dfrac{n}{d})^{\mu(d)}\).
Show that the sum of the odd divisors of \(n\) is \(-\sum_{d\ |\ n} (-1)^{(\dfrac{n}{d})} d.\)
Prove that the product of the integers \(\ge n\) and relatively prime to \(n\) is \(n^{\varphi(n)} \prod_{d\ |\ n} (\dfrac{d!}{d^d})^{\mu(\dfrac{n}{d})}\).
Show that every integer has a multiple of the form 11 ... 1100 ... 00.
Prove that there are infinitely many square-free numbers of the form \(n^2 + 1\).
Prove that \({m \choose 0} + {m \choose 3} + {m \choose 6} + \cdot\cdot\cdot \not\equiv 0) (mod 3).
Show that the number of representations of \(n\) as the sum of one or more consecutive positive integers is \(\tau(n_1)\) where n1 is the largest odd divisor of \(n\).
Prove that \(\varphi (x) = n!\) is solvable for every \(n\).
Prove that \(\varphi(x) = 2 \cdot 7^n\) is not solvable for any positive \(n\).
Prove that 30 is the largest integer such that every integer less than it and relatively prime to it is 1 or a prime.
Let \(a, b, x\) be integers and let \(x_0 = x\), \(x_{n + 1} = ax_n + b\) \(n > 0\). Prove that not all the \(x\)’s are primes.
Show that the only solutions of \(\varphi(n) = \tau(n)\) are \(n = 2, 3, 4, 8, 14, 20, 90\).
Show that \(\varphi (n + 1) = p_{n + 1} - p_n\) is valid only for \(1 \le n \le 5\).
Show that \(\dfrac{(2a)! (2b)!}{a! b!(a+ b)!}\) is an integer.
show that if \((a, b) = 1\) then \(\dfrac{(a + b - 1)!}{a! b!}\) is an integer.
Show that an integral polynomial of at least the first degree cannot represent only primes.
Show that if \(f(x)\) is an integral polynomial of degree > 0, then \(f(x)\) for \(x = 1, 2, ...\) has an infinite number of distinct prime divisors.
Find the number of integers prime to \(m\) in the set \({1 \cdot 2, 2 \cdot 3, ..., m \cdot (m + 1)}\).
Prove that the Fermat numbers are relatively prime in pairs.
Let \(T_1 = 2\), \(T_{n + 1} = T_n^2 - T_{n - 1}\). Prove that \(T_i, T_j) = 1, i \ne j\).
Prove that \(2 \zeta (3) = \sum_{n = 1}^{\infty} \dfrac{1}{n^2} (1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}).\)
Prove that the density of numbers for which \((n, \varphi(n)) = 1\) is zero.
Show that for some \(n\), \(2^n\) has 1000 consecutive 7’s in its digital representation.
Prove that infinitely many squares do not contain the digit 0.
Show that for some \(n\), \(p_n\) contains 1000 consecutive 7’s in its digital representation.
Show that the density of the numbers \(n\) for which \(\varphi(x) = n\) is solvable is zero.
Show that if \(\varphi(x) = n\) has exactly one solution then \(n > 10^{100}\).
Prove that \(e_p(n) = \dfrac{n - s_p(n)}{p - 1}\).
Let \(a_1\), \(a_2\), ..., \(a_{p - 1}\) be ordered by not necessarily distinct nonzero residue classes (mod \(p\)). Prove that there exist \(1 \le i \le j \le p- 1\) such that \(a_i \cdot a_{i + 1} \cdot\cdot\cdot\cdot\cdot a_j \equiv 1\) (mod \(p\)).
Show that the \(n^{\text{th}}\) prime is the limit of the sequence.
\(n_0 = n, n_{k + 1} = n_0 + \pi(n_0 + n_1 + \cdot\cdot \cdot + n_k).\)
Show that the \(n^{\text{th}}\) nonprime is the limit of the sequence
\(n, n + \pi(n), n + \pi(n + \pi (n)), ... .\)
Prove that every positive integer is either of the form \(n + \pi(n − 1)\) or of the form \(n + p_n\), but not both.
Show that \((3 + 2 \sqrt{2})^{2n - 1} + (3 - 2\sqrt{2})^{2n - 1} - 2\) is square for every \(n \ge 1\).
Prove that for every real \(\epsilon > 0\) there exists a real \(\alpha\) such that the fractional part of \(\alpha^n\) is greater than \(1 − \epsilon\) for every integer \(n > 0\).
Show that if \(p\) and \(q\) are integers \(\le n\), then it is possible to arrange \(n\) or fewer unit resistances to give a combined resistance of \(\dfrac{p}{q}\).
Show that \((a, n) = 1\) and \(x = a - 12 \sum_{k \ge 1} k [\dfrac{ka}{n}]\) imply \(ax \equiv 1\) (mod \(n\)).
If \((a, b) = d\) prove that \(\sum_{x = 1}^{a - 1} [\dfrac{bx}{a}] = \dfrac{(a - 1)(b - 1)}{2} + \dfrac{d - 1}{2}\).
Show that the sum of reciprocals of integers representable as sums of two squares is divergent.
Show that the sum of reciprocals of integers whose digital representation does not include 1000 consecutive 7’s is convergent.
Prove that every \(n > 1\) can be expressed as the sum of two deficient numbers.
Prove that every \(n > 10^5\) can be expressed as the sum of two abundant numbers.
Prove that every sufficiently large \(n\) can be expressed as the sum of two \(k\)-abundant numbers.
Prove that the \(n^{\text{th}}\) nonsquare is \(n + {\sqrt{n}}\). {\(x\)} denotes the integer closest to \(x\).)
Prove that the \(n^{\text{th}}\) nontriangular number is \(n + {\sqrt{2n}}\).
Prove that the \(n^{\text{th}}\) non-\(k^{\text{th}}\) power is
\(n + \lfloor \sqrt[k]{n + \lfloor \sqrt[k]{n} \rfloor} \rfloor.\)
Show that the binary operation \(\circ\) defined on nonnegative integers by
\(m \circ n = m + n + 2 \lfloor \sqrt{m} \rfloor \lfloor \sqrt{n} \rfloor\)
is associative.
Prove the same for the operation \(m \times n = m + n + 2 {\sqrt{m} } {\sqrt{n} }.\)
Prove that for \(p > 5\), \((p - 1)! + 1\) contains a prime factor \(\ne p\).
Show that the only solutions of \((n - 1)! = n^k - 1\) are \((n, k) = (2, 1), (3, 1)\) and (5, 2).
Show that \(x^{2^{\alpha}} \equiv 2^{2^{\alpha - 1}}\) (mod \(p\)) has a solution for every prime \(p\) if \(\alpha \ge 3\).
Show that if \(f(x)\) is a polynomial with integer coefficients and \(f(a)\) is a square for each \(a\), then \(f(x) = (g(x))^2\), where \(g(x)\) is a polynomial with integer coefficients.
Given integers \(a_1 < a_2 \cdot\cdot\cdot < a_k \le n\) with \(k \ge \lfloor \dfrac{n}{2} \rfloor\), prove that for some \(i \le j \le k\), \(a_i \ |\ a_j\).
Show that two of the \(a_i\)’s of Problem 72 are relatively prime.
With the \(a\)’s of Problem 72, show that \(a_i + a_j = a_k\) is solvable.
Show that the number of solutions of \(x + 2y + 3z = n\) in non negative integers is
\({\dfrac{(n + 3)^2}{12}}.\)
Show that the number of solutions of \(x + 2y + 4z = n\) in non negative integers is \({\dfrac{(n + 2)(n + 5)}{16} + (-1)^n \dfrac{n}{16}}\).
Show that n and n + 2 are simultaneously prime if and only if
\(\sum_{m \ge 1} {\lfloor \dfrac{n + 2}{m} \rfloor + \lfloor \dfrac{n}{m} \rfloor - \lfloor \dfrac{n + 1}{m} \rfloor - \lfloor \dfrac{n - 1}{m} \rfloor} = 4.\)
Show that \(n\) and \(n + 2\) are simultaneously prime if and only if
\(4(n - 1)! + 1 + n \equiv 0\) (mod \(n(n + 2)\)), \((n > 1).\)
Show that for every \(n\), \(6 \cdot 10^{n+2}\), and \(1125 \cdot 10^{2n+1} \pm 8\) are Pythagorean triples.
Show that the number of ordered pairs of integers whose l.c.m. is \(n\) is \(\tau(n^2)\).
Show that \(\dfrac{1}{2} + \dfrac{1}{3} + \cdot\cdot\cdot + \dfrac{1}{n}\) is never an integer.
Show that \(\dfrac{x^2 + 2y^2}{2x^2 + y^2}\) is a square if and only if \(x = y\).
Prove that
\(\sum_{n = 1}^{\infty} \dfrac{\varphi(n) x^n}{1 + x^n} = \dfrac{x(1 + x^2)}{(1 - x^2)^2}.\)
show that the number of regular \(n\)-gons of unit edge is \(\dfrac{\varphi(n)}{2}\).
Prove that the \(n^{\text{th}}\) order determinant with \(a_{ij} = (i, j)\) has value \(\prod_{i = 1}^{n} \varphi(i)\).
Prove that
\(\sum_{i = 1}^{n} {\sqrt{i}} = {\sqrt{n}} \dfrac{3n + 1 - {\sqrt{n}}^2}{3}.\)
Prove that if \(p = 4n + 3\) and \(q = 8n + 7\) are both prime then \(q\ |\ 2^p − 1\).
Show how to split the positive integers into two classes so that neither class contains all the positive terms of any arithmetic progression with common difference exceeding 1.
Show that the reciprocal of every integer \(n > 1\) can be expressed as the sum of a finite number of consecutive terms of the form \(\dfrac{1}{j(j + 1)}\)
In how many ways can this be done? (Answer: \(\dfrac{1}{2}(\tau(n^2) - 1)\).)
Show that every rational can be expressed as a sum of a finite number of distinct reciprocals of integers.
Show that the density of integers for which (\(n\), \(\lfloor \sqrt{n} \rfloor\)) = 1 is \(\dfrac{1}{\pi^2}\).
Show that the expected value of (\(n\), \(\lfloor \sqrt{n} \rfloor\)) is \(\dfrac{\pi^2}{6}\).
Prove that \(x^2 \equiv a\) (mod \(p\)) for every prime \(p\) implies that \(a\) is a square.
Prove that \(f(a, b) = f(a) f(b)\) for \((a, b) = 1\) and \(f(a + 1) \ge f(a)\) for every \(a\) imply that \(f(a) = a^k\).
Find all primes in the sequence 101, 10101, 1010101, . . . .
Find all primes in the sequence 1001, 1001001, 1001001001, . . . .
Show that if \(f(x) > 0\) for all \(x\) and \(f(x) \to 0\) as \(x \to \infty\) then there exists at most a finite number of solutions in integers of \(f(m) + f(n) + f(p) = 1\).
Prove that the least nonresidue of every prime \(p > 23\) is less than \(\sqrt{p}\).
Prove the existence of infinite sequences of 1’s, 2’s, and 3’s, no finite part of which is immediately repeated.
Let \(d^{*}(n)\) denote the number of square divisors of \(n\). Prove that
\(\text{lim}_{n \to \infty} \dfrac{1}{n} \sum_{m = 1}^{n} d^{*} (m) = \dfrac{\pi^2}{6}\).
Find all \(r\) such that \(n!\) cannot end in \(r\) zeros.
Let \(a_1, a_2, ..., a_n\) be integers with \(a_1 = 1\) and \(a_i < a_{i + 1} \le 2a_i\). Prove that there exists a sequence \({\epsilon_i}\) of \(\pm 1\)'s such that \(\sum_{i = 1}^{n} \epsilon_i a_i = 0\) or 1.
Show that for \(p\) a prime, \(p \equiv 1\) (mod 4)
\(\lfloor \sqrt{p} \rfloor + \lfloor \sqrt{2p} \rfloor + \cdot\cdot\cdot + \lfloor \sqrt{\dfrac{p - 1}{4} \cdot p} \rfloor = \dfrac{p^2 - 1}{12}.\)
Prove that \(\pi^2\) is irrational.
Prove that \(\cos \dfrac{p}{q}\) is irrational.
If \(\dfrac{n_i}{n_1 n_2 ... n_{i - 1}} \to \infty\) prove that \(\sum \dfrac{1}{n_i}\) is irrational.
Prove that \(ae^2 + be + c \ne 0\) if \(a, b, c\) are integers.
Prove that
\(\tau(n) = \lfloor \sqrt{n} \rfloor - \lfloor \sqrt{n - 1} \rfloor + 2 \sum_{d = 1}^{\lfloor \sqrt{n - 1} \rfloor} (\lfloor \dfrac{n}{d} \rfloor - \lfloor \dfrac{n - 1}{d} \rfloor).\)
Let \(n= a_0 + a_1 p + a_2 p^2 + \cdot \cdot \cdot + a_k p^k\) where \(p\) is a prime and \(0 \le a_i <p\). Show that the number of binomial coefficients of order \(n\) that are relatively prime to \(p\) is \(\prod (a_i + 1)\).
Show that if \(r_1, r_2, ..., r_{p - 1}\) form a complete residue system (mod \(p\)) then \(1r_1, 2r_2, ..., (p - 1)r_{p - 1}\) do not.
Show that 3 is a primitive root of every Fermat prime.
Show that the number of ways in which \(n\) can be represented as the product of two relatively prime factors is \(2^{\omega(n) - 1}\).
Prove that every even perfect number is of the form \(2^{p - 1} (2^p - 1)\).
Show that if \(f(x)\) is a polynomial with integral coefficients and there are \(\psi(m)\) integers relatively prime to m in the set \({f(1), f(2), ..., f(m)}\) then \(\psi\) is a weakly multiplicative function.
If \(p = 4n + 1\) is a prime, show that \((2n)!^2 + 1 \equiv 0\) (mod \(p\)).
Show that 128 is the largest integer not representable as the sum of distinct squares.
Show that \(x^3 + y^4 = z^5\) has infinitely many solutions.
Show that \(x^n + y^n = x^{n+1}\) has infinitely many solutions.
Show that for every \(k > 0\) there exists a lattice point (\(x_1, y_1\)) such that for every lattice point (\(x, y\)) whose distance from (\(x_1, y_1\)) does not exceed \(k\), the g.c.d. \((x, y) > 1\).
Prove that no four distinct squares are in arithmetic progression.
Prove that for \(n\) composite, \(\pi(n) < \dfrac{n}{\log n}\).
Prove that \(2^n\ |\ {(n + \sqrt{5})^n}\).
Prove that an odd \(p\) is prime if and only if \(p + k^2\) is not a square for \(k = 1, 2, ..., \dfrac{p - 3}{2}.\)

Unsolved Problems and Conjectures

Does \(\varphi (n) = \varphi (n + 1)\) have infinitely many solutions?
Does \(\sigma(n) = \sigma (n + 1)\) have infinitely many solutions?
Does \(\varphi (n) = \varphi (n + 1) = \cdot\cdot\cdot = \varphi (n + k)\) have solutions for every \(k\)? (Erd\(\ddot{o}\)s)
Conjecture: There is no \(n\) for which \(\varphi (x) = n\) has a unique solution. (Carmichael)
Conjecture: For every positive integer \(k > 1\) there exist infinitely many \(n\) for which \(\varphi (x) = n\) has exactly \(k\) solutions.
Do there exist solutions of \(\sigma (n) = 2n + 1\)?
Is \(\varphi (x) = \varphi (y) = 2n\) solvable for every \(n\)? (Moser)
Are there infinitely many solution of \(\tau (n) = \tau (n + 1)\)?
Are there infinitely many numbers not of the form \(\phi (n) + n\)? (Erd\(\ddot{o}\)s)
Are there infinitely many numbers not of the form \(\sigma (n) + n\)? (Erd\(\ddot{o}\)s)
Do there exist solutions of \(\sigma (x) = m\sigma (y)\) for every integer \(m\)? (Sierpinski)
Are 1, 2, 4, 8, and 128 the only powers of 2, all of whose digits are powers of 2? (Starke)
Does there exist for every \(n\), \(n\) distinct integers all of whose sums in pairs are squares? (This is true for \(n \le 5\).)
Does there exist a sequence of \({\epsilon_i}\) of \(\pm 1\)'s such that \(\sum_{i = 1}^{n} \epsilon_{i \cdot k}\) is bounded for every \(k\)? (Erd\(\ddot{o}\)s)
If \(f(n)\) is an arithmetic function of period \(k\) and not identically 0, is it true that \(\sum \dfrac{f(n)}{n} \ne 0\)? (Erd\(\ddot{o}\)s)
Conjecture: For \(n\) sufficiently large, \(n\) can be partitioned \(n = a + b + c + d = d + e + f\) with \(abc = def\). (Motzkin)
Is \(\sum_{n = 1}^{\infty} \dfrac{\sigma_k (n)}{n!}\) irrational for every \(k\)? (Erd\(\ddot{o}\)s and Kac)
Is \(\dfrac{1}{x} + \dfrac{1}{y} + \dfrac{1}{z} = \dfrac{4}{n}\) sovable for every \(n\)? (Erd\(\ddot{o}\)s)
Has \(n! + 1 = x^2\) any solutions with \(n > 7\)? (Brochard)
Is \(\dfrac{(2n)!}{(n + 2)!^2}\) an integer for infinitely many \(n\)? (Erd\(\ddot{o}\)s)
Is \(\dfrac{(2n)!}{n! (n + k)!}\) an integer for every \(k\) and infinitely many \(n\)? (Erd\(\ddot{o}\)s)
Does there exist an \(A\) such that \(\lfloor A^n \rfloor\) is prime for every \(n\)? (Mills)
Does \(\lfloor e^n \rfloor\) represent infinitely many primes?
Does \(\lfloor e^n \rfloor\) represent infinitely many composite numbers? (Erd\(\ddot{o}\)s)
The number 105 has the property that \(105 − 2^n\) is prime whenever it is positive. Is 105 the largest number with this property?
Is 968 the largest number \(n\) such that for all \(k\) with \((n, k) = 1\) and \(n > k^2\), \(n - k^2\) is prime? (Erd\(\ddot{o}\)s)
Does there exist a prime \(p > 41\) such that \(x^2 − x + p\) is prime for \(1 \le x \le p−1\)?
Let \(\alpha (n)\) denote the number of 1’s in the binary representation of \(n\). Does there exist a \(k\) such that for infinitely many primes \(p\), \(\alpha (p) < k\)? (Bellman)
If \(f(x)\) is a polynomial with integer coefficients, \(f_0 (a) = a\), and \(f_{n+1} (a) = f ( f_n (a))\), can a sequence \(f_n (a)\), \(n = 1, 2, ...\) consist entirely of primes?
For \(p\) sufficiently large and \(ab \ne 0\), \(n > 2\), does the polynomial \(x^n + ax + b\) assume more than \(\dfrac{p}{2}\) values (mod \(p\))? (Chowla)
Find pairs of integers \(m\), \(n\) such that \(m\), \(n\) have the same prime factors and \(m + 1\), \(n + 1\) have the same prime factors; e.g., \(m = 2^k - 2\) and \(n = 2^k (2^k - 2)\). Are these the only cases? (Strauss)
What is the largest integer not representable as the sum of distinct cubes?
Let \(1 < u_1 < u_2 < \cdot\cdot\cdot\) be the sequence of integers of the form \(x^2 + y^2\). Conjecture:
\(\text{lim}_{n \to \infty} \dfrac{u_{n + 1} - u_n}{u_n^{1/4}} = 0.\) (Chowla and Davenport)
Conjecture: \(|\sum_{n \le x} (-1)^{n - 1} p_n| \thicksim \dfrac{p_x}{2}.\) (Pillai)
Can every prime \(p \equiv 3\) (mod 8), \(p > 163\), be written as the sum of three distinct squares? (Chowla)
Is \(\zeta (3)\) irrational? Is \(\zeta (2s + 1)\) irrational?
Conjecture: The only solution of \(1^n + 2^n + \cdot\cdot\cdot + m^n = (m + 1)^n\) is 1 + 2 = 3. (Bowen)
Conjecture: the only solutions of \(a^n + (a + 1)^n + \cdot\cdot\cdot + (a + b)^n = (a + b + 1)^n\) are \(1 + 2 = 3\), \(3^2 + 4^2 = 5^2\), and \(3^3 + 4^3 + 5^3 = 6^3\). (Erd\(\ddot{o}\)s)
Does the equation \(1^2 + 2^2 + \cdot\cdot\cdot + m^2 = (m + 1)^2 + \cdot\cdot\cdot + n^2\) have solutions? (Kelly)?
The product of \(n > 1\) consecutive integers is not a \(k^{\text{th}}\) power.
Conjecture: If \(\alpha > 0\) is not an integer then the density of solutions of \((n, n^{\alpha}\) = 1\) is \(6/ \pi^2\). (Lambek and Moser)
Conjecture: The only solutions of
\(\dfrac{1}{x_1} \dfrac{1}{x_2} + \cdot\cdot\cdot + \dfrac{1}{x_n} + \dfrac{1}{x_1 x_2 ... x_n} = 1\)
are\(^3\)
\(\dfrac{1}{2} + \dfrac{1}{2} = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{6} = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{7} + \dfrac{1}{42} = 1\) (Erd\(\ddot{o}\)s)
Is it true that for all pairs of primes \(p\), \(q\) all sufficiently large numbers can be written as the sum of distinct numbers of the form \(p^{\alpha}q^{\beta}\)? (Erd\(\ddot{o}\)s)
Let \(a_1, a_2, ...\) be integers not exceeding \(n\) such that the l.c.m. of any two is \(> n\). What in the maximum of \(\sum \dfrac{1}{a_i}\)? Conjecture: 31/30. (Erd\(\ddot{o}\)s)
Let \(0 < a_1 < a_2 < \cdot\cdot\cdot < a_k \le n\) be such that the sums of distinct \(a_i\)'s are distinct. conjecture: \(k - \log_2 n\) is bounded. (Erd\(\ddot{o}\)s)
Give a relatively simple proof of Van der Waerden’s theorem for the case of two classes.
Give a relatively simple proof of Roth’s theorem: Any sequence that does not contain an arithmetic progression has zero density.
Give an elementary proof of Dirichlet’s theorem on quadratic residues:
\(\sum (\dfrac{n}{p}) > 0\) for \(p \equiv 3\) (mod 4).
Let \(a_1 < a_2 < ...\) be a sequence of positive integers and let \(f(n)\) denote the number of solutions of \(a_i + a_j = n\). Conjecture: If \(f(n) > 0\) for every \(n\) then \(f(n)\) is unbounded. (Erd\(\ddot{o}\)s and Turan)
If the \(f(n)\) of Problem 49 is > 0 for every \(n\) then every sufficiently large \(n\) can be written as the sum of three distinct \(a\)’s. (Kelly)
Construct a sequence of a’s for which the \(f(n)\) of Problem 49 is > 0 and for which \(f(n) < \log n\) for every \(n\). (Erd\(\ddot{o}\)s has shown that such sequences exist.)
Does there exist a sequence \(A\) with counting function \(A(n) < cn/ \log n\) such that every integer can be represented in the form \(a + 2^{i}, a \in A\)?
Improve the bound \([n!e]\) in Schur’s theorem in combinatorial number theory.
Conjecture. If \(a_1 < a_2 < \cdot\cdot\cdot\) is a sequence of integers with \(a_n/a_{n+1} \to 1\) and if for every \(d\), every residue (mod \(d\)) is representable as the sum of distinct \(a\)’s, then at most a finite number of integers are not representable as the sum of distinct \(a\)’s. (Erd\(\ddot{o}\)s)
Is the sum of the reciprocals of those integers that are representable as the sum of \(k\) \(k^{\text{th}}\) powers divergent? (Klamkin and Newman)
Conjecture: For every \(\epsilon > 0\) there exits an \(N = N(\epsilon)\) such that for \(n > N\) the \(n\)-dimensional game of tic-tac-toe played on a \(3 \times 3 \times \cdot\cdot\cdot \times 3\) board must terminate before \(\epsilon 3^n\) moves have been played. (Moser)
Same as Problem 56 with 3 replaced by \(k\).
Every integer belongs to one of the arithmetic progressions {\(2n\)}, {\(3n\)}, {\(4n + 1\)}, {\(6n + 5\)}, {\(12n + 7\)}, \(n = 1, 2, ...\). This is the simplest example of a finite set of arithmetic progressions, each with different common difference, all of whose common differences are greater than one, that contain all integers. Does there exist for every \(c > 0\) such a set of progressions, each common difference being \(> c\)? (Erd\(\ddot{o}\)s)
Give an explicit representation of \(n\) as the sum of four squares.
Do there exist for every \(n\), \(n\) primes that are consecutive terms of an arithmetic progression?
Let \(\dfrac{1}{1 + x + 2x^2} = \sum_{n = 1}^{\infty} a_n x^n\). Conjecture: \(|a_n| > c \log \log n\).
Are there infinitely primes of the form \(11 \cdot\cdot\cdot 11\)?
Are there infinitely many Euclid primes \(2 \cdot 3 \cdot \cdot \cdot \cdot \cdot p_n +1\)?
Conjecture: The least nonresidue of a prime \(p\) is \(< c \log p\).
Conjecture: The least primitive root of a prime \(p\) is \(< p^{\epsilon}\), \(p > p_0 (\epsilon)\).
Conjecture: The number of perfect numbers \(\le n\) is \(< c \log n\).
Find good bounds for the density of the abundant numbers.
Prove that the ratio of residues to nonresidues in the range \((1, [\sqrt{p}])\) approaches 1 as \(p \to \infty\).
Give an elementary proof of \(\prod_{p \le n} p < 3^n\).
Conjecture: \(\text{lim}_{n \to \infty} (a_{n + 1} - a_{n}) = \infty\) implies \(\sum_{n = 1} \dfrac{a_n}{2^{a_n}}\) irrational. (Erd\(\ddot{o}\)s)
Find all solutions of \(x^4 + y^4 = z^4 + t^4\).
Find all solutions of \(x^4 + y^4 + z^4 = t^4\).
Find all solutions of \(x^xy^y = z^z\).
Let \(\ell (n)\) be the least \(r\) for which there exists a chain of integers
\(a_0 = 1 < a_1 < a_2 < \cdot\cdot\cdot < a_r = n\),
where for each \(i > 0\), \(a_i = a_j + a_k\) for some \(j\), \(k < i\) (\(j = k\) permitted). Conjecture: \(\ell (2^q - 1) \le q + \ell (q) - 1\). (Scholz)
Conjecture: \(\ell (n) < \ell (2n)\) for all \(n > 0\). (Utz)
Let \(S(n)\) denote the number of solutions of \(\ell (x) = n\). Is it true that \(S(n) < S(n + 1)\) for all \(n > 0\)? (Utz)
Polya's conjecture: \(\sum_{n = 1}^x \lambda (n) \le 0\), \(x > 1\). (Checked for \(x < 800000.\))
Turan's conjecture: \(\sum_{n = 1}^{x} \dfrac{\lambda (n)}{n} > 0\). (Checked for \(x < 50000.\))
Pillai's conjecture: \(|x^m - y^n| < N\), \(m, n > 1\) has for every \(N\) only a finite number of solutions.
\(2^e\) is irrational.
Find a reasonable estimate for the number of solutions in positive integers of
\(\dfrac{1}{x_1} + \dfrac{1}{x_2} + \dfrac{1}{x_3} + \cdot\cdot\cdot + \dfrac{1}{x_n} = 1.\)