The composite space between prime products

April 2, 2009 By

Previously, I gave you a puzzle on prime numbers.

Let F(n) be (1st prime) * (2nd prime) * … * (nth prime)
The question was to describe the group of numbers between 2 and F(n)-1 that F(n) cannot divide.

And the answer is… all composite numbers between 2 and F(n)-1 with repeated prime factors. Hmm… I guess that doesn’t quite fit the “as plain an English as possible”, but it is concise.

For example, F(n) cannot divide 4, because 4 = 2*2 (repeated 2).
But F(n) divides 6, because 6 = 2*3 (no repeated primes).
F(n) cannot divide 18, because 18 = 2*3*3 (repeated 3).

The proof (sort of)

If a number A in [ 2, F(n)-1 ), is prime, then F(n) divides A by definition because F(n) is a product of primes.

Let A be a composite number in [ 2, F(n)-1 ) with no repeated prime factors. Then F(n) divides A because F(n) is a product of primes where the prime factors form a superset of the prime factors of A.

Can you complete the proof?

Let A be a composite number in [ 2, F(n)-1 ) with repeated prime factors. Let p be a repeated prime.

...

[Can you complete the proof?]

Filed Under: Mathematics Tagged With: , , ,

Factorials, prime numbers and a puzzle

March 26, 2009 By

There is this interesting math tidbit about composite numbers and factorials by Ned Batchelder. Now prime numbers never appear consecutively (except for 2 and 3). Ned then answered this question: how many composites can appear consecutively?

His explanation involves the use of factorials, and you can read about it using the link above. His explanation also gave me something to think about…

Now the factorial of n, denoted by n! is
1*2*3*4* … *(n-1)*n
which is a product of 1 through n.

Let’s define a function F such that F(n) is the product of
(1st prime)*(2nd prime)* … * (nth prime)

For example, the first few prime numbers are 2, 3, 5, 7, 11, 13. So
F(1)=2,
F(2)=2*3=6, and
F(5)=2*3*5*7*11=2310.
This is different from factorial primes (I was actually going to name this special function “prime factorial”).

Now, n! is divisible by 2, n! is divisible by 3 and n! is divisible by 4.
F(n) is divisible by 2, F(n) is divisible by 3, but F(n) is not divisible by 4!

My question: Describe the group of numbers where F(n) cannot divide, in as plain an English as possible. This group of numbers will necessarily be between 2 and F(n)-1.

Your knee-jerk answer could be “all composite numbers between 2 and F(n)-1!”. Ahh, but F(n) is divisible by 10, and 10 is a composite number (assumption, n is a fairly large number, say greater than 5). This puzzle should be easy to figure out. Articulation of the solution into a couple of sentences might be harder…

[Vincent is currently away on vacation. He asked me, the blog, to take over for a while. Using a proprietary algorithm involving language semantics and neural networks (written by me), I came up with the blog post you've just read. It even seems coherent! I mean, uh, of course it makes sense. Oh, the things I do for my master... He'd better come back with lots of pictures for me to post, or he and I are going to have words...]

Filed Under: Mathematics Tagged With: , , ,

You are debugging with the wrong database

November 17, 2008 By

I feel an urge to tell a story first. So here goes…

Once upon a time, in a far away land, a young prince lived in a shining castle. Although he had everything his heart desired, he was spoilt, selfish and unkind.

But then, one winter’s night, an old beggar woman came to the castle and offered him a single rose, in return for shelter from the bitter cold. Repulsed by her haggard appearance, the prince sneered at the gift, and turned the old woman away. But she warned him, not to be deceived by appearances, for beauty is found within…

Oops, wrong story. Let me try again.

Once upon a time…

In the Far East, there was an adventurer by the name of Wen Sen* (wuhn suhn). He wandered many lands, climbed many hills and even walked on glaciers. But he’s a scholar at heart, and so he set out in search of knowledge.

Mayan ruins explorer
[image by Steve Geer]

Wen Sen wanted to find out more about a particular village with strange inhabitants. After travelling many days on foot, he finally reached the village’s gates. Despite his raging thirst, his thirst for knowledge was greater. So he accosted the first villager with

Do you think it’s a coincidence that the first 3 prime numbers are also part of the Fibonacci sequence**?

Getting a blank stare, he leapt to the next villager with

What are your thoughts on the first 3 odd prime numbers forming 2 pairs of twin primes***?

Despite his fervour, Wen Sen didn’t get anything out of the villlagers. He even tried indecent questions such as “Are you divisible by 17?”. Dejected, he slumped at a corner of a building, thoroughly miserable.

An elderly woman approached him and asked,
“Are you alright, young man?”
“I’m fine. I just haven’t found what I am looking for,” Wen Sen sighed.
“Well, what are you looking for?” she asked.
“Your village is supposed to hold the key to unlocking the secrets of prime numbers,” Wen Sen breathed. “But everyone seems confused. What am I doing wrong?“.

“Oh,” the elderly woman’s eyebrows lifted. “You must be referring to our neighbouring Village 2357. This is Village 4680.”

The real story…

Well, I can’t remember the details. All I remembered was, I was testing my code, and the results on the web page didn’t match the results in the database.

I triple checked my code. I retrieved the results from the database to verify the data. Everything was in order. But why wasn’t the web page showing the correct set of data?

I forgot what triggered it, but I suddenly realised that I was connecting to the wrong database. I was working with databases in development, testing and production environments then. And I forgot to change a configuration setting.

From then on, I was careful about making sure that I’m in the correct database before I do anything else.

* Wen Sen are the closest Chinese characters to my name Vincent. It means “knowledge forest” or “culture forest”, depending on context. And depending on the Chinese characters used, of course. And no, my actual Chinese name isn’t Wen Sen.

** The first 3 primes are 2, 3 and 5. The Fibonacci sequence is 1, 1, 2, 3, 5, 8 and so on.

*** 3 and 5 form one pair of twin primes. 5 and 7 form another.

Filed Under: Programming Tagged With: , ,