Hacker News new | past | comments | ask | show | jobs | submit login

The techniques of constructing such sequences have been studied formally in combinatorics under the name "generating function".

http://en.wikipedia.org/wiki/Generating_function

In this case, the sequence 1, 2, 4, ..., 2^n has the generating function,

  g(z) = sum[i = 0 to inf] (2^i * z^i) 
       = 1 + 2z + 4z^2 + ... 
       = 1 / (1 - 2z)
Substituting a small number 10^-k, such as z = 0.0001 gives 10000/9998, and then right shifting by dividing 10000 leads to 1/9998.

What more interesting is that some other useful sequences can often be obtained from the function, by operations like differentiation and integration, or adding / multiplying with other functions.

For example:

  2z + (4*2)z^2 + (8*3)z^3 + (16*4)z^4 ...
  = d/dz(g(z))
  = d/dz(z * 1 / (1 - 2z))
  = 2 / (1 - 2z)^2
Put z = 1/10000 = 0.0001, this yields 50000000/24990001 = 2. 0008 0024 0064 0160 0384 ...



Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: