Ramanujan Primes

[reddwarf2956]

This thread is for Ramanujan primes and other related sequences here: http://oeis.org/wiki/Ramanujan_primes, also in the quote below describes a chain of primes different from other chains and we will talk about finding them.

For some n and k, we see that a(n) = A104272(k) as to form a chain of primes similar to a Cunningham chain. For example (and the first example), a(2) = 7, links A104272(2) = 11 = a(3), links A104272(3) = 17 = a(4), links A104272(4) = 29 = a(6), links A104272(6) = 47. Note that the links do not have to be of a form like q = 2*p+1 or q = 2*p-1. - John W. Nicholson, Dec 14 2013, https://oeis.org/A168421

So to start, what is the largest Nicholson chain?

[danaj]

The wording of that paragraph is awful. I cannot figure out what is supposed to link to what.

Why did we start at a(2) rather than a(1)? Where did a(5) go?

[science_man_88]

Originally Posted by danaj

The wording of that paragraph is awful. I cannot figure out what is supposed to link to what.

Why did we start at a(2) rather than a(1)? Where did a(5) go?

it's a connection between two sequences where a(5) doesn't show up in the other sequence I semi get what they are saying in the OEIS comment not completely though. the point is you can get a k for almost any n and link them together in a chain and they compare it tot cunningham chains. so my understanding is they are saying hey these two sequences are linked some how.

[danaj]

I believe I get it. We start with A168421(n) then for as long as we can we do:

  r = A104272(n)
  add r to chain
  k = A168421-1(r)
  stop if k not found
  n = k

Does "largest chain" mean the longest?

n = 820 yields 9 terms, as does 856.

n = 9742 yields 10 terms.

n = 30850 yields at least 11 terms.

That's the best I could get with the first 100M Ramanujan primes. With simple methods the memory starts to be an issue.

[danaj]

Using the method above, first n with a chain of length k:
k n [primes]
2 5 [23 41]
3 4 [17 29 47]
4 3 [11 17 29 47]
5 2 [7 11 17 29 47]
6 50 [331 641 1277 2531 5051 10093]
7 40 [251 487 967 1913 3821 7621 15233]
9 820 [7681 15349 30689 61357 122693 245339 490661 981301 1962581]
10 9742 [117497 234931 469841 939649 1879279 3758537 7517033 15034049 30068081 60136117]
11 30850 [410651 821281 1642549 3285041 6570049 13140079 26280127 52560217 105120403 210240781 420481541]

[reddwarf2956]

Originally Posted by science_man_88

it's a connection between two sequences where a(5) doesn't show up in the other sequence I semi get what they are saying in the OEIS comment not completely though. the point is you can get a k for almost any n and link them together in a chain and they compare it to cunningham chains. so my understanding is they are saying hey these two sequences are linked some how.

Yes, the sequences are linked by values and index values.
a(n) is A168421(n), so that A168421(2) = 7. The link here is the index, 2. A104272(2) = 11. Here the link is value, 11, A168421(3) = 11. The link here is the index, 3, A104272(3) = 17.
Value: A168421(4) = 17. Index: A104272(4) = 29.
Value: A168421(6) = 29. Index: A104272(6) = 47.
A168421 does not have the value 47 in the sequence, so the chain ends.

I am unsure of this code, if it does the same as above then great:

Originally Posted by danaj

I believe I get it. We start with A168421(n) then for as long as we can we do:

  r = A104272(n)
  add r to chain
  k = A168421-1(r)
  stop if k not found
  n = k

Does "largest chain" mean the longest?

I would say at first glance yes to the largest-longest question. But, it can also mean size from the first value to the last.

[danaj]

My first version uses code that:

1. Gets the first L ramanujan primes. For L = 100M this ends at about 4378M, takes 20 seconds.
2. Creates a list of the first L values of A168421 just like the code on the OEIS page. Almost 2 minutes. Last one is ~2189M.
3. Makes a L-entry hash of A168421 values to indices. About 1 minute.
4. Walks starting values looking for chains. Almost instant to find the chains above.

Given the number of expected calls for looking at reasonably small inputs, I'm thinking it would be better to avoid making all the lists.

1. Calculate A104272(n) as needed with nth_ramanujan_prime(n). I tried hard to make it fast even for large values by doing a lot of work on the bounds. Under 3ms at 10M, under 20ms at 100M, 200ms at 1000M, 400ms for 10,000M.
2. Calculate the inverse A168421 using a binary search method. Time for each call is just a next_prime on a halved nth_ramanujan_prime so should quick. Having upper/lower bounds would be helpful.

It would be slower if we were walking every n value, but it should be quite a bit faster overall for the longer chains, and has larger size limits (it's almost 30 seconds for my code to get the 10^11th Ramanujan prime, 67 seconds for the 10^12th so eventually we'll run out of time or space).

[danaj]

As far as I can tell, the code does what you describe. It gets RP[n] (the value), then looks it up in A168421 to get the index from that sequence, which is used as the next n. Repeat until it isn't in A168421.

I wrote a modified version, that doesn't use the big arrays/hashes. The binary search could certainly be improved with better starting points.

length 8 at n = 1036 (from 10037 to 1282277)
length 12 at 147391 (from 2211593 to 4529290013).
length 13 at 188849 (from 2882837 to 11807947427).
length 14 at 673990 (from 11201987 to 91766252549).
length 15 at 501244 (from 8172583 to 133899099401).

[reddwarf2956]

Here is another quote from https://oeis.org/A168421

Prime index of a(n), pi(a(n)) = i-n, is equal to A179196(n) - n + 1. - John W. Nicholson, Sep 15 2015

A179196 is the index of A104272. And yet another quote:

A084140(n) is the smallest integer where ceiling ((A104272(n)+1)/2), a(n) is the next prime after A084140(n). - John W. Nicholson, Oct 09 2013

These may be handy.

[reddwarf2956]

This conjecture may be useful if you got the prime and index while trying to find the next prime.http://www.mersenneforum.org/showthread.php?t=21045

[danaj]

Originally Posted by reddwarf2956

This conjecture may be useful if you got the prime and index while trying to find the next prime.http://www.mersenneforum.org/showthread.php?t=21045

How is that useful? It's not a proven conjecture, for one thing. The next_prime function is orders of magnitude faster than getting large nth Ramanujan primes. Better methods for those would be quite useful.