Subscribe to:
Post Comments (Atom)
skip to main |
skip to sidebar
Feedback Wanted!
- Is the College Mathline television program beneficial to you? If so we want to hear about it! Leave comments regarding the program.
Math in the real world
- Watch the blog posts for links and additional information about mathematics in the real world as shown on the program.
9 comments:
I love the show!
Mathline really helps me with my homework and the "real world" examples are cool.
I'm long out of college but I love to watch the show, just to see if I can get to the solution faster than Mathman Dan (usually, I don't -- it's amazing the calculus I've managed to forget over the last 40 years!).
The contest was fun -- but I admit I cheated -- I wrote a computer program and then worked backwards to the algorithm from the numerical solution.
But my main reason for posting is to let you know that "comments" don't work under Firefox. Someone out to check that out.
Thank you for your comments, and we don't consider your method for the contest cheating! We'll call it "field research." That's pretty cool you wrote a program for it. You should call in and officially win the contest if you believe you have the correct answer.
We tested comments using Firefox and it seemed to work okay, are you using Windows or Mac OS? We will try to figure out what is going on...
Are you in need of any more tutors or any other help for the show? I recently graduated college with a B.S. in Math and would like to put my skills to use. Please let me know what I can do or who I should contact if I can help with anything.
Thanks.
Hello, after next week's episode we will be on break for the summer. We will be back in September however. Send us an email at mathline@palomar.edu, we may indeed need some help then!
Regarding the contest, I see someone's found the solution so I'll go ahead and post my computer program solution.
A couple of things to note: the program is in a variant of a string processing language called "awk" (it's not named for the sound you make when you first encounter its syntax but for the programmers who invented it, Aho, Weinberger, and Kernighan, all legendary computer scientists). See the Wikipedia article for more information.
I'm sure any PERL, python, or java hackers could come up with something similar.
Here's the code:
#!/usr/local/bin/gawk -f
BEGIN {
m = 100000; # The number to count to
N = int( ( log( m ) / log( 10 ) ) + 0.5 );
print N; # Print the order of magnitude
zeroes = 0;
last0 = 0;
# first pass -- count all the zeroes.
for ( i = 1; i <= m; i++ ) {
iz = i + "";
gsub( /[1-9]/, "", iz );
zeroes += length( iz );
if ( i > 1 )
for ( k = 1; k <= m; k *= 10 )
if ( k == i ) {
z = zeroes - last0;
printf "%7d %7d %7d\n", i, zeroes, z;
last0 = zeroes;
} else if ( k > i )
break;
}
# Second pass, calculate the empirical solution
sum = 0;
for ( i = 1; i <= N; i++ ) {
term = 1 + ( ( 9 * ( i - 1 ) ) * pow( 10, i - 2 ) );
sum += term;
printf "%d %6d %6d\n", i, term, sum;
}
# Third pass, use combinatorics
sum = 0;
for ( n = 1; n <= N; n++ ) {
term = 0;
for ( i = 0; i < n; i++ ) {
ta = ( ( n - 1 ) - i ) * pow( 9, i + 1 );
tb = choose( n - 1, i );
term += ta * tb;
}
term++;
sum += term;
printf "%d %6d %6d\n", n, term, sum;
}
}
function pow( n, i )
{
return exp( log( n ) * i );
}
function choose( a, b )
{
return factorial( a ) / ( factorial( b ) * factorial( a - b ) );
}
function factorial( a, r, i )
{
r = 1;
if ( a > 0 )
for ( i = 2; i <= a; i++ )
r *= i;
return r;
}
Sorry about the lack of indentation but blogger apparently eats tabs and spaces.
As you can see I actually solve the problem three different ways. First, I use a brute force solution and simply count the zeroes. The only interesting thing in that is the way I count the zeroes. Since "awk" (or, actually, the variant I'm using, called "gawk") is a string processing language, everything, even the result of numerical computations, is a string. The "gawk" built-in function "gsub()", which stands for "global substitution", simply eliminates all the characters (remember, we're processing text strings) that are not "0". I then just count the number of characters which are left over.
As I said, brute force.
The second solution is based upon examining the results of the brute force solution and working backwards to a function.
It's hard to show in ASCII text but the summation is
zeroes = sigma(i = 1:N)[ 1 + ( 9 * ( i - 1) ) * 10^(i - 1)]
where sigma is the summation symbol, N is the number of digits (6 in the case of 100000), and i is the summation index. ^ is the exponentiation or power operation.
The third solution, which I came up with after thinking about the problem for a while, is to use some ideas from combinatorics or permutations in first year statistics.
The idea, basically, is to break the problem down into N smaller problems, counting from 1 to 9, 10 to 99, 100 to 999, etc.
I won't bore you with the reasoning but basically the function is
zeroes = sigma(n=1:N)[sigma(i=0:n)[( n - 1 ) - i ) * 9^(i + 1) * choose( n - 1, i )]]
Here "choose" is the binomial coefficient or the function
nCk = n! / ( ( k! * ( n - k )! )
I think I heard MathMan Dan call it "choose" on the show so that's what I called.
Sorry for (a) the lengthy post and (b) for the ugly formatting.
By the way, if your students haven't discovered the Wolfram Research web site "Mathworld", I heartily recommend it. There's a lot of really wonderful stuff there. If there was a Nobel Prize in cool, Eric Weisstein should win it.
Regarding the browser -- I'm running Firefox on a Linux box. It may have been something transient or something in my configuration since it seems to be working now.
Thanks for posting your code. I haven't programmed anything in a long while but I know enough to follow the logic. It's nice to three different methods (which all give the same result!). Your third method is the way I approached it myself. I agree about MathWorld, I refer to it often.
I've been watching and taping the show since the beginning. I love it!
AM
Post a Comment