Fun with math: Dividing one by 998001 yields a surprising result | Hacker News Reader

Fun with math: Dividing one by 998001 yields a surprising result

iheartchaos.com

754 pointskenver90 comments

There's some sleight of hand here. Not all the digits are exactly right. Look how it skips from 997 to 999:

http://www.futilitycloset.com/2012/01/08/math-notes-76/

Here's the math. Suppose you want a unit fraction 1/n with decimals that cycle through the 4-digit sequence abcd. Multiply by 10^4 to shift abcd into integer position, leaving repeating copies after the decimal point:

    10^4/n = abcd + 1/n

Solving for n gives n = (10^4 - 1) / abcd.

More generally, if you want to get a cycle equal to the d digits of an integer k, you want n = (10^d - 1) / k.

However, this only gives a true unit fraction when k divides 10^d - 1, so that n is an integer. Otherwise you are forced to truncate n and getting an approximate version of the cycle.

That's exactly what happened here: 10^d - 1 is not divisible by the integer 001002...998999.

Here's a small Python program that will generate the unit fraction given the number of digits to cycle through:

    import sys

    n = int(sys.argv[1])
    s = ''.join(("%0" + str(n) + "d") % (i,) for i in range(10**n))
    print "1/%d" % ((10**len(s) - 1) / int(s),)

Usage:

    $ python magic.py 3
    1/998001
    $ python magic.py 4
    1/99980001

This has just the right flavor for a Project Euler problem.

I just want to know I appreciate you posting this. Some people might be interested in "wow math sure can do some funky stuff", but others like myself really want to know why. I figure that's also covers a sizable group of us here on Hacker News.

It does indeed. I have a love/hate relationship with math. Love because it's fascinating and intergal to an understanding of our universe, hate because I had some horrible math teachers over the years...plus I do admit to being slightly lazy.

There is no why. It just is. This is the worst thing about being human :)

http://www.smbc-comics.com/index.php?db=comics&id=1914

Nice trick. It works in any even base b:

    xy = b((x - b/2) + (y - b/2)) + (b - x)(b - y)

For b = 2 in particular, x - b/2 and x - b/2 are the negative 1's complements of x and y, and b - x and b - y are the 2's complements. More generally, they are the same kinds of complements generalized to base b.

Because of that symmetric relationship with complementation, I suspect there is a conceptual proof waiting to be found. By conceptual I mean something that isn't just blind formula crunching. That would get us much closer to "why".

It's a bit sneaky to say it generates all three-digit numbers when 998 clearly isn't there, but as onedognight pointed out below, the leading 1 from the 1000 which follows 999 will cause 999 to overflow into 1000, which turns the 998 into a 999.

love the math. thanks for sharing.

A simple way to figure out how this works is to figure out another way to write it out. For the simpler case (1/9801) = 0.00010203...

      0.00
    + 0.0001
    + 0.000002
    + 0.00000003
      ...
    --------------

Each row is equal to x, but shifted over 2x digits. This is the same as dividing by 10^x. This simplifies to the formula:

    sum k=0 to infinity: k/(10^k)

This is fairly easily calculable, and results in 1/9801. Try it yourself on wolfram alpha: http://www.wolframalpha.com/input/?i=%28sum_%28k%3D1%29%5Ein...

The general any-number-base-b rule here (as others have noticed in base 10^k) is that

1/(b-1)^2 = 0.0123456... (where '1', '2'.. are base b digits).

The original post is this fact in base 1000.

Proof for any base: 1/(b-1) = 1/b + 1/b^2 + 1/b^3 + .. = 0.11111.. (base b).

So 1/(b-1)^2 = 0.11111.. * (1/b + 1/b^2 + 1/b^3 + ...) = 0.012345... QED.

Richard Feynman beat us all to the punch here by noticing that 1/243 = 0.004115226337..., a fact which he wrote in a letter from a secret lab to someone in the outside world, and which put him under suspicion of sending secret messages! That gem of a fraction turns out to be a result of the above stuff as 1/243 = 111 * (1/999^2) + 4/999.

Here's a slightly more detailed explanation:

http://tylerneylon.com/b/archives/51

I just want to repeat bdg's appreciation for the people who are explaining the actual theory, which is the interesting part. Funky results from arbitrary arithmetic is just a step short of numerology and while it's nifty in a stage magic kind of way, it's a little sad overall when you have no idea why that's the way it is.

This can be seen in python with (I had to dig into the docs for this, so here are the fruits of my labor :) )

    import decimal

    decimal.getcontext().prec=1000
    dec = decimal.Decimal(1)/decimal.Decimal(998001)
    
    #now doctor it up to see the numbers
    strdec = str(dec)[2:] #chop off the '0.'
    nums = zip(strdec[::3],strdec[1::3],strdec[2::3])
    print nums

I don't have a python shell available... what happens after 999?

It repeats.

EDIT: Um... I answered the good man's question. Could someone explain why this correct answer was voted down so I may improve it? I recognize that it is short, but that's really all there is too it. It's a decimal expansion, not a border collie.

The period is 2997, so set precision to 2997 if you want to see the repeat. Also, "998" doesn't appear 'in sequence' (it obviously appears as 97[9 98]0 981).

Edit: That's strange, about 998 being absent. What follows is definitely nonsense:

Don't really have time to think about this, but you can sort of generate the sum (ie by looking at the pattern) with

(1/1000) * sum i * 1000^-i , i = 0 to infinity

You could try and do a sum of a sum of geometric series and make it work

http://www.wolframalpha.com/input/?i=sum+i+*+1000%5E-i%2C+i%...

(998001 / 2997 = 3)

It's necessary that one number is absent. The period is 2997 as he mentions. Can't pack 1000 3 digit numbers into that ;)

Chuck Norris could :P

No sense of humor. Seriously.

It isn't about having, or not having, a sense of humor. It's just that Hacker News culture prides itself on maintaining a certain decorum to the discussion here... and it doesn't include internet memes, Chuck Norris jokes, or a lot of the other frivolous stuff that's accepted on Reddit, Digg, Slashdot, etc.

It's not that people here are stuffy, or humorless, or anything; we just want HN to be different, and not decay into a festering cesspool of malfeasance like Slashdot or whatever. There are plenty of places one can go to get that kind of stuff on the 'net. Here at HN, it will usually be downvoted mercilessly.

You're right - posts with nothing but a joke aren't really acceptable here. We want to discourage that sort of thing.

> That's strange, about 998 being absent. What follows is definitely nonsense

I had to re-read what the parent poster said to get it. So I thought I'd explain what he means when he says:

> Also, "998" doesn't appear 'in sequence' (it obviously appears as 97[9 98]0 981).

He is saying 998 is missing, as others have observed. He is also saying that if you took the string of digits and did a string search for "998", you'd obviously find those digits together in other places (specifically during the sequence of 979 980 981).

You'd also find them at 799 800 801.

You've got an extra ) on the 'nums = .....'

echo "scale=3000; 1/998001" | bc

In ruby (irb):

require 'bigdecimal'; BigDecimal.new(1).div(998001, 2997)

... and 1/9999999800000001 = .00000000 00000001 00000002 00000003 00000004 00000005 00000006 ... 99999996 99999997 99999999 ...repeating

Basically, the pattern is 1 over some number of 9s, followed by an 8, followed by the same number of 0s, followed by a 1.

So, 1/81, 1/9801, 1/998001, 1/99980001, 1/9999800001, etc.

it's 9x9, 99x99, 999x999, 9999x9999,....

Now for fun figure out why they all just skip N-1. AKA 1/81 = 012345679 not 0123456789.

It's because the it generates .0123456789(10), which in base 10 is actually .0123456790

You can have more fun if you mix up the length of the 9's.

For example, 1/9999/99 = 1/989901 = .00 00 01 01 02 02 03 03 ... 97 97 98 99 00 00 01 01 ...

1/999/9 = 1/8991 = .000 111 222 333 444 555 666 777 889 repeating.

You can see it at Wolfram Alpha http://www.wolframalpha.com/input/?i=1%2F998001

I was searching for some iOS documentation and found this and it's totally ruined my productivity!

Can anyone explain why it repeats in this way, or link to a place that has an explanation?

For x < 1, 1 + 2x + 3x^2 + 4x^3 + ... converges to 1/(1-x)^2. When x = 0.001, you get 1/.999^2 = 1000000/998001 = 1.002003004005...

Here is a more detailed explanation

1---------

If x = 0.001 then the sum x^2 + 2x^3 + 3x^4…. in its decimal places will have all the three digit numbers except the the second last starting with 000,001 and then till 997,999.

As pointed out by someone below,the reason 998 is missing is because after 997998999 the next coefficient is 1000.This overflow 1 will carry over and mess up all the nines to the right until it hits the eight at which point it will make it a 9.Therefore the series will become 997999000001002003... as subsequent overflows keep messing up the last digit to the left.During the addition of the 2000th term a similar thing will happen and the series at that location will become ...997999001002003...... and it will keep losing a term from the beginning in the subsequent 998 repetitions.

More generally if x = 10^-n,n>0 then the sum x^2 + 2x^3 + 3x^4 will have all the n digit numbers starting with (n-zeroes),(n-1 zeroes 1)…except the second last (10^n-2).

2---------

From http://en.wikipedia.org/wiki/Geometric_series

An infinite geometric series converges to a/(1-r) if and only if the absolute value of r is less than 1.

a + ar^2 + ar^3 .... = a/(1-r) if |r|<1 -------> [1]

3---------

1 + 2x + 3x^2.....

= (1) + (x+x) + (x^2+x^2+x^2)....

= (1+x+x^2...) + (x+x^2+x^3...) + ...

= 1/(1-x) + x/(1-x) + (x^2)/(1-x) + .... since x < 1 from [1]

= (1+x+x^2....)/(1-x)

= 1/(1-x)^2 since x < 1 from [1] ---------> [2]

4---------

So the number 0.000001002003004……997999000001002003....

= (x^2 + 2x^3 + 3x^4…..) , x = 0.001

= (x^2) * (1 + 2x + 3x^2 …..)

= (x^2)/((1-x)^2)

= (0.001)^2/(0.999)^2

= ((1/999))^2

= 1/998001

More generally the sum which has all the n digit numbers except (10^n-2) in its decimal places is given by (10^n-1)^(-2).

A quicker proof is to just differentiate. For |r| < 1, we have

    1 + r + r^2 + ... = 1/(1-r)

Differentiate both sides of the equation:

    1 + 2r + 3r^2 + ... = 1/(1-r)^2

Here's a bijective combinatorial proof, which I like best of all. It uses the concept of generating functions. As a caveat, it only shows the equality for formal power series, not analytic power series.

The series 1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r. Then 1/(1-r)^2 is the type of pairs of tuples (the tuples in a pair need not have the same length). A pair of tuples can be mapped to a single tuple by concatenation. Conversely, a single tuple can be split into a pair of tuples. How many ways can this splitting be done if the tuple has length n? In n+1 ways; for example, the 2-tuple (a,b) can be split into the 3 pairs of tuples ((a,b), ()), ((a), (b)) and ((), (a, b)), which are exactly the pairs that concatenate to (a,b). Thus the bijection from 1 + 2r + ... + (n+1) r^n + ... to 1/(1-r)^2 maps an element of (n+1) r^n, which is an index 0 <= k <= n and an n-tuple, to the pair of tuples gotten from splitting that n-tuple at index k.

Thanks ...the differential proof is very insightful and perhaps says something about differentiation itself.

EDIT 1: Forgive my ignorance but can you please elaborate on

1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r ?

EDIT 2: Okay I think I get it.

1 + r + r2 are the terms in the expansion of (1+r)n

It does say something important about differentiation, which shows up very clearly and explicitly in the theory of generating functions and combinatorial species, and relates to my second proof. When you differentiate a type, you get the type of its splittings or what Conor McBride calls its one-hole contexts.

> >1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r ?

r^n is the type of n-tuples with entries in r. When you sum over all n, you get the type of tuples of any length with entries in r.

One thing that might be confusing you is that I'm thinking of r itself as a type, not as a number. You get a number from a type by counting its elements, but a type has much more structure than just its size.

Thanks. That's really cool.

Here's yet another proof. This one uses probability theory.

Let's warm up with a probabilistic proof of

    1 + p + p^2 + ... = 1/(1-p)

in the form

    (1-p)(1 + p + p^2 + ...) = 1

This says that if you have a Bernoulli process with failure probability p and success probability 1-p, you will eventually succeed with probability 1. Indeed, (1-p) p^n is the probability that you will succeed after n failures.

To see this is true (it is certainly intuitively plausible), note that the probability of taking longer than n tries is p^n, which goes to zero as n goes to infinity.

We can apply the same kind of reasoning to

    (1-p)^2 (1 + 2p + 3p^2 + ...) = 1

As before, we have a process with failure probability p and success probability p-1. However, rather than stopping after the first success, we will continue until we have two successes. Now take a look at the terms of the equation's left-hand side:

    (1-p)^2 (n+1) p^n

This is the probability that we will have gotten 2 successes (and hence n failures) after n+2 steps. The second success must always be the final trial, so there are n+1 possible positions for the first success. That explains the factor of n+1.

With that understood, the equation simply says that we will eventually get 2 successes with probability 1. To see why, note that the probability of never getting any successes in n tries is p^n as before, which tends to zero. So we will eventually get at least one success with probability 1. But once we have that first success, getting the second success is just our first problem repeated, so we know that happens eventually with probability 1.

This proof technique generalizes easily. If we keep trying until we have 3 successes, we get a factor of C(n+2, 2) = (n+2)(n+1)/2 for the number of ways the first 2 successes can be placed before the third and final success when there are n failures and 3 successes. We show that a first success occurs eventually with probability 1 as before, which reduces the problem to getting two subsequent successes, a problem we already solved.

You can see this yields a proof by induction for this whole class of series identities, but it's not of those unenlightening proofs by induction that shows you something is true but does not tell you why.

Here's a similar derivation (assuming |x| < 1), applying the geometric summation twice in the last two steps, but presented a bit more visually:

    x + 2x^2 + 3x^3 + 4x^2..

    =

    x +  x^2 +  x^3 + x^4 + ...
      +  x^2 +  x^3 + x^4 + ...
             +  x^3 + x^4 + ...
                    + x^4 + ...

    = sum i from 0 to infinity (sum j=i to infinity (x^j)) 

    = sum i from 0 to infinity ((x^i)/(1-x))

    = 1/(1-x)^2

  ;Here is my version in Common Lisp
  ;Supply your own flatten function
  ;or borrow one from let-over-lambda or something
  ;http://letoverlambda.com/lol.lisp

  (defun long-div (dividend divisor depth)
    (cond
     ((> depth 0)
      (flatten (list
                (truncate (/ dividend divisor))
                (long-div (* 10 (mod dividend divisor))     
                 divisor (- depth 1)))))
     (t ())))

The source with real (readable) text, without annoying animation:

http://www.futilitycloset.com/2012/01/08/math-notes-76/

So we're missing 998 here in actuality ?

Yes. And 1/9801 skips 98.

Thanks for posting. I'm trying to keep a collection of these type of things so that when she's ready, it'll be another tool to get/keep my daughter excited about math.

Care to share? Would be handy to have for my daughter... :)

I'll start a post when I have enough worth sharing. She's 4 now and we're still working with basic math. I've found a few books that incorporate math that she's enjoyed; right now we're halfway through The Phantom Tollbooth. Milo just left Dictionopolis so we're headed to Digitopolis shortly...

Make sure you show her Gauss’s trick for summing arithmetic series.

There's no 998 (and it's not a rounding issue)!

    ... 995 996 997 999

And even the suggested 1/9801 for two digits produces no 98

    ... 95 96 97 99 00 01 02 ...

And extrapolating it to one digit, 1/81 gives

    0.012345679012345679...

Again, the 100 overflows to the 99. This makes the 99 a 100 and then that overflows again and the 98 turns to a 99.

you could always do 1/99980001 - that would have a 0998

But it would lack a 9998.

then i suppose we need 1/9999800001 !

But it would lack... just kidding.

Another way to get the real consecutive numbers is to make a rest so we avoid that annoying increment at the end:

1/998001 - 1e-1000

It's because the 1000 will end up adding one to the 999 which becomes 1000 which adds one to 998.

Yes, that is funky.

  def long_div(x,y,N=10):
    """Given two integers x and y, return us the N digits of x/y."""
    #First work out the integer part
    x = int(x)
    divisor = y = int(y)
    quotients = [x/y]
    dividend = x % y
    for digit in range(N):
      dividend *= 10
      quotient = dividend/divisor
      dividend = dividend%divisor
      quotients.append(quotient)
  
    return quotients
  
  def pretty_print(quotients, G=3):
    """Pretty print quotients by grouping digits by 3."""
    strp = ''
    cnt = 1
    for n in quotients[1:]:
      strp += str(n)
      cnt +=1
      if cnt > G:
        print strp
        strp = ''
        cnt = 1
  
  
  quotients = long_div(1,998001,N=3000)
  pretty_print(quotients,G=3)

You can find the Catalan numbers buy computing 500,000,000,000 - Sqrt(500,000,000,000*500,000,000,000 - 1)....

http://people.csail.mit.edu/devadas/numerics_demo/chord.html

For an explanation better than I can provide of what they are and how it works, see 6.006 lecture 11 notes!

http://courses.csail.mit.edu/6.006/fall11/lectures/lecture11...

Some fun that can fit on a poket calculator:

12345679 * 9 = 111111111

12345679 * 18 = 222222222

12345679 * 27 = 333333333

12345679 * 36 = 444444444

12345679 * 45 = 555555555

12345679 * 54 = 666666666

12345679 * 63 = 777777777

12345679 * 72 = 888888888

12345679 * 81 = 999999999

12345679 * 999999999 = 12345678987654321

And this too: 111111111111111111111111111 / 9 = 12345679012345679012345679

The way I was introduced to this was as a math trick: Pick a number 1-9, multiply by 9, then 12345679, and you get a string of whatever number you picked.

Also, pick any three-digit number, multiply by 7, 11, and 13 (or 1001), and you get your three-digit number repeated twice.

My productivity for today went downhill! :)

Love the trick with how this can be done via differentiating the equation:

1 + r + r^2 + ... = 1/(1-r)

Slightly off-topic, but it bugs me that the article feels obliged to contain a picture of the number. Firstly, why the hell would you want to display plain text as a picture? Secondly, if I click through to the source, I get a slightly better picture. Did IHC take a photo of the original website with their phone camera and upload it? Mind is boggling. Encouraged by the better quality picture on geekosystem I decided to click through to THEIR source. And there's a plaintext version. Kudos to <a href="http://www.futilitycloset.com/2012/01/08/math-notes-76/<...; for having a modicum of common sense.

This reminded me of a fun fact from an old professor's paper: 1/99007599 has a binary expansion of period 48993900.

http://www.math.ucsb.edu/~agboola/teaching/2005/winter/old-1...

Also, 1/4999 yields the sequence of square numbers.

It's really powers of 2, not square numbers. That is, 2^x, not x^2.

For all squares, http://m.wolframalpha.com/input/?i=100010000%2F999700029999&... 100010000/999700029999 Tack on extra 0s and 9s to allocate more digits per square.

Incidentally, understanding how this works is helpful to programmers. If you know why this happens, you'll know why you can't write:

   double x = 0.1;

and get something that works.

> you can't write ... and get something that works.

That's taking things a bit far, isn't it? Sure, you can't exactly express 0.1 as a double - but you can get many things that work really well using the approximation.

What I meant to say was, "you can't expect something with a terminating representation in base 10 to always have a terminating representation in base 2". When you play with these cases in base 10, it builds intuition that can be applied to base 2 math.

Is there a number f(n) such that 1/f(n) yields all n-digit numbers, and is there a formula f to generate them?

You may play with the Champernowne constant :

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

The link is blocked at my workplace. I really don't understand how their filter system works.

Same here! For the category 'pornography'...

We have websense here and it too seems to block perfectly benign things with bogus reasons. This link is categorized as adult content.

IHC is far from benign. They've moved the most explicit stuff to a different domain, but the site is still NSFW, generally.

It's clearly geek porn.

Same here

It has the word Boobies in one of the comments.

Ha ha, mine too. It says it's "adult content".

There's a special place in hell for business owners who inflict Websense or any other method of censoring content on their own employees.

If you don't trust me to use it, don't give me a computer, or an internet connection.

I work in information security for a company that uses content filtering, let me explain the standard reasoning (with the disclaimer that I don't speak for my company or yours, etc).

Your work computer and Internet access is governed by a policy that all employees have to sign. Among other things, this policy says that your time at work is supposed to be used doing work-related things. The only way to enforce this policy is to filter out things that are not business-related. This policy at many companies is usually pretty lax and ad-hoc, really only blocking categories of sites, not individual sites themselves. The categories usually include pornography/extreme content, games, etc.

Other categories are blocked due to the fear of data leakage. Google Docs/Dropbox is common for this. The last thing you want your employees doing is putting sensitive information onto the Internet where competitors or ill-wishers can view them. The goal here is to make it more difficult to share, not impossible (knowing that email/removable media is still an option).

We want you to do your work. We understand there are times when you need Internet access. But no, we don't trust you, because you're on Hacker News right now (as am I). If the world were a better place, we could trust the security of the company to the users/employees. You and I both know this isn't true. While you're at work, your company owns your time under the terms of your contract. It's not censorship because private organizations have no responsibility to ensure your freedoms.

TL;DR try complaining to your CIO that you can't get to iheartchaos.com. S/He'll tell you to get back to work.

It has 'Fun' in the header ;)

Set up a recursion: 1000x - .001 (repeating) = x

The .001 repeating = 1/999, simplify, voila.

What happens after 999? It wraps around back to 000! This is cool.

Well, being a rational number, it has to wrap around somewhere. And since 999 + 001 == 000 (with the caveats for carries that people have explained elsewhere), it makes sense for it to wrap around at that point.

1. Take 1 as a divisor

2. Choosing a suitable dividend

3. Calculate quotient

4. Instant interesting observation!

1/49 is "almost" surprising. 0.0204081632

Try taking the square root of it

That's nothing! 6922251 * 8 on a calculator spells my ex's nickname....

Hmm. http://www.reddit.com/r/math/comments/oiv7s/cool_fraction/

Did you read on Egyptian fractions? http://en.wikipedia.org/wiki/Egyptian_fraction

Reply on news.ycombinator.com