home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14490 < prev    next >
Encoding:
Internet Message Format  |  1992-11-07  |  1.9 KB
  1. Xref: sparky sci.math:14490 rec.puzzles:7084
  2. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!news.acns.nwu.edu!network.ucsd.edu!galaxy!guitar!baez
  3. From: baez@guitar.ucr.edu (john baez)
  4. Newsgroups: sci.math,rec.puzzles
  5. Subject: Math puzzles - answer
  6. Message-ID: <23678@galaxy.ucr.edu>
  7. Date: 5 Nov 92 20:30:37 GMT
  8. Sender: news@galaxy.ucr.edu
  9. Followup-To: sci.math
  10. Organization: University of California, Riverside
  11. Lines: 47
  12. Nntp-Posting-Host: guitar.ucr.edu
  13.  
  14. Robert Southworth, bog@ugcs.caltech.edu, asked me to post this for him:
  15.  
  16. John Baez (jbaez@riesz.mit.edu) posted two math puzzles 
  17. <1992Oct28.170601.19561@galois.mit.edu>, to which he later gave
  18. partial answers. He writes:
  19.  
  20. > The second question concerned the sum from 1 to infinity of o(2^n)/2^n.
  21. > Here o(2^n) is the number of odd digits in the decimal representation of
  22. > 2^n.  The sum is surprisingly simple - it's 1/9.
  23.  
  24. (1) Clearly the kth digit (the multiplier of 10^k in the decimal
  25. representation) of 2^n is odd iff 
  26.  
  27.         [2^n/10^k] is odd,
  28.  
  29. where [] denotes the greatest integer function. 
  30.  
  31. (2) Similarly, the (-n)th bit (the multiplier of 2^(-n), in the binary
  32. representation) of 10^(-k) is odd (i.e. equal to 1) iff
  33.  
  34.         [10^(-k)/2^(-n)] = [2^n/10^k] is odd.
  35.  
  36.  
  37. Let d_nk be congruent to [2^n/10^k] mod 2, d_nk = 0 or 1. Then by (1),
  38.  
  39.         o(2^n) = sum_k d_nk,
  40.  
  41. and by (2),
  42.  
  43.         10^(-k) = sum_n (d_nk * 2^(-n)).
  44.  
  45. The result follows by reversing the order of summation, as follows:
  46.  
  47.         sum_n o(2^n)/2^n = sum_n (sum_k d_nk)/2^n
  48.                          = sum_k (sum_n d_nk/2^n)
  49.                          = sum_k 10^(-k)
  50.                          = 1/9.
  51.  
  52. (Note that 10^0 is not included in the final sum over k, because the
  53. 0th digit of 2^n is even for all n>=1.)
  54.  
  55. This problem is easy to generalize. The particular values 2 and 10 are
  56. not important; their only crucial property is that 10 is divisible by 2.
  57.  
  58.  
  59.     Robert Southworth      bog@ugcs.caltech.edu
  60.  
  61.