Practical Numbers and Egyptian Fractions

Practical Numbers and Egyptian Fractions

Practical numbers are natural numbers where each natural number small than them can be written as the sum of the original numbers divisors. For example, the number 12 is practical because it has the divisors 1, 2, 3, 4, 6 and 12. From these we can make 1 (by itself), 2, 3, 4, 1+4=5, 6, 6+1=7, 6+2=8, 6+1+2=9, 6+4=10 and 6+4+1=11.

The practical numbers start off abundant, but quickly trail off into rarity as you move along the number line. In some ways they are reminiscent of primes numbers as they are the building blocks of arithmetic, like the primes are the building blocks of multiplication. The sequence begins: 1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144...

Let's look at some properties. First you might notice that all of these numbers are even apart from 1, which feels like the opposite of primes. No odd number can be because a factor of 2 is needed to have a sum of 2. Further, notice that any power of 2 must be in the list because the sums of powers of 2 span the natural numbers (if they didn't then binary wouldn't work). This guarantees that we must have an infinite number of practical numbers straight away. Further, any perfect number is also practical.

To briefly introduce another concept: Egyptian Fractions are fractions that are expressed as the sum of unitary fractions (fractions with a numerator of 1). For example instead of writing 2/13, the Egyptians would write 1/8+1/52+1/104.

These are often hard to work out and the Egyptians had a whole bag of tricks for working them out. Simply taking the biggest chunk possible out of the target fraction is often inefficient (the so called Greedy Algorithm); for example 2/25 can be written as:

Using the Greedy Algorithm (developed by Fibonacci)

Using the Greedy Algorithm (developed by Fibonacci)

Or as:  

Efficient

Efficient

However the Greedy Algorithm will always terminate in a series of finite length.

The reason I have brought up Egyptian Fractions is because practical numbers have a particular use for them. Numbers which have a denominator which is practical can always be written in Egyptian form trivially, for example: 13/20=10/20+2/20+1/20=1/2+1/10+1/20. This makes practical numbers, well, rather practical. The number of terms you will need for writing out x/y is of the order log(y) so it is efficient.

Going further with this

5 Ball Flash

5 Ball Flash

Not Enough Information?

Not Enough Information?