This site is supported by donations to The OEIS Foundation.

Strong pseudoprimes

From OeisWiki
(Redirected from Strong pseudoprime)
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


A strong pseudoprime is an Euler pseudoprime with a special property. An odd composite number (where is odd) is a strong pseudoprime to a base if

or

The first condition is stronger.

Strong pseudoprimes and Euler pseudoprimes

Every strong pseudoprime is also an Euler pseudoprime. But not every Euler pseudoprime is a strong pseudoprime. The reason is because is a multiple of , so for a strong pseudoprime we have

In the most cases is or . But in some cases is , or , in these cases overlapping the definition of Euler pseudoprime and the definition of strong pseudoprimes.

Properties

  • Every strong pseudoprime is odd, because every Euler pseudoprime is odd.
  • If a strong pseudoprime is pseudoprime to a base in , than is pseudoprime to a base in and vice versa.
  • There exist Carmichael numbers that are also strong pseudoprimes.

Sequences

A181782 Odd composite numbers that are strong pseudoprimes to some base .

{25, 49, 65, 85, 91, 121, 125, 133, 145, 169, 175, 185, 205, 217, 221, 231, 247, 259, 265, 289, 301, 305, 325, 341, 343, 361, 365, 377, 385, 403, 425, 427, 435, 445, 451, 469, 475, ...}

Table of strong pseudoprimes between 15 and 1505

Case 1a
Case 2a
Case 1b
Case 2b


25 3 7, 18
49 3 18, 30 19, 31
65 1 8, 18, 47, 57
85 21 13, 38, 47, 72
91 45 9, 16, 22, 29, 53, 74, 79, 81 10, 12, 17, 38, 62, 69, 75, 82
121 15 3, 9, 27, 81 40, 94, 112, 118
125 31 57, 68
133 33 11, 30, 39, 58, 64, 102, 106, 121 12, 27, 31, 69, 75, 94, 103, 122
145 9 12, 17, 128, 133
169 21 22, 146 23, 147 19, 70, 80, 89, 99, 150
175 87 51, 151 24, 124
185 23 43, 68, 117, 142
205 51 32, 73, 132, 173
217 27 25, 32, 36, 67, 149, 156, 191, 211 6, 26, 61, 68, 150, 181, 185, 192
221 55 21, 47, 174, 200
231 115 64, 148, 169, 190 41, 62, 83, 167
247 123 68, 87, 144, 159, 172, 178, 191, 235 12, 56, 69, 75, 88, 103, 160, 179
259 129 100, 121, 137, 149, 158, 186, 211, 232 27, 48, 73, 101, 110, 122, 138, 159
265 33 23, 83, 182, 242
289 9 38, 251, 110, 134, 155, 179, 40, 65, 75, 131, 158, 214, 224, 249
301 75 36, 44, 79, 92, 130, 135, 165, 221 80, 136, 166, 171, 209, 222, 257, 265
305 19 72, 133, 172, 233
325 81 126, 276 49, 199
341 85 4, 16, 47, 64, 70, 78, 97, 125, 126, 157, 159, 163, 188, 190, 202, 218, 221, 225, 256, 280, 287, 295, 311, 312 29, 30, 46, 54, 61, 85, 116, 120, 123, 139, 151, 153, 178, 182, 184, 215, 216, 244, 263, 271, 277, 294, 325, 337
343 171 18, 324 19, 325
361 45 28, 54, 62, 68, 99, 234, 245, 292 69, 116, 127, 262, 293, 299, 307, 333
365 91
377 47 70, 99, 278, 307
385 3 221, 331 54, 164
403 201 87, 94, 118, 191, 211, 222, 315, 373 30, 88, 181, 192, 212, 285, 309, 316
425 53 132, 157, 268, 293
427 213 74, 123, 135, 169, 184, 291, 352, 379 48, 75, 136, 243, 258, 292, 304, 353
435 217 16, 136, 181, 226, 256, 286 149, 179, 209, 254, 299, 419
451 225 16, 37, 42, 59, 79, 92, 100, 119, 124, 133, 141, 174, 180, 201, 221, 223, 247, 256, 262, 324, 344, 346, 379, 411 40, 72, 105, 107, 127, 189, 195, 204, 228, 230, 250, 271, 277, 310, 318, 327, 332, 351, 359, 373, 392, 409, 414, 435
469 117 29, 37, 135, 163, 305, 372, 403, 431 38, 66, 97, 164, 306, 334, 432, 440
475 237 26, 201 274, 449
481 15 100, 211, 248, 269, 334, 380, 417, 445 36, 64, 101, 147, 212, 233, 270, 381 6, 8, 31, 45, 60, 80, 97, 119, 125, 154, 162, 171, 177, 193, 214, 216, 228, 236, 245, 253, 265, 267, 288, 304, 310, 319, 327, 356, 362, 384, 401, 421, 436, 450, 473, 475
485 121 22, 172, 313, 463
493 123 157, 191, 302, 336
505 63 192, 212, 293, 313
511 255 8, 64, 74, 81, 137, 336, 373, 429 82, 138, 145, 374, 430, 437, 447, 503
529 33 118, 170, 177, 255, 266, 334, 399, 466, 487, 501 28, 42, 63, 130, 195, 263, 274, 352, 359, 411
533 133 73, 255, 278, 460
545 17 33, 142, 403, 512
553 69 23, 102, 134, 260, 317, 396, 450, 529 24, 103, 157, 236, 293, 419, 451, 530
559 279 79, 87, 92, 165, 178, 302, 380, 393 166, 179, 257, 381, 394, 467, 472, 480
561 35 103, 256, 460, 511 50, 101, 305, 458
565 141 98, 128, 437, 467
589 147 87, 125, 191, 273, 311, 315, 501, 552 37, 88, 274, 278, 316, 398, 464, 502
595 297 86, 256 339, 509
625 39 182, 443
629 157 191, 302, 327, 438
637 159 79, 165, 263, 295, 373, 393, 471, 508 129, 166, 244, 264, 342, 374, 472, 558
645 161 16, 121, 226, 256, 391, 451 194, 254, 389, 419, 524, 629
651 325 64, 190, 295, 442 209, 356, 461, 587
671 335 9, 20, 34, 58, 70, 81, 119, 180, 182, 203, 245, 278, 302, 306, 339, 367, 375, 386, 400, 485, 489, 522, 619, 630 41, 52, 149, 182, 186, 271, 285, 296, 304, 332, 365, 369, 393, 426, 468, 479, 491, 552, 590, 601, 613, 637, 651, 662
679 339 158, 326, 352, 389, 449, 520, 583, 617 62, 96, 159, 230, 290, 327, 353, 521
685 171 37, 237, 448, 648
689 43 83, 242, 447, 606
697 87 132, 319, 378, 565
703 351 7, 9, 16, 26, 44, 47, 49, 63, 81, 83, 100, 112, 118, 120, 121, 123, 137, 144, 149, 157, 158, 182, 194, 195, 197, 201, 218, 229, 232, 234, 248, 256, 271, 275, 292, 305, 308, 329, 330, 334, 340, 343, 349, 359, 366, 367, 377. 386, 396, 403, 404, 408, 416, 419, 423, 441, 453, 454, 460, 482, 491, 514, 519, 530, 552, 556, 562, 567, 571, 581, 593, 625, 636, 638, 655, 662, 663, 676, 682 3, 21, 27, 40, 41, 48, 65, 67, 78, 110, 122, 132, 136, 141, 147, 151, 173, 184, 189, 212, 221, 243, 249, 250, 262, 280, 284, 287, 295, 299, 300, 307, 317, 326, 336, 337, 344, 354, 360, 363, 369, 373, 374, 395, 398, 411, 428, 432, 447, 455, 469, 471, 474, 485, 502, 506, 508, 509, 521, 545, 546, 554, 559, 566, 580, 582, 583, 585, 591, 603, 620, 622, 640, 654, 656, 659, 677, 687, 694, 696
715 357 276, 386 329, 439
721 45 46, 149, 207, 310, 365, 561, 571, 674 47, 150, 160, 356, 411, 514, 572, 675
725 181 157, 307, 418, 568
745 93 193, 342, 403, 552
763 381 172, 219, 263, 281, 372, 499, 590, 655 108, 173, 264, 391, 482, 500, 544, 591
775 387 501, 676 99, 274
781 195 5, 25, 125, 147, 196, 199, 214, 218, 267, 289, 309, 356, 412, 427, 498, 522, 551, 554, 573, 625, 664, 696, 735, 764 17, 46, 85, 117, 156, 208, 227, 230, 259, 283, 354, 369, 425, 472, 492, 514, 563, 567, 582, 585, 634, 656, 756, 776
785 49 28, 342, 443, 757
793 99 74, 196, 230, 352, 367, 562, 672, 718 75, 121, 231, 426, 441, 563, 597, 719 11, 21, 32, 50, 72, 93, 111, 151, 154, 162, 215, 223, 255, 265, 284, 294, 345, 395, 398, 448, 499, 509, 528, 538, 570, 578, 631, 639, 642, 682, 700, 721, 743, 761, 772, 782
805 201 116, 576 229, 689
817 51 49, 87, 178, 216, 552, 638, 767, 780 37, 50, 179, 265, 601, 639, 730, 768
841 105 190, 571, 574, 605, 645, 778 63, 196, 236, 267, 270, 651 14, 41, 60, 137, 221, 374, 416, 425, 467, 620, 704, 781, 800, 827
845 211 268, 408, 437, 577
847 423 485, 606 241, 362
861 215 379, 631, 652, 715 146, 209, 230, 482
865 27 93, 253, 612, 772
871 435 29, 68, 230, 269, 573, 640, 833, 841 30, 38, 231, 298, 602, 641, 803, 842
889 111 107, 128, 361, 382, 400, 527, 781, 869 20, 108, 362, 489, 507, 528, 761, 782
891 445 82, 163, 487, 730 161, 404, 728, 809
901 225 30, 242, 659, 871
905 113 162, 343, 562, 743
925 231 26, 676 249, 899
931 465 30, 197, 324, 410, 520, 638, 704, 900 31, 227, 293, 411, 521, 607, 734, 901
949 237 74, 81, 300, 373, 575, 731, 794, 867 82, 155, 218, 374, 576, 649, 868, 875 24, 46, 70, 76, 97, 119, 122, 149, 216, 265, 268, 319, 362, 392, 411, 414, 435, 462, 487, 514, 535, 538, 557, 587, 630, 681, 684, 733, 800, 827, 830, 852, 873, 879, 903, 925
961 15 235, 338, 374, 388, 439, 448, 521, 531, 547, 628, 732, 816, 844, 846 115, 117, 145, 229, 333, 414, 430, 440, 513, 522, 573, 587, 623, 726
965 241 112, 467, 498, 853
973 243 235, 459, 513, 557, 652, 737, 835, 876 97, 138, 236, 321, 416, 460, 514, 738
985 123 183, 408, 577, 802
1001 125 92, 456, 729, 911 90, 272, 545, 909
1015 507 291, 436 579, 724
1025 1 32, 132, 893, 993
1027 513 55, 159, 339, 497, 529, 633, 924, 971 56, 103, 394, 498, 530, 688, 868, 972
1035 517 271, 361, 496, 541, 676, 721, 811, 901, 946, 991 44, 89, 134, 224, 314, 359, 494, 539, 674, 764
1037 259 72, 438, 599, 965
1045 261 111, 386, 441, 606, 771, 826, 881, 936 109, 164, 219, 274, 439, 604, 659, 934
1057 33 32, 183, 303, 485, 571, 722, 907, 1024 33, 150, 335, 486, 572, 754, 874, 1025
1065 133 91, 316, 616, 676, 811, 826 239, 254, 389, 449, 749, 974
1073 67 191, 260, 302, 771, 813, 882
1075 537 251, 651 424, 824
1099 549 144, 158, 169, 326, 772, 786, 954 13, 145, 313, 327, 773, 930, 941, 955
1105 69 256, 341 764, 849 47, 72, 98, 123, 132, 242, 268, 293, 327, 353, 463, 548, 557, 642, 752, 778, 812, 837, 863, 973, 982, 1007, 1033, 1058
1111 555 36, 102, 137, 185, 188, 196, 203, 289, 339, 390, 405, 488, 499, 592, 642, 708, 892, 895, 903, 993, 1004, 1046, 1094, 1105 6, 17, 65, 107, 118, 208, 216, 219, 403, 469, 519, 612, 623, 706, 721, 772, 822, 908, 915, 923, 926, 974, 1009, 1075
1141 285 58, 221, 267, 547, 653, 816, 919, 1082 59, 222, 325, 488, 594, 874, 920, 1083
1145 143 107, 122, 1023, 1038
1147 573 63, 149, 211, 408, 470, 528, 676, 935 212, 471, 619, 677, 739, 936, 998, 1084
1221 305 223, 334, 445, 889 332, 776, 887, 998
1225 153 226, 851 374, 999
1241 155 319, 557, 684, 922
1261 315 35, 61, 326, 352, 874, 971 36, 62, 290, 387, 909, 935, 1200, 1226
1273 159 68, 96, 163, 305, 372, 805, 900, 1109 164, 373, 468, 901, 968, 1110, 1177, 1205
1281 5 253, 400, 1156, 1240 41, 125, 881, 1028
1309 327 375, 562 747, 934
1313 41 515, 616, 697, 798
1333 333 36, 87, 466, 552, 780, 904, 1210, 1296 37, 123, 429, 553, 781, 867, 1246, 1297
1345 21 82, 187, 1158, 1263
1369 171 581, 678, 737, 787, 932, 1015, 1045, 1069 300, 324, 354, 437, 582, 632, 691, 788 18, 76, 117, 348, 356, 424, 473, 476, 494, 875, 893, 896, 945, 1013, 1021, 1252, 1293, 1351
1385 173 217, 337, 1048, 1168
1393 87 92, 106, 200, 291, 305, 996, 1087, 1101 292, 306, 397, 1088, 1102, 1193, 1287, 1301
1417 177 172, 263, 328, 1153, 1244, 1262, 1309, 1353 64, 108, 155, 173, 264, 1089, 1154, 1245 8. 33, 41, 76, 150, 177, 210, 226, 294, 319, 395, 444, 512, 553, 578, 613, 687, 695, 722, 730, 804, 839, 864, 905, 973, 1022, 1098, 1123, 1191, 1207, 1240, 1267, 1341, 1376, 1384, 1409
1441 45 53, 58, 89, 192, 320, 323, 394, 454, 482, 577, 708, 713, 716, 839, 918, 1006, 1049, 1101, 1109, 1137, 1180, 1237, 1268. 1368 73, 173, 204, 261, 304, 332, 340, 392, 435, 523, 602, 725, 728, 733, 864, 959, 987, 1047, 1118, 1121, 1249, 1352, 1383, 1388
1445 361 38, 327, 1118, 1407
1465 183 138, 448, 1017, 1327
1469 367 437, 580, 889, 1032
1477 369 212, 225, 407, 436, 681, 634, 858, 1040 437, 619, 843, 859, 1041, 1070, 1252, 1265
1501 375 102, 134, 159, 292, 1208, 1265, 1398, 1445 56, 103, 236, 293, 1209, 1342, 1367, 1399

See also

  • Richard E. Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, 2001, ISBN 0-387-25282-7.
  • Paulo Ribenboim, The New Book of Prime Number Records, Springer-Verlag, 1996, ISBN 0-387-94457-5.