<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<script language="JavaScript" type="text/javascript">
<!--
-->
</script>
<link rel="stylesheet" type="text/css" href="pstyyli.css" />
<style type="text/css">
<!--
-->
</style>
<title>Thoughts concerning the selection of PSK-PRN prime for CETI.</title>
</head>
<body bgcolor="ffffff">
Concerning the "PRN Sequence Considerations" that you present in your article
<a href="http://www.linas.org/theory/seti.html">A Better Way to Search for ETI Signals</a>
I have some comments to make.
You write:
<blockquote>
To this end, one might attempt to look for notable primes
and generators. Are there notable, 'famous' primes in the
vicinity that are 'prefereable' in some way?
e.g. 2<sup>32</sup>+-1?
Are there notable generators? e.g. generators that not only
have long sequences and good PRN properties, but are also
notable by their relationship to other famous problems,
e.g. finite/sporadic groups, Fermat's Last Theorm, etc.?
</blockquote>
First of all, I think the fame of FLT will not last that long,
being a result of the specific way mathematics has developed
in Greece and Europe, with some specific margin notes, etc.
On other planets the problem might be viewed just as
"an interesting, and hard", but not universally significant.
Instead, I would start searching the candidate primes
from the simplest possible ideas that occur for any
mathematical civilization. E.g.
<ol type="I">
<li>Mersenne primes (of form 2<sup>p</sup> - 1 where p is a prime),
<a href="http://www.research.att.com/~njas/sequences/A000668">A000668</a>:
3,7,31,127,8191,131071,524287,2147483647,2305843009213693951,...
are certainly known to them.
<li>The Fibonacci numbers <a href="http://www.research.att.com/~njas/sequences/A000045">A000045</a>
must be known by any aspiring combinatorialist and number theoretician
in the whole known universe (I think that here on Terra as well they were discovered
by many civilizations independently.)
After a while, any number theoretician realizes that after <em>n=4</em>
the <em>n</em>th Fibonacci number <em>F<sub>n</sub></em>
can be prime only when <em>n</em> itself is prime. This brings forth the sequence
<a href="http://www.research.att.com/~njas/sequences/A001605">A001605</a>:
3,4,5,7,11,13,17,23,29,43,47,83,131,137,359,431,433,... of such indices,
and the corresponding <em>Fibonacci primes</em> themselves,
the sequence <a href="http://www.research.att.com/~njas/sequences/A005478">A005478</a>:
2,3,5,13,89,233,1597,28657,514229,433494437,2971215073,99194853094755497,...
<li>Intimately connected with the Fibonacci numbers are the Lucas numbers,
<a href="http://www.research.att.com/~njas/sequences/A000032">A000032</a>,
2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,...
that occur on the next row of the Wythoff array
<a href="http://www.research.att.com/~njas/sequences/A035513">A035513</a>.
Their intersection with primes gives
the sequence <a href="http://www.research.att.com/~njas/sequences/A005479">A005479</a>,
3,7,11,29,47,199,521,2207,3571,9349,3010349,54018521,370248451,6643838879,119218851371,...
<li>There are many other, combinatorially or number-theoretically significant "core"-sequences,
where primes occur, e.g. the sequence
<a href="http://www.research.att.com/~njas/sequences/A000041">A000041</a> counting
the integer partitions,
contains primes
(the sequence <a href="http://www.research.att.com/~njas/sequences/A049575">A049575</a>):
2,3,5,7,11,101,17977,10619863,6620830889,80630964769,228204732751,...
<li>Bell numbers <a href="http://www.research.att.com/~njas/sequences/A000110">A000110</a>
which count the set partitions (among other things), contain also primes
<a href="http://www.research.att.com/~njas/sequences/A051131">A051131</a>:
2,5,877,27644437,35742549198872617291353508656626642567,...
<li>Primes of the form n!-1, sequence
<a href="http://www.research.att.com/~njas/sequences/A055490">A055490</a>:
5,23,719,5039,479001599,87178291199,...
and of the form n!+1,
sequence <a href="http://www.research.att.com/~njas/sequences/A088332">A088332</a>:
2,3,7,39916801,10888869450418352160768000001,...
<li>Numerators and denominators of continued fraction convergents of SQRT(2),
sequences <a href="http://www.research.att.com/~njas/sequences/A001333">A001333</a>
and <a href="http://www.research.att.com/~njas/sequences/A000129">A000129</a>
respectively, contain primes:
sequence <a href="http://www.research.att.com/~njas/sequences/A086395">A086395</a>
(3,7,17,41,239,577,665857,9369319,63018038201,489133282872437279,...) for the former,
and sequence <a href="http://www.research.att.com/~njas/sequences/A086383">A086383</a>
(2,5,29,5741,33461,44560482149,1746860020068409,68480406462161287469,...) for the latter.
<li>Numerators and denominators of continued fraction convergents of Π (Pi),
sequences <a href="http://www.research.att.com/~njas/sequences/A002485">A002485</a>
and <a href="http://www.research.att.com/~njas/sequences/A002486">A002486</a>
respectively, contain primes:
sequence <a href="http://www.research.att.com/~njas/sequences/A086785">A086785</a>
(3,103993,833719,4272943,411557987,2111972998212909763,...) for the former,
and sequence <a href="http://www.research.att.com/~njas/sequences/A086788">A086788</a>
(7,113,265381,842468587426513207,...) for the latter.
<li>Numerators and denominators of continued fraction convergents of <em>e</em>,
sequences <a href="http://www.research.att.com/~njas/sequences/A007676">A007676</a>
and <a href="http://www.research.att.com/~njas/sequences/A007677">A007677</a>
respectively, contain primes:
sequence <a href="http://www.research.att.com/~njas/sequences/A086791">A086791</a>
(2,3,11,19,193,49171,1084483,563501581931,332993721039856822081,...) for the former,
and sequence <a href="http://www.research.att.com/~njas/sequences/A094008">A094008</a>
(3,7,71,18089,10391023,781379079653017,2111421691000680031,...) for the latter.
<li>Jacobsthal sequence <a href="http://www.research.att.com/~njas/sequences/A001045">A001045</a>
contains primes
<a href="http://www.research.att.com/~njas/sequences/A049883">A049883</a>:
3,5,11,43,683,2731,43691,174763,2796203,715827883,2932031007403,...
(which after 5 seem all to be of the form (2<sup>p</sup>+1)/3, c.f.
<a href="http://www.research.att.com/~njas/sequences/A000979">A000979</a>.)
</ol>
It would be good if the prime p were one of Sophie Germain primes
<a href="http://www.research.att.com/~njas/sequences/A005384">A005384</a>, i.e.
that 2p+1 is also prime, and especially if it is one of the safe primes
<a href="http://www.research.att.com/~njas/sequences/A005385">A005385</a>, i.e.
that (p-1)/2 is also prime.
(See also Cunningham chains, <a href="http://www.research.att.com/~njas/sequences/A057331">A057331</a>,
sequence 2,2,2,2,2,89,1122659,19099919,85864769,26089808579,554688278429,4090932431513069,...
where a(n) = smallest prime p such that the first n iterates of p under x-> 2x+1
are all primes.)
<p><br /></p>
<table>
<tr><th>Prime p</th> <th>Form</th><td>(p-1)/2 factored</td><td>2p + 1 factored</td><td>member of</td></tr>
<tr><th>103993</th><td>4k+1</td><td>2<sup>2</sup> 3 7 619</td><td>3 13 5333</td><td>Numerator of a convergent to Pi</td></tr>
<tr><th>131071</th><td>4k+3</td><td>3 5 17 257</td><td>3<sup>3</sup> 7 19 73</td><td>Mersenne prime</td></tr>
<tr><th>174763</th><td>4k+3</td><td>3<sup>2</sup> 7 19 73</td><td>3 263 443</td><td>Jacobsthal sequence</td></tr>
<tr><th>265381</th><td>4k+1</td><td>2 3 5 4423</td><td>3 176921</td><td>Denominator of a convergent to Pi</td></tr>
<tr><th>514229</th><td>4k+1</td><td>2 11 13 29 31</td><td>137 7507</td><td>Fibonacci number</td></tr>
<tr><th>524287</th><td>4k+3</td><td>3<sup>3</sup> 7 19 73</td><td>3 5<sup>2</sup> 11 31 41</td><td>Mersenne prime</td></tr>
<tr><th>665857</th><td>4k+1</td><td>2<sup>7</sup> 3<sup>2</sup> 17<sup>2</sup></td><td>3 5 7 11 1153</td><td>Numerator of a convergent to SQRT(2)</td></tr>
<tr><th>833719</th><td>4k+3</td><td>3 283 491</td><td>3<sup>3</sup> 61757</td><td>Numerator of a convergent to Pi</td></tr>
<tr><th>1084483</th><td>4k+3</td><td>3<sup>3</sup> 7 19 151</td><td>3 131 5519</td><td>Numerator of a convergent to <em>e</em></td></tr>
<tr><th>2796203</th><td>4k+3</td><td>23 89 683</td><td>5592407</td><td>Jacobsthal sequence; Sophie Germain prime</td></tr>
<tr><th>3010349</th><td>4k+1</td><td>2 11 31 2207</td><td>6020699</td><td>Lucas number; Sophie Germain prime</td></tr>
<tr><th>4272943</th><td>4k+3</td><td>3 712157</td><td>3<sup>2</sup> 7 135649</td><td>Numerator of a convergent to Pi</td></tr>
<tr><th>5592407</th><td>4k+3</td><td>2796203</td><td>5 179 12497</td><td>Member of both <a href="http://www.research.att.com/~njas/sequences/A023105">A023105</a> and <a href="http://www.research.att.com/~njas/sequences/A083582">A083582</a>; 1 + 2*<b>2796203</b> (the latter in Jacobsthal seq.); Safe prime</td></tr>
<tr><th>9369319</th><td>4k+3</td><td>3 7 19 59 199</td><td>3<sup>2</sup> 2082071</td><td>Numerator of a convergent to SQRT(2)</td></tr>
<tr><th>10391023</th><td>4k+3</td><td>3<sup>2</sup> 577279</td><td>3 11 13 193 251</td><td>Denominator of a convergent to <em>e</em></td></tr>
<tr><th>10619863</th><td>4k+3</td><td>3 11 160907</td><td>3 929 7621</td><td>Partition number</td></tr>
<tr><th>27644437</th><td>4k+1</td><td>2 3<sup>3</sup> 23 31 359</td><td>3 5<sup>3</sup> 61 2417</td><td>Bell number</td></tr>
<tr><th>39916801</th><td>4k+1</td><td>2<sup>7</sup> 3<sup>4</sup> 5<sup>2</sup> 7 11</td><td>3 73 364537</td><td>Prime of the form n!+1</td></tr>
<tr><th>54018521</th><td>4k+1</td><td>2<sup>2</sup> 5 17 19 37 113</td><td>108037043</td><td>Lucas number; Sophie Germain prime</td></tr>
<tr><th>370248451</th><td>4k+3</td><td>3 5<sup>2</sup> 11 13 41 421</td><td>3 151 607 2693</td><td>Lucas number</td></tr>
<tr><th>411557987</th><td>4k+3</td><td>7 29396999</td><td>5<sup>2</sup> 11 2993149</td><td>Numerator of a convergent to Pi</td></tr>
<tr><th>433494437</th><td>4k+1</td><td>2 29 89 199 211</td><td>5<sup>3</sup> 6935911</td><td>Fibonacci number</td></tr>
<tr><th>479001599</th><td>4k+3</td><td>53 4518883</td><td>19 23 31 70717</td><td>Prime of the form n!-1</td></tr>
<tr><th>715827883</th><td>4k+3</td><td>3 7 11 31 151 331</td><td>3<sup>2</sup> 47 3384529</td><td>Jacobsthal sequence</td></tr>
<tr><th>2147483647</th><td>4k+3</td><td>3<sup>2</sup> 7 11 31 151 331</td><td>3 5 17 257 65537</td><td>Mersenne prime</td></tr>
<tr><th>2971215073</th><td>4k+1</td><td>2<sup>4</sup> 3<sup>2</sup> 7 23 139 461</td><td>3 38393 51593</td><td>Fibonacci number</td></tr>
<tr><th>6620830889</th><td>4k+1</td><td>2 2 7 10559 11197</td><td>4079 3246301</td><td>Partition number</td></tr>
<tr><th>6643838879</th><td>4k+3</td><td>47 139 461 1103</td><td>19 73 9580157</td><td>Lucas number</td></tr>
<tr><th>44560482149</th><td>4k+1</td><td>2 7 13 13 31 31 41 239</td><td>89120964299</td><td>Denominator of a convergent to SQRT(2), i.e. Pell sequence; Sophie Germain prime</td></tr>
<tr><th>63018038201</th><td>4k+1</td><td>2 2 5 5 13 13 29 239 269</td><td>17203 7326401</td><td>Numerator of a convergent to SQRT(2)</td></tr>
<tr><th>80630964769</th><td>4k+1</td><td>2 2 2 2 3 37 157 191 757</td><td>3 3 3 3 29 6151 11161</td><td>Partition number</td></tr>
<tr><th>87178291199</th><td>4k+3</td><td>101 431575699</td><td>174356582399</td><td>Prime of the form n!-1; Sophie Germain prime</td></tr>
</table>
<!--
the sequence <a href="http://www.research.att.com/~njas/sequences/"></a>.
-->
</body>
</thml>