Thursday, July 9, 2009

Geek of The Week: Nick Hamblet

Not sure whether you have been following the comments on Prime Time? But, Nick, known to us in the comments as SumIdiot, came up with a nice proof showing that it's impossible to group the digits of a number n in primes so that you wind up with the prime factorization of that number. For example, the digits of 241 can be grouped as (2)(41), but 2 and 41 aren't the prime factors of 241. Another example, 573 could be grouped (5)(7)(3), but again the product (5)(7)(3) is not equal to 573. Enough.

What Nick actually showed was the larger result: any grouping of a number's digits, prime or not, will always have a product strictly less than the number itself. How did he do it? Here's his proof from the comments.
Given d+1 integers between 0 and 9, called a_0, ... a_d, let me write A=(a_d a_{d-1} ... a_0) for the number \sum_{i=0}^{d}a_i 10^i.

Consider the product obtained by splitting this digit string into (a_d ... a_s)(a_{s-1} ... a_0). So this is a product of a d-s+1 digit number and an s digit number (take s >= 1).

Now A=(a_d ... a_0) = 10^s(a_d ... a_s) + (a_{s-1} ... a_0) is at least as big as 10^s(a_d ... a_s). However, since 10^s is strictly bigger than (a_{s-1} ... a_0), A >= (a_d ... a_s)10^s > (a_d ... a_s)(a_{s-1} ... a_0).

So any integer is bigger than the product obtained by splitting it's decimal string into two pieces. It seems the general statement, splitting the decimal string into any number of pieces, follows by induction.
Clever! Nick has also given me the chance to break in a blogroll (Only on the new domain). He runs a real nice blog Sumidiot here.

**Reminder YofX will be moving to in 11 days on 7/20**

No comments: