Ripple Numbers

In this blog post, I am coining the term "Ripple Numbers", a new integer sequence, which has got some very interesting properties.

The definition goes as follows:

For any positive integer s (call it seed), when it is expressed as the product of two numbers mxn (m, n > 0), the base ripple number (call it b) will be equal to 2(m+n+2).

The subsequent ripples take the form b + 8r, where the values of r are 1, 2, 3, .. and so on.

A ripple number can be thought of as a wave which covers a seed number fully in all directions.

For example take number 6. It can be expressed as the product of two numbers 2x3.

So the ripple numbers for 6 can be computed as shown below.

But if we take another factorisation of 6, which is 1x6, then the ripples look like the following.

So, it can be observed that, based on the factorisation of the seed number, the ripples will have a very different representation for the same seed value.

When one of the multiples of the seed factors is 1, then the base ripple expression condenses into more compact form as below.

Let us suppose for the seed s=mxn, the value of m=1.

Then the base ripple expression 2(m+n+2) becomes 2(n+3).

Also the sum of the seed and base ripple becomes 1xn + 2(n+3) = 3n+6.

These two expressions are very useful, and the tables below are the listing of ripple number sequences and their consecutive sums for the first 6 seeds as per the compact formulae mentioned above.

Ripples:

{1, 08, 16, 24, 32, 40, 48, 56, 64, 72, 80}

{2, 10, 18, 26, 34, 42, 50, 58, 66, 74, 82}

{3, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84}

{4, 14, 22, 30, 38, 46, 54, 62, 70, 78, 86}

{5, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88}

{6, 18, 26, 34, 42, 50, 58, 66, 74, 82, 90}

Sum Series:

01 -> {09, 25, 49, 81, 121, 169, 225, 289, 361, 441}

02 -> {12, 30, 56, 90, 132, 182, 240, 306, 380, 462}

03 -> {15, 35, 63, 99, 143, 195, 255, 323, 399, 483}

04 -> {18, 40, 70, 108, 154, 208, 270, 340, 418, 504}

05 -> {21, 45, 77, 117, 165, 221, 285, 357, 437, 525}

06 -> {24, 50, 84, 126, 176, 234, 300, 374, 456, 546}

It can be observed in the sum series that, it is forming squares of odd numbers starting with 3, 5, 7, ... when the seed value is 1. 

And also it can be observed that the whole series is forming the odd number tables 3, 5, 7, ... vertically.

So, the sum series has got the special property of generating all odd number tables, without any need for multiplication, which is very useful in generating prime number sieves.

Formulation of the Sum Series:

The reason why the sum series is forming odd number tables is because, the sum of the consecutive ripple numbers along with their seed, forms the composite numbers of the form (m+x)*(n+x) where x is the set of even numbers starting from 2.

The proof goes as follows:

For a seed of the form mxn, it is known that the base ripple is equal to 2(m+n+2).

Adding the seed and the base ripple, yields the expression:

mn + 2(m+n+2) = mn+ 2m + 2n + 4

= m(n+2) + 2(n+2) = (m+2) * (n+2)

By adding the second ripple to the above expression, it becomes:

mn + (2m + 2n + 4) + [(2m + 2n + 4) + 8] = mn + 4m + 4n + 16
= m(n+4) + 4(n+4) = (m+4) * (n+4)

So, by the theory of induction, the next ripple yields the sum (m+6)*(n+6)... so on.

Ripple Sieve for Prime Number Generation:

As said earlier, the ripple sum series (using the compact formulae) can be used for sieving primes, by generating the series for the odd values of seed numbers 1, 3, 5, ... etc., because we all know that primes end with the digits 1,3,7, and 9 only, and exclude any multiples of 2.

The computational efficiency of this sieve exactly matches with the Sieve of Eratosthenes, but the limit check goes far beyond to (n-6)/3, against square root of (n) of Eratosthenes sieve, making it not very suitable for sieving.

Notes:

While the Ripple Sieve is not as efficient as Eratosthenes, it almost matches in the time complexity with another very elegant, but very less known prime sieving algorithm developed by the Indian Mathematician, S. P. Sundaram. Please follow the links below to know more about it.

https://en.wikipedia.org/wiki/Sieve_of_Sundaram

https://luckytoilet.wordpress.com/2010/04/18/the-sieve-of-sundaram/

The ripple number sequence {1, 08, 16, 24, 32, 40, 48, 56, 64, 72, 80, ...} matches with the co-ordination sequence of Root Lattice B2, but it is out of scope for the discussion of this blog. Following is the wiki link to know more about root systems and lattices.

https://en.wikipedia.org/wiki/Root_system

Polite Numbers and Prime Numbers

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.

 

3 Table starting from 2 

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)

            #The polite number 2i+1 will be prime,

            # 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.