Karl Heuer has done an experiment refuting a conjecture from Hakmem. I've appended the retyped item 32 after his message. I imagine that the original conjecture was based on a small sample. Wrt KHs conjecture, must the near-integer fraction p be rational? A unit fraction? (Think x = cbrt2.) It seems obvious that the set of x>1 with other-than uniform density must be of measure 0, but obvious isn't a proof. Also, imagine that x = 100+tiny. If the definition of being "near" an integer is within +-.05, then each additional power of x has quite a bit of wiggle room: The window grows from width .10 to 10, allowing us to tweak x to taste for each new power. So we could build practically any coarse distribution we want. What's possible here? Rich rcs@xmission.com ----- Forwarded message from kwzh@gnu.org ----- Date: Mon, 27 Jul 2009 06:44:12 -0400 From: Karl Heuer <kwzh@gnu.org> Reply-To: Karl Heuer <kwzh@gnu.org> Subject: HAKMEM 32 To: Richard Schroeppel <rcs@cs.arizona.edu> Hi there. Yesterday, on a whim, I decided to test your claim at the end of Item 32 of HAKMEM -- that { frac((3+sqrt(2))^n) | n in N } appears to have a non-uniform distribution and a cluster point at 0. Using exact Bignum arithmetic, I computed the first 250000 values of the sequence, each truncated to three decimal places; the histogram of those 1000 buckets looked consistent with a uniform distribution. The sample had a mean of 499.752 and standard deviation 288.651, quite close to what one should expect for the null hypothesis of uniformity. Can you shed any light on what led you to say otherwise, a few decades ago? Google search on [hakmem "item 32"] doesn't seem to have any hits other than the original text, which suggests that nobody in the Web-visible world has ever looked into it. (Conjecture: for any real x, frac(x^n) has near-integers with some density p, with the remaining 1-p being a uniform distribution on the unit interval.) Karl Heuer ----- End forwarded message ----- ITEM 32 (Schroeppel) Take a random real number and raise it to large powers; we expect the fraction part to be uniformly distributed. Some exceptions: 1 -- phi = (1 + sqrt5)/2 2 -- all -1 < X < 1 3 -- sqrt2 (half are integers, other half are probably uniformly distributed) 4 -- 1 + sqrt2 -- Proof: N N (1 + sqrt2) + (1 - sqrt2) = integer (by induction); N the (1 - sqrt2) goes to zero. 5 -- 2 + sqrt2 -- similar to 1 + sqrt2 6 -- any algebraic number whose conjugates are all inside the unit circle. Now, 3 + sqrt2 is suspicious; it looks non-uniform, and seems to have a cluster point at zero. PROBLEM: Is it non-uniform?