| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Knuth has an interesting problem in the current issue of the
American Mathematical Monthly (Oct 1985, page 590, problem E3106):
Let S(n) be the set of all positive integes k such that the fractional
part of n/k is 1/2 or more. Fo example,
S(17) = {2,3,6,9,10,11,18,19,20,...,34}.
Prove that
SUM phi(k) = n^2 ,
where phi is Euler's totient function and the SUM is taken over
all k belonging to S(n).
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 342.1 | TOOLS::STAN | Mon Oct 21 1985 21:00 | 66 | ||
Very interesting...
If we replace phi(k) in the problem with other functions,
we get some very strange sequences, whose patterns I do not
recognize. I have tabulated some below:
Notation: phi(k) Euler totient
sum(k) Sum of numbers less than k and relatively prime to k
div(k) Number of divisors of k
divsum(k) Sum of divisors of k
Remember that we are summing over those k for which the fractional part of n/k
is greater than or equal to 1/2.
N phi(k) k k^2 sum(k) div(k) divsum(k)
-- ------ -- --- ------ ------ ---------
1 1 2 4 1 2 3
2 4 7 25 7 5 11
3 9 17 81 21 11 28
4 16 26 174 53 12 41
5 25 45 343 94 21 73
6 36 61 575 167 24 101
7 49 83 895 267 30 134
8 64 108 1326 383 34 174
9 81 139 1889 550 43 229
10 100 165 2537 774 46 271
11 121 209 3403 980 58 342
12 144 237 4363 1307 55 387
13 169 282 5524 1646 64 455
14 196 330 6894 2027 74 540
15 225 384 8516 2507 86 641
16 256 417 10161 3143 80 680
17 289 483 12251 3668 92 783
18 324 544 14552 4272 101 900
19 361 602 17008 5110 107 981
20 400 664 19826 5880 110 1084
21 441 738 23008 6851 122 1217
22 484 794 26200 8032 125 1301
23 529 896 30156 8926 146 1477
24 576 948 34076 10305 134 1551
25 625 1036 38480 11616 146 1693
26 676 1122 43250 12964 155 1833
27 729 1216 48520 14616 168 2004
28 784 1296 53842 16233 171 2131
29 841 1406 59988 17840 183 2298
30 900 1490 66330 19919 186 2464
31 961 1584 72938 22215 192 2593
32 1024 1689 80219 24209 196 2762
33 1089 1821 88299 26246 214 2997
34 1156 1907 95979 29140 217 3123
35 1225 2051105179 31366 235 3374
36 1296 2136114134 34492 226 3519
37 1369 2248123574 37787 232 3672
38 1444 2392134066 40468 250 3925
39 1521 2544145266 43404 268 4192
40 1600 2630155954 47378 256 4308
41 1681 2793168381 50659 274 4573
42 1764 2909180771 54815 277 4793
43 1849 3061193861 58585 289 5016
44 1936 3193207527 62596 292 5223
45 2025 3361222547 67153 313 5566
46 2116 3497236877 71796 322 5776
47 2209 3673253127 76136 334 6039
48 2304 3797269369 80931 316 6216
49 2401 3952286132 86638 325 6447
50 2500 4139304395 91326 343 6795
| |||||
| 342.2 | TOOLS::STAN | Mon Oct 21 1985 21:09 | 55 | ||
Anyone see a formula for the cardinality of the set S?
I have tabulated it's values below:
N #(S)
--- ----
1 1
2 2
3 4
4 4
5 7
6 7
7 9
8 10
9 12
10 12
11 16
12 14
13 17
14 19
15 21
16 19
17 23
18 24
19 26
20 26
21 28
22 28
23 34
24 30
25 33
26 35
27 37
28 37
29 41
30 39
31 41
32 42
33 46
34 46
35 50
36 46
37 48
38 52
39 56
40 52
41 57
42 55
43 59
44 59
45 61
46 63
47 67
48 63
49 65
50 68
| |||||
| 342.3 | ADVAX::J_ROTH | Tue Oct 22 1985 09:44 | 15 | ||
I suspect the following may be a useful line of reasoning: The set S(n) includes the consecutive integers n+1 to 2*n. Consider a 2 dimensional lattice of points with integer coordinates 1 through 2*n (ie: the set [1,2*n]^2), and let us mark all lattice points (x,y) where x and y belong to S(n) and gcd(x,y) = 1. Can we show that the marked lattice points outside the square [n+1,2*n]^2 just fill in the unmarked lattice points in this square? (If I can find my Farey sequence plotting program I'll try and display this and see if an obvious pattern shows itself). - Jim | |||||
| 342.4 | ADVAX::J_ROTH | Tue Oct 22 1985 10:35 | 7 | ||
I tried plotting the points mentioned in .-1 realise the analogy is not very good... still, I suspect that the reason has to do with 'filling in' of that consecutive sequence n+1 to 2*n. It just seems too likely that there is an underlying geometric reason behind Knuth's problem. - Jim | |||||
| 342.5 | LATOUR::JMUNZER | Thu Oct 31 1985 13:04 | 111 | ||
Proof, plus a strange way to draw n-squared. Good one, Stan.
John
[1] Given n, consider the fractions [ j / k ] such that
1 <= j < k <= n
[2] There are
SUM (k = 1 to k = n) OF [ f (n / k) * phi(k) ]
such fractions, where
f (x) = largest integer f such that f <= x.
Proof: consider each distinct fractional value. It appears
once in lowest terms, and maybe some more times. If
the lowest terms are [ j / k ], then the fractions
[j / k], [2j / 2k], [3j / 3k], ..., [rj / rk]
will appear in [1], where r = f (n / k)
The lowest term fractions whose denominators are [ k ]
have numerators which are less than k and relatively
prime to k; i.e. there are phi (k) of them.
So [2] is true by summing over all possible denominators.
[3] But, counting another way, there are
n * (n - 1) / 2
such fractions: 1 with denominator 2
2 with denominator 3
3 with denominator 4
.
.
n-1 with denominator n
[4] So,
[a] SUM (k = 1 to k = n) OF [ f (n / k) * phi(k) ] = n * (n - 1) / 2
Similarly,
[b] SUM (k = 1 to k = 2n) OF [ f (2n / k) * phi(k) ] = 2n * (2n - 1) / 2
Since f (n / k) = 0 for k > n, [a] is equivalent to:
[c] SUM (k = 1 to k = 2n) OF [ f (n / k) * phi(k) ] = n * (n - 1) / 2
Subtracting [b] - 2 * [c],
[d] SUM (k = 1 to k = 2n)
OF [ { f (2n / k) - 2 * f (n / k) } * phi(k) ]
= 2n * (2n - 1) / 2 - 2 * n * (n - 1) / 2
= 2 n*n - n - n * n + n
= n*n
But f (2n / k) - 2 * f (n / k) = 1 if k in S(n)
0 if k not in S(n)
Proof: k in S(n) <==> fractional part of n/k >= 1/2
<==> rk + k/2 <= n < rk+k for some r
<==> 2rk + k <= 2n < 2rk+2k for some r
<==> f(2n/k) - 2 * f(n/k) = 2r+1 - 2r = 1
So [d] can be rephrased as:
[e] SUM (k in S(n)) OF phi(k) = n*n
QED
** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
A curious way to draw [d] is:
Work with points (integer coordinates) inside the triangle whose
vertices are
(0, 0), (2n + 1, 0), and (2n + 1, 2n + 1)
Draw as many straight lines as necessary from the origin to those
points, with more than one point on a line if the slope is right
e.g., if n = 3, then
(6, 1) is on a line by itself
but
(2, 1), (4, 2), and (6, 3) share a line
There are n*n lines with an odd number of points on them. (!)
E.g., for n = 3, they are:
line to (6, 1)
line to (5, 1)
line to (4, 1)
line to (5, 2)
line to (2, 1), (4, 2), and (6, 3)
line to (5, 3)
line to (4, 3)
line to (5, 4)
line to (6, 5)
| |||||