Tuesday, April 7, 2009

Prime Time

I was thinking about the possibility of defining a subset of the naturals containing numbers whose digits (appropriately grouped) are its own prime factorization. For example, take 32. It would be a number of this kind if 32 = (3)(2). (Of course it's not.) Are there any members of this set? Well, every prime number is trivially a member, 7 = 7, 11 = 11. The interesting question is, does this set have any composite members? I haven't been able to think of one yet.

I quickly checked the numbers less than 100 and there aren't any examples there. The only single digit numbers in this set are the primes. Consider the double digit numbers, 10 through 19. Let A be a digit, 0 through 9, if 1A = (1)(A), then 1A = A. Since no two digit number is equivalent to a one digit number, this isn't possible. (Note, 1A does not mean 1*A.) What about the numbers 20-29? If 2A = (2)(A), then the most (2)(A) could be is 14, because the most A could be is 7. But we know 2A is in the 20's so this is not possible. Any number in the 30's, 50's, and 70's will have the same problem. Any number 4A can only be grouped (4A) because 4 is not prime. So only the boring numbers (primes) in the 40's make it into the set. Same is true for the 60's, 80's, and 90's. What can we conclude? There is no composite example less than 100.

What about 3 digit numbers? We can start to make arguments by thinking of the grouping possibilities. If ABC is a three digit number, then we could group (A)(B)(C), (AB)(C), (A)(BC). Your mission: find a composite number in this set, or prove that there aren't any.

pic by kingfal


sumidiot said...

Interesting question! I've been vaguely trying to learn python recently, and thought this would be a good exercise. The loop I wrote wasn't particularly clever, but didn't turn up any results. Neither did the extension to 4 digits. Guess that means it's time to try to prove I didn't miss any :)

It seems, to me, pretty reasonable that there aren't any composites in this set. The products you look at never seem to be big enough.

HM said...

I know what you mean the products always seem to turn out too low. To illustrate that and eliminate some possibilities, any number of 7 or more digits cannot have all its primes grouped in single digits. At most a number with seven digits and grouped as single digit primes could be the product of seven sevens, or 7^7, which is 823,543 a six digit number. Look at the progression of 7's
7^5= 16,807
7^6 = 117,649
7^7 = 823,543
Each time the exponent increases from n to n+1, there is less real estate in the n+1 digit numbers. n = 3, only 27% of the numbers are even possibilities. When n=4, around 16%; n = 5, 8% and so on...

Looking at it more analytically and remembering that if we add one to the floor of log (x) we get the number of digits in x, it is true for any single digit prime p, we must have log(p^n)>n-1. In the previous example p=7 and the inequality is not satisfied for all n>=7. It is a little late for me, so I might have slopped this up, but in general I think for any prime of b digits, log(p^n)>n/b-1. 97 is the highest two digit prime. I wonder for what value of n the inequality will fail? That's all I have tonight.

sumidiot said...

I guess this problem has been kicking around in the back of my head long enough it now seems easy (I wish that would happen with my thesis!).

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.

HM said...

Really clever! I love this and you even got a more general fact. Sorry it took me so long to look this over.