TAOCP 1.2.4: Integer Functions and Elementary Number Theory
Section 1.2.4 exercises: 46/46 solved.
Section 1.2.4. Integer Functions and Elementary Number Theory
Exercises from TAOCP Volume 1 Section 1.2.4: 46/46 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [00] | immediate | verified | 36s |
| 2 | ▶ [01] | simple | verified | 27s |
| 3 | [M10] | math-simple | solved | 5m11s |
| 4 | ▶ [M10] | math-simple | verified | 3m10s |
| 5 | [16] | medium | solved | 39s |
| 6 | ▶ [20] | medium | verified | 7m16s |
| 7 | [M15] | math-simple | solved | 5m31s |
| 8 | [00] | immediate | verified | 35s |
| 9 | [05] | simple | verified | 2m13s |
| 10 | ▶ [10] | simple | verified | 1m10s |
| 11 | [00] | immediate | solved | 7m04s |
| 12 | [00] | immediate | verified | 2m56s |
| 13 | [M00] | math-immediate | verified | 2m22s |
| 14 | ▶ [12] | simple | verified | 34s |
| 15 | [10] | simple | verified | 1m03s |
| 16 | [M10] | math-simple | verified | 43s |
| 17 | [M15] | math-simple | verified | 30s |
| 18 | [M15] | math-simple | solved | 32s |
| 19 | ▶ [M10] | math-simple | verified | 30s |
| 20 | [M15] | math-simple | verified | 2m23s |
| 21 | [M22] | math-medium | solved | 7m21s |
| 22 | ▶ [M10] | math-simple | verified | 3m11s |
| 23 | [M10] | math-simple | solved | 33s |
| 24 | ▶ [M20] | math-medium | solved | 41s |
| 25 | [M02] | math-simple | verified | 1m18s |
| 26 | [M15] | math-simple | verified | 1m03s |
| 27 | [M15] | math-simple | verified | 34s |
| 28 | ▶ [M25] | math-medium | verified | 39s |
| 29 | [M22] | math-medium | verified | 48s |
| 30 | [M30] | math-hard | verified | 36s |
| 31 | [M22] | math-medium | verified | 33s |
| 32 | [M18] | math-medium | verified | 2m11s |
| 33 | [M18] | math-medium | solved | 32s |
| 34 | ▶ [M21] | math-medium | solved | 4m59s |
| 35 | ▶ [M20] | math-medium | verified | 1m18s |
| 36 | [M23] | math-medium | verified | 45s |
| 37 | ▶ [M30] | math-hard | verified | 11m54s |
| 38 | [M26] | math-hard | solved | 48s |
| 39 | [HM35] | hm-hard | solved | 5m26s |
| 40 | [HM46] | hm-research | solved | 53s |
| 41 | [M23] | math-medium | solved | 28s |
| 42 | [M24] | math-medium | solved | 32s |
| 43 | [M23] | math-medium | verified | 2m17s |
| 44 | [M24] | math-medium | verified | 1m33s |
| 45 | ▶ [M28] | math-hard | verified | 51s |
| 46 | [M29] | math-hard | verified | 1m10s |
TAOCP 1.2.4 Exercise 1
By the definitions of floor and ceiling, \lfloor 1.
TAOCP 1.2.4 Exercise 2
For any real number $x$, the floor function $\lfloor x \rfloor$ is an integer by definition.
TAOCP 1.2.4 Exercise 3
Let \lfloor x\rfloor \le x < \lfloor x\rfloor+1, and recall that $\lfloor x\rfloor$ is the greatest integer not exceeding $x$.
TAOCP 1.2.4 Exercise 4
Let $n=\lceil x\rceil$.
TAOCP 1.2.4 Exercise 5
Let $x$ be a positive real number.
TAOCP 1.2.4 Exercise 6
Let n=\lfloor x\rfloor.
TAOCP 1.2.4 Exercise 7
Let $x$ and $y$ be arbitrary real numbers.
TAOCP 1.2.4 Exercise 8
By definition (1), $x \bmod y = x - y \lfloor x/y \rfloor$ when $y \ne 0$, and $x \bmod 0 = x$.
TAOCP 1.2.4 Exercise 9
By equation (1), x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor.
TAOCP 1.2.4 Exercise 10
By equation (1), x \bmod y = x - y\left\lfloor \frac{x}{y}\right\rfloor.
TAOCP 1.2.4 Exercise 11
The reviewer found no errors in the solution to Exercise 1.
TAOCP 1.2.4 Exercise 12
Every integer $x$ is divisible by 1, since $x = 1 \cdot x$.
TAOCP 1.2.4 Exercise 13
By convention, $\gcd(0,n)=|n|$.
TAOCP 1.2.4 Exercise 14
Let $x \equiv 2 \pmod 3,$ $x \equiv 3 \pmod 5.$ Since $3 \perp 5$, Law D implies that these two congruences determine a unique congruence class modulo $15$.
TAOCP 1.2.4 Exercise 15
By definition (1), x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor .
TAOCP 1.2.4 Exercise 16
By definition (1), x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor .
TAOCP 1.2.4 Exercise 17
By definition of congruence, the statement u \equiv v \pmod m means that $u-v$ is an integral multiple of $m$.
TAOCP 1.2.4 Exercise 18
Assume $a \equiv b \pmod r$ and $a \equiv b \pmod s$, with $r \perp s$.
TAOCP 1.2.4 Exercise 19
Since $n \perp m$, the extended Euclidean algorithm (Algorithm 1.
TAOCP 1.2.4 Exercise 20
Assume that ax \equiv by \pmod m, \qquad a \equiv b \pmod m, \qquad
TAOCP 1.2.4 Exercise 21
The existence of a factorization into primes follows by induction on $n$, using exercise 1.
TAOCP 1.2.4 Exercise 22
Take $m=6$ and $a=2$.
TAOCP 1.2.4 Exercise 23
Consider integers $a=2$, $b=8$, $r=4$, and $s=6$.
TAOCP 1.2.4 Exercise 24
Law A extends without change to arbitrary real numbers.
TAOCP 1.2.4 Exercise 25
By Theorem F, if $p$ is prime then a^p \equiv a \pmod p.
TAOCP 1.2.4 Exercise 26
Let $p$ be an odd prime, $a$ any integer, and define $b = a^{(p-1)/2}.$ We are asked to show that $b \bmod p$ is either $0$, $1$, or $p-1$.
TAOCP 1.2.4 Exercise 27
Let $p$ be a prime number.
TAOCP 1.2.4 Exercise 28
Let $R={r_1,r_2,\ldots,r_{\varphi(m)}}$ be the set of integers in ${0,1,\ldots,m-1}$ that are relatively prime to $m$.
TAOCP 1.2.4 Exercise 29
Let $f(n)$ be a function of positive integers.
TAOCP 1.2.4 Exercise 30
Let $n$ be a positive integer and let $\varphi(n)$ denote the number of integers in ${0,1,\ldots,n-1}$ that are relatively prime to $n$, as in exercise 27.
TAOCP 1.2.4 Exercise 31
Let $f(n)$ be a multiplicative function, and define $g(n) = \sum_{d \mid n} f(d).$ We want to show that $g$ is multiplicative, that is, for any integers $r \perp s$, $g(rs) = g(r) g(s).$ Since $r \per...
TAOCP 1.2.4 Exercise 32
Every divisor pair $(c,d)$ that appears on the left-hand side satisfies c \mid d,\qquad d \mid n.
TAOCP 1.2.4 Exercise 33
Let $m$ and $n$ be integers.
TAOCP 1.2.4 Exercise 34
We seek all real numbers $b>1$ such that \lfloor \log_b x\rfloor=\lfloor \log_b \lfloor x\rfloor\rfloor \qquad (x\ge 1).
TAOCP 1.2.4 Exercise 35
Let $x$ be a real number, and let $m$ and $n$ be integers with $n>0$.
TAOCP 1.2.4 Exercise 36
We first evaluate S_n=\sum_{k=1}^n \left\lfloor \frac{k}{2}\right\rfloor.
TAOCP 1.2.4 Exercise 37
Let S(x)=\sum_{k=0}^{n-1}\left\lfloor \frac{mk+x}{n}\right\rfloor, where $m,n\in\mathbb Z$, $n>0$, and let
TAOCP 1.2.4 Exercise 38
Let S(x,y)=\sum_{0\le k<y}\left\lfloor x+\frac{k}{y}\right\rfloor, \qquad y>0.
TAOCP 1.2.4 Exercise 39
Let S_n(f;x)=\sum_{k=0}^{n-1}f\!
TAOCP 1.2.4 Exercise 40
We consider the class of _replicative functions_ $f$, defined in Exercise 39, satisfying f(x) + f\left(x+\frac{1}{n}\right) + \cdots + f\left(x+\frac{n-1}{n}\right) = f(nx) for all positive integers $...
TAOCP 1.2.4 Exercise 41
The sequence is formed by repeating each positive integer $k$ exactly $k$ times: 1,\ 2,2,\ 3,3,3,\ 4,4,4,4,\ \ldots Hence $a_n=k$ precisely when $n$ lies in the block occupied by the $k$'s.
TAOCP 1.2.4 Exercise 42
We prove the identity \sum_{k=1}^n a_k = na_n-\sum_{k=1}^{n-1}k(a_{k+1}-a_k), \qquad n>0.
TAOCP 1.2.4 Exercise 43
We wish to evaluate $S_n = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor.$ Let $m = \lfloor \sqrt{n} \rfloor$, so that $m^2 \le n < (m+1)^2$.
TAOCP 1.2.4 Exercise 44
Let S(n)=\sum_{k\ge0}\sum_{1\le j<b}\left\lfloor \frac{n+j b^k}{b^{k+1}}\right\rfloor .