Primes: n*2^m+1: Difference between revisions
Content added Content deleted
(Add PARI/GP implementation) |
|||
| (12 intermediate revisions by 9 users not shown) | |||
| Line 1: | Line 1: | ||
{{ |
{{task}} |
||
;Task |
;Task |
||
* Find and display the first 45 ('''n''') primes of the form '''n × 2<sup>m</sup> + 1''' where '''m''' is the smallest valid non-negative integer. |
* Find and display the first 45 ('''n''') primes of the form '''n × 2<sup>m</sup> + 1''' where '''m''' is the smallest valid non-negative integer. |
||
| Line 505: | Line 505: | ||
( 41 1: 83 )( 42 0: 43 )( 43 2: 173 )( 44 1: 89 )( 45 2: 181 ) |
( 41 1: 83 )( 42 0: 43 )( 43 2: 173 )( 44 1: 89 )( 45 2: 181 ) |
||
</pre> |
</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">cnt: 0 |
|||
n: 1 |
|||
while [cnt < 45][ |
|||
m: 0 |
|||
while [true][ |
|||
p: inc n * 2^m |
|||
if prime? p [ |
|||
print ["n:" n "m:" m "p:" p] |
|||
inc 'cnt |
|||
break |
|||
] |
|||
inc 'm |
|||
] |
|||
inc 'n |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>n: 1 m: 0 p: 2 |
|||
n: 2 m: 0 p: 3 |
|||
n: 3 m: 1 p: 7 |
|||
n: 4 m: 0 p: 5 |
|||
n: 5 m: 1 p: 11 |
|||
n: 6 m: 0 p: 7 |
|||
n: 7 m: 2 p: 29 |
|||
n: 8 m: 1 p: 17 |
|||
n: 9 m: 1 p: 19 |
|||
n: 10 m: 0 p: 11 |
|||
n: 11 m: 1 p: 23 |
|||
n: 12 m: 0 p: 13 |
|||
n: 13 m: 2 p: 53 |
|||
n: 14 m: 1 p: 29 |
|||
n: 15 m: 1 p: 31 |
|||
n: 16 m: 0 p: 17 |
|||
n: 17 m: 3 p: 137 |
|||
n: 18 m: 0 p: 19 |
|||
n: 19 m: 6 p: 1217 |
|||
n: 20 m: 1 p: 41 |
|||
n: 21 m: 1 p: 43 |
|||
n: 22 m: 0 p: 23 |
|||
n: 23 m: 1 p: 47 |
|||
n: 24 m: 2 p: 97 |
|||
n: 25 m: 2 p: 101 |
|||
n: 26 m: 1 p: 53 |
|||
n: 27 m: 2 p: 109 |
|||
n: 28 m: 0 p: 29 |
|||
n: 29 m: 1 p: 59 |
|||
n: 30 m: 0 p: 31 |
|||
n: 31 m: 8 p: 7937 |
|||
n: 32 m: 3 p: 257 |
|||
n: 33 m: 1 p: 67 |
|||
n: 34 m: 2 p: 137 |
|||
n: 35 m: 1 p: 71 |
|||
n: 36 m: 0 p: 37 |
|||
n: 37 m: 2 p: 149 |
|||
n: 38 m: 5 p: 1217 |
|||
n: 39 m: 1 p: 79 |
|||
n: 40 m: 0 p: 41 |
|||
n: 41 m: 1 p: 83 |
|||
n: 42 m: 0 p: 43 |
|||
n: 43 m: 2 p: 173 |
|||
n: 44 m: 1 p: 89 |
|||
n: 45 m: 2 p: 181</pre> |
|||
=={{header|EasyLang}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang=easylang> |
|||
func isprim num . |
|||
i = 2 |
|||
while i <= sqrt num |
|||
if num mod i = 0 |
|||
return 0 |
|||
. |
|||
i += 1 |
|||
. |
|||
return 1 |
|||
. |
|||
for n = 1 to 45 |
|||
m = 0 |
|||
repeat |
|||
p = n * (pow 2 m) + 1 |
|||
until isprim p = 1 |
|||
m += 1 |
|||
. |
|||
print n & " " & m & " " & p |
|||
. |
|||
</syntaxhighlight> |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
| Line 577: | Line 668: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq.''' |
'''Works with gojq, the Go implementation of jq.''' |
||
gojq supports unbounded-precision integer arithmetic but the following |
gojq supports unbounded-precision integer arithmetic but the following |
||
algorithm for prime number detection is not up to the stretch tasks. |
algorithm for prime number detection is not up to the stretch tasks. |
||
| Line 1,086: | Line 1,178: | ||
399 2 1597 |
399 2 1597 |
||
400 0 401 |
400 0 401 |
||
</pre> |
|||
=={{header|Nim}}== |
|||
===Task=== |
|||
<syntaxhighlight lang = "Nim">import std/strformat |
|||
func isPrime(n: Natural): bool = |
|||
if n < 2: return false |
|||
if (n and 1) == 0: return n == 2 |
|||
if n mod 3 == 0: return n == 3 |
|||
var k = 5 |
|||
var delta = 2 |
|||
while k * k <= n: |
|||
if n mod k == 0: return false |
|||
inc k, delta |
|||
delta = 6 - delta |
|||
result = true |
|||
echo " n m prime" |
|||
for n in 1..45: |
|||
var m = 0 |
|||
var term = n |
|||
while true: |
|||
if isPrime(term + 1): |
|||
echo &"{n:2} {m} {term + 1:5}" |
|||
break |
|||
inc m |
|||
term *= 2 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:12ex;overflow:scroll;>> n m prime |
|||
1 0 2 |
|||
2 0 3 |
|||
3 1 7 |
|||
4 0 5 |
|||
5 1 11 |
|||
6 0 7 |
|||
7 2 29 |
|||
8 1 17 |
|||
9 1 19 |
|||
10 0 11 |
|||
11 1 23 |
|||
12 0 13 |
|||
13 2 53 |
|||
14 1 29 |
|||
15 1 31 |
|||
16 0 17 |
|||
17 3 137 |
|||
18 0 19 |
|||
19 6 1217 |
|||
20 1 41 |
|||
21 1 43 |
|||
22 0 23 |
|||
23 1 47 |
|||
24 2 97 |
|||
25 2 101 |
|||
26 1 53 |
|||
27 2 109 |
|||
28 0 29 |
|||
29 1 59 |
|||
30 0 31 |
|||
31 8 7937 |
|||
32 3 257 |
|||
33 1 67 |
|||
34 2 137 |
|||
35 1 71 |
|||
36 0 37 |
|||
37 2 149 |
|||
38 5 1217 |
|||
39 1 79 |
|||
40 0 41 |
|||
41 1 83 |
|||
42 0 43 |
|||
43 2 173 |
|||
44 1 89 |
|||
45 2 181 |
|||
</pre> |
|||
===Stretch tasks=== |
|||
{{libheader|Nim-Integers}} |
|||
<syntaxhighlight lang = "Nim">import std/strformat |
|||
import integers |
|||
func compressed(str: string; size: int): string = |
|||
## Return a compressed value for long strings of digits. |
|||
if str.len <= 2 * size: str |
|||
else: &"{str[0..<size]}...{str[^size..^1]} ({str.len} digits)" |
|||
echo " n m prime" |
|||
for n in 1..400: |
|||
var m = 0 |
|||
var term = newInteger(n) |
|||
while true: |
|||
if isPrime(term + 1): |
|||
echo &"{n:3} {m:4} {compressed($(term + 1), 10)}" |
|||
break |
|||
inc m |
|||
term *= 2 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:12ex;overflow:scroll;"> n m prime |
|||
1 0 2 |
|||
2 0 3 |
|||
3 1 7 |
|||
4 0 5 |
|||
5 1 11 |
|||
6 0 7 |
|||
7 2 29 |
|||
8 1 17 |
|||
9 1 19 |
|||
10 0 11 |
|||
11 1 23 |
|||
12 0 13 |
|||
13 2 53 |
|||
14 1 29 |
|||
15 1 31 |
|||
16 0 17 |
|||
17 3 137 |
|||
18 0 19 |
|||
19 6 1217 |
|||
20 1 41 |
|||
21 1 43 |
|||
22 0 23 |
|||
23 1 47 |
|||
24 2 97 |
|||
25 2 101 |
|||
26 1 53 |
|||
27 2 109 |
|||
28 0 29 |
|||
29 1 59 |
|||
30 0 31 |
|||
31 8 7937 |
|||
32 3 257 |
|||
33 1 67 |
|||
34 2 137 |
|||
35 1 71 |
|||
36 0 37 |
|||
37 2 149 |
|||
38 5 1217 |
|||
39 1 79 |
|||
40 0 41 |
|||
41 1 83 |
|||
42 0 43 |
|||
43 2 173 |
|||
44 1 89 |
|||
45 2 181 |
|||
46 0 47 |
|||
47 583 1487939695...6574002177 (178 digits) |
|||
48 1 97 |
|||
49 2 197 |
|||
50 1 101 |
|||
51 1 103 |
|||
52 0 53 |
|||
53 1 107 |
|||
54 1 109 |
|||
55 4 881 |
|||
56 1 113 |
|||
57 2 229 |
|||
58 0 59 |
|||
59 5 1889 |
|||
60 0 61 |
|||
61 4 977 |
|||
62 7 7937 |
|||
63 1 127 |
|||
64 2 257 |
|||
65 1 131 |
|||
66 0 67 |
|||
67 2 269 |
|||
68 1 137 |
|||
69 1 139 |
|||
70 0 71 |
|||
71 3 569 |
|||
72 0 73 |
|||
73 2 293 |
|||
74 1 149 |
|||
75 1 151 |
|||
76 4 1217 |
|||
77 3 617 |
|||
78 0 79 |
|||
79 2 317 |
|||
80 3 641 |
|||
81 1 163 |
|||
82 0 83 |
|||
83 1 167 |
|||
84 2 337 |
|||
85 4 1361 |
|||
86 1 173 |
|||
87 2 349 |
|||
88 0 89 |
|||
89 1 179 |
|||
90 1 181 |
|||
91 8 23297 |
|||
92 7 11777 |
|||
93 2 373 |
|||
94 582 1487939695...6574002177 (178 digits) |
|||
95 1 191 |
|||
96 0 97 |
|||
97 2 389 |
|||
98 1 197 |
|||
99 1 199 |
|||
100 0 101 |
|||
101 3 809 |
|||
102 0 103 |
|||
103 16 6750209 |
|||
104 5 3329 |
|||
105 1 211 |
|||
106 0 107 |
|||
107 3 857 |
|||
108 0 109 |
|||
109 6 6977 |
|||
110 3 881 |
|||
111 1 223 |
|||
112 0 113 |
|||
113 1 227 |
|||
114 1 229 |
|||
115 2 461 |
|||
116 1 233 |
|||
117 3 937 |
|||
118 4 1889 |
|||
119 1 239 |
|||
120 1 241 |
|||
121 8 30977 |
|||
122 3 977 |
|||
123 6 7873 |
|||
124 6 7937 |
|||
125 1 251 |
|||
126 0 127 |
|||
127 2 509 |
|||
128 1 257 |
|||
129 3 1033 |
|||
130 0 131 |
|||
131 1 263 |
|||
132 4 2113 |
|||
133 4 2129 |
|||
134 1 269 |
|||
135 1 271 |
|||
136 0 137 |
|||
137 3 1097 |
|||
138 0 139 |
|||
139 2 557 |
|||
140 1 281 |
|||
141 1 283 |
|||
142 2 569 |
|||
143 53 1288029493427961857 |
|||
144 2 577 |
|||
145 6 9281 |
|||
146 1 293 |
|||
147 8 37633 |
|||
148 0 149 |
|||
149 3 1193 |
|||
150 0 151 |
|||
151 4 2417 |
|||
152 3 1217 |
|||
153 1 307 |
|||
154 2 617 |
|||
155 1 311 |
|||
156 0 157 |
|||
157 8 40193 |
|||
158 1 317 |
|||
159 6 10177 |
|||
160 2 641 |
|||
161 3 1289 |
|||
162 0 163 |
|||
163 2 653 |
|||
164 9 83969 |
|||
165 1 331 |
|||
166 0 167 |
|||
167 7 21377 |
|||
168 1 337 |
|||
169 2 677 |
|||
170 3 1361 |
|||
171 8 43777 |
|||
172 0 173 |
|||
173 1 347 |
|||
174 1 349 |
|||
175 2 701 |
|||
176 1 353 |
|||
177 2 709 |
|||
178 0 179 |
|||
179 1 359 |
|||
180 0 181 |
|||
181 4 2897 |
|||
182 7 23297 |
|||
183 1 367 |
|||
184 6 11777 |
|||
185 3 1481 |
|||
186 1 373 |
|||
187 6 11969 |
|||
188 581 1487939695...6574002177 (178 digits) |
|||
189 1 379 |
|||
190 0 191 |
|||
191 1 383 |
|||
192 0 193 |
|||
193 2 773 |
|||
194 1 389 |
|||
195 4 3121 |
|||
196 0 197 |
|||
197 15 6455297 |
|||
198 0 199 |
|||
199 2 797 |
|||
200 1 401 |
|||
201 3 1609 |
|||
202 2 809 |
|||
203 13 1662977 |
|||
204 1 409 |
|||
205 2 821 |
|||
206 15 6750209 |
|||
207 2 829 |
|||
208 4 3329 |
|||
209 1 419 |
|||
210 0 211 |
|||
211 20 221249537 |
|||
212 3 1697 |
|||
213 2 853 |
|||
214 2 857 |
|||
215 1 431 |
|||
216 1 433 |
|||
217 66 1601177385...9890802689 (23 digits) |
|||
218 5 6977 |
|||
219 1 439 |
|||
220 2 881 |
|||
221 1 443 |
|||
222 0 223 |
|||
223 8 57089 |
|||
224 1 449 |
|||
225 3 1801 |
|||
226 0 227 |
|||
227 11 464897 |
|||
228 0 229 |
|||
229 6 14657 |
|||
230 1 461 |
|||
231 1 463 |
|||
232 0 233 |
|||
233 1 467 |
|||
234 2 937 |
|||
235 2 941 |
|||
236 3 1889 |
|||
237 4 3793 |
|||
238 0 239 |
|||
239 1 479 |
|||
240 0 241 |
|||
241 36 16561393893377 |
|||
242 7 30977 |
|||
243 1 487 |
|||
244 2 977 |
|||
245 1 491 |
|||
246 5 7873 |
|||
247 6 15809 |
|||
248 5 7937 |
|||
249 1 499 |
|||
250 0 251 |
|||
251 1 503 |
|||
252 2 1009 |
|||
253 2 1013 |
|||
254 1 509 |
|||
255 2 1021 |
|||
256 0 257 |
|||
257 279 2496329526...9292015617 (87 digits) |
|||
258 2 1033 |
|||
259 38 71193377898497 |
|||
260 1 521 |
|||
261 1 523 |
|||
262 0 263 |
|||
263 29 141197049857 |
|||
264 3 2113 |
|||
265 2 1061 |
|||
266 3 2129 |
|||
267 2 1069 |
|||
268 0 269 |
|||
269 3 2153 |
|||
270 0 271 |
|||
271 4 4337 |
|||
272 11 557057 |
|||
273 1 547 |
|||
274 2 1097 |
|||
275 7 35201 |
|||
276 0 277 |
|||
277 2 1109 |
|||
278 1 557 |
|||
279 2 1117 |
|||
280 0 281 |
|||
281 1 563 |
|||
282 0 283 |
|||
283 30 303868936193 |
|||
284 1 569 |
|||
285 1 571 |
|||
286 52 1288029493427961857 |
|||
287 3 2297 |
|||
288 1 577 |
|||
289 10 295937 |
|||
290 5 9281 |
|||
291 4 4657 |
|||
292 0 293 |
|||
293 1 587 |
|||
294 7 37633 |
|||
295 2 1181 |
|||
296 1 593 |
|||
297 3 2377 |
|||
298 2 1193 |
|||
299 1 599 |
|||
300 1 601 |
|||
301 4 4817 |
|||
302 3 2417 |
|||
303 1 607 |
|||
304 2 1217 |
|||
305 3 2441 |
|||
306 0 307 |
|||
307 2 1229 |
|||
308 1 617 |
|||
309 1 619 |
|||
310 0 311 |
|||
311 9 159233 |
|||
312 0 313 |
|||
313 4 5009 |
|||
314 7 40193 |
|||
315 1 631 |
|||
316 0 317 |
|||
317 7 40577 |
|||
318 5 10177 |
|||
319 2 1277 |
|||
320 1 641 |
|||
321 1 643 |
|||
322 2 1289 |
|||
323 1 647 |
|||
324 2 1297 |
|||
325 2 1301 |
|||
326 1 653 |
|||
327 3 2617 |
|||
328 8 83969 |
|||
329 1 659 |
|||
330 0 331 |
|||
331 4 5297 |
|||
332 3 2657 |
|||
333 5 10657 |
|||
334 6 21377 |
|||
335 19 175636481 |
|||
336 0 337 |
|||
337 4 5393 |
|||
338 1 677 |
|||
339 3 2713 |
|||
340 2 1361 |
|||
341 1 683 |
|||
342 7 43777 |
|||
343 2 1373 |
|||
344 3 2753 |
|||
345 1 691 |
|||
346 0 347 |
|||
347 3 2777 |
|||
348 0 349 |
|||
349 10 357377 |
|||
350 1 701 |
|||
351 12 1437697 |
|||
352 0 353 |
|||
353 21 740294657 |
|||
354 1 709 |
|||
355 6 22721 |
|||
356 5 11393 |
|||
357 2 1429 |
|||
358 0 359 |
|||
359 1 719 |
|||
360 6 23041 |
|||
361 28 96905199617 |
|||
362 3 2897 |
|||
363 1 727 |
|||
364 6 23297 |
|||
365 5 11681 |
|||
366 0 367 |
|||
367 12 1503233 |
|||
368 5 11777 |
|||
369 1 739 |
|||
370 2 1481 |
|||
371 1 743 |
|||
372 0 373 |
|||
373 2 1493 |
|||
374 5 11969 |
|||
375 1 751 |
|||
376 580 1487939695...6574002177 (178 digits) |
|||
377 11 772097 |
|||
378 0 379 |
|||
379 14 6209537 |
|||
380 1 761 |
|||
381 3 3049 |
|||
382 0 383 |
|||
383 6393 1169394518...1620750337 (1928 digits) |
|||
384 1 769 |
|||
385 8 98561 |
|||
386 1 773 |
|||
387 2 1549 |
|||
388 0 389 |
|||
389 11 796673 |
|||
390 3 3121 |
|||
391 4 6257 |
|||
392 3 3137 |
|||
393 1 787 |
|||
394 14 6455297 |
|||
395 5 12641 |
|||
396 0 397 |
|||
397 4 6353 |
|||
398 1 797 |
|||
399 2 1597 |
|||
400 0 401 |
|||
</pre> |
|||
=={{header|PARI/GP}}== |
|||
{{trans|Julia}} |
|||
<syntaxhighlight lang="PARI/GP"> |
|||
/* Check if there is an m such that n * 2^m + 1 is prime */ |
|||
n2m1(n) = { |
|||
for(m = 0, 10^300, |
|||
if(isprime(n * 2^m + 1), return([1, m])); |
|||
); |
|||
return([0, 0]); |
|||
} |
|||
{ |
|||
print(" N M Prime\n------------------"); |
|||
for(n = 1, 400, |
|||
result = n2m1(n); |
|||
if(result[1], |
|||
print(Str(n) " " Str(result[2]) " " n * 2^result[2] + 1); |
|||
); |
|||
); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:12ex;overflow:scroll;"> |
|||
N M Prime |
|||
------------------ |
|||
1 0 2 |
|||
2 0 3 |
|||
3 1 7 |
|||
4 0 5 |
|||
5 1 11 |
|||
6 0 7 |
|||
7 2 29 |
|||
8 1 17 |
|||
9 1 19 |
|||
10 0 11 |
|||
11 1 23 |
|||
12 0 13 |
|||
13 2 53 |
|||
14 1 29 |
|||
15 1 31 |
|||
16 0 17 |
|||
17 3 137 |
|||
18 0 19 |
|||
19 6 1217 |
|||
20 1 41 |
|||
21 1 43 |
|||
22 0 23 |
|||
23 1 47 |
|||
24 2 97 |
|||
25 2 101 |
|||
26 1 53 |
|||
27 2 109 |
|||
28 0 29 |
|||
29 1 59 |
|||
30 0 31 |
|||
31 8 7937 |
|||
32 3 257 |
|||
33 1 67 |
|||
34 2 137 |
|||
35 1 71 |
|||
36 0 37 |
|||
37 2 149 |
|||
38 5 1217 |
|||
39 1 79 |
|||
40 0 41 |
|||
41 1 83 |
|||
42 0 43 |
|||
43 2 173 |
|||
44 1 89 |
|||
45 2 181 |
|||
46 0 47 |
|||
47 583 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
48 1 97 |
|||
49 2 197 |
|||
50 1 101 |
|||
51 1 103 |
|||
52 0 53 |
|||
53 1 107 |
|||
54 1 109 |
|||
55 4 881 |
|||
56 1 113 |
|||
57 2 229 |
|||
58 0 59 |
|||
59 5 1889 |
|||
60 0 61 |
|||
61 4 977 |
|||
62 7 7937 |
|||
63 1 127 |
|||
64 2 257 |
|||
65 1 131 |
|||
66 0 67 |
|||
67 2 269 |
|||
68 1 137 |
|||
69 1 139 |
|||
70 0 71 |
|||
71 3 569 |
|||
72 0 73 |
|||
73 2 293 |
|||
74 1 149 |
|||
75 1 151 |
|||
76 4 1217 |
|||
77 3 617 |
|||
78 0 79 |
|||
79 2 317 |
|||
80 3 641 |
|||
81 1 163 |
|||
82 0 83 |
|||
83 1 167 |
|||
84 2 337 |
|||
85 4 1361 |
|||
86 1 173 |
|||
87 2 349 |
|||
88 0 89 |
|||
89 1 179 |
|||
90 1 181 |
|||
91 8 23297 |
|||
92 7 11777 |
|||
93 2 373 |
|||
94 582 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
95 1 191 |
|||
96 0 97 |
|||
97 2 389 |
|||
98 1 197 |
|||
99 1 199 |
|||
100 0 101 |
|||
101 3 809 |
|||
102 0 103 |
|||
103 16 6750209 |
|||
104 5 3329 |
|||
105 1 211 |
|||
106 0 107 |
|||
107 3 857 |
|||
108 0 109 |
|||
109 6 6977 |
|||
110 3 881 |
|||
111 1 223 |
|||
112 0 113 |
|||
113 1 227 |
|||
114 1 229 |
|||
115 2 461 |
|||
116 1 233 |
|||
117 3 937 |
|||
118 4 1889 |
|||
119 1 239 |
|||
120 1 241 |
|||
121 8 30977 |
|||
122 3 977 |
|||
123 6 7873 |
|||
124 6 7937 |
|||
125 1 251 |
|||
126 0 127 |
|||
127 2 509 |
|||
128 1 257 |
|||
129 3 1033 |
|||
130 0 131 |
|||
131 1 263 |
|||
132 4 2113 |
|||
133 4 2129 |
|||
134 1 269 |
|||
135 1 271 |
|||
136 0 137 |
|||
137 3 1097 |
|||
138 0 139 |
|||
139 2 557 |
|||
140 1 281 |
|||
141 1 283 |
|||
142 2 569 |
|||
143 53 1288029493427961857 |
|||
144 2 577 |
|||
145 6 9281 |
|||
146 1 293 |
|||
147 8 37633 |
|||
148 0 149 |
|||
149 3 1193 |
|||
150 0 151 |
|||
151 4 2417 |
|||
152 3 1217 |
|||
153 1 307 |
|||
154 2 617 |
|||
155 1 311 |
|||
156 0 157 |
|||
157 8 40193 |
|||
158 1 317 |
|||
159 6 10177 |
|||
160 2 641 |
|||
161 3 1289 |
|||
162 0 163 |
|||
163 2 653 |
|||
164 9 83969 |
|||
165 1 331 |
|||
166 0 167 |
|||
167 7 21377 |
|||
168 1 337 |
|||
169 2 677 |
|||
170 3 1361 |
|||
171 8 43777 |
|||
172 0 173 |
|||
173 1 347 |
|||
174 1 349 |
|||
175 2 701 |
|||
176 1 353 |
|||
177 2 709 |
|||
178 0 179 |
|||
179 1 359 |
|||
180 0 181 |
|||
181 4 2897 |
|||
182 7 23297 |
|||
183 1 367 |
|||
184 6 11777 |
|||
185 3 1481 |
|||
186 1 373 |
|||
187 6 11969 |
|||
188 581 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
189 1 379 |
|||
190 0 191 |
|||
191 1 383 |
|||
192 0 193 |
|||
193 2 773 |
|||
194 1 389 |
|||
195 4 3121 |
|||
196 0 197 |
|||
197 15 6455297 |
|||
198 0 199 |
|||
199 2 797 |
|||
200 1 401 |
|||
201 3 1609 |
|||
202 2 809 |
|||
203 13 1662977 |
|||
204 1 409 |
|||
205 2 821 |
|||
206 15 6750209 |
|||
207 2 829 |
|||
208 4 3329 |
|||
209 1 419 |
|||
210 0 211 |
|||
211 20 221249537 |
|||
212 3 1697 |
|||
213 2 853 |
|||
214 2 857 |
|||
215 1 431 |
|||
216 1 433 |
|||
217 66 16011773855979890802689 |
|||
218 5 6977 |
|||
219 1 439 |
|||
220 2 881 |
|||
221 1 443 |
|||
222 0 223 |
|||
223 8 57089 |
|||
224 1 449 |
|||
225 3 1801 |
|||
226 0 227 |
|||
227 11 464897 |
|||
228 0 229 |
|||
229 6 14657 |
|||
230 1 461 |
|||
231 1 463 |
|||
232 0 233 |
|||
233 1 467 |
|||
234 2 937 |
|||
235 2 941 |
|||
236 3 1889 |
|||
237 4 3793 |
|||
238 0 239 |
|||
239 1 479 |
|||
240 0 241 |
|||
241 36 16561393893377 |
|||
242 7 30977 |
|||
243 1 487 |
|||
244 2 977 |
|||
245 1 491 |
|||
246 5 7873 |
|||
247 6 15809 |
|||
248 5 7937 |
|||
249 1 499 |
|||
250 0 251 |
|||
251 1 503 |
|||
252 2 1009 |
|||
253 2 1013 |
|||
254 1 509 |
|||
255 2 1021 |
|||
256 0 257 |
|||
257 279 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 |
|||
258 2 1033 |
|||
259 38 71193377898497 |
|||
260 1 521 |
|||
261 1 523 |
|||
262 0 263 |
|||
263 29 141197049857 |
|||
264 3 2113 |
|||
265 2 1061 |
|||
266 3 2129 |
|||
267 2 1069 |
|||
268 0 269 |
|||
269 3 2153 |
|||
270 0 271 |
|||
271 4 4337 |
|||
272 11 557057 |
|||
273 1 547 |
|||
274 2 1097 |
|||
275 7 35201 |
|||
276 0 277 |
|||
277 2 1109 |
|||
278 1 557 |
|||
279 2 1117 |
|||
280 0 281 |
|||
281 1 563 |
|||
282 0 283 |
|||
283 30 303868936193 |
|||
284 1 569 |
|||
285 1 571 |
|||
286 52 1288029493427961857 |
|||
287 3 2297 |
|||
288 1 577 |
|||
289 10 295937 |
|||
290 5 9281 |
|||
291 4 4657 |
|||
292 0 293 |
|||
293 1 587 |
|||
294 7 37633 |
|||
295 2 1181 |
|||
296 1 593 |
|||
297 3 2377 |
|||
298 2 1193 |
|||
299 1 599 |
|||
300 1 601 |
|||
301 4 4817 |
|||
302 3 2417 |
|||
303 1 607 |
|||
304 2 1217 |
|||
305 3 2441 |
|||
306 0 307 |
|||
307 2 1229 |
|||
308 1 617 |
|||
309 1 619 |
|||
310 0 311 |
|||
311 9 159233 |
|||
312 0 313 |
|||
313 4 5009 |
|||
314 7 40193 |
|||
315 1 631 |
|||
316 0 317 |
|||
317 7 40577 |
|||
318 5 10177 |
|||
319 2 1277 |
|||
320 1 641 |
|||
321 1 643 |
|||
322 2 1289 |
|||
323 1 647 |
|||
324 2 1297 |
|||
325 2 1301 |
|||
326 1 653 |
|||
327 3 2617 |
|||
328 8 83969 |
|||
329 1 659 |
|||
330 0 331 |
|||
331 4 5297 |
|||
332 3 2657 |
|||
333 5 10657 |
|||
334 6 21377 |
|||
335 19 175636481 |
|||
336 0 337 |
|||
337 4 5393 |
|||
338 1 677 |
|||
339 3 2713 |
|||
340 2 1361 |
|||
341 1 683 |
|||
342 7 43777 |
|||
343 2 1373 |
|||
344 3 2753 |
|||
345 1 691 |
|||
346 0 347 |
|||
347 3 2777 |
|||
348 0 349 |
|||
349 10 357377 |
|||
350 1 701 |
|||
351 12 1437697 |
|||
352 0 353 |
|||
353 21 740294657 |
|||
354 1 709 |
|||
355 6 22721 |
|||
356 5 11393 |
|||
357 2 1429 |
|||
358 0 359 |
|||
359 1 719 |
|||
360 6 23041 |
|||
361 28 96905199617 |
|||
362 3 2897 |
|||
363 1 727 |
|||
364 6 23297 |
|||
365 5 11681 |
|||
366 0 367 |
|||
367 12 1503233 |
|||
368 5 11777 |
|||
369 1 739 |
|||
370 2 1481 |
|||
371 1 743 |
|||
372 0 373 |
|||
373 2 1493 |
|||
374 5 11969 |
|||
375 1 751 |
|||
376 580 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
377 11 772097 |
|||
378 0 379 |
|||
379 14 6209537 |
|||
380 1 761 |
|||
381 3 3049 |
|||
382 0 383 |
|||
383 6393 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337 |
|||
384 1 769 |
|||
385 8 98561 |
|||
386 1 773 |
|||
387 2 1549 |
|||
388 0 389 |
|||
389 11 796673 |
|||
390 3 3121 |
|||
391 4 6257 |
|||
392 3 3137 |
|||
393 1 787 |
|||
394 14 6455297 |
|||
395 5 12641 |
|||
396 0 397 |
|||
397 4 6353 |
|||
398 1 797 |
|||
399 2 1597 |
|||
400 0 401 |
|||
</pre> |
</pre> |
||
| Line 1,620: | Line 2,644: | ||
<!--</syntaxhighlight>--> |
<!--</syntaxhighlight>--> |
||
Output same as Wren (plus a few not particularly helpful digit counts). |
Output same as Wren (plus a few not particularly helpful digit counts). |
||
=={{header|Python}}== |
|||
{{libheader|gmpy2}} |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="python" line> # primesn2m1.py by Xing216 |
|||
from gmpy2 import is_prime, mpz |
|||
print(" n m prime") |
|||
for n in range(1, 401): |
|||
m = 0 |
|||
term = mpz(n) |
|||
while True: |
|||
if is_prime(term + 1): |
|||
print(f"{n:3d} {m} {term + 1:5d}") |
|||
break |
|||
m += 1 |
|||
term *= 2 |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:20ex"> |
|||
n m prime |
|||
1 0 2 |
|||
2 0 3 |
|||
3 1 7 |
|||
4 0 5 |
|||
5 1 11 |
|||
6 0 7 |
|||
7 2 29 |
|||
8 1 17 |
|||
9 1 19 |
|||
10 0 11 |
|||
11 1 23 |
|||
12 0 13 |
|||
13 2 53 |
|||
14 1 29 |
|||
15 1 31 |
|||
16 0 17 |
|||
17 3 137 |
|||
18 0 19 |
|||
19 6 1217 |
|||
20 1 41 |
|||
21 1 43 |
|||
22 0 23 |
|||
23 1 47 |
|||
24 2 97 |
|||
25 2 101 |
|||
26 1 53 |
|||
27 2 109 |
|||
28 0 29 |
|||
29 1 59 |
|||
30 0 31 |
|||
31 8 7937 |
|||
32 3 257 |
|||
33 1 67 |
|||
34 2 137 |
|||
35 1 71 |
|||
36 0 37 |
|||
37 2 149 |
|||
38 5 1217 |
|||
39 1 79 |
|||
40 0 41 |
|||
41 1 83 |
|||
42 0 43 |
|||
43 2 173 |
|||
44 1 89 |
|||
45 2 181 |
|||
46 0 47 |
|||
47 583 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
48 1 97 |
|||
49 2 197 |
|||
50 1 101 |
|||
51 1 103 |
|||
52 0 53 |
|||
53 1 107 |
|||
54 1 109 |
|||
55 4 881 |
|||
56 1 113 |
|||
57 2 229 |
|||
58 0 59 |
|||
59 5 1889 |
|||
60 0 61 |
|||
61 4 977 |
|||
62 7 7937 |
|||
63 1 127 |
|||
64 2 257 |
|||
65 1 131 |
|||
66 0 67 |
|||
67 2 269 |
|||
68 1 137 |
|||
69 1 139 |
|||
70 0 71 |
|||
71 3 569 |
|||
72 0 73 |
|||
73 2 293 |
|||
74 1 149 |
|||
75 1 151 |
|||
76 4 1217 |
|||
77 3 617 |
|||
78 0 79 |
|||
79 2 317 |
|||
80 3 641 |
|||
81 1 163 |
|||
82 0 83 |
|||
83 1 167 |
|||
84 2 337 |
|||
85 4 1361 |
|||
86 1 173 |
|||
87 2 349 |
|||
88 0 89 |
|||
89 1 179 |
|||
90 1 181 |
|||
91 8 23297 |
|||
92 7 11777 |
|||
93 2 373 |
|||
94 582 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
95 1 191 |
|||
96 0 97 |
|||
97 2 389 |
|||
98 1 197 |
|||
99 1 199 |
|||
100 0 101 |
|||
101 3 809 |
|||
102 0 103 |
|||
103 16 6750209 |
|||
104 5 3329 |
|||
105 1 211 |
|||
106 0 107 |
|||
107 3 857 |
|||
108 0 109 |
|||
109 6 6977 |
|||
110 3 881 |
|||
111 1 223 |
|||
112 0 113 |
|||
113 1 227 |
|||
114 1 229 |
|||
115 2 461 |
|||
116 1 233 |
|||
117 3 937 |
|||
118 4 1889 |
|||
119 1 239 |
|||
120 1 241 |
|||
121 8 30977 |
|||
122 3 977 |
|||
123 6 7873 |
|||
124 6 7937 |
|||
125 1 251 |
|||
126 0 127 |
|||
127 2 509 |
|||
128 1 257 |
|||
129 3 1033 |
|||
130 0 131 |
|||
131 1 263 |
|||
132 4 2113 |
|||
133 4 2129 |
|||
134 1 269 |
|||
135 1 271 |
|||
136 0 137 |
|||
137 3 1097 |
|||
138 0 139 |
|||
139 2 557 |
|||
140 1 281 |
|||
141 1 283 |
|||
142 2 569 |
|||
143 53 1288029493427961857 |
|||
144 2 577 |
|||
145 6 9281 |
|||
146 1 293 |
|||
147 8 37633 |
|||
148 0 149 |
|||
149 3 1193 |
|||
150 0 151 |
|||
151 4 2417 |
|||
152 3 1217 |
|||
153 1 307 |
|||
154 2 617 |
|||
155 1 311 |
|||
156 0 157 |
|||
157 8 40193 |
|||
158 1 317 |
|||
159 6 10177 |
|||
160 2 641 |
|||
161 3 1289 |
|||
162 0 163 |
|||
163 2 653 |
|||
164 9 83969 |
|||
165 1 331 |
|||
166 0 167 |
|||
167 7 21377 |
|||
168 1 337 |
|||
169 2 677 |
|||
170 3 1361 |
|||
171 8 43777 |
|||
172 0 173 |
|||
173 1 347 |
|||
174 1 349 |
|||
175 2 701 |
|||
176 1 353 |
|||
177 2 709 |
|||
178 0 179 |
|||
179 1 359 |
|||
180 0 181 |
|||
181 4 2897 |
|||
182 7 23297 |
|||
183 1 367 |
|||
184 6 11777 |
|||
185 3 1481 |
|||
186 1 373 |
|||
187 6 11969 |
|||
188 581 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
189 1 379 |
|||
190 0 191 |
|||
191 1 383 |
|||
192 0 193 |
|||
193 2 773 |
|||
194 1 389 |
|||
195 4 3121 |
|||
196 0 197 |
|||
197 15 6455297 |
|||
198 0 199 |
|||
199 2 797 |
|||
200 1 401 |
|||
201 3 1609 |
|||
202 2 809 |
|||
203 13 1662977 |
|||
204 1 409 |
|||
205 2 821 |
|||
206 15 6750209 |
|||
207 2 829 |
|||
208 4 3329 |
|||
209 1 419 |
|||
210 0 211 |
|||
211 20 221249537 |
|||
212 3 1697 |
|||
213 2 853 |
|||
214 2 857 |
|||
215 1 431 |
|||
216 1 433 |
|||
217 66 16011773855979890802689 |
|||
218 5 6977 |
|||
219 1 439 |
|||
220 2 881 |
|||
221 1 443 |
|||
222 0 223 |
|||
223 8 57089 |
|||
224 1 449 |
|||
225 3 1801 |
|||
226 0 227 |
|||
227 11 464897 |
|||
228 0 229 |
|||
229 6 14657 |
|||
230 1 461 |
|||
231 1 463 |
|||
232 0 233 |
|||
233 1 467 |
|||
234 2 937 |
|||
235 2 941 |
|||
236 3 1889 |
|||
237 4 3793 |
|||
238 0 239 |
|||
239 1 479 |
|||
240 0 241 |
|||
241 36 16561393893377 |
|||
242 7 30977 |
|||
243 1 487 |
|||
244 2 977 |
|||
245 1 491 |
|||
246 5 7873 |
|||
247 6 15809 |
|||
248 5 7937 |
|||
249 1 499 |
|||
250 0 251 |
|||
251 1 503 |
|||
252 2 1009 |
|||
253 2 1013 |
|||
254 1 509 |
|||
255 2 1021 |
|||
256 0 257 |
|||
257 279 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 |
|||
258 2 1033 |
|||
259 38 71193377898497 |
|||
260 1 521 |
|||
261 1 523 |
|||
262 0 263 |
|||
263 29 141197049857 |
|||
264 3 2113 |
|||
265 2 1061 |
|||
266 3 2129 |
|||
267 2 1069 |
|||
268 0 269 |
|||
269 3 2153 |
|||
270 0 271 |
|||
271 4 4337 |
|||
272 11 557057 |
|||
273 1 547 |
|||
274 2 1097 |
|||
275 7 35201 |
|||
276 0 277 |
|||
277 2 1109 |
|||
278 1 557 |
|||
279 2 1117 |
|||
280 0 281 |
|||
281 1 563 |
|||
282 0 283 |
|||
283 30 303868936193 |
|||
284 1 569 |
|||
285 1 571 |
|||
286 52 1288029493427961857 |
|||
287 3 2297 |
|||
288 1 577 |
|||
289 10 295937 |
|||
290 5 9281 |
|||
291 4 4657 |
|||
292 0 293 |
|||
293 1 587 |
|||
294 7 37633 |
|||
295 2 1181 |
|||
296 1 593 |
|||
297 3 2377 |
|||
298 2 1193 |
|||
299 1 599 |
|||
300 1 601 |
|||
301 4 4817 |
|||
302 3 2417 |
|||
303 1 607 |
|||
304 2 1217 |
|||
305 3 2441 |
|||
306 0 307 |
|||
307 2 1229 |
|||
308 1 617 |
|||
309 1 619 |
|||
310 0 311 |
|||
311 9 159233 |
|||
312 0 313 |
|||
313 4 5009 |
|||
314 7 40193 |
|||
315 1 631 |
|||
316 0 317 |
|||
317 7 40577 |
|||
318 5 10177 |
|||
319 2 1277 |
|||
320 1 641 |
|||
321 1 643 |
|||
322 2 1289 |
|||
323 1 647 |
|||
324 2 1297 |
|||
325 2 1301 |
|||
326 1 653 |
|||
327 3 2617 |
|||
328 8 83969 |
|||
329 1 659 |
|||
330 0 331 |
|||
331 4 5297 |
|||
332 3 2657 |
|||
333 5 10657 |
|||
334 6 21377 |
|||
335 19 175636481 |
|||
336 0 337 |
|||
337 4 5393 |
|||
338 1 677 |
|||
339 3 2713 |
|||
340 2 1361 |
|||
341 1 683 |
|||
342 7 43777 |
|||
343 2 1373 |
|||
344 3 2753 |
|||
345 1 691 |
|||
346 0 347 |
|||
347 3 2777 |
|||
348 0 349 |
|||
349 10 357377 |
|||
350 1 701 |
|||
351 12 1437697 |
|||
352 0 353 |
|||
353 21 740294657 |
|||
354 1 709 |
|||
355 6 22721 |
|||
356 5 11393 |
|||
357 2 1429 |
|||
358 0 359 |
|||
359 1 719 |
|||
360 6 23041 |
|||
361 28 96905199617 |
|||
362 3 2897 |
|||
363 1 727 |
|||
364 6 23297 |
|||
365 5 11681 |
|||
366 0 367 |
|||
367 12 1503233 |
|||
368 5 11777 |
|||
369 1 739 |
|||
370 2 1481 |
|||
371 1 743 |
|||
372 0 373 |
|||
373 2 1493 |
|||
374 5 11969 |
|||
375 1 751 |
|||
376 580 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 |
|||
377 11 772097 |
|||
378 0 379 |
|||
379 14 6209537 |
|||
380 1 761 |
|||
381 3 3049 |
|||
382 0 383 |
|||
383 6393 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337 |
|||
384 1 769 |
|||
385 8 98561 |
|||
386 1 773 |
|||
387 2 1549 |
|||
388 0 389 |
|||
389 11 796673 |
|||
390 3 3121 |
|||
391 4 6257 |
|||
392 3 3137 |
|||
393 1 787 |
|||
394 14 6455297 |
|||
395 5 12641 |
|||
396 0 397 |
|||
397 4 6353 |
|||
398 1 797 |
|||
399 2 1597 |
|||
400 0 401 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
First 382 in less than a second. 383 pushes the total accumulated time over 25 seconds. |
First 382 in less than a second. 383 pushes the total accumulated time over 25 seconds. |
||
| Line 2,025: | Line 3,469: | ||
399 2: 1597 |
399 2: 1597 |
||
400 0: 401</pre> |
400 0: 401</pre> |
||
=={{header|RPL}}== |
|||
As big ints are limited to 499 digits, it is not possible to calculate the 47th prime number. |
|||
{{works with|HP|49}} |
|||
« <span style="color:red">{ } |
|||
1 45</span> '''FOR''' n |
|||
<span style="color:red">0</span> |
|||
'''WHILE''' <span style="color:red">2</span> OVER ^ n * <span style="color:red">1</span> + DUP ISPRIME? NOT '''REPEAT''' |
|||
DROP <span style="color:red">1</span> + |
|||
'''END''' |
|||
NIP + |
|||
'''NEXT''' |
|||
» '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
1: { 2 3 7 5 11 7 29 17 19 11 23 13 53 29 31 17 137 19 1217 41 43 23 47 97 101 53 109 29 59 31 7937 257 67 137 71 37 149 1217 79 41 83 43 173 89 181 } |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Perl}} |
|||
Takes ~2 seconds to run. |
|||
<syntaxhighlight lang="ruby" line>for n in (1..400) { |
|||
var p = (^Inf -> lazy.map {|m| [m, n * 2**m + 1] }.first_by { .tail.is_prime }) |
|||
printf("%3s %4s: %s\n", n, p...) |
|||
}</syntaxhighlight> |
|||
(same output as the Perl version) |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-gmp}} |
{{libheader|Wren-gmp}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
<syntaxhighlight lang=" |
<syntaxhighlight lang="wren">import "./gmp" for Mpz |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Revision as of 01:09, 29 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
- Find and display the first 45 (n) primes of the form n × 2m + 1 where m is the smallest valid non-negative integer.
- Stretch
- Find and display the first 50 (n) primes of the form n × 2m + 1 where m is the smallest valid non-negative integer.
- Stretch harder
- Find and display the first 400 (n) primes of the form n × 2m + 1 where m is the smallest valid non-negative integer. Specifically term 383.
- See also
A050921 - Smallest prime of form n*2^m+1
ALGOL 68
Doesn't attempt the stretchier stretch goal but does show the primes up to 400 with up to 2000 digits and m at most 600 which turns out to be all of them except for 383.
The values of the primes are interesting - most will fit in 64 bits (those up to 45 will fit in 16 bits) but there are a small number that have hundreds or thousands of digits.
NB the primes.incl.a68 source is available on a page in Rosetta Code - see the library above.
BEGIN # find primes of the form 1+n*2^m where m is the lowest integer >= 0 #
# such that 1+n*2^m is prime #
PR read "primes.incl.a68" PR # include peime utilities #
PR precision 2000 PR # set the precision of LONG LONG INT #
INT max m := 600; # maximum m we will consider #
FOR n TO 400 DO
INT m := 0;
LONG LONG INT two to m := 1;
LONG LONG INT p := 0;
BOOL not found := TRUE;
WHILE not found AND m <= max m DO
IF not found := NOT is probably prime( p := ( LENG LENG n * two to m ) + 1 ) THEN
two to m *:= 2;
m +:= 1
FI
OD;
IF not found THEN
print( ( whole( n, -3 ), " not found", newline ) )
ELSE
print( ( whole( n, -3 ), " ", whole( m, -8 ), ": ", whole( p, 0 ), newline ) )
FI
OD
END- Output:
1 0: 2 2 0: 3 3 1: 7 4 0: 5 5 1: 11 6 0: 7 7 2: 29 8 1: 17 9 1: 19 10 0: 11 11 1: 23 12 0: 13 13 2: 53 14 1: 29 15 1: 31 16 0: 17 17 3: 137 18 0: 19 19 6: 1217 20 1: 41 21 1: 43 22 0: 23 23 1: 47 24 2: 97 25 2: 101 26 1: 53 27 2: 109 28 0: 29 29 1: 59 30 0: 31 31 8: 7937 32 3: 257 33 1: 67 34 2: 137 35 1: 71 36 0: 37 37 2: 149 38 5: 1217 39 1: 79 40 0: 41 41 1: 83 42 0: 43 43 2: 173 44 1: 89 45 2: 181 46 0: 47 47 583: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 48 1: 97 49 2: 197 50 1: 101 51 1: 103 52 0: 53 53 1: 107 54 1: 109 55 4: 881 56 1: 113 57 2: 229 58 0: 59 59 5: 1889 60 0: 61 61 4: 977 62 7: 7937 63 1: 127 64 2: 257 65 1: 131 66 0: 67 67 2: 269 68 1: 137 69 1: 139 70 0: 71 71 3: 569 72 0: 73 73 2: 293 74 1: 149 75 1: 151 76 4: 1217 77 3: 617 78 0: 79 79 2: 317 80 3: 641 81 1: 163 82 0: 83 83 1: 167 84 2: 337 85 4: 1361 86 1: 173 87 2: 349 88 0: 89 89 1: 179 90 1: 181 91 8: 23297 92 7: 11777 93 2: 373 94 582: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 95 1: 191 96 0: 97 97 2: 389 98 1: 197 99 1: 199 100 0: 101 101 3: 809 102 0: 103 103 16: 6750209 104 5: 3329 105 1: 211 106 0: 107 107 3: 857 108 0: 109 109 6: 6977 110 3: 881 111 1: 223 112 0: 113 113 1: 227 114 1: 229 115 2: 461 116 1: 233 117 3: 937 118 4: 1889 119 1: 239 120 1: 241 121 8: 30977 122 3: 977 123 6: 7873 124 6: 7937 125 1: 251 126 0: 127 127 2: 509 128 1: 257 129 3: 1033 130 0: 131 131 1: 263 132 4: 2113 133 4: 2129 134 1: 269 135 1: 271 136 0: 137 137 3: 1097 138 0: 139 139 2: 557 140 1: 281 141 1: 283 142 2: 569 143 53: 1288029493427961857 144 2: 577 145 6: 9281 146 1: 293 147 8: 37633 148 0: 149 149 3: 1193 150 0: 151 151 4: 2417 152 3: 1217 153 1: 307 154 2: 617 155 1: 311 156 0: 157 157 8: 40193 158 1: 317 159 6: 10177 160 2: 641 161 3: 1289 162 0: 163 163 2: 653 164 9: 83969 165 1: 331 166 0: 167 167 7: 21377 168 1: 337 169 2: 677 170 3: 1361 171 8: 43777 172 0: 173 173 1: 347 174 1: 349 175 2: 701 176 1: 353 177 2: 709 178 0: 179 179 1: 359 180 0: 181 181 4: 2897 182 7: 23297 183 1: 367 184 6: 11777 185 3: 1481 186 1: 373 187 6: 11969 188 581: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 189 1: 379 190 0: 191 191 1: 383 192 0: 193 193 2: 773 194 1: 389 195 4: 3121 196 0: 197 197 15: 6455297 198 0: 199 199 2: 797 200 1: 401 201 3: 1609 202 2: 809 203 13: 1662977 204 1: 409 205 2: 821 206 15: 6750209 207 2: 829 208 4: 3329 209 1: 419 210 0: 211 211 20: 221249537 212 3: 1697 213 2: 853 214 2: 857 215 1: 431 216 1: 433 217 66: 16011773855979890802689 218 5: 6977 219 1: 439 220 2: 881 221 1: 443 222 0: 223 223 8: 57089 224 1: 449 225 3: 1801 226 0: 227 227 11: 464897 228 0: 229 229 6: 14657 230 1: 461 231 1: 463 232 0: 233 233 1: 467 234 2: 937 235 2: 941 236 3: 1889 237 4: 3793 238 0: 239 239 1: 479 240 0: 241 241 36: 16561393893377 242 7: 30977 243 1: 487 244 2: 977 245 1: 491 246 5: 7873 247 6: 15809 248 5: 7937 249 1: 499 250 0: 251 251 1: 503 252 2: 1009 253 2: 1013 254 1: 509 255 2: 1021 256 0: 257 257 279: 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 258 2: 1033 259 38: 71193377898497 260 1: 521 261 1: 523 262 0: 263 263 29: 141197049857 264 3: 2113 265 2: 1061 266 3: 2129 267 2: 1069 268 0: 269 269 3: 2153 270 0: 271 271 4: 4337 272 11: 557057 273 1: 547 274 2: 1097 275 7: 35201 276 0: 277 277 2: 1109 278 1: 557 279 2: 1117 280 0: 281 281 1: 563 282 0: 283 283 30: 303868936193 284 1: 569 285 1: 571 286 52: 1288029493427961857 287 3: 2297 288 1: 577 289 10: 295937 290 5: 9281 291 4: 4657 292 0: 293 293 1: 587 294 7: 37633 295 2: 1181 296 1: 593 297 3: 2377 298 2: 1193 299 1: 599 300 1: 601 301 4: 4817 302 3: 2417 303 1: 607 304 2: 1217 305 3: 2441 306 0: 307 307 2: 1229 308 1: 617 309 1: 619 310 0: 311 311 9: 159233 312 0: 313 313 4: 5009 314 7: 40193 315 1: 631 316 0: 317 317 7: 40577 318 5: 10177 319 2: 1277 320 1: 641 321 1: 643 322 2: 1289 323 1: 647 324 2: 1297 325 2: 1301 326 1: 653 327 3: 2617 328 8: 83969 329 1: 659 330 0: 331 331 4: 5297 332 3: 2657 333 5: 10657 334 6: 21377 335 19: 175636481 336 0: 337 337 4: 5393 338 1: 677 339 3: 2713 340 2: 1361 341 1: 683 342 7: 43777 343 2: 1373 344 3: 2753 345 1: 691 346 0: 347 347 3: 2777 348 0: 349 349 10: 357377 350 1: 701 351 12: 1437697 352 0: 353 353 21: 740294657 354 1: 709 355 6: 22721 356 5: 11393 357 2: 1429 358 0: 359 359 1: 719 360 6: 23041 361 28: 96905199617 362 3: 2897 363 1: 727 364 6: 23297 365 5: 11681 366 0: 367 367 12: 1503233 368 5: 11777 369 1: 739 370 2: 1481 371 1: 743 372 0: 373 373 2: 1493 374 5: 11969 375 1: 751 376 580: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 377 11: 772097 378 0: 379 379 14: 6209537 380 1: 761 381 3: 3049 382 0: 383 383 not found 384 1: 769 385 8: 98561 386 1: 773 387 2: 1549 388 0: 389 389 11: 796673 390 3: 3121 391 4: 6257 392 3: 3137 393 1: 787 394 14: 6455297 395 5: 12641 396 0: 397 397 4: 6353 398 1: 797 399 2: 1597 400 0: 401
ALGOL W
Although most of the primes up to 500 will fit in 32 bits, obviously 383 won't, having over 6000 digits, so this doesn;t attempt to show more than the first 45. NB: 47 is the first prime that won't fit in 32 bits.
begin % find primes of the form 1+n*2^m where m is the lowest integer >= 0 %
% such that 1+n*2^m is prime %
integer MAX_M, MAX_PRIME;
MAX_M := 22;
MAX_PRIME := 10000;
begin
logical array prime ( 1 :: MAX_PRIME );
% sieve the primes to MAX_PRIME %
prime( 1 ) := false; prime( 2 ) := true;
for i := 3 step 2 until MAX_PRIME do prime( i ) := true;
for i := 4 step 2 until MAX_PRIME do prime( i ) := false;
for i := 3 step 2 until truncate( sqrt( MAX_PRIME ) ) do begin
integer ii; ii := i + i;
if prime( i ) then for pr := i * i step ii until MAX_PRIME do prime( pr ) := false
end for_i ;
% find the n*2^m + 1 primes %
for n := 1 until 45 do begin
integer m, twoToM, p;
logical notFound;
m := 0;
twoToM := 1;
p := 0;
notFound := true;
while notFound and m <= MAX_M do begin
p := ( n * twoToM ) + 1;
notFound := not prime( p );
if notFound then begin
twoToM := twoToM + twoToM;
m := m + 1
end if_notFound
end while_notFound_and_m_le_MAX_M ;
if notFound
then writeon( i_w := 3, s_w := 0, "(", n, " not found)" )
else writeon( i_w := 3, s_w := 0, "(", n, " ", i_w := 1, m, ": ", i_w := 4, p, " )" );
if n rem 5 = 0 then write()
end for_n
end
end.- Output:
( 1 0: 2 )( 2 0: 3 )( 3 1: 7 )( 4 0: 5 )( 5 1: 11 ) ( 6 0: 7 )( 7 2: 29 )( 8 1: 17 )( 9 1: 19 )( 10 0: 11 ) ( 11 1: 23 )( 12 0: 13 )( 13 2: 53 )( 14 1: 29 )( 15 1: 31 ) ( 16 0: 17 )( 17 3: 137 )( 18 0: 19 )( 19 6: 1217 )( 20 1: 41 ) ( 21 1: 43 )( 22 0: 23 )( 23 1: 47 )( 24 2: 97 )( 25 2: 101 ) ( 26 1: 53 )( 27 2: 109 )( 28 0: 29 )( 29 1: 59 )( 30 0: 31 ) ( 31 8: 7937 )( 32 3: 257 )( 33 1: 67 )( 34 2: 137 )( 35 1: 71 ) ( 36 0: 37 )( 37 2: 149 )( 38 5: 1217 )( 39 1: 79 )( 40 0: 41 ) ( 41 1: 83 )( 42 0: 43 )( 43 2: 173 )( 44 1: 89 )( 45 2: 181 )
Arturo
cnt: 0
n: 1
while [cnt < 45][
m: 0
while [true][
p: inc n * 2^m
if prime? p [
print ["n:" n "m:" m "p:" p]
inc 'cnt
break
]
inc 'm
]
inc 'n
]
- Output:
n: 1 m: 0 p: 2 n: 2 m: 0 p: 3 n: 3 m: 1 p: 7 n: 4 m: 0 p: 5 n: 5 m: 1 p: 11 n: 6 m: 0 p: 7 n: 7 m: 2 p: 29 n: 8 m: 1 p: 17 n: 9 m: 1 p: 19 n: 10 m: 0 p: 11 n: 11 m: 1 p: 23 n: 12 m: 0 p: 13 n: 13 m: 2 p: 53 n: 14 m: 1 p: 29 n: 15 m: 1 p: 31 n: 16 m: 0 p: 17 n: 17 m: 3 p: 137 n: 18 m: 0 p: 19 n: 19 m: 6 p: 1217 n: 20 m: 1 p: 41 n: 21 m: 1 p: 43 n: 22 m: 0 p: 23 n: 23 m: 1 p: 47 n: 24 m: 2 p: 97 n: 25 m: 2 p: 101 n: 26 m: 1 p: 53 n: 27 m: 2 p: 109 n: 28 m: 0 p: 29 n: 29 m: 1 p: 59 n: 30 m: 0 p: 31 n: 31 m: 8 p: 7937 n: 32 m: 3 p: 257 n: 33 m: 1 p: 67 n: 34 m: 2 p: 137 n: 35 m: 1 p: 71 n: 36 m: 0 p: 37 n: 37 m: 2 p: 149 n: 38 m: 5 p: 1217 n: 39 m: 1 p: 79 n: 40 m: 0 p: 41 n: 41 m: 1 p: 83 n: 42 m: 0 p: 43 n: 43 m: 2 p: 173 n: 44 m: 1 p: 89 n: 45 m: 2 p: 181
EasyLang
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
for n = 1 to 45
m = 0
repeat
p = n * (pow 2 m) + 1
until isprim p = 1
m += 1
.
print n & " " & m & " " & p
.
FreeBASIC
#include "isprime.bas"
Print !" N M Prime\n------------------"
For n As Integer = 1 To 45
Dim As Ulongint m = 0
Do
Dim As Ulongint p = n * (2 ^ m) + 1
If isPrime(p) Then
Print Using "### #### ####"; n; m; p
Exit Do
End If
m += 1
Loop
Next n
SleepJ
' n m prime',":(,.1+(*2^])/@|:)(,.~#\)i.&1"1]1 p:1+(1+i.45) */ 2^i.9
n m prime
1 0 2
2 0 3
3 1 7
4 0 5
5 1 11
6 0 7
7 2 29
8 1 17
9 1 19
10 0 11
11 1 23
12 0 13
13 2 53
14 1 29
15 1 31
16 0 17
17 3 137
18 0 19
19 6 1217
20 1 41
21 1 43
22 0 23
23 1 47
24 2 97
25 2 101
26 1 53
27 2 109
28 0 29
29 1 59
30 0 31
31 8 7937
32 3 257
33 1 67
34 2 137
35 1 71
36 0 37
37 2 149
38 5 1217
39 1 79
40 0 41
41 1 83
42 0 43
43 2 173
44 1 89
45 2 181
(Most of the implementation here is about merging intermediate values and formatting for display. The calculation for m is i.&1"1]1 p:1+(1+i.45) */ 2^i.9 -- for n in the range 1..45, try all m exponents in the range 0..8 and find the first m value for each n which corresponds to a prime.)
jq
Works with gojq, the Go implementation of jq.
gojq supports unbounded-precision integer arithmetic but the following algorithm for prime number detection is not up to the stretch tasks.
# Input should be an integer
# No sqrt!
def isPrime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
else 5
| until( . <= 0;
if .*. > $n then -1
elif ($n % . == 0) then 0
else . + 2
| if ($n % . == 0) then 0
else . + 4
end
end)
| . == -1
end;
# Emit [m, n*2**m+1] where m is smallest non-negative integer such that n * 2**m + 1 is prime
# WARNING: continues searching ad infinitum ...
def n2m1:
. as $n
| first(
foreach range(0; infinite) as $m (null;
if . == null then 1 else 2*. end;
(. * $n + 1)
| select(isPrime) | [$m, .] ) ) ;
# The task:
"[N,M,Prime]\n------------------",
( range(1;45) | [.] + n2m1 )Invocation: jq -nrc -f n2m1.jq
- Output:
[1,0,2] [2,0,3] [3,1,7] [4,0,5] [5,1,11] [6,0,7] [7,2,29] [8,1,17] [9,1,19] [10,0,11] [11,1,23] [12,0,13] [13,2,53] [14,1,29] [15,1,31] [16,0,17] [17,3,137] [18,0,19] [19,6,1217] [20,1,41] [21,1,43] [22,0,23] [23,1,47] [24,2,97] [25,2,101] [26,1,53] [27,2,109] [28,0,29] [29,1,59] [30,0,31] [31,8,7937] [32,3,257] [33,1,67] [34,2,137] [35,1,71] [36,0,37] [37,2,149] [38,5,1217] [39,1,79] [40,0,41] [41,1,83] [42,0,43] [43,2,173] [44,1,89] [45,2,181] [46,0,47]
Julia
""" Rosetta code task: rosettacode.org/wiki/Primes:_n*2%5Em%2B1 """
using Primes
""" Return true if there is an m such that n * 2**m + 1 is prime """
function n2m1(n)
for m in big"0":big"10"^300
isprime(n * big"2"^m + 1) && return true, m
end
return false, 0
end
println(" N M Prime\n------------------")
for n in 1:400
tf, m = n2m1(n)
tf && println(lpad(n, 5), lpad(m, 5), " ", n * big"2"^m + 1)
end
- Output:
N M Prime
------------------
1 0 2
2 0 3
3 1 7
4 0 5
5 1 11
6 0 7
7 2 29
8 1 17
9 1 19
10 0 11
11 1 23
12 0 13
13 2 53
14 1 29
15 1 31
16 0 17
17 3 137
18 0 19
19 6 1217
20 1 41
21 1 43
22 0 23
23 1 47
24 2 97
25 2 101
26 1 53
27 2 109
28 0 29
29 1 59
30 0 31
31 8 7937
32 3 257
33 1 67
34 2 137
35 1 71
36 0 37
37 2 149
38 5 1217
39 1 79
40 0 41
41 1 83
42 0 43
43 2 173
44 1 89
45 2 181
46 0 47
47 583 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177
48 1 97
49 2 197
50 1 101
51 1 103
52 0 53
53 1 107
54 1 109
55 4 881
56 1 113
57 2 229
58 0 59
59 5 1889
60 0 61
61 4 977
62 7 7937
63 1 127
64 2 257
65 1 131
66 0 67
67 2 269
68 1 137
69 1 139
70 0 71
71 3 569
72 0 73
73 2 293
74 1 149
75 1 151
76 4 1217
77 3 617
78 0 79
79 2 317
80 3 641
81 1 163
82 0 83
83 1 167
84 2 337
85 4 1361
86 1 173
87 2 349
88 0 89
89 1 179
90 1 181
91 8 23297
92 7 11777
93 2 373
94 582 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177
95 1 191
96 0 97
97 2 389
98 1 197
99 1 199
100 0 101
101 3 809
102 0 103
103 16 6750209
104 5 3329
105 1 211
106 0 107
107 3 857
108 0 109
109 6 6977
110 3 881
111 1 223
112 0 113
113 1 227
114 1 229
115 2 461
116 1 233
117 3 937
118 4 1889
119 1 239
120 1 241
121 8 30977
122 3 977
123 6 7873
124 6 7937
125 1 251
126 0 127
127 2 509
128 1 257
129 3 1033
130 0 131
131 1 263
132 4 2113
133 4 2129
134 1 269
135 1 271
136 0 137
137 3 1097
138 0 139
139 2 557
140 1 281
141 1 283
142 2 569
143 53 1288029493427961857
144 2 577
145 6 9281
146 1 293
147 8 37633
148 0 149
149 3 1193
150 0 151
151 4 2417
152 3 1217
153 1 307
154 2 617
155 1 311
156 0 157
157 8 40193
158 1 317
159 6 10177
160 2 641
161 3 1289
162 0 163
163 2 653
164 9 83969
165 1 331
166 0 167
167 7 21377
168 1 337
169 2 677
170 3 1361
171 8 43777
172 0 173
173 1 347
174 1 349
175 2 701
176 1 353
177 2 709
178 0 179
179 1 359
180 0 181
181 4 2897
182 7 23297
183 1 367
184 6 11777
185 3 1481
186 1 373
187 6 11969
188 581 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177
189 1 379
190 0 191
191 1 383
192 0 193
193 2 773
194 1 389
195 4 3121
196 0 197
197 15 6455297
198 0 199
199 2 797
200 1 401
201 3 1609
202 2 809
203 13 1662977
204 1 409
205 2 821
206 15 6750209
207 2 829
208 4 3329
209 1 419
210 0 211
211 20 221249537
212 3 1697
213 2 853
214 2 857
215 1 431
216 1 433
217 66 16011773855979890802689
218 5 6977
219 1 439
220 2 881
221 1 443
222 0 223
223 8 57089
224 1 449
225 3 1801
226 0 227
227 11 464897
228 0 229
229 6 14657
230 1 461
231 1 463
232 0 233
233 1 467
234 2 937
235 2 941
236 3 1889
237 4 3793
238 0 239
239 1 479
240 0 241
241 36 16561393893377
242 7 30977
243 1 487
244 2 977
245 1 491
246 5 7873
247 6 15809
248 5 7937
249 1 499
250 0 251
251 1 503
252 2 1009
253 2 1013
254 1 509
255 2 1021
256 0 257
257 279 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617
258 2 1033
259 38 71193377898497
260 1 521
261 1 523
262 0 263
263 29 141197049857
264 3 2113
265 2 1061
266 3 2129
267 2 1069
268 0 269
269 3 2153
270 0 271
271 4 4337
272 11 557057
273 1 547
274 2 1097
275 7 35201
276 0 277
277 2 1109
278 1 557
279 2 1117
280 0 281
281 1 563
282 0 283
283 30 303868936193
284 1 569
285 1 571
286 52 1288029493427961857
287 3 2297
288 1 577
289 10 295937
290 5 9281
291 4 4657
292 0 293
293 1 587
294 7 37633
295 2 1181
296 1 593
297 3 2377
298 2 1193
299 1 599
300 1 601
301 4 4817
302 3 2417
303 1 607
304 2 1217
305 3 2441
306 0 307
307 2 1229
308 1 617
309 1 619
310 0 311
311 9 159233
312 0 313
313 4 5009
314 7 40193
315 1 631
316 0 317
317 7 40577
318 5 10177
319 2 1277
320 1 641
321 1 643
322 2 1289
323 1 647
324 2 1297
325 2 1301
326 1 653
327 3 2617
328 8 83969
329 1 659
330 0 331
331 4 5297
332 3 2657
333 5 10657
334 6 21377
335 19 175636481
336 0 337
337 4 5393
338 1 677
339 3 2713
340 2 1361
341 1 683
342 7 43777
343 2 1373
344 3 2753
345 1 691
346 0 347
347 3 2777
348 0 349
349 10 357377
350 1 701
351 12 1437697
352 0 353
353 21 740294657
354 1 709
355 6 22721
356 5 11393
357 2 1429
358 0 359
359 1 719
360 6 23041
361 28 96905199617
362 3 2897
363 1 727
364 6 23297
365 5 11681
366 0 367
367 12 1503233
368 5 11777
369 1 739
370 2 1481
371 1 743
372 0 373
373 2 1493
374 5 11969
375 1 751
376 580 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177
377 11 772097
378 0 379
379 14 6209537
380 1 761
381 3 3049
382 0 383
383 6393 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337
384 1 769
385 8 98561
386 1 773
387 2 1549
388 0 389
389 11 796673
390 3 3121
391 4 6257
392 3 3137
393 1 787
394 14 6455297
395 5 12641
396 0 397
397 4 6353
398 1 797
399 2 1597
400 0 401
Nim
Task
import std/strformat
func isPrime(n: Natural): bool =
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
echo " n m prime"
for n in 1..45:
var m = 0
var term = n
while true:
if isPrime(term + 1):
echo &"{n:2} {m} {term + 1:5}"
break
inc m
term *= 2
- Output:
> n m prime 1 0 2 2 0 3 3 1 7 4 0 5 5 1 11 6 0 7 7 2 29 8 1 17 9 1 19 10 0 11 11 1 23 12 0 13 13 2 53 14 1 29 15 1 31 16 0 17 17 3 137 18 0 19 19 6 1217 20 1 41 21 1 43 22 0 23 23 1 47 24 2 97 25 2 101 26 1 53 27 2 109 28 0 29 29 1 59 30 0 31 31 8 7937 32 3 257 33 1 67 34 2 137 35 1 71 36 0 37 37 2 149 38 5 1217 39 1 79 40 0 41 41 1 83 42 0 43 43 2 173 44 1 89 45 2 181
Stretch tasks
import std/strformat
import integers
func compressed(str: string; size: int): string =
## Return a compressed value for long strings of digits.
if str.len <= 2 * size: str
else: &"{str[0..<size]}...{str[^size..^1]} ({str.len} digits)"
echo " n m prime"
for n in 1..400:
var m = 0
var term = newInteger(n)
while true:
if isPrime(term + 1):
echo &"{n:3} {m:4} {compressed($(term + 1), 10)}"
break
inc m
term *= 2
- Output:
n m prime 1 0 2 2 0 3 3 1 7 4 0 5 5 1 11 6 0 7 7 2 29 8 1 17 9 1 19 10 0 11 11 1 23 12 0 13 13 2 53 14 1 29 15 1 31 16 0 17 17 3 137 18 0 19 19 6 1217 20 1 41 21 1 43 22 0 23 23 1 47 24 2 97 25 2 101 26 1 53 27 2 109 28 0 29 29 1 59 30 0 31 31 8 7937 32 3 257 33 1 67 34 2 137 35 1 71 36 0 37 37 2 149 38 5 1217 39 1 79 40 0 41 41 1 83 42 0 43 43 2 173 44 1 89 45 2 181 46 0 47 47 583 1487939695...6574002177 (178 digits) 48 1 97 49 2 197 50 1 101 51 1 103 52 0 53 53 1 107 54 1 109 55 4 881 56 1 113 57 2 229 58 0 59 59 5 1889 60 0 61 61 4 977 62 7 7937 63 1 127 64 2 257 65 1 131 66 0 67 67 2 269 68 1 137 69 1 139 70 0 71 71 3 569 72 0 73 73 2 293 74 1 149 75 1 151 76 4 1217 77 3 617 78 0 79 79 2 317 80 3 641 81 1 163 82 0 83 83 1 167 84 2 337 85 4 1361 86 1 173 87 2 349 88 0 89 89 1 179 90 1 181 91 8 23297 92 7 11777 93 2 373 94 582 1487939695...6574002177 (178 digits) 95 1 191 96 0 97 97 2 389 98 1 197 99 1 199 100 0 101 101 3 809 102 0 103 103 16 6750209 104 5 3329 105 1 211 106 0 107 107 3 857 108 0 109 109 6 6977 110 3 881 111 1 223 112 0 113 113 1 227 114 1 229 115 2 461 116 1 233 117 3 937 118 4 1889 119 1 239 120 1 241 121 8 30977 122 3 977 123 6 7873 124 6 7937 125 1 251 126 0 127 127 2 509 128 1 257 129 3 1033 130 0 131 131 1 263 132 4 2113 133 4 2129 134 1 269 135 1 271 136 0 137 137 3 1097 138 0 139 139 2 557 140 1 281 141 1 283 142 2 569 143 53 1288029493427961857 144 2 577 145 6 9281 146 1 293 147 8 37633 148 0 149 149 3 1193 150 0 151 151 4 2417 152 3 1217 153 1 307 154 2 617 155 1 311 156 0 157 157 8 40193 158 1 317 159 6 10177 160 2 641 161 3 1289 162 0 163 163 2 653 164 9 83969 165 1 331 166 0 167 167 7 21377 168 1 337 169 2 677 170 3 1361 171 8 43777 172 0 173 173 1 347 174 1 349 175 2 701 176 1 353 177 2 709 178 0 179 179 1 359 180 0 181 181 4 2897 182 7 23297 183 1 367 184 6 11777 185 3 1481 186 1 373 187 6 11969 188 581 1487939695...6574002177 (178 digits) 189 1 379 190 0 191 191 1 383 192 0 193 193 2 773 194 1 389 195 4 3121 196 0 197 197 15 6455297 198 0 199 199 2 797 200 1 401 201 3 1609 202 2 809 203 13 1662977 204 1 409 205 2 821 206 15 6750209 207 2 829 208 4 3329 209 1 419 210 0 211 211 20 221249537 212 3 1697 213 2 853 214 2 857 215 1 431 216 1 433 217 66 1601177385...9890802689 (23 digits) 218 5 6977 219 1 439 220 2 881 221 1 443 222 0 223 223 8 57089 224 1 449 225 3 1801 226 0 227 227 11 464897 228 0 229 229 6 14657 230 1 461 231 1 463 232 0 233 233 1 467 234 2 937 235 2 941 236 3 1889 237 4 3793 238 0 239 239 1 479 240 0 241 241 36 16561393893377 242 7 30977 243 1 487 244 2 977 245 1 491 246 5 7873 247 6 15809 248 5 7937 249 1 499 250 0 251 251 1 503 252 2 1009 253 2 1013 254 1 509 255 2 1021 256 0 257 257 279 2496329526...9292015617 (87 digits) 258 2 1033 259 38 71193377898497 260 1 521 261 1 523 262 0 263 263 29 141197049857 264 3 2113 265 2 1061 266 3 2129 267 2 1069 268 0 269 269 3 2153 270 0 271 271 4 4337 272 11 557057 273 1 547 274 2 1097 275 7 35201 276 0 277 277 2 1109 278 1 557 279 2 1117 280 0 281 281 1 563 282 0 283 283 30 303868936193 284 1 569 285 1 571 286 52 1288029493427961857 287 3 2297 288 1 577 289 10 295937 290 5 9281 291 4 4657 292 0 293 293 1 587 294 7 37633 295 2 1181 296 1 593 297 3 2377 298 2 1193 299 1 599 300 1 601 301 4 4817 302 3 2417 303 1 607 304 2 1217 305 3 2441 306 0 307 307 2 1229 308 1 617 309 1 619 310 0 311 311 9 159233 312 0 313 313 4 5009 314 7 40193 315 1 631 316 0 317 317 7 40577 318 5 10177 319 2 1277 320 1 641 321 1 643 322 2 1289 323 1 647 324 2 1297 325 2 1301 326 1 653 327 3 2617 328 8 83969 329 1 659 330 0 331 331 4 5297 332 3 2657 333 5 10657 334 6 21377 335 19 175636481 336 0 337 337 4 5393 338 1 677 339 3 2713 340 2 1361 341 1 683 342 7 43777 343 2 1373 344 3 2753 345 1 691 346 0 347 347 3 2777 348 0 349 349 10 357377 350 1 701 351 12 1437697 352 0 353 353 21 740294657 354 1 709 355 6 22721 356 5 11393 357 2 1429 358 0 359 359 1 719 360 6 23041 361 28 96905199617 362 3 2897 363 1 727 364 6 23297 365 5 11681 366 0 367 367 12 1503233 368 5 11777 369 1 739 370 2 1481 371 1 743 372 0 373 373 2 1493 374 5 11969 375 1 751 376 580 1487939695...6574002177 (178 digits) 377 11 772097 378 0 379 379 14 6209537 380 1 761 381 3 3049 382 0 383 383 6393 1169394518...1620750337 (1928 digits) 384 1 769 385 8 98561 386 1 773 387 2 1549 388 0 389 389 11 796673 390 3 3121 391 4 6257 392 3 3137 393 1 787 394 14 6455297 395 5 12641 396 0 397 397 4 6353 398 1 797 399 2 1597 400 0 401
PARI/GP
/* Check if there is an m such that n * 2^m + 1 is prime */
n2m1(n) = {
for(m = 0, 10^300,
if(isprime(n * 2^m + 1), return([1, m]));
);
return([0, 0]);
}
{
print(" N M Prime\n------------------");
for(n = 1, 400,
result = n2m1(n);
if(result[1],
print(Str(n) " " Str(result[2]) " " n * 2^result[2] + 1);
);
);
}- Output:
N M Prime ------------------ 1 0 2 2 0 3 3 1 7 4 0 5 5 1 11 6 0 7 7 2 29 8 1 17 9 1 19 10 0 11 11 1 23 12 0 13 13 2 53 14 1 29 15 1 31 16 0 17 17 3 137 18 0 19 19 6 1217 20 1 41 21 1 43 22 0 23 23 1 47 24 2 97 25 2 101 26 1 53 27 2 109 28 0 29 29 1 59 30 0 31 31 8 7937 32 3 257 33 1 67 34 2 137 35 1 71 36 0 37 37 2 149 38 5 1217 39 1 79 40 0 41 41 1 83 42 0 43 43 2 173 44 1 89 45 2 181 46 0 47 47 583 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 48 1 97 49 2 197 50 1 101 51 1 103 52 0 53 53 1 107 54 1 109 55 4 881 56 1 113 57 2 229 58 0 59 59 5 1889 60 0 61 61 4 977 62 7 7937 63 1 127 64 2 257 65 1 131 66 0 67 67 2 269 68 1 137 69 1 139 70 0 71 71 3 569 72 0 73 73 2 293 74 1 149 75 1 151 76 4 1217 77 3 617 78 0 79 79 2 317 80 3 641 81 1 163 82 0 83 83 1 167 84 2 337 85 4 1361 86 1 173 87 2 349 88 0 89 89 1 179 90 1 181 91 8 23297 92 7 11777 93 2 373 94 582 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 95 1 191 96 0 97 97 2 389 98 1 197 99 1 199 100 0 101 101 3 809 102 0 103 103 16 6750209 104 5 3329 105 1 211 106 0 107 107 3 857 108 0 109 109 6 6977 110 3 881 111 1 223 112 0 113 113 1 227 114 1 229 115 2 461 116 1 233 117 3 937 118 4 1889 119 1 239 120 1 241 121 8 30977 122 3 977 123 6 7873 124 6 7937 125 1 251 126 0 127 127 2 509 128 1 257 129 3 1033 130 0 131 131 1 263 132 4 2113 133 4 2129 134 1 269 135 1 271 136 0 137 137 3 1097 138 0 139 139 2 557 140 1 281 141 1 283 142 2 569 143 53 1288029493427961857 144 2 577 145 6 9281 146 1 293 147 8 37633 148 0 149 149 3 1193 150 0 151 151 4 2417 152 3 1217 153 1 307 154 2 617 155 1 311 156 0 157 157 8 40193 158 1 317 159 6 10177 160 2 641 161 3 1289 162 0 163 163 2 653 164 9 83969 165 1 331 166 0 167 167 7 21377 168 1 337 169 2 677 170 3 1361 171 8 43777 172 0 173 173 1 347 174 1 349 175 2 701 176 1 353 177 2 709 178 0 179 179 1 359 180 0 181 181 4 2897 182 7 23297 183 1 367 184 6 11777 185 3 1481 186 1 373 187 6 11969 188 581 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 189 1 379 190 0 191 191 1 383 192 0 193 193 2 773 194 1 389 195 4 3121 196 0 197 197 15 6455297 198 0 199 199 2 797 200 1 401 201 3 1609 202 2 809 203 13 1662977 204 1 409 205 2 821 206 15 6750209 207 2 829 208 4 3329 209 1 419 210 0 211 211 20 221249537 212 3 1697 213 2 853 214 2 857 215 1 431 216 1 433 217 66 16011773855979890802689 218 5 6977 219 1 439 220 2 881 221 1 443 222 0 223 223 8 57089 224 1 449 225 3 1801 226 0 227 227 11 464897 228 0 229 229 6 14657 230 1 461 231 1 463 232 0 233 233 1 467 234 2 937 235 2 941 236 3 1889 237 4 3793 238 0 239 239 1 479 240 0 241 241 36 16561393893377 242 7 30977 243 1 487 244 2 977 245 1 491 246 5 7873 247 6 15809 248 5 7937 249 1 499 250 0 251 251 1 503 252 2 1009 253 2 1013 254 1 509 255 2 1021 256 0 257 257 279 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 258 2 1033 259 38 71193377898497 260 1 521 261 1 523 262 0 263 263 29 141197049857 264 3 2113 265 2 1061 266 3 2129 267 2 1069 268 0 269 269 3 2153 270 0 271 271 4 4337 272 11 557057 273 1 547 274 2 1097 275 7 35201 276 0 277 277 2 1109 278 1 557 279 2 1117 280 0 281 281 1 563 282 0 283 283 30 303868936193 284 1 569 285 1 571 286 52 1288029493427961857 287 3 2297 288 1 577 289 10 295937 290 5 9281 291 4 4657 292 0 293 293 1 587 294 7 37633 295 2 1181 296 1 593 297 3 2377 298 2 1193 299 1 599 300 1 601 301 4 4817 302 3 2417 303 1 607 304 2 1217 305 3 2441 306 0 307 307 2 1229 308 1 617 309 1 619 310 0 311 311 9 159233 312 0 313 313 4 5009 314 7 40193 315 1 631 316 0 317 317 7 40577 318 5 10177 319 2 1277 320 1 641 321 1 643 322 2 1289 323 1 647 324 2 1297 325 2 1301 326 1 653 327 3 2617 328 8 83969 329 1 659 330 0 331 331 4 5297 332 3 2657 333 5 10657 334 6 21377 335 19 175636481 336 0 337 337 4 5393 338 1 677 339 3 2713 340 2 1361 341 1 683 342 7 43777 343 2 1373 344 3 2753 345 1 691 346 0 347 347 3 2777 348 0 349 349 10 357377 350 1 701 351 12 1437697 352 0 353 353 21 740294657 354 1 709 355 6 22721 356 5 11393 357 2 1429 358 0 359 359 1 719 360 6 23041 361 28 96905199617 362 3 2897 363 1 727 364 6 23297 365 5 11681 366 0 367 367 12 1503233 368 5 11777 369 1 739 370 2 1481 371 1 743 372 0 373 373 2 1493 374 5 11969 375 1 751 376 580 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 377 11 772097 378 0 379 379 14 6209537 380 1 761 381 3 3049 382 0 383 383 6393 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337 384 1 769 385 8 98561 386 1 773 387 2 1549 388 0 389 389 11 796673 390 3 3121 391 4 6257 392 3 3137 393 1 787 394 14 6455297 395 5 12641 396 0 397 397 4 6353 398 1 797 399 2 1597 400 0 401
Perl
use v5.36;
use bigint;
use ntheory 'is_prime';
for my $n (1..400) {
for (my $m=0 ; ; $m += 1) {
if (is_prime(my $p = $n * 2**$m + 1)) { printf "%3d %4d: %s\n",$n,$m,$p; last }
}
}
- Output:
1 0: 2 2 0: 3 3 1: 7 4 0: 5 5 1: 11 6 0: 7 7 2: 29 8 1: 17 9 1: 19 10 0: 11 11 1: 23 12 0: 13 13 2: 53 14 1: 29 15 1: 31 16 0: 17 17 3: 137 18 0: 19 19 6: 1217 20 1: 41 21 1: 43 22 0: 23 23 1: 47 24 2: 97 25 2: 101 26 1: 53 27 2: 109 28 0: 29 29 1: 59 30 0: 31 31 8: 7937 32 3: 257 33 1: 67 34 2: 137 35 1: 71 36 0: 37 37 2: 149 38 5: 1217 39 1: 79 40 0: 41 41 1: 83 42 0: 43 43 2: 173 44 1: 89 45 2: 181 46 0: 47 47 583: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 48 1: 97 49 2: 197 50 1: 101 51 1: 103 52 0: 53 53 1: 107 54 1: 109 55 4: 881 56 1: 113 57 2: 229 58 0: 59 59 5: 1889 60 0: 61 61 4: 977 62 7: 7937 63 1: 127 64 2: 257 65 1: 131 66 0: 67 67 2: 269 68 1: 137 69 1: 139 70 0: 71 71 3: 569 72 0: 73 73 2: 293 74 1: 149 75 1: 151 76 4: 1217 77 3: 617 78 0: 79 79 2: 317 80 3: 641 81 1: 163 82 0: 83 83 1: 167 84 2: 337 85 4: 1361 86 1: 173 87 2: 349 88 0: 89 89 1: 179 90 1: 181 91 8: 23297 92 7: 11777 93 2: 373 94 582: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 95 1: 191 96 0: 97 97 2: 389 98 1: 197 99 1: 199 100 0: 101 101 3: 809 102 0: 103 103 16: 6750209 104 5: 3329 105 1: 211 106 0: 107 107 3: 857 108 0: 109 109 6: 6977 110 3: 881 111 1: 223 112 0: 113 113 1: 227 114 1: 229 115 2: 461 116 1: 233 117 3: 937 118 4: 1889 119 1: 239 120 1: 241 121 8: 30977 122 3: 977 123 6: 7873 124 6: 7937 125 1: 251 126 0: 127 127 2: 509 128 1: 257 129 3: 1033 130 0: 131 131 1: 263 132 4: 2113 133 4: 2129 134 1: 269 135 1: 271 136 0: 137 137 3: 1097 138 0: 139 139 2: 557 140 1: 281 141 1: 283 142 2: 569 143 53: 1288029493427961857 144 2: 577 145 6: 9281 146 1: 293 147 8: 37633 148 0: 149 149 3: 1193 150 0: 151 151 4: 2417 152 3: 1217 153 1: 307 154 2: 617 155 1: 311 156 0: 157 157 8: 40193 158 1: 317 159 6: 10177 160 2: 641 161 3: 1289 162 0: 163 163 2: 653 164 9: 83969 165 1: 331 166 0: 167 167 7: 21377 168 1: 337 169 2: 677 170 3: 1361 171 8: 43777 172 0: 173 173 1: 347 174 1: 349 175 2: 701 176 1: 353 177 2: 709 178 0: 179 179 1: 359 180 0: 181 181 4: 2897 182 7: 23297 183 1: 367 184 6: 11777 185 3: 1481 186 1: 373 187 6: 11969 188 581: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 189 1: 379 190 0: 191 191 1: 383 192 0: 193 193 2: 773 194 1: 389 195 4: 3121 196 0: 197 197 15: 6455297 198 0: 199 199 2: 797 200 1: 401 201 3: 1609 202 2: 809 203 13: 1662977 204 1: 409 205 2: 821 206 15: 6750209 207 2: 829 208 4: 3329 209 1: 419 210 0: 211 211 20: 221249537 212 3: 1697 213 2: 853 214 2: 857 215 1: 431 216 1: 433 217 66: 16011773855979890802689 218 5: 6977 219 1: 439 220 2: 881 221 1: 443 222 0: 223 223 8: 57089 224 1: 449 225 3: 1801 226 0: 227 227 11: 464897 228 0: 229 229 6: 14657 230 1: 461 231 1: 463 232 0: 233 233 1: 467 234 2: 937 235 2: 941 236 3: 1889 237 4: 3793 238 0: 239 239 1: 479 240 0: 241 241 36: 16561393893377 242 7: 30977 243 1: 487 244 2: 977 245 1: 491 246 5: 7873 247 6: 15809 248 5: 7937 249 1: 499 250 0: 251 251 1: 503 252 2: 1009 253 2: 1013 254 1: 509 255 2: 1021 256 0: 257 257 279: 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 258 2: 1033 259 38: 71193377898497 260 1: 521 261 1: 523 262 0: 263 263 29: 141197049857 264 3: 2113 265 2: 1061 266 3: 2129 267 2: 1069 268 0: 269 269 3: 2153 270 0: 271 271 4: 4337 272 11: 557057 273 1: 547 274 2: 1097 275 7: 35201 276 0: 277 277 2: 1109 278 1: 557 279 2: 1117 280 0: 281 281 1: 563 282 0: 283 283 30: 303868936193 284 1: 569 285 1: 571 286 52: 1288029493427961857 287 3: 2297 288 1: 577 289 10: 295937 290 5: 9281 291 4: 4657 292 0: 293 293 1: 587 294 7: 37633 295 2: 1181 296 1: 593 297 3: 2377 298 2: 1193 299 1: 599 300 1: 601 301 4: 4817 302 3: 2417 303 1: 607 304 2: 1217 305 3: 2441 306 0: 307 307 2: 1229 308 1: 617 309 1: 619 310 0: 311 311 9: 159233 312 0: 313 313 4: 5009 314 7: 40193 315 1: 631 316 0: 317 317 7: 40577 318 5: 10177 319 2: 1277 320 1: 641 321 1: 643 322 2: 1289 323 1: 647 324 2: 1297 325 2: 1301 326 1: 653 327 3: 2617 328 8: 83969 329 1: 659 330 0: 331 331 4: 5297 332 3: 2657 333 5: 10657 334 6: 21377 335 19: 175636481 336 0: 337 337 4: 5393 338 1: 677 339 3: 2713 340 2: 1361 341 1: 683 342 7: 43777 343 2: 1373 344 3: 2753 345 1: 691 346 0: 347 347 3: 2777 348 0: 349 349 10: 357377 350 1: 701 351 12: 1437697 352 0: 353 353 21: 740294657 354 1: 709 355 6: 22721 356 5: 11393 357 2: 1429 358 0: 359 359 1: 719 360 6: 23041 361 28: 96905199617 362 3: 2897 363 1: 727 364 6: 23297 365 5: 11681 366 0: 367 367 12: 1503233 368 5: 11777 369 1: 739 370 2: 1481 371 1: 743 372 0: 373 373 2: 1493 374 5: 11969 375 1: 751 376 580: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 377 11: 772097 378 0: 379 379 14: 6209537 380 1: 761 381 3: 3049 382 0: 383 383 6393: 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337 384 1: 769 385 8: 98561 386 1: 773 387 2: 1549 388 0: 389 389 11: 796673 390 3: 3121 391 4: 6257 392 3: 3137 393 1: 787 394 14: 6455297 395 5: 12641 396 0: 397 397 4: 6353 398 1: 797 399 2: 1597 400 0: 401
PL/M
... under CP/M (or an emulator)
Interestingly, the primes up to m = 45 all have a single digit m and will all fit in 16 bits, which is handy as the 8080 PL/M compiler doesn't support integers larger than unsigned 16-bit.
100H: /* FIND PRIMES OF THE FORM N * 2**M + 1 */
DECLARE FALSE LITERALLY '0';
DECLARE TRUE LITERALLY '0FFH';
/* CP/M SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* END SYSTEM CALL AND I/O ROUTINES */
/* SIEVE THE PRIMES TO 8000 */
DECLARE PRIME ( 8001 )BYTE;
DO;
DECLARE ( I, S ) ADDRESS;
PRIME( 0 ), PRIME( 1 ) = FALSE;
PRIME( 2 ) = TRUE;
DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END;
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
DO I = 3 TO LAST( PRIME ) / 2 BY 2;
IF PRIME( I ) THEN DO;
DO S = I * I TO LAST( PRIME ) BY I + I; PRIME( S ) = FALSE; END;
END;
END;
END;
DECLARE MAX$M LITERALLY '14'; /* MAXIMUM M WE WILL CONSIDER */
/* FIND THE PRIMES */
DECLARE ( N, M, P, TWO$TO$M ) ADDRESS;
DECLARE NOT$FOUND BYTE;
DO N = 1 TO 45;
M = 0;
TWO$TO$M = 1;
P = 0;
NOT$FOUND = 1;
DO WHILE M <= MAX$M
AND ( NOT$FOUND := NOT PRIME( P := ( N * TWO$TO$M ) + 1 ) );
TWO$TO$M = TWO$TO$M + TWO$TO$M;
M = M + 1;
END;
CALL PR$CHAR( '(' );
IF N < 10 THEN CALL PR$CHAR( ' ' );
CALL PR$NUMBER( N );
IF NOT$FOUND THEN DO;
CALL PR$STRING( .' NOT FOUND$' );
END;
ELSE DO;
CALL PR$CHAR( ' ' );
CALL PR$NUMBER( M );
CALL PR$CHAR( ':' );
CALL PR$CHAR( ' ' );
IF P < 10 THEN CALL PR$CHAR( ' ' );
IF P < 100 THEN CALL PR$CHAR( ' ' );
IF P < 1000 THEN CALL PR$CHAR( ' ' );
CALL PR$NUMBER( P );
CALL PR$CHAR( ' ' );
CALL PR$CHAR( ' ' );
END;
CALL PR$CHAR( ')' );
IF N MOD 5 = 0 THEN CALL PR$NL;
END;
EOF- Output:
( 1 0: 2 )( 2 0: 3 )( 3 1: 7 )( 4 0: 5 )( 5 1: 11 ) ( 6 0: 7 )( 7 2: 29 )( 8 1: 17 )( 9 1: 19 )(10 0: 11 ) (11 1: 23 )(12 0: 13 )(13 2: 53 )(14 1: 29 )(15 1: 31 ) (16 0: 17 )(17 3: 137 )(18 0: 19 )(19 6: 1217 )(20 1: 41 ) (21 1: 43 )(22 0: 23 )(23 1: 47 )(24 2: 97 )(25 2: 101 ) (26 1: 53 )(27 2: 109 )(28 0: 29 )(29 1: 59 )(30 0: 31 ) (31 8: 7937 )(32 3: 257 )(33 1: 67 )(34 2: 137 )(35 1: 71 ) (36 0: 37 )(37 2: 149 )(38 5: 1217 )(39 1: 79 )(40 0: 41 ) (41 1: 83 )(42 0: 43 )(43 2: 173 )(44 1: 89 )(45 2: 181 )
Phix
with javascript_semantics include mpfr.e printf(1," N M Prime\n------------------\n") mpz p = mpz_init() for n=1 to 400 do integer m = 0 while true do mpz_set_si(p,n) mpz_mul_2exp(p,p,m) mpz_add_si(p,p,1) if mpz_prime(p) then printf(1,"%3d %4d %s\n", {n,m,mpz_get_short_str(p)}) exit end if m += 1 end while end for
Output same as Wren (plus a few not particularly helpful digit counts).
Python
# primesn2m1.py by Xing216
from gmpy2 import is_prime, mpz
print(" n m prime")
for n in range(1, 401):
m = 0
term = mpz(n)
while True:
if is_prime(term + 1):
print(f"{n:3d} {m} {term + 1:5d}")
break
m += 1
term *= 2
}
- Output:
n m prime 1 0 2 2 0 3 3 1 7 4 0 5 5 1 11 6 0 7 7 2 29 8 1 17 9 1 19 10 0 11 11 1 23 12 0 13 13 2 53 14 1 29 15 1 31 16 0 17 17 3 137 18 0 19 19 6 1217 20 1 41 21 1 43 22 0 23 23 1 47 24 2 97 25 2 101 26 1 53 27 2 109 28 0 29 29 1 59 30 0 31 31 8 7937 32 3 257 33 1 67 34 2 137 35 1 71 36 0 37 37 2 149 38 5 1217 39 1 79 40 0 41 41 1 83 42 0 43 43 2 173 44 1 89 45 2 181 46 0 47 47 583 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 48 1 97 49 2 197 50 1 101 51 1 103 52 0 53 53 1 107 54 1 109 55 4 881 56 1 113 57 2 229 58 0 59 59 5 1889 60 0 61 61 4 977 62 7 7937 63 1 127 64 2 257 65 1 131 66 0 67 67 2 269 68 1 137 69 1 139 70 0 71 71 3 569 72 0 73 73 2 293 74 1 149 75 1 151 76 4 1217 77 3 617 78 0 79 79 2 317 80 3 641 81 1 163 82 0 83 83 1 167 84 2 337 85 4 1361 86 1 173 87 2 349 88 0 89 89 1 179 90 1 181 91 8 23297 92 7 11777 93 2 373 94 582 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 95 1 191 96 0 97 97 2 389 98 1 197 99 1 199 100 0 101 101 3 809 102 0 103 103 16 6750209 104 5 3329 105 1 211 106 0 107 107 3 857 108 0 109 109 6 6977 110 3 881 111 1 223 112 0 113 113 1 227 114 1 229 115 2 461 116 1 233 117 3 937 118 4 1889 119 1 239 120 1 241 121 8 30977 122 3 977 123 6 7873 124 6 7937 125 1 251 126 0 127 127 2 509 128 1 257 129 3 1033 130 0 131 131 1 263 132 4 2113 133 4 2129 134 1 269 135 1 271 136 0 137 137 3 1097 138 0 139 139 2 557 140 1 281 141 1 283 142 2 569 143 53 1288029493427961857 144 2 577 145 6 9281 146 1 293 147 8 37633 148 0 149 149 3 1193 150 0 151 151 4 2417 152 3 1217 153 1 307 154 2 617 155 1 311 156 0 157 157 8 40193 158 1 317 159 6 10177 160 2 641 161 3 1289 162 0 163 163 2 653 164 9 83969 165 1 331 166 0 167 167 7 21377 168 1 337 169 2 677 170 3 1361 171 8 43777 172 0 173 173 1 347 174 1 349 175 2 701 176 1 353 177 2 709 178 0 179 179 1 359 180 0 181 181 4 2897 182 7 23297 183 1 367 184 6 11777 185 3 1481 186 1 373 187 6 11969 188 581 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 189 1 379 190 0 191 191 1 383 192 0 193 193 2 773 194 1 389 195 4 3121 196 0 197 197 15 6455297 198 0 199 199 2 797 200 1 401 201 3 1609 202 2 809 203 13 1662977 204 1 409 205 2 821 206 15 6750209 207 2 829 208 4 3329 209 1 419 210 0 211 211 20 221249537 212 3 1697 213 2 853 214 2 857 215 1 431 216 1 433 217 66 16011773855979890802689 218 5 6977 219 1 439 220 2 881 221 1 443 222 0 223 223 8 57089 224 1 449 225 3 1801 226 0 227 227 11 464897 228 0 229 229 6 14657 230 1 461 231 1 463 232 0 233 233 1 467 234 2 937 235 2 941 236 3 1889 237 4 3793 238 0 239 239 1 479 240 0 241 241 36 16561393893377 242 7 30977 243 1 487 244 2 977 245 1 491 246 5 7873 247 6 15809 248 5 7937 249 1 499 250 0 251 251 1 503 252 2 1009 253 2 1013 254 1 509 255 2 1021 256 0 257 257 279 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 258 2 1033 259 38 71193377898497 260 1 521 261 1 523 262 0 263 263 29 141197049857 264 3 2113 265 2 1061 266 3 2129 267 2 1069 268 0 269 269 3 2153 270 0 271 271 4 4337 272 11 557057 273 1 547 274 2 1097 275 7 35201 276 0 277 277 2 1109 278 1 557 279 2 1117 280 0 281 281 1 563 282 0 283 283 30 303868936193 284 1 569 285 1 571 286 52 1288029493427961857 287 3 2297 288 1 577 289 10 295937 290 5 9281 291 4 4657 292 0 293 293 1 587 294 7 37633 295 2 1181 296 1 593 297 3 2377 298 2 1193 299 1 599 300 1 601 301 4 4817 302 3 2417 303 1 607 304 2 1217 305 3 2441 306 0 307 307 2 1229 308 1 617 309 1 619 310 0 311 311 9 159233 312 0 313 313 4 5009 314 7 40193 315 1 631 316 0 317 317 7 40577 318 5 10177 319 2 1277 320 1 641 321 1 643 322 2 1289 323 1 647 324 2 1297 325 2 1301 326 1 653 327 3 2617 328 8 83969 329 1 659 330 0 331 331 4 5297 332 3 2657 333 5 10657 334 6 21377 335 19 175636481 336 0 337 337 4 5393 338 1 677 339 3 2713 340 2 1361 341 1 683 342 7 43777 343 2 1373 344 3 2753 345 1 691 346 0 347 347 3 2777 348 0 349 349 10 357377 350 1 701 351 12 1437697 352 0 353 353 21 740294657 354 1 709 355 6 22721 356 5 11393 357 2 1429 358 0 359 359 1 719 360 6 23041 361 28 96905199617 362 3 2897 363 1 727 364 6 23297 365 5 11681 366 0 367 367 12 1503233 368 5 11777 369 1 739 370 2 1481 371 1 743 372 0 373 373 2 1493 374 5 11969 375 1 751 376 580 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 377 11 772097 378 0 379 379 14 6209537 380 1 761 381 3 3049 382 0 383 383 6393 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337 384 1 769 385 8 98561 386 1 773 387 2 1549 388 0 389 389 11 796673 390 3 3121 391 4 6257 392 3 3137 393 1 787 394 14 6455297 395 5 12641 396 0 397 397 4 6353 398 1 797 399 2 1597 400 0 401
Raku
First 382 in less than a second. 383 pushes the total accumulated time over 25 seconds.
-> $n { (^∞).map: -> $m { if (my $p = $n × 2 ** $m + 1).is-prime { printf "%3d %4d: %d\n",$n,$m,$p; last } } } for 1..400
- Output:
1 0: 2 2 0: 3 3 1: 7 4 0: 5 5 1: 11 6 0: 7 7 2: 29 8 1: 17 9 1: 19 10 0: 11 11 1: 23 12 0: 13 13 2: 53 14 1: 29 15 1: 31 16 0: 17 17 3: 137 18 0: 19 19 6: 1217 20 1: 41 21 1: 43 22 0: 23 23 1: 47 24 2: 97 25 2: 101 26 1: 53 27 2: 109 28 0: 29 29 1: 59 30 0: 31 31 8: 7937 32 3: 257 33 1: 67 34 2: 137 35 1: 71 36 0: 37 37 2: 149 38 5: 1217 39 1: 79 40 0: 41 41 1: 83 42 0: 43 43 2: 173 44 1: 89 45 2: 181 46 0: 47 47 583: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 48 1: 97 49 2: 197 50 1: 101 51 1: 103 52 0: 53 53 1: 107 54 1: 109 55 4: 881 56 1: 113 57 2: 229 58 0: 59 59 5: 1889 60 0: 61 61 4: 977 62 7: 7937 63 1: 127 64 2: 257 65 1: 131 66 0: 67 67 2: 269 68 1: 137 69 1: 139 70 0: 71 71 3: 569 72 0: 73 73 2: 293 74 1: 149 75 1: 151 76 4: 1217 77 3: 617 78 0: 79 79 2: 317 80 3: 641 81 1: 163 82 0: 83 83 1: 167 84 2: 337 85 4: 1361 86 1: 173 87 2: 349 88 0: 89 89 1: 179 90 1: 181 91 8: 23297 92 7: 11777 93 2: 373 94 582: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 95 1: 191 96 0: 97 97 2: 389 98 1: 197 99 1: 199 100 0: 101 101 3: 809 102 0: 103 103 16: 6750209 104 5: 3329 105 1: 211 106 0: 107 107 3: 857 108 0: 109 109 6: 6977 110 3: 881 111 1: 223 112 0: 113 113 1: 227 114 1: 229 115 2: 461 116 1: 233 117 3: 937 118 4: 1889 119 1: 239 120 1: 241 121 8: 30977 122 3: 977 123 6: 7873 124 6: 7937 125 1: 251 126 0: 127 127 2: 509 128 1: 257 129 3: 1033 130 0: 131 131 1: 263 132 4: 2113 133 4: 2129 134 1: 269 135 1: 271 136 0: 137 137 3: 1097 138 0: 139 139 2: 557 140 1: 281 141 1: 283 142 2: 569 143 53: 1288029493427961857 144 2: 577 145 6: 9281 146 1: 293 147 8: 37633 148 0: 149 149 3: 1193 150 0: 151 151 4: 2417 152 3: 1217 153 1: 307 154 2: 617 155 1: 311 156 0: 157 157 8: 40193 158 1: 317 159 6: 10177 160 2: 641 161 3: 1289 162 0: 163 163 2: 653 164 9: 83969 165 1: 331 166 0: 167 167 7: 21377 168 1: 337 169 2: 677 170 3: 1361 171 8: 43777 172 0: 173 173 1: 347 174 1: 349 175 2: 701 176 1: 353 177 2: 709 178 0: 179 179 1: 359 180 0: 181 181 4: 2897 182 7: 23297 183 1: 367 184 6: 11777 185 3: 1481 186 1: 373 187 6: 11969 188 581: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 189 1: 379 190 0: 191 191 1: 383 192 0: 193 193 2: 773 194 1: 389 195 4: 3121 196 0: 197 197 15: 6455297 198 0: 199 199 2: 797 200 1: 401 201 3: 1609 202 2: 809 203 13: 1662977 204 1: 409 205 2: 821 206 15: 6750209 207 2: 829 208 4: 3329 209 1: 419 210 0: 211 211 20: 221249537 212 3: 1697 213 2: 853 214 2: 857 215 1: 431 216 1: 433 217 66: 16011773855979890802689 218 5: 6977 219 1: 439 220 2: 881 221 1: 443 222 0: 223 223 8: 57089 224 1: 449 225 3: 1801 226 0: 227 227 11: 464897 228 0: 229 229 6: 14657 230 1: 461 231 1: 463 232 0: 233 233 1: 467 234 2: 937 235 2: 941 236 3: 1889 237 4: 3793 238 0: 239 239 1: 479 240 0: 241 241 36: 16561393893377 242 7: 30977 243 1: 487 244 2: 977 245 1: 491 246 5: 7873 247 6: 15809 248 5: 7937 249 1: 499 250 0: 251 251 1: 503 252 2: 1009 253 2: 1013 254 1: 509 255 2: 1021 256 0: 257 257 279: 249632952651006185613150855026822179503549278818199928480857894651449200648869292015617 258 2: 1033 259 38: 71193377898497 260 1: 521 261 1: 523 262 0: 263 263 29: 141197049857 264 3: 2113 265 2: 1061 266 3: 2129 267 2: 1069 268 0: 269 269 3: 2153 270 0: 271 271 4: 4337 272 11: 557057 273 1: 547 274 2: 1097 275 7: 35201 276 0: 277 277 2: 1109 278 1: 557 279 2: 1117 280 0: 281 281 1: 563 282 0: 283 283 30: 303868936193 284 1: 569 285 1: 571 286 52: 1288029493427961857 287 3: 2297 288 1: 577 289 10: 295937 290 5: 9281 291 4: 4657 292 0: 293 293 1: 587 294 7: 37633 295 2: 1181 296 1: 593 297 3: 2377 298 2: 1193 299 1: 599 300 1: 601 301 4: 4817 302 3: 2417 303 1: 607 304 2: 1217 305 3: 2441 306 0: 307 307 2: 1229 308 1: 617 309 1: 619 310 0: 311 311 9: 159233 312 0: 313 313 4: 5009 314 7: 40193 315 1: 631 316 0: 317 317 7: 40577 318 5: 10177 319 2: 1277 320 1: 641 321 1: 643 322 2: 1289 323 1: 647 324 2: 1297 325 2: 1301 326 1: 653 327 3: 2617 328 8: 83969 329 1: 659 330 0: 331 331 4: 5297 332 3: 2657 333 5: 10657 334 6: 21377 335 19: 175636481 336 0: 337 337 4: 5393 338 1: 677 339 3: 2713 340 2: 1361 341 1: 683 342 7: 43777 343 2: 1373 344 3: 2753 345 1: 691 346 0: 347 347 3: 2777 348 0: 349 349 10: 357377 350 1: 701 351 12: 1437697 352 0: 353 353 21: 740294657 354 1: 709 355 6: 22721 356 5: 11393 357 2: 1429 358 0: 359 359 1: 719 360 6: 23041 361 28: 96905199617 362 3: 2897 363 1: 727 364 6: 23297 365 5: 11681 366 0: 367 367 12: 1503233 368 5: 11777 369 1: 739 370 2: 1481 371 1: 743 372 0: 373 373 2: 1493 374 5: 11969 375 1: 751 376 580: 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177 377 11: 772097 378 0: 379 379 14: 6209537 380 1: 761 381 3: 3049 382 0: 383 383 6393: 11693945185971565896920916176753769281418376445302724140914106576604960252116205468905429628661873192664799900323401294531072465400997845029722990758855393414014415817179228695517839305455702961095094596926622802342799137107509767542153683280899327558274011281588755909890607960835140712630830933978801393590855371457894042968287926562847826310125559303901351824980311279986492793008248059208985097459095049075732193161126922389950080848742183055141518931962329796357335158955758486061360294773463111842316561192036096585088267052290025273980611139612478214293303564141730470933187279751846912161098280963960686648202780382930927114525552446602357404550468641236474238897222372272898562140228039886991631673186995098587756569010989657598363351856992206826342175536967926902668804937341514786382018872919876784539436965319822540039220122728568129762675989071883516915894567537630751801497223803135172643203770169327233350522822938630733126833423559124391441973547309619943019237705312515304113424366223388373606440335025932390399945086075175009569272136997988977568262327875607690344516747889133920438003737328060362069562108376086129279385800262195985974144460914705464874882401864174074796383557151951711000378565395148939760434428093058777242253682181813425273399277638142811972296863003382484684788329148214958434057306251885787781329925372401240556666727438408378656900945061970219566055969587385482421092779185798692904507774583223151161566406541599486350580593707153172641891804260963429951215526999443852964537303345106153870841180251403751871193132336680841124129779119999935597712685839886558769823834654994044516702436738265181698869580022472787153167463772595005393815295009535991557511340157179280662197799109181549751673455040271529561595718940092424231253150263268513067972937042222806102175350331146290864120703025608712817763221723427454002746818270565050919821097445991953785331131470462682015972815241620750337 384 1: 769 385 8: 98561 386 1: 773 387 2: 1549 388 0: 389 389 11: 796673 390 3: 3121 391 4: 6257 392 3: 3137 393 1: 787 394 14: 6455297 395 5: 12641 396 0: 397 397 4: 6353 398 1: 797 399 2: 1597 400 0: 401
RPL
As big ints are limited to 499 digits, it is not possible to calculate the 47th prime number.
« { } 1 45 FOR n 0 WHILE 2 OVER ^ n * 1 + DUP ISPRIME? NOT REPEAT DROP 1 + END NIP + NEXT » 'TASK' STO
- Output:
1: { 2 3 7 5 11 7 29 17 19 11 23 13 53 29 31 17 137 19 1217 41 43 23 47 97 101 53 109 29 59 31 7937 257 67 137 71 37 149 1217 79 41 83 43 173 89 181 }
Sidef
Takes ~2 seconds to run.
for n in (1..400) {
var p = (^Inf -> lazy.map {|m| [m, n * 2**m + 1] }.first_by { .tail.is_prime })
printf("%3s %4s: %s\n", n, p...)
}
(same output as the Perl version)
Wren
import "./gmp" for Mpz
import "./fmt" for Fmt
System.print(" N M Prime")
System.print("------------------")
for (n in 1..400) {
var m = 0
while (true) {
var p = Mpz.from(n).mul(Mpz.one.lsh(m)).add(1)
if (p.probPrime(15) > 0) {
Fmt.print("$3d $4d $20a", n, m, p)
break
}
m = m + 1
}
}
- Output:
Primes with more than 40 digits have been (mercifully) abbreviated.
N M Prime ------------------ 1 0 2 2 0 3 3 1 7 4 0 5 5 1 11 6 0 7 7 2 29 8 1 17 9 1 19 10 0 11 11 1 23 12 0 13 13 2 53 14 1 29 15 1 31 16 0 17 17 3 137 18 0 19 19 6 1217 20 1 41 21 1 43 22 0 23 23 1 47 24 2 97 25 2 101 26 1 53 27 2 109 28 0 29 29 1 59 30 0 31 31 8 7937 32 3 257 33 1 67 34 2 137 35 1 71 36 0 37 37 2 149 38 5 1217 39 1 79 40 0 41 41 1 83 42 0 43 43 2 173 44 1 89 45 2 181 46 0 47 47 583 14879396952621968769...86306341246574002177 48 1 97 49 2 197 50 1 101 51 1 103 52 0 53 53 1 107 54 1 109 55 4 881 56 1 113 57 2 229 58 0 59 59 5 1889 60 0 61 61 4 977 62 7 7937 63 1 127 64 2 257 65 1 131 66 0 67 67 2 269 68 1 137 69 1 139 70 0 71 71 3 569 72 0 73 73 2 293 74 1 149 75 1 151 76 4 1217 77 3 617 78 0 79 79 2 317 80 3 641 81 1 163 82 0 83 83 1 167 84 2 337 85 4 1361 86 1 173 87 2 349 88 0 89 89 1 179 90 1 181 91 8 23297 92 7 11777 93 2 373 94 582 14879396952621968769...86306341246574002177 95 1 191 96 0 97 97 2 389 98 1 197 99 1 199 100 0 101 101 3 809 102 0 103 103 16 6750209 104 5 3329 105 1 211 106 0 107 107 3 857 108 0 109 109 6 6977 110 3 881 111 1 223 112 0 113 113 1 227 114 1 229 115 2 461 116 1 233 117 3 937 118 4 1889 119 1 239 120 1 241 121 8 30977 122 3 977 123 6 7873 124 6 7937 125 1 251 126 0 127 127 2 509 128 1 257 129 3 1033 130 0 131 131 1 263 132 4 2113 133 4 2129 134 1 269 135 1 271 136 0 137 137 3 1097 138 0 139 139 2 557 140 1 281 141 1 283 142 2 569 143 53 1288029493427961857 144 2 577 145 6 9281 146 1 293 147 8 37633 148 0 149 149 3 1193 150 0 151 151 4 2417 152 3 1217 153 1 307 154 2 617 155 1 311 156 0 157 157 8 40193 158 1 317 159 6 10177 160 2 641 161 3 1289 162 0 163 163 2 653 164 9 83969 165 1 331 166 0 167 167 7 21377 168 1 337 169 2 677 170 3 1361 171 8 43777 172 0 173 173 1 347 174 1 349 175 2 701 176 1 353 177 2 709 178 0 179 179 1 359 180 0 181 181 4 2897 182 7 23297 183 1 367 184 6 11777 185 3 1481 186 1 373 187 6 11969 188 581 14879396952621968769...86306341246574002177 189 1 379 190 0 191 191 1 383 192 0 193 193 2 773 194 1 389 195 4 3121 196 0 197 197 15 6455297 198 0 199 199 2 797 200 1 401 201 3 1609 202 2 809 203 13 1662977 204 1 409 205 2 821 206 15 6750209 207 2 829 208 4 3329 209 1 419 210 0 211 211 20 221249537 212 3 1697 213 2 853 214 2 857 215 1 431 216 1 433 217 66 16011773855979890802689 218 5 6977 219 1 439 220 2 881 221 1 443 222 0 223 223 8 57089 224 1 449 225 3 1801 226 0 227 227 11 464897 228 0 229 229 6 14657 230 1 461 231 1 463 232 0 233 233 1 467 234 2 937 235 2 941 236 3 1889 237 4 3793 238 0 239 239 1 479 240 0 241 241 36 16561393893377 242 7 30977 243 1 487 244 2 977 245 1 491 246 5 7873 247 6 15809 248 5 7937 249 1 499 250 0 251 251 1 503 252 2 1009 253 2 1013 254 1 509 255 2 1021 256 0 257 257 279 24963295265100618561...49200648869292015617 258 2 1033 259 38 71193377898497 260 1 521 261 1 523 262 0 263 263 29 141197049857 264 3 2113 265 2 1061 266 3 2129 267 2 1069 268 0 269 269 3 2153 270 0 271 271 4 4337 272 11 557057 273 1 547 274 2 1097 275 7 35201 276 0 277 277 2 1109 278 1 557 279 2 1117 280 0 281 281 1 563 282 0 283 283 30 303868936193 284 1 569 285 1 571 286 52 1288029493427961857 287 3 2297 288 1 577 289 10 295937 290 5 9281 291 4 4657 292 0 293 293 1 587 294 7 37633 295 2 1181 296 1 593 297 3 2377 298 2 1193 299 1 599 300 1 601 301 4 4817 302 3 2417 303 1 607 304 2 1217 305 3 2441 306 0 307 307 2 1229 308 1 617 309 1 619 310 0 311 311 9 159233 312 0 313 313 4 5009 314 7 40193 315 1 631 316 0 317 317 7 40577 318 5 10177 319 2 1277 320 1 641 321 1 643 322 2 1289 323 1 647 324 2 1297 325 2 1301 326 1 653 327 3 2617 328 8 83969 329 1 659 330 0 331 331 4 5297 332 3 2657 333 5 10657 334 6 21377 335 19 175636481 336 0 337 337 4 5393 338 1 677 339 3 2713 340 2 1361 341 1 683 342 7 43777 343 2 1373 344 3 2753 345 1 691 346 0 347 347 3 2777 348 0 349 349 10 357377 350 1 701 351 12 1437697 352 0 353 353 21 740294657 354 1 709 355 6 22721 356 5 11393 357 2 1429 358 0 359 359 1 719 360 6 23041 361 28 96905199617 362 3 2897 363 1 727 364 6 23297 365 5 11681 366 0 367 367 12 1503233 368 5 11777 369 1 739 370 2 1481 371 1 743 372 0 373 373 2 1493 374 5 11969 375 1 751 376 580 14879396952621968769...86306341246574002177 377 11 772097 378 0 379 379 14 6209537 380 1 761 381 3 3049 382 0 383 383 6393 11693945185971565896...15972815241620750337 384 1 769 385 8 98561 386 1 773 387 2 1549 388 0 389 389 11 796673 390 3 3121 391 4 6257 392 3 3137 393 1 787 394 14 6455297 395 5 12641 396 0 397 397 4 6353 398 1 797 399 2 1597 400 0 401