mersenneforum.org "Divides Phi" category
 Register FAQ Search Today's Posts Mark Forums Read

 2019-03-09, 22:47 #34 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 23×5×17 Posts If he gave me the source code, I could compile it myself (using Windows Bash). I really want to try it out. Last fiddled with by Stargate38 on 2019-03-09 at 22:49
 2019-03-09, 23:34 #35 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5,153 Posts What makes you think it is free, or open source? Has it not crossed your mind to offer to purchase it from him? Then again, you've shown a propensity in many threads to demand things be given to you. Perhaps, if his price is too high for you, you could write something similar yourself, and donate it to the community to show you understand the value of labor.
 2020-05-18, 18:09 #36 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,229 Posts I have identified two enormous new top entries for the "Divides Phi" category; they will probably appear in a few days. (they are previously identified as primes) One of them has m << n *. I even need to brush the dust off my old source and.or rewrite from scratch (that ancient LLR patch doesn't stick to newer versions of LLR). In fact for the very special use case ( b=3 ), I am compelled to write special code. ___ Footnote: similar to the Fermat factor notation (which is of course a sub-case of a cyclotomic, with b=2), k * bn +1 may divide some Phi( bm , 2). with m<=n. For b>3, almost always, m is = n or nearly n. But for b = 3, there is a higher chance of m being way lower than n.
2020-05-19, 20:34   #37
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,229 Posts

Quote:
 Proposition (Wilfrid Keller): If p = 2*3^n + 1 is prime then p divides 2^(3^n) + (-1)^n. I think that Wilfrid Keller gave me a proof of this, 20 years ago, but I have forgotten it, sorry. Chris may provide it? The converse is mere supposition. Conjecture 2: If p = 2*3^n + 1 is an integer that divides 2^(3^n) + (-1)^n, then p is prime.
...and I can see that first proposition holds really well, just try it in PARI and you will find that Mod(2,p)^((p-1)/2) is -1 for even n, and +1 for odd n values.

(Recall that if p is prime, then Mod(2,p)^(p-1) = 1 by little Fermat. We are looking at its square root and it is either -1 or +1. There is probably a short path to demonstrating that it is -1 and +1 precisely for even and odd n values.)

For conjecture 2, we need to prove that this is a primality test. A slightly weaker version is to square and say that the 2-PRP Fermat test is a strict primality test for p = 2*3^n + 1 family.

This conjecture 2 reminds me strongly of the Iskra-Berrizbeitia test for the Gaussian-Mersenne series. (in it, you do a test that is visually just slightly shorter than a 5-PRP test but their theorem proves that this is a strict primality proof.)

2020-05-19, 21:10   #38
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·32·5·17 Posts

Quote:
 Originally Posted by Batalov (Recall that if p is prime, then Mod(2,p)^(p-1) = 1 by little Fermat. We are looking at its square root and it is either -1 or +1. There is probably a short path to demonstrating that it is -1 and +1 precisely for even and odd n values.)
Check out https://en.wikipedia.org/wiki/Euler%27s_criterion, pretty old, but still good stuff.

 2020-05-20, 00:05 #39 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 968710 Posts I think I see. Does it take care of Conjecture 2, as well?
2020-05-20, 08:57   #40
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101111110102 Posts

Quote:
 Originally Posted by Batalov I think I see. Does it take care of Conjecture 2, as well?
You need a little more:
For N=2*3^n+1 if 2^(N-1)==1 mod N and gcd(2^((N-1)/3)-1,N)=1 then N is prime, direct use of the Generalized Pocklington theorem. So provable, and roughly in the same time (just need one more gcd).

2020-05-30, 13:57   #41
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

7×457 Posts

All odd prime p divides Phi(n,2) for an integer n, in fact, n = ord_p(2)

Code:
p, n
3, 2
5, 4
7, 3
11, 10
13, 12
17, 8
19, 18
23, 11
29, 28
31, 5
37, 36
41, 20
43, 14
47, 23
53, 52
59, 58
61, 60
67, 66
71, 35
73, 9
79, 39
83, 82
89, 11
97, 48
101, 100
103, 51
107, 106
109, 36
113, 28
127, 7
131, 130
137, 68
139, 138
149, 148
151, 15
157, 52
163, 162
167, 83
173, 172
179, 178
181, 180
191, 95
193, 96
197, 196
199, 99
211, 210
223, 37
227, 226
229, 76
233, 29
239, 119
241, 24
251, 50
257, 16
263, 131
269, 268
271, 135
277, 92
281, 70
283, 94
293, 292
307, 102
311, 155
313, 156
317, 316
331, 30
337, 21
347, 346
349, 348
353, 88
359, 179
367, 183
373, 372
379, 378
383, 191
389, 388
397, 44
401, 200
409, 204
419, 418
421, 420
431, 43
433, 72
439, 73
443, 442
449, 224
457, 76
461, 460
463, 231
467, 466
479, 239
487, 243
491, 490
499, 166
503, 251
509, 508
521, 260
523, 522
541, 540
547, 546
557, 556
563, 562
569, 284
571, 114
577, 144
587, 586
593, 148
599, 299
601, 25
607, 303
613, 612
617, 154
619, 618
631, 45
641, 64
643, 214
647, 323
653, 652
659, 658
661, 660
673, 48
677, 676
683, 22
691, 230
701, 700
709, 708
719, 359
727, 121
733, 244
739, 246
743, 371
751, 375
757, 756
761, 380
769, 384
773, 772
787, 786
797, 796
809, 404
811, 270
821, 820
823, 411
827, 826
829, 828
839, 419
853, 852
857, 428
859, 858
863, 431
877, 876
881, 55
883, 882
887, 443
907, 906
911, 91
919, 153
929, 464
937, 117
941, 940
947, 946
953, 68
967, 483
971, 194
977, 488
983, 491
991, 495
997, 332
1009, 504
1013, 92
1019, 1018
1021, 340
1031, 515
1033, 258
1039, 519
1049, 262
1051, 350
1061, 1060
1063, 531
1069, 356
1087, 543
1091, 1090
1093, 364
1097, 274
1103, 29
1109, 1108
1117, 1116
1123, 1122
1129, 564
1151, 575
1153, 288
1163, 166
1171, 1170
1181, 236
1187, 1186
1193, 298
1201, 300
1213, 1212
1217, 152
1223, 611
1229, 1228
1231, 615
1237, 1236
1249, 156
1259, 1258
1277, 1276
1279, 639
1283, 1282
1289, 161
1291, 1290
1297, 648
1301, 1300
1303, 651
1307, 1306
1319, 659
1321, 60
1327, 221
1361, 680
1367, 683
1373, 1372
1381, 1380
1399, 233
1409, 704
1423, 237
1427, 1426
1429, 84
1433, 179
1439, 719
1447, 723
1451, 1450
1453, 1452
1459, 486
1471, 245
1481, 370
1483, 1482
1487, 743
1489, 744
1493, 1492
1499, 1498
1511, 755
1523, 1522
1531, 1530
1543, 771
1549, 1548
1553, 194
1559, 779
1567, 783
1571, 1570
1579, 526
1583, 791
1597, 532
1601, 400
1607, 803
1609, 201
1613, 52
1619, 1618
1621, 1620
1627, 542
1637, 1636
1657, 92
1663, 831
1667, 1666
1669, 1668
1693, 1692
1697, 848
1699, 566
1709, 244
1721, 215
1723, 574
1733, 1732
1741, 1740
1747, 1746
1753, 146
1759, 879
1777, 74
1783, 891
1787, 1786
1789, 596
1801, 25
1811, 362
1823, 911
1831, 305
1847, 923
1861, 1860
1867, 1866
1871, 935
1873, 936
1877, 1876
1879, 939
1889, 472
1901, 1900
1907, 1906
1913, 239
1931, 1930
1933, 644
1949, 1948
1951, 975
1973, 1972
1979, 1978
1987, 1986
1993, 996
1997, 1996
1999, 333
2003, 286
2011, 402
2017, 336
2027, 2026
2029, 2028
2039, 1019
2053, 2052
2063, 1031
2069, 2068
2081, 1040
2083, 2082
2087, 1043
2089, 29
2099, 2098
2111, 1055
2113, 44
2129, 532
2131, 2130
2137, 1068
2141, 2140
2143, 51
2153, 1076
2161, 1080
2179, 726
2203, 734
2207, 1103
2213, 2212
2221, 2220
2237, 2236
2239, 1119
2243, 2242
2251, 750
2267, 2266
2269, 2268
2273, 568
2281, 190
2287, 381
2293, 2292
2297, 1148
2309, 2308
2311, 1155
2333, 2332
2339, 2338
2341, 780
2347, 782
2351, 47
2357, 2356
2371, 2370
2377, 1188
2381, 476
2383, 397
2389, 2388
2393, 598
2399, 1199
2411, 482
2417, 1208
2423, 1211
2437, 2436
2441, 305
2447, 1223
2459, 2458
2467, 2466
2473, 618
2477, 2476
2503, 1251
2521, 1260
2531, 2530
2539, 2538
2543, 1271
2549, 2548
2551, 1275
2557, 2556
2579, 2578
2591, 1295
2593, 81
2609, 1304
2617, 1308
2621, 2620
2633, 1316
2647, 1323
2657, 166
2659, 2658
2663, 1331
2671, 445
2677, 2676
2683, 2682
2687, 79
2689, 224
2693, 2692
2699, 2698
2707, 2706
2711, 1355
2713, 1356
2719, 1359
2729, 1364
2731, 26
2741, 2740
2749, 916
2753, 1376
2767, 461
2777, 1388
2789, 2788
2791, 465
2797, 2796
2801, 1400
2803, 2802
2819, 2818
2833, 118
2837, 2836
2843, 2842
2851, 2850
2857, 102
2861, 2860
2879, 1439
2887, 1443
2897, 1448
2903, 1451
2909, 2908
2917, 972
2927, 1463
2939, 2938
2953, 492
2957, 2956
2963, 2962
2969, 371
2971, 110
2999, 1499
3001, 1500
3011, 3010
3019, 3018
3023, 1511
3037, 3036
3041, 1520
3049, 762
3061, 204
3067, 3066
3079, 1539
3083, 3082
3089, 772
3109, 444
3119, 1559
3121, 156
3137, 784
3163, 1054
3167, 1583
3169, 1584
3181, 1060
3187, 3186
3191, 55
3203, 3202
3209, 1604
3217, 804
3221, 644
3229, 1076
3251, 650
3253, 3252
3257, 407
3259, 1086
3271, 545
3299, 3298
3301, 660
3307, 3306
3313, 828
3319, 1659
3323, 3322
3329, 1664
3331, 222
3343, 557
3347, 3346
3359, 1679
3361, 168
3371, 3370
3373, 1124
3389, 484
3391, 113
3407, 1703
3413, 3412
3433, 1716
3449, 431
3457, 576
3461, 3460
3463, 577
3467, 3466
3469, 3468
3491, 3490
3499, 3498
3511, 1755
3517, 3516
3527, 1763
3529, 882
3533, 3532
3539, 3538
3541, 236
3547, 3546
3557, 3556
3559, 1779
3571, 3570
3581, 3580
3583, 1791
3593, 1796
3607, 601
3613, 3612
3617, 1808
3623, 1811
3631, 605
3637, 3636
3643, 3642
3659, 3658
3671, 1835
3673, 918
3677, 3676
3691, 3690
3697, 1848
3701, 3700
3709, 3708
3719, 1859
3727, 1863
3733, 3732
3739, 534
3761, 188
3767, 1883
3769, 1884
3779, 3778
3793, 1896
3797, 3796
3803, 3802
3821, 764
3823, 637
3833, 958
3847, 1923
3851, 3850
3853, 3852
3863, 1931
3877, 3876
3881, 388
3889, 648
3907, 3906
3911, 1955
3917, 3916
3919, 1959
3923, 3922
3929, 1964
3931, 3930
3943, 219
3947, 3946
3967, 1983
3989, 3988
4001, 1000
4003, 4002
4007, 2003
4013, 4012
4019, 4018
4021, 4020
4027, 1342
4049, 506
4051, 50
4057, 169
4073, 2036
4079, 2039
4091, 4090
4093, 4092
Attached Files
 factorization of Phi(n,2).txt (80.6 KB, 174 views)

 2020-05-30, 13:58 #42 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 7×457 Posts The thread seems to be "factorization of Phi(n,2) for very large n", e.g. 2 · 10859^87905 + 1 is a factor of Phi(n,2) for n=10859^87905 Also, Phi(n,2) is completely factored for all n<=1206
 2020-05-30, 14:02 #43 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 319910 Posts Are there any factorization status for Phi(n,2) for n<=2^16 e.g. for n=3005, the factorization status for Phi(n,2) is Code: 385549595471 (12 digits) * 13122095873179566186720736445243053751 (38 digits) * 302457545946976075241913...444613530959396558225431 (a composite with 674 digits)
 2020-05-30, 19:44 #44 carpetpool     "Sam" Nov 2016 22×83 Posts There is also this possible sequence I am approaching the T5K range for. It would be interesting to find a prime (k=6) making the "Divides Phi" achievable class (Probability 1/3). There is one here found about two decades ago. I can attach the sieve file associated for this sequence if anyone's interested in testing further. Last fiddled with by carpetpool on 2020-05-30 at 19:50

 Similar Threads Thread Thread Starter Forum Replies Last Post NookieN PrimeNet 9 2018-06-18 19:14 Runtime Error PrimeNet 4 2018-01-07 20:20 Buckle Factoring 7 2010-03-29 22:56 jinydu Homework Help 10 2008-08-06 19:17

All times are UTC. The time now is 09:58.

Wed Jan 19 09:58:33 UTC 2022 up 180 days, 4:27, 0 users, load averages: 1.33, 1.24, 1.22