"Divides Phi" category - Page 4

Stargate38 · 2019-03-09, 22:47

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

VBCurtis · 2019-03-09, 23:34

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.

Batalov · 2020-05-18, 18:09

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 * bⁿ +1 may divide some Phi( b^m , 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.

Batalov · 2020-05-19, 20:34

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.

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

R. Gerbicz · 2020-05-19, 21:10

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.

Batalov · 2020-05-20, 00:05

I think I see.

Does it take care of Conjecture 2, as well?

R. Gerbicz · 2020-05-20, 08:57

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

sweety439 · 2020-05-30, 13:57

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

Code:

sweety439 · 2020-05-30, 13:58

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

sweety439 · 2020-05-30, 14:02

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)

carpetpool · 2020-05-30, 19:44

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.

2019-03-09, 22:47	#34
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 3·13·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

2020-05-30, 14:02	#43
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 5×7×83 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 144₁₆ 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
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

2019-03-09, 23:34	#35
VBCurtis "Curtis" Feb 2005 Riverside, CA 1001011111101₂ 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 2²·23·103 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 bⁿ +1 may divide some Phi( b^m , 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-20, 00:05	#39
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×23×103 Posts	I think I see. Does it take care of Conjecture 2, as well?

2020-05-30, 13:58	#42
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 5·7·83 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