Polite Numbers and their Relationship to Prime Numbers
Author: Rayan Ivaturi
Email: irayan@gmail.com
1.
Introduction
Prime numbers and
their properties are being discussed mainly in the multiplicative number
theory, and in fact prime numbers have dominated that branch of number theory
always.
Additive number
theory, though primarily discusses the abelian groups and their properties, is
an interesting branch of number theory for studying the number properties of polite numbers, Fibonacci series etc.
This paper discusses
about polite numbers, their properties and mainly their relationship to prime
numbers.
2.
Polite Numbers and their Representation
In Additive number
theory, polite numbers are integers, which can be represented as sum of two or
more consecutive positive integers.
For an example, take
the set of first 4 positive integers
{1, 2, 3, 4}
Following are all
the possible polite numbers combinations, and their representations that can be
generated.
1+2+3+4 =10
2+3+4 = 9
3+4 = 7
1+2+3 = 6
2+3 = 5
1+2 = 3
3.
Representing Odd Numbers as Polite Numbers
As every odd integer
can be represented as (2n-1) for some positive integer n, it can also be represented as the sum of
consecutive integers: (n-1) + n
So every odd integer
can be represented as a sum of two consecutive numbers, and hence as a polite
number.
In fact every
positive integer which is not a power of 2, can be expressed as a polite
number, but is beyond the scope of this paper.
4.
Number of Polite Numbers that can be generated from the Set
of Natural Numbers {1.. n}
The total number
of polite numbers that can be generated from the set of positive integers
{1..n} are: n(n-1)/2
A simple proof for
it is as follows:
All the distinct
polite number combinations that can be formed containing the number n are: 1+2+3+…+n, 2+3+…+n, … up to
(n-1)+n, which are (n-1) in count.
All the distinct
polite number combinations that can be formed containing the number (n-1) are: 1+2+3+…+(n-1), 2+3+…+(n-1),
… up to (n-2)+(n-1), which are (n-2) in count, and so on till there will only
be two consecutive numbers that are in the combination, which forms a single
polite number.
So the total number
of polite numbers that can be generated from the set of positive integers {1..n}
are: (n-1)+(n-2)+…+1
which is nothing but
the sum of first (n-1) positive numbers:
= (n-1)(n-1+1) / 2 =
n(n-1)/2
5.
Multiplicative Representation of Polite Numbers
n Polite Numbers
--- --------------------
01 03 -> 1 Table with Odd Numbers from 3
02 05 06 -> 3 Table
from 2
03 07 09 10 -> 2 Table with Odd Numbers from 5
04 09 12 14 15
-> 5 Table from 3
05 11 15 18 20 21 -> 3 Table with Odd Numbers from 7
06 13 18 22 25 27 28
-> 7 Table from 4
07 15 21 26 30 33 35 36 -> 4 Table with Odd Numbers from 9
08 17 24 30 35 39 42 44 45
-> 9 Table from 5
09 19 27 34 40 45 49 52 54 55 -> 5 Table with Odd Numbers from 11
10 21 30 38 45 51 56 60 63 65 66
-> 11 Table from 6
From the above
table, it can be observed that, polite numbers form a triangle of numbers, with
each column of polite numbers forming up a multiplication table with a definite
pattern.
It can also be
observed that, every polite number will fall into one of the following two type
of tables, based on their properties.
1)
Sequential
Tables with Odd Numbers
2)
Odd
Number Tables
6.
Polite Numbers that fall into Sequential Tables with Odd
Numbers
Sequential tables demonstrate
the following pattern, and both odd and even polite numbers will be part of
this group.
1 Table with Odd
Numbers starting from 3
(Nothing but Odd Numbers >=3)
2 Table with Odd
Numbers starting from 5
3 Table with Odd
Numbers starting from 7
…
7.
Polite Numbers that fall into Odd Number Tables
Odd Number tables demonstrate
the following pattern, and obviously odd polite numbers only will be part of
this group.
5 Table starting
from 3
7 Table starting
from 4
…
8.
The Pattern of Occurrence of Multiplication Tables in
Polite Numbers
There is also a
pattern on how the Sequential Tables, and Odd Number Tables repeat themselves.
They repeat
alternatively for each row of polite numbers, staring from Odd Number Table.
The pattern of
occurrence of Sequential and Odd Number tables is as follows.
Here n stands for
the highest number in the set {1..n}, which is used for generating the row of
all polite number combinations containing the value n.
The least set with
which we can start generating polite numbers is {1,2}, hence the starting value
for n is 2.
n=2 -> 1 Table with Odd Numbers starting
from 3
n=3 -> 3 Table starting from 2
n=4 -> 2 Table with Odd Numbers starting
from 5
n=5 -> 5 Table starting from 3
…
9.
The Relationship between Polite Numbers and Prime Numbers
It is interesting to
observe that, there exists a direct relationship between polite numbers and
prime numbers.
This is due to the
observation in the previous section that, all polite numbers follow a definite
multiplicative pattern.
The first
observation is that, all the odd numbers starting from 3 are occurring in
sequence in the first column.
The second observation is that, for any positive integer n, the first odd number that is getting
generated in any row of polite numbers is 2n-1.
Another interesting
observation is, if a polite number is a prime, then it occurs only once in the
first column, by making it the only occurrence in the polite number list.
Based on the above
observations, following two lemmas are formulated.
Lemma 1: For all
prime numbers (except 2) , there is one and only one polite number
representation, and it can be expressed as sum of two consecutive numbers only.
Lemma 2: For any positive integer n, the polite
number (2n+1) will be prime, if it is not in the group of polite numbers that
can be generated with all the possible combinations using the set of integers
{1..n}
10.
Algorithm
For any positive value of n, the following algorithm (written in Python),
computes all the prime numbers <= 2n+1.
#Input n
n = 20
#Create
an empty list
polite_list = []
#Loop
i from [1 .. n]
for i in range(1, n+1):
#initialise the polite number to i
polite = i
#Add the values [i-1, ... 1] to form
the polite number
for j in range(i-1, 0, -1):
polite
+= j
#Add the polite number
to the list
polite_list.append(polite)
# if it is not in the polite number list
k = 2 * i + 1
if k not in
polite_list:
print(k,
end=" ")
11. Time Complexity of the Algorithm
The time complexity
of the algorithm is O [n(n-1)/2] needing n(n-1)/2 numbers to be stored in the memory.
Though it is not an
efficient algorithm for generating primes, the simplicity lies in the fact that,
it just uses the primitive operation, addition only.
The above algorithm
can further be improved by making the following enhancements:
1)
Storing
the polite numbers greater than 2n only in the polite number list, will reduce the list size to much smaller than n(n-1)/2
2)
Instead
of storing the polite numbers, reserving n(n-1)/2 bits and marking their index
positions at polite number intervals, will reduce the memory utilisation
significantly.
12.
Conclusion
It is interesting to
observe that prime numbers could be derived from polite numbers, and the
sieving method is elegantly simple involving only the primitive operation of
addition.
By studying polite
numbers, the unique additive properties of prime numbers have been uncovered, demonstrating
the fact that additive number theory is in fact complementary to multiplicative
number theory.
