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

**+ 0**

__5__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

**+ 0**

__3__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

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?

LikeLike

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

LikeLiked by 1 person