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

 2014-09-27, 03:02 #1 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×13×359 Posts "Divides Phi" category This is an interesting category, and Keller, Broadhurst and others submitted many such primes. The test for it is implemented in the old Y.Gallot's Proth.exe (the newest executable is >10 years old but it runs; its SSE2 code emits an error on modern CPUs, so this can be disabled in 'Options'). Because there is no detailed page for the properties of such numbers, I took a sheet of paper and sat for an hour pondering. Ok, what do we know? 1. Candidates can be primes p = 2q^n+1 with prime q. 2. q ≡ 11 (mod 12) is a well known requirement. (Proof is left to the reader. :wink-wink: ... Seriously though, there probably exists a paper from Keller and probably as early as from 70s) 3. n is odd. 4. $Phi(q^n,2) = {{2^{q^n} -1} \over {2^{q^{n-1}} -1}}$, so we need 2^q^n ≡ 1 (mod p) but 2^q^{n-1} $\ne$ 1 (mod p) UTM database carries some more exotic examples: with k>2 (then q is not restricted to 11 (mod 12) and n is not only odd) or with k*q^n+1 | Phi(q^m,2), where m != n. This category sieves well with sr1sieve (cannot combine multiple bases into one workunit for sr2sieve) and tests with LLR. Final check can be done with the old Proth.exe or with modified LLR (with 2^q $\ne$ 1 (mod p) added test). _____________________ 2 · 10859^87905 + 1 and 2 · 11171^100961+1 are found and are under final check with Proth.exe (this is quite slow)... Both checks finished: both divide Phi(q^n,2). Last fiddled with by Batalov on 2014-09-27 at 17:54 Reason: some fluff removed
 2014-09-27, 17:53 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts Keller (with Ingo Buechel) once reported to have searched k=2 for bases 383 (limit 433k), 467 (347k; a prime found in 2006!), 647 (322k), 947 (105k), 67607 (412k !!). These series have no known primes. These efforts could be of some interest to CRUS; I've seen these values still outstanding when I scanned their status yesterday. Last fiddled with by Batalov on 2014-09-27 at 18:29 Reason: fixed a typo (in the quoted message)
 2014-09-27, 20:45 #3 paulunderwood     Sep 2002 Database er0rr 2·7·257 Posts http://primes.utm.edu/primes/page.php?id=118560 does not appear on http://primes.utm.edu/top20/page.php?id=37 EDIT: it does now. C.C. was away for a day. Last fiddled with by Batalov on 2014-09-29 at 17:28 Reason: (official comment was updated)
 2014-09-27, 21:04 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts All of these initial labels get manually promoted by C. "The Prime Mogul " C. Or 'demoted' as the case may be for "Divides xGF(n,a,b)!!!!" that get automatically submitted by the PrimeGrid's engine. It's the weekend. P.S. There's another one!
2014-09-27, 21:15   #5
paulunderwood

Sep 2002
Database er0rr

2·7·257 Posts

Quote:
 Originally Posted by Batalov P.S. There's another one!
Congrats. Are you going for #1?

2014-09-27, 21:53   #6
Citrix

Jun 2003

30538 Posts

Quote:
 Originally Posted by Batalov Keller (with Ingo Buechel) once reported to have searched k=2 for bases 383 (limit 433k), 467 (347k; a prime found in 2006!), 647 (322k), 947 (105k), 67607 (412k !!). These series have no known primes. These efforts could be of some interest to CRUS; I've seen these values still outstanding when I scanned their status yesterday.
You might be interested in http://www.mersenneforum.org/showthr...t=10354&page=3 (This is an extremely big project to work on:( )

Also there used to be a project to search 2*a^a+1....everything under 40k was tested.

2014-09-28, 01:52   #7
Batalov

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

2·13·359 Posts

Quote:
 Originally Posted by paulunderwood Congrats. Are you going for #1?
Certainly.

But this time with a proof of Dividing Phi first, and submitting second. It should show up in the top in about two hours, with overall rank ~271.

 2014-09-28, 06:29 #8 paulunderwood     Sep 2002 Database er0rr 2×7×257 Posts Congrats again, this time for 681817 digits
 2014-10-03, 19:32 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts the order-of-2 (mod p) test I have modded LLR to run a naively refactored order-of-2-mod p test instead of Proth.exe (and even though naive, this is a fast solution; as fast as the primality test, 1-2 hr max; this is what I used for the current top1 and top3; Proth.exe would have taken cpu-days). I've scanned all known 155 current and former "Divides Phi" categorized Proth primes and they, of course, all confirmed. After that validity test, I moved on to the untagged prime and composite base q Proth numbers (Proth.exe does not run the order-of-2 test on them), and found half a dozen interesting divisors. The largest of them is Ian's CRUS S695 prime with k=2, and it was large enough to enter the top20. While the initial identification of such numbers is routine (we can check that 2^(q^n) ≡ 1 (mod k*q^n+1)), the determination of exact Phi() that they divide is more cumbersome than with prime q's. One has to divide away all prime factors of q separately and together until 2^(q^n/factors) !≡ 1. For this particular number, 695 = 5 * 139 and while 2^(q^n/139) already !≡ 1, 2^(q^n/5^k) ≡ 1 for 0<=k<=4 and not for k=5. Hence, as reported, "Divides Phi(695^94625/5^4,2)".
 2014-10-10, 15:34 #10 paulunderwood     Sep 2002 Database er0rr 2·7·257 Posts Congrats yet again, this time for a megaprime: 2 * 59^608685 + 1 Last fiddled with by paulunderwood on 2014-10-10 at 15:34
 2014-10-10, 18:25 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 933410 Posts Thanks. Of course a prime q=383, 647, 947 or 67607 (no known primes) would have been so much nicer, but after quite a bit of time spent on them nothing yet was found. So, a small fishing expedition was sent out to small q's - even though they have known primes, they are much faster (this is a short version of a long story; 67607, unfortunately is "generic FFT" only, which is very significantly slower).

 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 12:06.

Tue Mar 9 12:06:43 UTC 2021 up 96 days, 8:18, 0 users, load averages: 1.33, 1.30, 1.32