Primes: n*2^m+1: Difference between revisions
Content added Content deleted
(Add PARI/GP implementation) |
(Added Java) |
||
Line 664: | Line 664: | ||
(Most of the implementation here is about merging intermediate values and formatting for display. The calculation for m is <code>i.&1"1]1 p:1+(1+i.45) */ 2^i.9</code> -- 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.) |
(Most of the implementation here is about merging intermediate values and formatting for display. The calculation for m is <code>i.&1"1]1 p:1+(1+i.45) */ 2^i.9</code> -- 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.) |
||
=={{header|Java}}== |
|||
Though it takes about 15 minutes to find the numbers up to 400 on my Windows 11 laptop, it can find all of them except 383 in a few seconds.<br/> |
|||
Tested with OpenJDK version 22. |
|||
<syntaxhighlight lang="java"> |
|||
import java.math.BigInteger; |
|||
public class primesNx2ToMPlus1 // find primes of the form 1+n*2^m where m is |
|||
{ // the lowest integer >= 0 such that 1+n*2^m is prime |
|||
static final int maxM = 8000; // maximum m we will consider |
|||
public static void main( String[] args ) |
|||
{ |
|||
BigInteger nn = BigInteger.ZERO; |
|||
for( int n = 1; n <= 400; n ++ ) |
|||
{ |
|||
int m = 0; |
|||
BigInteger twoToM = BigInteger.ONE; |
|||
BigInteger p = BigInteger.ZERO; |
|||
boolean notFound = true; |
|||
nn = nn.add( BigInteger.ONE ); |
|||
while( notFound && m <= maxM ) |
|||
{ |
|||
p = nn.multiply( twoToM ).add( BigInteger.ONE ); |
|||
if( ( notFound = ! p.isProbablePrime( 10 ) ) ) |
|||
{ |
|||
twoToM = twoToM.add( twoToM ); |
|||
m += 1; |
|||
} |
|||
} |
|||
System.out.print( String.format( "%3d", n ) ); |
|||
if( notFound ) |
|||
{ |
|||
System.out.println( " not found" ); |
|||
} |
|||
else |
|||
{ |
|||
System.out.println( " " + String.format( "%6d", m ) + ": " + p.toString() ); |
|||
} |
|||
} |
|||
} // main |
|||
} // primesNx2ToMPlus1 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
As with many other samples, the long primes have been manually shortened. |
|||
<pre style="height:30ex;overflow:scroll;"> |
|||
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: 148793969526...246574002177 |
|||
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: 148793969526...246574002177 |
|||
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: 148793969526...246574002177 |
|||
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: 249632952651...869292015617 |
|||
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: 148793969526...246574002177 |
|||
377 11: 772097 |
|||
378 0: 379 |
|||
379 14: 6209537 |
|||
380 1: 761 |
|||
381 3: 3049 |
|||
382 0: 383 |
|||
383 6393: 116939451859...241620750337 |
|||
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|jq}}== |
=={{header|jq}}== |