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

## 2 thoughts on “Prime Number Indexing Magic”

1. Chahat Deep Singh says:

Haha! Rohan Numbers!
Nice 🙂
Just curious, is there a method or any established algorithm or equation that can compute the index without knowing the previous prime number?

Like

1. Ridersofrohan says:

Yes, take a look at the pi-function. However, the proof for that theorem uses properties of the zeta function and complex analysis. This is just a weaker formulation using Euclid’s Algorithm

Liked by 1 person