"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 [URL="http://primes.utm.edu/top20/page.php?id=37"]no detailed page[/URL] 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. [TEX]Phi(q^n,2) = {{2^{q^n} -1} \over {2^{q^{n-1}} -1}}[/TEX], so we need 2^q^n ≡ 1 (mod p) but 2^q^{n-1} [TEX]\ne[/TEX] 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 [TEX]\ne[/TEX] 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)... [COLOR=DarkGreen]Both checks finished: both divide Phi(q^n,2).[/COLOR]

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.

[url]http://primes.utm.edu/primes/page.php?id=118560[/url] does not appear on [url]http://primes.utm.edu/top20/page.php?id=37[/url] :geek:


[COLOR="DarkGreen"][SIZE="1"]EDIT: it does now. C.C. was away for a day.[/SIZE][/COLOR]

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 [URL="http://primes.utm.edu/primes/page.php?id=118563"]another one[/URL]!

[QUOTE=Batalov;383988]

P.S. There's [URL="http://primes.utm.edu/primes/page.php?id=118563"]another one[/URL]![/QUOTE]

Congrats. Are you going for #1? :smile:

[QUOTE=Batalov;383979]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.[/QUOTE]

You might be interested in [url]http://www.mersenneforum.org/showthread.php?t=10354&page=3[/url] (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.

[QUOTE=paulunderwood;383990]Congrats. Are you going for #1? :smile:[/QUOTE]
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.

Congrats again, this time for [URL="http://primes.utm.edu/primes/page.php?id=118564"]681817 digits[/URL] :toot:

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 [URL="http://primes.utm.edu/primes/page.php?id=97516"]enter the top20[/URL].

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)".

Congrats yet again, this time for a megaprime: [URL="http://primes.utm.edu/primes/page.php?id=118614"]2 * 59^608685 + 1[/URL] :banana:

Thanks.

[SIZE="1"]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 [I]very[/I] significantly slower).[/SIZE]

After the recent George's fix to the foundation (which allows choosing fast special FFT where available, much faster than a general mod), the search for a 2*67607^n+1 prime (and a likely Divides Phi entry) is now possible once again! I'll give it a shot, maybe...

I have observed a slew of "Divides Phi" mega-primes being submitted. Are these easy to find or are these due to a lot of crunching?

Edit: Congratulations!

It's a lot of iron and a good choice of candidates :rolleyes:
...and having the DivPhi self-compiled binary.
Put these three together and you got something.

Any chance you could tell me how/where to get that DivPhi binary, or at least its source code? I would love to crunch some of those numbers myself. Just something to do when I'm not running factorizations.

I really want to download that program of yours.
 

It's been over a month, and there's been no answer to my question. Where can I get DivPhi?

all n's and k's are written in duodecimal, only consider n ends with E (i.e. n = 11 mod 12), searched to duodecimal 1000 (decimal 1728).

[QUOTE=sweety439;510169]all n's and k's are written in duodecimal, only consider n ends with E (i.e. n = 11 mod 12), searched to duodecimal 1000 (decimal 1728).[/QUOTE]
[COLOR="Red"]That is false. [/COLOR]
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46623 2*3^152529+1 72776 gb 2000 Divides Phi(3^152528,2)
88279 2*3^6225+1 2971 C 1992 Divides Phi(3^6223,2)
94491 2*3^4217+1 2013 C 1992 Divides Phi(3^4217,2)
[/CODE]

And what about these examples?
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46760 10*79^37853+1 71832 p67 2005 Divides Phi(79^37853,2)
47960 6*31^43640+1 65084 p67 2004 Divides Phi(31^43640,2)
47983 22*5^93078+1 65061 p67 2004 Divides Phi(5^93077,2)
49755 10*7^70115+1 59256 p67 2004 Divides Phi(7^70114,2)
58087 72*7^40122+1 33909 g151 2002 Divides Phi(7^40121,2)
62022 10*79^15023+1 28510 g255 2003 Divides Phi(79^15023,2)
63201 10*7^29447+1 24887 g151 2000 Divides Phi(7^29446,2)
73588 6*19^8776+1 11224 gk 1999 Divides Phi(19^8776,2)
73855 10*43^6569+1 10732 g154 1999 Divides Phi(43^6569,2)
75051 6*17^7717+1 9497 gk 1999 Divides Phi(17^7717,2)
75656 38*5^12727+1 8898 gk 2000 Divides Phi(5^12727,2)
77176 8*29^5189+1 7590 gk 2000 Divides Phi(29^5189,2)
81124 40*19^4531+1 5796 gk 1999 Divides Phi(19^4531,2)
92326 10*10111^551+1 2208 g141 1999 Divides Phi(10111^551,2)
96820 10*10111^431+1 1728 g141 1999 Divides Phi(10111^431,2)
97115 30*7^1944+1 1645 K 1994 Divides Phi(7^1944,2)
97376 30*11^1514+1 1579 K 1994 Divides Phi(11^1514,2)
97522 30*19^1210+1 1549 K 1994 Divides Phi(19^1210,2)
98309 16*13^1309+1 1460 K 1994 Divides Phi(13^1309,2)
102020 40*29^886+1 1298 K 1994 Divides Phi(29^886,2)
102436 24*19^1005+1 1287 K 1994 Divides Phi(19^1005,2)
106355 30*13^1074+1 1198 K 1994 Divides Phi(13^1074,2)
118605 26*3^2121+1 1014 K 1994 Divides Phi(3^2121,2)
118738 8*29^689+1 1009 K 1994 Divides Phi(29^689,2)
[/CODE]

[QUOTE=Batalov;510184][COLOR="Red"]That is false. [/COLOR]
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46623 2*3^152529+1 72776 gb 2000 Divides Phi(3^152528,2)
88279 2*3^6225+1 2971 C 1992 Divides Phi(3^6223,2)
94491 2*3^4217+1 2013 C 1992 Divides Phi(3^4217,2)
[/CODE]

And what about these examples?
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46760 10*79^37853+1 71832 p67 2005 Divides Phi(79^37853,2)
47960 6*31^43640+1 65084 p67 2004 Divides Phi(31^43640,2)
47983 22*5^93078+1 65061 p67 2004 Divides Phi(5^93077,2)
49755 10*7^70115+1 59256 p67 2004 Divides Phi(7^70114,2)
58087 72*7^40122+1 33909 g151 2002 Divides Phi(7^40121,2)
62022 10*79^15023+1 28510 g255 2003 Divides Phi(79^15023,2)
63201 10*7^29447+1 24887 g151 2000 Divides Phi(7^29446,2)
73588 6*19^8776+1 11224 gk 1999 Divides Phi(19^8776,2)
73855 10*43^6569+1 10732 g154 1999 Divides Phi(43^6569,2)
75051 6*17^7717+1 9497 gk 1999 Divides Phi(17^7717,2)
75656 38*5^12727+1 8898 gk 2000 Divides Phi(5^12727,2)
77176 8*29^5189+1 7590 gk 2000 Divides Phi(29^5189,2)
81124 40*19^4531+1 5796 gk 1999 Divides Phi(19^4531,2)
92326 10*10111^551+1 2208 g141 1999 Divides Phi(10111^551,2)
96820 10*10111^431+1 1728 g141 1999 Divides Phi(10111^431,2)
97115 30*7^1944+1 1645 K 1994 Divides Phi(7^1944,2)
97376 30*11^1514+1 1579 K 1994 Divides Phi(11^1514,2)
97522 30*19^1210+1 1549 K 1994 Divides Phi(19^1210,2)
98309 16*13^1309+1 1460 K 1994 Divides Phi(13^1309,2)
102020 40*29^886+1 1298 K 1994 Divides Phi(29^886,2)
102436 24*19^1005+1 1287 K 1994 Divides Phi(19^1005,2)
106355 30*13^1074+1 1198 K 1994 Divides Phi(13^1074,2)
118605 26*3^2121+1 1014 K 1994 Divides Phi(3^2121,2)
118738 8*29^689+1 1009 K 1994 Divides Phi(29^689,2)
[/CODE][/QUOTE]

Well, I am already searched 2*n^k+1 and 2*n^k-1 for all bases n up to duodecimal 1000 (decimal 1728), and the exponent k are also searched to k=duodecimal 1000 (decimal 1728), there are only few bases n<=1000 (decimal 1728) without primes of the form 2*n^k+1 or 2*n^k-1 with k<=1000 (decimal 1728), these are the two text files, if you want it. Note: all the n's and k's in these two text files are written in duodecimal, and for 2*n^k+1, if n=1 (mod 3), then all numbers of the form 2*n^k+1 are divisible by 3, thus, I didn't search 2*n^k+1 for n=1 (mod 3), i.e. n ends with 1, 4, 7, or X in duodecimal.

[QUOTE=Batalov;510184][COLOR="Red"]That is false. [/COLOR]
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46623 2*3^152529+1 72776 gb 2000 Divides Phi(3^152528,2)
88279 2*3^6225+1 2971 C 1992 Divides Phi(3^6223,2)
94491 2*3^4217+1 2013 C 1992 Divides Phi(3^4217,2)
[/CODE]

And what about these examples?
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46760 10*79^37853+1 71832 p67 2005 Divides Phi(79^37853,2)
47960 6*31^43640+1 65084 p67 2004 Divides Phi(31^43640,2)
47983 22*5^93078+1 65061 p67 2004 Divides Phi(5^93077,2)
49755 10*7^70115+1 59256 p67 2004 Divides Phi(7^70114,2)
58087 72*7^40122+1 33909 g151 2002 Divides Phi(7^40121,2)
62022 10*79^15023+1 28510 g255 2003 Divides Phi(79^15023,2)
63201 10*7^29447+1 24887 g151 2000 Divides Phi(7^29446,2)
73588 6*19^8776+1 11224 gk 1999 Divides Phi(19^8776,2)
73855 10*43^6569+1 10732 g154 1999 Divides Phi(43^6569,2)
75051 6*17^7717+1 9497 gk 1999 Divides Phi(17^7717,2)
75656 38*5^12727+1 8898 gk 2000 Divides Phi(5^12727,2)
77176 8*29^5189+1 7590 gk 2000 Divides Phi(29^5189,2)
81124 40*19^4531+1 5796 gk 1999 Divides Phi(19^4531,2)
92326 10*10111^551+1 2208 g141 1999 Divides Phi(10111^551,2)
96820 10*10111^431+1 1728 g141 1999 Divides Phi(10111^431,2)
97115 30*7^1944+1 1645 K 1994 Divides Phi(7^1944,2)
97376 30*11^1514+1 1579 K 1994 Divides Phi(11^1514,2)
97522 30*19^1210+1 1549 K 1994 Divides Phi(19^1210,2)
98309 16*13^1309+1 1460 K 1994 Divides Phi(13^1309,2)
102020 40*29^886+1 1298 K 1994 Divides Phi(29^886,2)
102436 24*19^1005+1 1287 K 1994 Divides Phi(19^1005,2)
106355 30*13^1074+1 1198 K 1994 Divides Phi(13^1074,2)
118605 26*3^2121+1 1014 K 1994 Divides Phi(3^2121,2)
118738 8*29^689+1 1009 K 1994 Divides Phi(29^689,2)
[/CODE][/QUOTE]

Um... Currently I know what you means, not only 2*b^n+1 with b ends with E in duodecimal, but also some numbers k*b^n+1 with k>2 also divides Phi(b^n,2) ... but these b's seem to be all primes ...... of course since gcd(k+1,b-1) must be 1 and b is prime > 2 (thus odd), thus these k's must be even ... but are there any k=4 primes?

[QUOTE=sweety439;510197]Um... these b's seem to be all primes .....[/QUOTE]
Wrong again.
[CODE]2*695^94625+1 Divides Phi(695^94625/5^4,2) [g427] [268924 digits] L1471 2011 [/CODE]

[QUOTE=Batalov;510220]Wrong again.
[CODE]2*695^94625+1 Divides Phi([B]695^94625/5^4[/B],2) [g427] [268924 digits] L1471 2011 [/CODE][/QUOTE]

This is not "Divides Phi([B]695^94625[/B],2)", i.e. k*b^n+1 does not divide Phi(b^n,2), and not belong to this category.

[QUOTE=sweety439;510243]This is not "Divides Phi([B]695^94625[/B],2)", i.e. k*b^n+1 does not divide Phi(b^n,2), and not belong to this category.[/QUOTE]

And wrong again.
You appear to look but not see. (Also explains your endless threads with miniature results.)

Look [B]carefully [/B]at these first two lines (posted before) --
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46623 2*3^152529+1 72776 gb 2000 Divides Phi(3^152528,2)
88279 2*3^6225+1 2971 C 1992 Divides Phi(3^6223,2)
94491 2*3^4217+1 2013 C 1992 Divides Phi(3^4217,2)
[/CODE]

I tried to find a precise description of the "divides phi" category, without success. The "Divides Phi" page [url=https://primes.utm.edu/top20/page.php?id=37]here[/url] features[quote] Definitions and Notes

Description to be added. Do you want to write it and supply the necessary references?[/quote]I note that the number k*(b^n) + 1 divides 2^(b^n) - 1, but divides the "primitive part" Phi((b^n)/m, 2) for a (very small) m. I also note that, with a composite b, m can be something other than a power of b.

As long as the divisor m is small enough (which it certainly is in the proffered examples), the fact that k*b^n + 1 divides Phi((b^n)/m,2) still proves that k*b^n + 1 is prime. So saying "it doesn't fit the category" is at best a minor quibble.

Perhaps some leeway could be included in the "Definitions and notes" part of the Divides Phi page, reflecting that the fact k*b^n + 1 "divides phi" also proves it prime.

@Batalov: Please tell me where to get DivPhi! I've been wanting to download it for over a month now.

What could it be?
/scratches head/

Remove me form your ignore list right now! I want to use that program.

[QUOTE=Batalov;510244]And wrong again.
You appear to look but not see. (Also explains your endless threads with miniature results.)

Look [B]carefully [/B]at these first two lines (posted before) --
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
46623 2*3^152529+1 72776 gb 2000 Divides Phi(3^152528,2)
88279 2*3^6225+1 2971 C 1992 Divides Phi(3^6223,2)
94491 2*3^4217+1 2013 C 1992 Divides Phi(3^4217,2)
[/CODE][/QUOTE]

2*3^152529+1 is 6*3^152528+1 (with k=6, b=3), 2*3^6225+1 is 18*3^6223+1 (with k=18, b=3), thus they also divide Phi(b^n,2).

The category is called "Divides Phi".
Not "Divides Phi(b^n,2)".
[QUOTE="https://primes.utm.edu/top20/page.php?id=37"]These forms are defined in this collection's home page. This page is about one of those forms. Comments and suggestions [U][COLOR=Blue]requested[/COLOR][/U]. <-- [COLOR=blue]so, follow that link. (Caldwell does not read this forum. No use writing a 'War and Peace' here)[/COLOR][/QUOTE]

It is an obvious extension (a superset) of the set of "[URL="https://primes.utm.edu/top20/page.php?id=8"]Divides Fermat Number[/URL]". Shares many of the same features in the structure of these rare factors.

This category also should have restrictions -- otherwise any prime "Divides Something".

[QUOTE=Stargate38;510344]Remove me form your ignore list right now! I want to use that program.[/QUOTE]
"...right now"!? Are you for real?
Isn't it self-explanatory using just this one post why you are on the ignore list?
And with posts like this you are not going to get off it, I can guarantee you that.

[QUOTE=Stargate38;510344]Remove me form your ignore list right now! I want to use that program.[/QUOTE]That is awfully demanding. You want something from someone that has chosen to ignore you. If you are on their ignore list, why do you think that they would see your post? You catch more flies with honey....
:tantrum:

Because I want to know where/how to download DivPhi. I've been waiting for weeks on end, with no download link or anything. Please give me a download link.

[QUOTE=Uncwilly;510367]That is awfully demanding. You want something from someone that has chosen to ignore you. If you are on their ignore list, why do you think that they would see your post? You catch more flies with honey....
:tantrum:[/QUOTE]I'm pretty much at sea when it comes to computer terminology, but when I saw the original reference to the program in this thread

[QUOTE=Batalov;506932]
...and having the DivPhi self-compiled binary.
[/QUOTE]
I did flag the modifier "self-compiled" as possibly important. Of course "binary" is important; I would hazard a guess that whether a precompiled binary actually [i]works[/i] would depend very much on the system you try to run it on.

OK, enough of me proclaiming my ignorance for now...

If he gave me the source code, I could compile it myself (using Windows Bash). I really want to try it out.

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.

I have identified two enormous new top entries for the "Divides Phi" category; they will probably appear in a few days. (they are [I]previously [/I]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 ( [SPOILER]b=3[/SPOILER] ), 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 * b[SUP]n[/SUP] +1 may divide some Phi( b[SUP]m[/SUP] , 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.

David Broadhurst wrote:
[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.[/QUOTE]
...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 [URL="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.189.311"]Iskra-Berrizbeitia test[/URL] 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.)

[QUOTE=Batalov;545880]
(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.)
[/QUOTE]

Check out [url]https://en.wikipedia.org/wiki/Euler%27s_criterion[/url], pretty old, but still good stuff.

I think I see.

Does it take care of Conjecture 2, as well?

[QUOTE=Batalov;545897]I think I see.

Does it take care of Conjecture 2, as well?[/QUOTE]

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).

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
[/CODE]

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

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)
[/CODE]

There is also [URL="https://oeis.org/A332763"]this[/URL] 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 [URL="https://primes.utm.edu/primes/page.php?id=18014"]here[/URL] found about two decades ago.

I can attach the sieve file associated for this sequence if anyone's interested in testing further.

[QUOTE=carpetpool;546827]There is also [URL="https://oeis.org/A332763"]this[/URL] 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 [URL="https://primes.utm.edu/primes/page.php?id=18014"]here[/URL] found about two decades ago.

I can attach the sieve file associated for this sequence if anyone's interested in testing further.[/QUOTE]

You can search 6*p^n+1 for all primes p, if p != 1 mod 7 and p != 34 mod 35, then there should be infinitely many primes of the form 6*p^n+1, but there is not always an easy prime, e.g. for p = 409, the first such prime is 6*409^369832+1, a 965900-digit prime!!

[QUOTE=sweety439;547072]You can search 6*p^n+1 for all primes p, if p != 1 mod 7 and p != 34 mod 35, then there should be infinitely many primes of the form 6*p^n+1, but there is not always an easy prime, e.g. for p = 409, the first such prime is 6*409^369832+1, a 965900-digit prime!![/QUOTE]

p = 1 mod 4 increases the odds of such a prime, as N = 6*p^n+1 is congruent 7 mod 8, but there is still 1/3 chance --- which at 965K digits, I'm not sure if anyone would be willing to test if N | Phi(p^k,2). If more primes were found, probably then it could be worth it. I was considering working on such a project if others were interested. AFAIK, Ryan is testing [URL="https://www.rieselprime.de/ziki/Williams_prime_PP_5"]6*5^n+1[/URL] and he's had quite extensive computation power lately so maybe he'll luck out soon...

6*13^n+1 is next on the list so, I might give that sequence a quick check...

A new interest for "Divides Phi"
 

3*2^n+1 divides Phi(3*2^(n-1),2) for n = 5, 6, 8, 12, and the cofactor of them are all primes ([URL="http://factordb.com/index.php?id=1100000000017315254"]this is the cofactor for n=12[/URL]), are there any other such n?

[QUOTE=sweety439;581698]... are there any other such n?[/QUOTE]
Is that a riddle? We give up. What is the answer? :rolleyes: