The problem of "counting ones" by kyungmi lim (http://geocities.yahoo.com/kyungmi_lim/) Feb. 2005 A word about the notations. It is hard to write math in plain text. One can write math in TeX, but that makes an awkward reading. So i use notations somewhat in between: powers: N^2, N^(B-1) summation: Sum_{ ... } with the range in the braces subscripts: N_b, N_(B-1) tuples: (a,b,...,z) Marco came up with several conjectures on numbers in base B. One of them says: for a given positive integer number N lets define D(N) = Sum_{n <= N} #(1,B,n) - N where #(1,B,n) is the numbers of digit '1' in the representation of 'n' in base B. there exists a finite number of positive integers N that satisfy D(N) = 0 and the largest number is (1) N_B = (1,1, ..., 1,0) in base B ie, N_B = Sum_{k=1 .. B-1} B^k My homework is to prove this conjecture. I divide the proof in two steps - (2) D(N_B) = 0 - (3) for any N > N_B, D(N) > 0 ------------------------------------------------------ Proof of (2). For convenience write #(n) = #(1,B,n) since the base, B, and the digit, '1', are fixed. Lets consider an example, B=5, N_B=11110, and count the '1's in base 5. 0 1 2 3 4 ............................................. D(4) = 1 10 20 30 40 11 21 31 41 12 22 32 42 13 23 33 43 14 24 34 44 .............................. D(24) = 2 * 5 100 110 ... 140 200 ... 300 ... 400 ... 440 101 . ... 441 102 . ... 442 103 ... 443 104 ... 444 D(124) = 3 * 5^2 1000 .... 1400 2000 .... 3000 .... 4000 .... 1001 ... 1044 ....................................... 4444 D(624) = 4 * 5^3 10000 11000 ... 20000 ... 30000 ... 40000 ... ... ... 20001 ... 30001 ... ... 10100 11100 ... ... ... ... ... 44000 . ... ... ... ... ... ... ... . 11110 ... ... ... ... ... 44400 . ... ... ... ... ... ... ... . ... ... ... ... ... ... 44440 10444 ... ... ... ... ... ... 44444 From this example we see that - there are B^d numbers from 0 to B^d - 1 - there are B^(d-1) digit '1's in each column, and there are d columns Therefore (4) S(d) = Sum_{n=0 .. B^d-1} #(n) = d * B^(d-1) In particular this gives (5) S(B-1) = Sum_{n=0 .. B^(B-1)-1} #(n) = (B-1) * B^(B-2) How many '1' are there from B^(B-1) to N_B, inclusive ? Lets go back to the example and see the structure of the numbers. Define ___B-k___ ___k___ (6) s(k) = (1,1,...,1,0,...,0) from s(B-1) to s(B-2)-1 there are B^(B-2) numbers, and B^(B-2)+S(B-2) '1's, from s(B-2) to s(B-3)-1 there are B^(B-3) numbers, and 2*B^(B-3)+S(B-3) '1's, ... from s(2) to s(1)-1 there are B numbers, and (B-2)*B+S(1) '1's, and s(1) is just 1 number and has (B-1) '1's. From these and (5) we have Sum_{n=0 .. N_B} #(n) = (B-1) * B^(B-2) + B^(B-2) + (B-2)*B^(B-3) + 2 * B^(B-3) + (B-3)*B^(B-4) + ... + (B-2) * B + 1 (8) + (B-1) = B^(B-1) + B^(B-2) + B^(B-3) + ... + B^2 + B = Sum_{n=1 .. B-1} B^n = N_B This proves eq. (2). ------------------------------------------------------- Proof of (3) We will prove it in three steps: - for the numbers from N_B+1 to 2*B^(B-1)-1 - for the numbers from 2*B^(B-1) to N_f=B^B - 1 - for the numbers greater or equal to B^B [1] - - - - - - - - - - - - - - - - - - - - - - - - - - - Looking again at the example we notice that from N_B + 1 to 2*B^(B-1)-1, each number has at least one '1' (and N_B + 1 has B '1's). Therefore D>0 for these numbers. Using the leading '1's to compensate for the increment of natural numbers, D(2*B^(B-1)-1) is just the sum of '1's in the remaining columns (from the second to the rightmost) in these numbers. D(2*B^(B-1)-1) = = S(B-1) - [ Sum_{n=B^(B-1) .. N_B} #(n) - (N_B - (B^(B-1) - 1)) ] (9) = (B-1)*B^(B-2) - [ B^(B-2) + Sum_{k=1 .. B-2} B^k - Sum_{k=1 .. B-1} B^k + B^(B-1) - 1 ] = (B-2) * B^(B-2) + 1 For B=2 this is 1 and the next number is B^B. For B>=3, the next step is to show that all integers from 2*B^(B-1) to N_f = B^B - 1 have D(n) > 0. Then we think about the numbers that are greater or equal than N_f. [2] - - - - - - - - - - - - - - - - - - - - - - - - - - - Let m(k) = k * B^(B-1). Every block from m(k) to m(k+1)-1 has exactly the same sequence of numbers if we disregard the digit 'k' in the first column. There are B^(B-1) numbers in each block. Moreover the 'k's in the first column does not contribute to the sum of '1's. Therefore if we write the numbers in the block k as n(k,x) = m(k)+x = k*B^(B-1) + x, with 0 <= x < B^(B-1), Sum_{n=0 .. n(k,x)} #(n) = Sum_{n=0 .. k*B^(B-1)} #(n) + Sum_{n=0 .. x} #(n) For B-1>= k > h >=2, D(n(h,x)) = Sum_{n=0 .. n(h,x)} #(n) - n(h,x) = Sum_{n=0 .. k*B^(B-1)} #(n) - (k-h) Sum_{n=0 .. B^(B-1)} #(n) + Sum_{n=0 .. x} #(n) - (k * B^(B-1) - (k-h) * B^(B-1) + x ) (10) = D(n(k,x)) - (k-h) * S(B-1) + (k-h) * B^(B-1) = D(n(k,x)) + (k-h) * B^(B-2) Therefore if D>0 for every number in the last block, k=B-1, then D>0 for every number in the other blocks as well, ie, from 2*B^(B-1) to N_f=B^B - 1. Compute D for N_f and m(B-1) - 1, D(N_f) = Sum_{n=0 .. N_f} #(n) - N_f = S(B) - (B^B - 1) (11) = B * B^(B-1) - B^B + 1 = 1 D(m(B-1) - 1) = Sum_{n=0 .. (B-1)*B^(B-1)} #(n) - (B-1)*B^(B-1) + 1 = S(B) - S(B-1) - (B-1)*B^(B-1) + 1 (12) = B*B^(B-1) - (B-1)*B^(B-2) - (B-1)*B^(B-1) + 1 = B^(B-2) + 1 D(m(B-1)) is less than the number of integers in the block from m(B-1) to N_f. We need to check D inside the block. The strategy is to break the block into segments and use the positive amount of D at the entrance of each segment to compensate for the increment of natural numbers inside the segment, without computing D for each number. In fact if we can segment the block in a way that the entrance value of D for each segment is greater than the amount of numbers it contains we are sure that D is positive for every number in the segment. Therefore D>0 in the whole block, which is what we need to prove for the second step. Let's break the block such that the closer a segment is to N_f the shorter it is. Define ____B-k____ ____k____ (13) r(k) = (B-1,...,B-1,0,0,...,0) 1<=k<=B-1 with segments: r(1) --> N_f for k=1. It contains B numbers. r(k) --> r(k-1) for 1=1, (13') D(r(k)-1) = Sum_{n=0 .. B^B} #(n) - S(k) - (B^B - B^k -1) = B^k - k * B^(k-1) + 1 which is less that B^k - B^(k-1). For the segment k=1, D(r(1)-1) = B, and there are B-1 numbers from r(1) to N_F-1. Therefore D>0 in this segment. For k>=2 further segmentation is needed. Define ____B-k____ ___k-1___ (14) r(k,a) = (B-1,...,B-1,a,0,0,...,0) 0<= a < B-1, 2 <= k <= B-1 with segments r(k,a) --> r(k,a+1)-1 which contain B^(k-1) numbers. Clearly r(k,0) = r(k), and r(k,B-1)=r(k). (15) D(r(k,0)-1) = Sum_{n=0 .. B^B} #(n) - S(k) -(B^B - B^k -1) = (B-k)*B^(k-1) + 1 Since D(r(k,0)-1) > B^(k-1), D>0 for each number in the segment a=0. The following B^(k-1) numbers (segment a=1) have at least one '1'. Therefore D>0 for them as well. In general, for segments a>=2, D(r(k,a)-1) = (B-k)*B^(k-1) + 1 + a*S(k-1) + B^(k-1) - a*B^(k-1) = (B-k+1-a)*B^(k-1) + 1 + a*(k-1)*B^(k-2) The derivative of this with respect to a is negative, dD(r(k,a)-1)/da = (-B+k-1)*B^(k-2) < 0 therefore D is monotonically decreasing function of 'a'. It attains the minimum at a=B-2, D(r(k,B-2)-1) = (-k+3)*B^(k-1) + 1 + (B-2)*(k-1)*B^(k-2) (16) = B^(k-1) + (B-2*k+2)*B^(k-2) + 1 This is not always greater than B^(k-1). Let's introduce smaller segments. Define ___B-k____ ___k-2__ (17) r(k,a,b) = (B-1,..,B-1,a,b,0,0,..,0) 2<=k<=B-1, 2<=a<=B-2, 0<=b<=B-1 with segment r(k,a,b) --> r(k,a,b+1) containing B^(k-2) numbers. From eq. (16) D(r(k,a,0)-1) > B^(k-2), therefore D>0 for the segment b=0. In the next segment (b=1) each number has at least one '1'. Therefore D>0 for segment b=1. For b >= 2 D(r(k,a,b)-1) = (B-k+1-a)*B^(k-1) + 1 + a*(k-1)*B^(k-2) + b*S(k-2) + B^(k-2) - b*B^(k-2) = (B-k+1)*B^(k-1) + B^(k-2) + 1 - a*(B-k+1)*B^(k-2) - b*(B-k+2)*B^(k-3) and its derivative with respect to 'b' is negative: dD(r(k,a,b)-1)/db = - (B-k+2)*B^(k-3) Therefore it is monotonically decreasing function of 'b' and its minimum (at a=B-2, b=B-1) is D(r(k,a,b)-1)_min = (B-k+1)*B^(k-2) + (B-k+2)*B^(k-3) + 1 > B^(k-2) Hence D>0 for each segment of 'b' for 2<=k<=B-1, 2<=a<=B-2, 2<=b<=B-1. We conclude that D(n)>0 for each number from r(B-1,0,0)=(B-1)*B^(B-1) to N_f. This complete the proof that D>0 for each number from 2*B^(B-1) to N_f. [3] - - - - - - - - - - - - - - - - - - - - - - - - - - - The last step shows that D(n)>0 for all n>N_f=B^B. For k>=0, D(B^(B+k)-1) = S(B+k) - (B^(B+k)-1) = 1 + k*B^(B+k-1) > 0 Since from B^(B+k) to 2*B^(B+k) every number has '1' in the first column, D>0 for these numbers (there are B^(B+k) of them). We proceed as we did in step [1]. D(2*B^(B+k)-1) = 1 + k*B^(B+k-1) + S(B+k) = 1 + 2*k*B^(B+k-1) + B^(B+k) > B^(B+k) Therefore we can proceed with the next B^(B+k) numbers. In general for 2 <= a <= B-1, D(a*B^(B+k)-1) = 1 + (a-1)*k*B^(B+k-1) + S(B+k) = 1 + a*k*B^(B+k-1) + B^(B+k) > B^(B+k) Therefore D is always positive for the numbers from B^(B+k) to (B-1)*B^(B+k) + B^(B+k) - 1. since this is true for any k>=0, D>0 for all n>N_f, and this completes the proof of (3).