cp's OEIS Frontend

A141537 An example of a simple prime-generating algorithm similar to Rowland's (A106108) that is a particular instance of a more general algorithm (see comments).

%I A141537 #27 Jan 31 2025 17:42:48
%S A141537 47,227,71,359,113,563,173,839,251,1187,347,1607,461,2099,593,2663,
%T A141537 743,3299,911,4007,1097,4787,1301,5639,1523,6563,43,7559,43,8627,2297,
%U A141537 9767,2591,10979,2903,12263,53,13619,3581,41,3947,16547,61,18119,4733,19763,5153,47
%N A141537 An example of a simple prime-generating algorithm similar to Rowland's (A106108) that is a particular instance of a more general algorithm (see comments).
%C A141537 Below is a general algorithm that can be used as a starting point for finding similar ones and three examples.
%C A141537 Not every possibility will work (additional conditions may apply) but it is easy to see that there are an infinite number of algorithms much like Rowland's that will have hundreds or thousands of primes between the 1's before a composite is encountered.
%C A141537 1) Initialize the integers x, k, a and b and choose f(x), g(k).
%C A141537 2) Repeat indefinitely:
%C A141537    2a) x = x + 1;
%C A141537    2b) set c = GCD( f(x), f(x - 1) - a*g(k) );
%C A141537    2c) if c > 1, then c is a term of the sequence and k = k + b.
%C A141537 The present sequence is generated by using f(x) = x^2 - x + 41, g(k) = k, x = 1, k = 2, a = 3 and b = 1.
%C A141537 Examples:
%C A141537 A) f(x) = 5*x^2 + 5*x + 1, g(k) = k, x = 1, k = 2, a = 10, b = 1. These values generate the sequence: 11, 31, 61, 101, 151, 211, 281, 19, 41, 29, 661, 11, 911, 1051, 1201, 1361, 1531, 59, 1901, ...
%C A141537 B) f(x) = x^2 - x + 41, g(k) = k, x = 1, k = 2, a = 3, b = 1. These values generate the sequence: 47, 227, 71, 359, 113, 563, 173, 839, 251,1187,347, 1607, 461,2099,593, 2663, 743,3299, 911, 4007, ...
%C A141537 C) f(x) = 5*x^2 + 5*x + 1, g(k) = k^2 - k + 41, x = 1, k = 2, a = 2, b = 1. These values generate the sequence: 11, 1979, 2549, 11,4691, 11, 8929, 29, 11, 22051, 41, 19, 48619, 61751, 11, 229, 11, 144779, 175141, 11, ...
%D A141537 Eric S. Rowland, A simple prime-generating recurrence, Abstracts Amer. Math. Soc., 29 (No. 1, 2008), p. 50 (Abstract 1035-11-986).
%H A141537 Paolo Xausa, <a href="/A141537/b141537.txt">Table of n, a(n) for n = 1..10000</a>
%t A141537 Module[{k = 2, c, f}, f[x_] := x^2 - x + 41; Table[If[(c = GCD[f[x], f[x - 1] - 3*k]) > 1, k++; c, Nothing], {x, 12000}]] (* _Paolo Xausa_, Jan 31 2025 *)
%Y A141537 Cf. A084662, A106108, A137613.
%K A141537 nonn
%O A141537 1,1
%A A141537 Aldrich Stevens (aldrichstevens(AT)msn.com), Aug 15 2008
%E A141537 Edited by _Paolo Xausa_, Jan 31 2025