1/999999999999999999999998999999999999999999999999

[pkfrank]

I feel like this would make infinitely more sense to me if not for that singular "8" hiding close to the middle. Can anyone ELI5 what's going on here?

[svat]

Short answer: the denominator is (10^48 - 10^24 - 1).

Long answer follows.

It's actually easier to understand if you work backwards and arrive at the expression yourself, by asking yourself: "If I wanted the number that starts like 0.0...000 0...001 0...001 0...002 0...003 0...005 0...008 ... (with each block being 24 digits long), how would I express that number?"

Well, calling the Fibonacci numbers f_n (with f_1=0), that decimal expansion you want is sum (f_n 10^(-24n)) over n≥1. This is sum (f_n x^n) evaluated at x = 10^(-24). It is easy to work out (especially if you know the trick already) that sum (f_n x^n) = x^2 / (1 - x - x^2), which at x = 10^(-24) gives that the number we want is 1/(10^48 - 10^24 - 1), which is exactly what 1/999999999999999999999998999999999999999999999999 is.

This may be more interesting if you consider more examples:

* if we want the number 0 . 0001 0002 0004 0008 0016 0032 0064 0128..., then it is sum (2^(n-1) 10000^(-n)). We can calculate that sum(2^(n-1) x^n) is x/(1-2x), which at x = 1/10000 becomes 1/9998. And indeed 1/9998 = 0.0001000200040008001600320064012802560512102420484096...

Similarly,

* if we want the number 0 . 000 001 002 003 004 005 ..., then it is sum ((n-1) 1000^(-n)). And sum ((n-1) x^n) is x^2/(1-x)^2, and putting x = 1/1000 in it gives 1/999^2 = 1/998001, and indeed 1/998001 = 0.000001002003004005006007008009010011012013014015016...

Basically whenever sum (a_n x^n) has a nice form (aka the generating function of the sequence), you can plug in x = 1/(some power of 10) and get such pretty decimal expansions.

(Edit: Formatting, and the "short answer" at the top.)

[conistonwater]

The generating function for Fibonacci numbers is

    x/(1-x-x^2) = \sum_{n\geq0} F_n x^n,

so you just let x = 1e-24. In this case it's x^2/(1-x-x^2) to make the fraction come out with numerator 1.

[andrewstuart2]

I may be wrong, but I believe it's some sort of math. Or wizardry.

[mineshaftgap]

This explains it well.

http://www.quora.com/Which-is-the-Fibonacci-inverse-number

[olog-hai]

"Divide the number 999,999,999,999,999,999,999,998,999,999,999,999,999,999,999,999 into 1"

Isn't this poor wording? The author is dividing 1 by the large number above, not the other way around.

[martincmartin]

"Divide b into a" means the same as "divide a by b".

[cmaggard]

I've seen it both ways- "Divide four by two" is equivalent to "Divide two into four" in my experience.

[jjaredsimpson]

x into y is y/x

[aseem]

This would be fun response to the usual interview white boarding question.

[signa11]

> This would be fun response to the usual interview white boarding question.

i don't really understand what you mean here. may you please elaborate ? thanks !

[djent]

There's no way I'd get a job if they asked me to express the Fibonacci sequence in a series of 24 digit blah blah blah as a fraction.

[hathawsh]

Python can perform a similar calculation using large integers:

  10 ** (24 * 116) / 999999999999999999999998999999999999999999999999

Very cool math.

[mariusz331]

Interesting. Something I didn't realize: for n > 4, F(n) = F(n-2) * 3 - F(n-4)

fibonacci sequence is defined as: F(n) = F(n-1) + F(n-2)

substitute F(n-1) with F(n-2) + F(n-3): F(n) = F(n-2) + F(n-3) + F(n-2)

substitute F(n-3) with F(n-4) + F(n-5): F(n) = F(n-2) + F(n-5) + F(n-4) + F(n-2)

substitute F(n-4) with F(n-2) - F(n-3): F(n) = F(n-2) + F(n-5) + F(n-2) - F(n-3) + F(n-2)

simplify: F(n) = 3 * F(n-2) + F(n-5) - F(n-3)

because F(n-3) = F(n-4) + F(n-5), -F(n-4) = F(n-5)) - F(n-3):

F(n) = 3 * F(n-2) - F(n-4)

[GhotiFish]

IT WORKS!

  Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
  This is free software with ABSOLUTELY NO WARRANTY.
  For details type `warranty'. 
  scale=24*20
   
  1/999999999999999999999998999999999999999999999999
  .0000000000000000000000000000000000000000000000010000000000000000000\
  00001000000000000000000000002000000000000000000000003000000000000000\
  00000000500000000000000000000000800000000000000000000001300000000000\
  00000000000210000000000000000000000340000000000000000000000550000000\
  00000000000000089000000000000000000000144000000000000000000000233000\
  00000000000000000037700000000000000000000061000000000000000000000098\
  70000000000000000000015970000000000000000000025840000000000000000000\
  04181

Don't know how.

[boxfire]

> echo 'scale=500-1;10/(10^20-10^10-1)' | BC_LINE_LENGTH=12 bc

will give you the ten digit ones, with the last digit rounded up on the very end.

I havent quite got an exact formula for scale before the rounding is wrong, e.g. for 100 digits:

> echo 'scale=50000-2000-1;10/(10^200-10^100-1)' | BC_LINE_LENGTH=102 bc

[cliftonk]

Very cool. https://gist.github.com/clifton/97f8a862a590c15e1785

[bigethan]

not nearly as cool, but in 8th grade I enjoyed:

  987654312 / 123456789 = 8

[sumitviii]

> 987654321 / 123456789 = 8

FTFY

[bbcbasic]

The sequence popping out of 'nowehere' like this reminds me of a upenn cis194 Haskell homework*

Fib sequence can be expressed as:

F(x) = x / (1 − x − x^2)

where x is an infinite stream of 0,1,0,0,0....

and with sane definitions of divide, add, multiply, subtract for these streams.

* http://www.seas.upenn.edu/~cis194/spring13/hw/06-laziness.pd.... Ex 6

[zarndawg]

Maybe a dumb question...so I wrote out the derivation for the generating function and am of course getting x/1-x-x^2. Is the idea just that multiplying through by x just shifts the generating function so you end up with the generating function for f(n)x^(n+1)? Which still gives the resulting decimal expansion?

[Mandatum]

Tried it in Windows cmd:

> C:\Users\X>set /a result=1/2147483647

> 0

> C:\Users\X>set /a result=1/2147483648

> Invalid number. Numbers are limited to 32-bits of precision.

[easymovet]

mostly works in wolfram: http://www.wolframalpha.com/input/?i=1%2F9999999999999999999...

[mjg4775]

mathematica: http://pastebin.com/GfNG8bLU

[curiously]

It seems like day by day the stories being posted on HN more and more resembles something like reddit, and by that I mean stories like this are just so minimal in value and more geared towards self promotion

[chris_wot]

Did you just come from Reddit to tell us that?

[kevando]

I feel like if I posted this to facebook, I would lose at least 1 friend.

[dmvaldman]

a friend not worth having!

[sonabinu]

Awesome!

[Trufa]

What is going on with the quality of the comments in this thread?

[Crito]

Reddit is extremely unpopular here; mentioning it is a good way to start a flamewar.

Can't say I've seen many flamewars about HN on reddit though.

[AdieuToLogic]

SIGFPE: floating-point exception

:-)

[Shivetya]

while not city specific we have the Silver Comet trail here in Georgia, follows old rail road tracks

http://www.silvercometga.com/

[bsmith]

You've got the wrong thread, I'm afraid.