Problem A: [Apo80, Chap. 3, Exc 21] Determine all positive integers n such that |_sqrt(n)_| divides n. Find a closed formula for w2(N) := #{ n in {1..N} | |_sqrt(n)_| divides n }. Show 3sqrt(N + 16/9)-4 <= w2(N) <= 3sqrt(N)-2. Problem B: [GKP88, Section 3.2, The Concrete Mathematics Club Casino] Determine all positive integers n such that |_n^(1/3)_| divides n. Find a closed formula for w(N) := #{ n in {1..N} | |_n^(1/3)_| divides n } Show 3/2 * N^(2/3) + 5/2 * N^(1/3) - 121/24 < w(N) <= 3/2 * N^(2/3) + 5/2 * N^(1/3) - 3. Solution A: For integers n between two squares k^2 <= n < (k+1)^2 there are only three possible values. These are k*k, k*(k+1) and k*(k+2) = (k+1)^2 - 1. Therefore the set of positive integers with this property is W2 = { 1,2,3, 4,6,8, 9,12,15, 16,20,24, 25,30,35, ... }. So we have the special values w2(k^2 - 1) = 3(k-1) = 3k - 3 w2(k^2) = 3k - 2. Now for the general case. Let k = |_sqrt(N)_| then w2(N) = w2(k^2) + |_(N - k^2)/k_| = 2k + |_N/k_| - 2. The Concrete Mathematics Club Casino: ------------------------------------- This is a problem from Graham, Knuth, Patashnik [they can't refuse] [GKP88: Section 3.2: Floor/Ceiling Applications]. Let |_x_| := floor(x) and let w(N) := #{ n in {1..N} | |_n^(1/3)_| divides n } then they show that (3.13) w(N) = |_N/K_| + 1/2 * K^2 + 5/2 * K - 3 with K = |_N^(1/3)_| Problem: Return to the Wheel of Fortune [GKP88 (9.39)] Now look for an approximation which is floor-free better than (9.39) w(N) = 3/2 * N^(2/3) + O(N^(1/3). Solution B: ----------- Let theta1 = N^(1/3) - K and theta2 = N/K - |_N/K_|. It is easy seen that 2/3 1/3 w(N) = 3/2 * N + 5/2 * N + O(1) as we have w(N) = |_N/K_| + 1/2 * K^2 + 5/2 * K - 3 = N/K + 1/2 * K^2 + 5/2 * K + O(1) = (K+theta1)^3 / K + 1/2 * K^2 + 5/2 * K + O(1) = K^2 + 3 * K*theta1 + 1/2 * K^2 + 5/2 * K + O(1) = 3/2 * K^2 + (5/2 + 3*theta1)*K + O(1) = 3/2 * (K+theta1)^2 + 5/2 * (K+theta1) + O(1) = 3/2 * N^(2/3) + 5/2 * N^(1/3) + O(1) The approximation is no surprise as we have 2/3 1/3 w(N) = 3/2 * N + 5/2 * N - 3, if N is a cube. Define the remainder function theta(N) as 2/3 1/3 w(N) = 3/2 * N + 5/2 * N - 3 - theta(N). We already know that theta(N) = O(1). The same procedure as above but not omitting O(1) terms leads to theta(N) = (5/2 - 3/2 * theta1 - theta1^2 / K)*theta1 + theta2 What are the best upper and lower bounds on theta(N)? We show: 0 <= theta(N) < 49/24 which is best possible. The best lower bound is 0 as 5/2 - 3/2 * theta1 - theta1^2 / K can not be negative. The best upper bound is 49/24. For fixed theta1 (not zero) theta is increasing in K. Letting K be oo we only need to find the maximum of (5/2 - 3/2 * theta1)*theta1 and of theta2. The first part reaches its maximum value 25/24 for theta1=5/6. The second part reaches its maximum value 1 for theta2=1. Table of w(N) = w_approx(N) + theta(N). N w_approx w theta theta1 theta2 --------------------------------------------------------------------- 10 9.348 9 0.34847 0.15443 0.00000 100 40.920 40 0.92049 0.64159 0.00000 1000 172.000 172 0.00000 0.00000 0.00000 10000 747.099 746 1.09919 0.54435 0.19048 100000 3344.692 3343 1.69176 0.41589 0.91304 1000000 15247.000 15247 0.00000 0.00000 0.00000 10000000 70159.441 70158 1.44118 0.44347 0.62791 100000000 324322.601 324322 0.60071 0.15888 0.24138 1000000000 1502497.000 1502497 0.00000 0.00000 0.00000 NOTE: w(10^9) = 1502497 and not 1502496 as stated in Concrete Math. This is a "slippery floor" problem [GKP88, (7.38) following]. So I won a check of 2^8 cents for finding the most unimportent error in this book. References: Apo80: Tom M. Apostol; Introduction to Analytic Number Theory, Springer, 1980 Chap 3: Averages of arithmetical functions Properties of the Greatest-Integer Function: Exc 13-26 CoK89: Curtis N. Cooper, Robert E. Kennedy; Chebyshev's Inequality and Natural Density, AMM 96 (Feb. 1989) 118-124. - Let f be an integer valued function. S = { n : f(n) divides n } they consider f = digital sum. The set S is called Niven numbers. GKP88: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik; Concrete Mathematics, Addison Wessley, Reading (1994) 2nd Ed. Chap 3: Integer Functions Sect 3.1: Floors and Ceilings Sect 3.2: Floor/Ceiling Applications - The Concrete Math Club Casino (3.13) - Return to the Wheel of Fortune (9.39) Sect 3.3: Floor/Ceiling Recurrences Sect 3.4: Mod: the Binary Operation Sect 3.5: Floor/Ceiling Sums Way75: Alan Wayne; SSM 3581, School Science and Mathematics, 75 (1975) 386 & 744 (Solution Charles W. Trigg) - Find the set of natural numbers each of which is exactly divisible by the greatet integer in its cube root. -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/