mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2014-09-27, 03:02   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

918210 Posts
Post "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
Batalov is offline   Reply With Quote
Old 2014-09-27, 17:53   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

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)
Batalov is offline   Reply With Quote
Old 2014-09-27, 20:45   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

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)
paulunderwood is offline   Reply With Quote
Old 2014-09-27, 21:04   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

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!
Batalov is offline   Reply With Quote
Old 2014-09-27, 21:15   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

Quote:
Originally Posted by Batalov View Post

P.S. There's another one!
Congrats. Are you going for #1?
paulunderwood is offline   Reply With Quote
Old 2014-09-27, 21:53   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

30478 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
Citrix is offline   Reply With Quote
Old 2014-09-28, 01:52   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011110111102 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
Batalov is offline   Reply With Quote
Old 2014-09-28, 06:29   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101101100012 Posts
Default

Congrats again, this time for 681817 digits
paulunderwood is offline   Reply With Quote
Old 2014-10-03, 19:32   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217368 Posts
Default 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)".
Batalov is offline   Reply With Quote
Old 2014-10-10, 15:34   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

Congrats yet again, this time for a megaprime: 2 * 59^608685 + 1

Last fiddled with by paulunderwood on 2014-10-10 at 15:34
paulunderwood is offline   Reply With Quote
Old 2014-10-10, 18:25   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

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).
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Any fast paths out of Category 3 purgatory NookieN PrimeNet 9 2018-06-18 19:14
Option to prefer higher category work? Runtime Error PrimeNet 4 2018-01-07 20:20
646730219521 Divides F19 Buckle Factoring 7 2010-03-29 22:56
p^n - 1 divides p^m - 1 ==> n divides m jinydu Homework Help 10 2008-08-06 19:17

All times are UTC. The time now is 20:35.

Wed Dec 2 20:35:15 UTC 2020 up 83 days, 17:46, 2 users, load averages: 1.53, 1.52, 1.69

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.