Prime Number Indexing Magic

How do you find out the index of a prime number? To elaborate, we say 2 is the first prime, 3 is the second, 11 is the fifth and so on. So 1 is the index of 2. 2 is the index of 3, and 5 is the index of 11 and so on.

I discovered recently that for SOME prime numbers, given a consecutive prime, we can find out their indices using Euclid’s algorithm. Consider the following examples.


 Example: Compute the index of 37 and 31
By Euclid’s Algorithm, we have:

37 = 31 x 1 + 6
31 = 6 x 5 + 1
6 = 1 x 6 + 0

Now, simply add the highlighted numbers to get 12, the index of 37. Since they are consecutive, 31 is the 11th prime.

 Example: Compute the index of 29 and 23
By Euclid’s Algorithm, we have:

29 = 23 x 1 + 6
23 = 6 x 3 + 5
6 = 5 x 1 + 1
5 = 1 x 5 + 0

Now, simply add the highlighted numbers to get 10, the index of 29. Since they are consecutive, 23 is the 9th prime.

One final example,

 Example: Compute the index of 23 and 19
By Euclid’s Algorithm, we have:

23 = 19 x 1 + 4
19 = 4 x 4 + 3
4 = 3 x 1 + 1
3= 1 x 3 + 0

Now, simply add the highlighted numbers to get 9, the index of 23. Since they are consecutive, 19 is the 8th prime.


However, the funny thing is that this doesn’t work for all consecutive prime numbers. I initially thought that this was applicable to primes with a difference of 6 until I discovered (23,19). And this is not even injective, let alone bijective. More specifically, I would love to claim that the set of all 4-difference and 6-difference pair of consecutive primes gave this beautiful result, but take (53,59) which doesn’t follow this algorithm.

I’m going to follow on this and try to come up with a pattern (maybe theorem?). I hope one of you could offer some suggestions too. In the meantime, let’s call these numbers, “Rohan’s Numbers”, shall we? 😛


So it’s been 5 days since this post and I wanted to add something to it. I wrote a simple script to test my idea and here are the pairs of primes within the first 1000000000 primes that give us the index upon applying Euclid’s algorithm:

19, 23
23, 29
31, 37
43, 47
8171, 8179
479461, 479473
479497, 479509
479569, 479581
479581, 479593
189960439,  189960457.

Pretty rare!

Here is the code:

function [rohans_nums] = compute_pairs(n)
% This function returns all the pairs of primes that give the index of ...
% themselves upon applying Euclid's Algorithm.
%
% INPUT: n : First n primes within which you want to find the pairs.
% OUTPUT: rohans_nums: N by 2 array of pairs where N are the number of pairs that you found
clc
clear all

% Declare the array of primes
p = primes(n);

% Set variable
count = 0;

% Start iterations
for i = 1:length(p) - 1

    %     Make initializations
    p2 = p(i);
    p1 = p(i + 1);
    a = p2;
    b = p1;
    sum = 0;

    %    Run Euclid Algorithm
    while(p2>0)
        q=floor(p1/p2);
        r=p1-q*p2;
        p1=p2;
        p2=r;
        sum = sum + q;
    end

    %     Store relevant pairs
    if(sum == i + 1)
        count = count + 1;
        rohans_nums(count,1:2) = [a, b];
    end
end
end
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s