1/999999999999999999999998999999999999999999999999(futilitycloset.com)
futilitycloset.com
1/999999999999999999999998999999999999999999999999
http://www.futilitycloset.com/2015/06/28/made-to-order-4/
97 comments
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?
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.)
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.)
I recommend generatingfunctionology by herbert wilf for the interested.
The beautiful idea here is to consider formal power series (encoding sequences of values in polynomials without demanding convergence) https://en.wikipedia.org/wiki/Formal_power_series
The beautiful idea here is to consider formal power series (encoding sequences of values in polynomials without demanding convergence) https://en.wikipedia.org/wiki/Formal_power_series
Is any of this useful for compression?
This is a great response. Thanks for taking the time to write this.
are you a master of math?
[deleted]
The generating function for Fibonacci numbers is
x/(1-x-x^2) = \sum_{n\geq0} F_n x^n,
You can see the pattern with smaller fractions too:
1/89 = 0.0 1 1 2 3 5...
1/9899 = 0.00 01 01 02 03 05 08 13 21 34 55...
1/998999 = 0.001 002 003 005 008 013 021 034 055 089...
1/89 = 0.0 1 1 2 3 5...
1/9899 = 0.00 01 01 02 03 05 08 13 21 34 55...
1/998999 = 0.001 002 003 005 008 013 021 034 055 089...
I may be wrong, but I believe it's some sort of math. Or wizardry.
This explains it well.
http://www.quora.com/Which-is-the-Fibonacci-inverse-number
http://www.quora.com/Which-is-the-Fibonacci-inverse-number
Wouldn't that have been a better title than that stupid number?
Well, the title piqued my curiosity and made me click on it to see what it was about.
0x0(2)
"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.
Isn't this poor wording? The author is dividing 1 by the large number above, not the other way around.
"Divide b into a" means the same as "divide a by b".
Which I why I hate that wording, because that means "divide b into a" is equivalent to "divide a into b parts". And that's just confusing.
It feels to me as though far too much of any given field uses redundant (the same concept expressed lots of different ways) or misleading (something made to sound far more complicated than it actually is) terminology and causes unnecessary amounts of confusion among anyone trying to learn it.
But it loses its English meaning for a=1. Whereas, "divide ten into two" would make sense.
I'm with you on the wording. The word "into" is ambiguous on its own and even more ambiguous used with "divide." There's a discussion of that here: http://mathforum.org/library/drmath/view/52296.html
As an example, a person can easily read "divide 24 into 6" as "divide 24 into 6 [parts]," i.e. 24/x = 6, x = 4 — as opposed to 6/24 = x, x = 0.25. This use is especially reinforced by everyday experiences like dividing a cake into eight slices.
As an example, a person can easily read "divide 24 into 6" as "divide 24 into 6 [parts]," i.e. 24/x = 6, x = 4 — as opposed to 6/24 = x, x = 0.25. This use is especially reinforced by everyday experiences like dividing a cake into eight slices.
I've seen it both ways- "Divide four by two" is equivalent to "Divide two into four" in my experience.
Really? I've always read "divide by" and "divide into" as meaning the exact same thing:
"Divide four by two" = 4/2 = 2
"Divide two into four" = 2/4 = 1/2
Could this be a US/UK English difference?
"Divide four by two" = 4/2 = 2
"Divide two into four" = 2/4 = 1/2
Could this be a US/UK English difference?
I think this phrasing is less confusing when it refers to labels rather than actual numerals. For instance 'divide the price into the exchange rate', which would mean the same as 'divide the exchange rate by the price'.
Why would you use this phrasing? I suppose it can flow more easily in some cases, for instance 'first work out X, then work out Y, then divide them both into Z and see which one is larger' is less of a mouthful than the alternative.
Why would you use this phrasing? I suppose it can flow more easily in some cases, for instance 'first work out X, then work out Y, then divide them both into Z and see which one is larger' is less of a mouthful than the alternative.
It comes from "how many times does 2 go into 4", which is "4/2".
If you go to a pizza restaurant and ask them to "Divide two (large pizzas) into four (portions)" they would indeed give each person 1/2 pizza. So for colloquial use you are correct. Which makes the math definition confusing.
Perhaps it is some kind of regional difference. I've always lived on the US West Coast, and I've heard "divide four by two" expressed as "divide two into four" many times - and never the other way around.
I never use the "into" phrasing myself because it is confusing to me. But it does make some kind of sense if you think about it this way: "How many twos can you put into four?"
I never use the "into" phrasing myself because it is confusing to me. But it does make some kind of sense if you think about it this way: "How many twos can you put into four?"
To me, "divide A into B" sounds like a some sort of anachronism that you might find in a 17th century one-room schoolhouse, while "divide B by A" sounds perfectly natural.
I went to school on the US East Coast, so you might be onto something here.
I went to school on the US East Coast, so you might be onto something here.
"Divide two into four" to me means that I am dividing two into four parts, which would equal one half.
"Divide the cake into two pieces" does not mean I'm giving you another cake.
x into y is y/x
This would be fun response to the usual interview white boarding question.
> 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 !
i don't really understand what you mean here. may you please elaborate ? thanks !
A common warm up question in a coding interview is to write (on the whiteboard) a program that prints the Fibonacci numbers in sequence. Arguably, you can write this fraction and claim this answers the question, though I don't know any programming language where this would actually work without a bunch of more code around it.
Edit: other comments have examples in Python, Clojure and bc.
Edit: other comments have examples in Python, Clojure and bc.
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.
Python can perform a similar calculation using large integers:
10 ** (24 * 116) / 999999999999999999999998999999999999999999999999
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)
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)
[deleted]
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
> 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
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
Why not just use
scale=499
scale=500-1
Originally in my terminal I was experimenting to find a cutoff for the point where the numbers become inaccurate. All of those formulas were in terms of digits and had a -1 on the end.
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
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
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?
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.
> 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.
mostly works in wolfram: http://www.wolframalpha.com/input/?i=1%2F9999999999999999999...
mathematica: http://pastebin.com/GfNG8bLU
[deleted]
Awesome!
What is going on with the quality of the comments in this thread?
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.
Can't say I've seen many flamewars about HN on reddit though.
SIGFPE: floating-point exception
:-)
:-)
while not city specific we have the Silver Comet trail here in Georgia, follows old rail road tracks
http://www.silvercometga.com/
http://www.silvercometga.com/
You've got the wrong thread, I'm afraid.
[deleted]