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/