CodeWords
Code, in words.
Wednesday, October 26, 2011
Transition to New Site
Wednesday, October 5, 2011
Steve Jobs, Rest in Peace
Today a great entrepreneur, one of the great American capitalists, Steve Jobs, passed away at the rather young age of 56. As others have said, we are all a bit poorer for it.
I didn't always agree with his style, I wasn't always a fan of his company's products, and I certainly didn't like the personality cult that surrounded him, but I have great respect for the man who believed in what he did, thought big, sought to empower people, and did it with style and aesthetics. He is an inspiration to us all.
Monday, August 29, 2011
Finding Files with PowerShell, Part 2
This version (see Finding Files with PowerShell) gives the full path of the items:
Get-ChildItem -Recurse -Filter *some*pattern* | ForEach-Object -Process { $_.FullName } |
Tuesday, August 16, 2011
Finding Files with PowerShell
I miss the UNIX find
command in Windows. I could get it with Cygwin or GNUWin32, but that requires littering my machine with extra stuff. So, PowerShell to the rescue:
ls -Recurse -Filter *some*pattern* | ft directory, name |
Friday, July 15, 2011
Monday, June 20, 2011
How Likely Are You to Be Dealt a Royal Flush?
A royal flush consists of a certain five cards of the same suit. Assume we are dealt one of these cards. Then the suit is determined, and we now need the remaining four cards of that suit. So, let's take the probability of being dealt one of the certain five cards (10, J, Q, K, A) of any suit. Since there are five such cards per suit, and there are four suits (the set of suits is {♢,♡,♣,♠}), then we can get any one of those cards to start building a royal flush. Therefore, the probability of getting a starting card is P(starting card)=2052.
Saturday, June 18, 2011
Calculating the Number of Trailing Zeros in a Factorial
The factorial function, denoted n!, where n∈Z∗, is defined as follows: n!={1if n=0,n(n−1)!otherwise.
Let us define a function z:N→N that accepts an argument n that yields the number of trailing zeros in n!. So, using our two examples above, we know that z(10)=2 and z(20)=4. Now, what is z(100)?
An integer a has k trailing zeros iff a=b⋅10k for some integer b. Now, the prime factors of 10 are 2 and 5. So, what if we consider the prime factors of each factor in a factorial product? For example, consider the first six terms (after 1) of 100! and their prime factors. We omit 1 because of its idempotence: 2=23=34=225=56=2⋅37=7
You might have noticed from our example of 7! that there are four 2s and only one 5. Consider that there are n/2 even factors in n!—that is, every other integer factor of n!, starting at 2, is even. So there are n/2 even factors. Each of these has at least one 2 in its prime factorization, and many of them have more than one. Now consider how many factors of 5 there are in n!: there are, in fact, n/5. So, we can see that, for every 5 we find in n!, there is a 2 we can match with it. This suggests that we only need count the 5s and not the pairs of 2 and 5.
This now suggests an algorithm, presented here in Java:
public class Solution { | |
public static void main(String[] args) { | |
System.out.println(countTrailingZerosOfFactorial(100)); | |
} | |
private static final int countTrailingZerosOfFactorial(final int n) { | |
int count = 0; | |
for (int factor = 5; factor <= n; factor += 5) | |
count += countFives(factor); | |
return count; | |
} | |
private static final int countFives(int factor) { | |
if (!divides(5, factor)) | |
return 0; | |
return 1 + countFives(factor / 5); | |
} | |
private static final boolean divides(final int d, final int n) { | |
return n % d == 0; | |
} | |
} |
Using this algorithm, we find that z(100)=24.