Explaining the bizarre pattern in making change for a googol dollars (infinite generating functions)

Comments · 846

• AL

  @AlRoderick · 5 years ago

  &quot;We started with an infinite sum so let&apos;s count our blessings&quot;<br><br>Well it does seem like there are countably many...

  94

• MA

  @Mathologer · 5 years ago

  A &quot;short&quot; video for a change, &quot;only&quot; 30 minutes long :)

  427

• JO

  @johnchessant3012 · 5 years ago

  <a href="https://www.youtube.com/watch?v=VLbePGBOVeg&amp;t=1275">21:15</a> &quot;Oh wow, this formula implies that the coefficients for 5n, 5n+1, 5n+2, 5n+3, 5n+4 must be the same!&quot;<br><b>thinks about original problem for a minute</b><br>... Oh.

  33

• AL

  @alimymir · 5 years ago

  quick answer: a lot

  143

• ME

  @mebamme · 5 years ago (edited)

  This video makes a lot of cents.

  258

• KU

  @KusacUK · 5 years ago

  As we’re all home-schooling at the moment, the school is sending challenge sheets out to all the kids. The final question on my daughter’s maths one was “how many different ways can you make £3.10 using coins”. <br><br>She’s 7 years old...<br><br>I just changed the question to “think of a few ways you could” instead, because even I didn’t know how to solve it. But now I do! I don’t think I’ll be teaching this to her yet though.

  188

• SU

  @subhasish-m · 5 years ago

  The power of 2 coins can make any amount in exactly one way! (binary representations :))

  115

• TH

  @thedoublehelix5661 · 5 years ago

  I already knew about generating functions, but seeing that automated algebra and the reason for all those 3s and 0s was seriously amazing

  35

• TO

  @tobiasgorgen7592 · 5 years ago (edited)

  Last time i was this early, The sum of all natural numbers still equaled infinity

  176

• XU

  @Xubono · 5 years ago

  Some of us will recognise Donald Knuth as the creator of the typesetting language TeX. For that alone, he has been responsible for the professional quality appearance of thousands of PhD theses.

  74

• SY

  @sypeeoui · 5 years ago

  I studied the infinite generating function for high school math competitions. They are very useful in combinatorics problem!

  74

• MA

  @maxwchase · 5 years ago (edited)

  Programming challenge (did this around <a href="https://www.youtube.com/watch?v=VLbePGBOVeg&amp;t=821">13:41</a>): because all of the coins evenly divide a dollar, it must be the case that a sum of coins to a multiple of a dollar can be separated into some groups of coins in which no single denomination adds up to a dollar, and the rest, in which each single denomination adds up to a multiple of a dollar. The former cases can be enumerated by doing the product trick without the exponent of 100, and taking the coefficient of each exponent divisible by 100, including 0. There are ways to make change like this for zero through four dollars inclusive. This gives us one part of the solution. The other part is to determine how many ways the remainder could be made. But this is a simpler problem, because it&apos;s equivalent to asking &quot;How many ways are there to add five (number of denominations - 1) boundaries to a set of a given size&quot; which is equivalent to asking for (size of set + 5) choose 5, which can be hard-coded as a sequence of multiplications followed by a division. (I could have tried expanding out the polynomial explicitly, but that sounds like effort).<br><br>So, the final answer is to, for each amount of dollars that can be made without using a dollar&apos;s worth of a single denomination, multiply that by the number of combinations for the remaining dollars.<br><br>I coded this up in Python, and it&apos;s pretty fast. I just started added zeroes to the exponent on the ten, and it was pretty acceptable performance up to 2 * 10 ^ 100,000. I&apos;ll post the value for 2 * 10 ^ 1,000,000 when it finishes, because that&apos;s much slower. Okay, yeah, that took a few minutes. One sec... Oh geez, it overflowed the buffer.<br><br>I&apos;m not pasting five million digits in here. See https://pastebin.com/MA2a9p3R<br><br>EDIT: At <a href="https://www.youtube.com/watch?v=VLbePGBOVeg&amp;t=1382">23:02</a> I&apos;m seeing the same coefficients in the center row that I had my program calculate for &quot;ways to make dollars without a single denomination adding up to a dollar&quot; So I guess this is going in the same direction.

  13