mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Conjectured compositeness tests for N=k⋅2n±c by Predrag (https://www.mersenneforum.org/showthread.php?t=20467)

T.Rex 2015-09-04 21:23

Conjectured compositeness tests for N=k⋅2n±c by Predrag
 
Predrag (not sure he wants his name to appear since he published as "MathBot") has published [URL="http://math.stackexchange.com/questions/1394160/conjectured-compositeness-tests-for-n-k-cdot-2n-pm-c"]a question in StackExchange[/URL] about a set of 4 conjectures he has built dealing with: "Conjectured compositeness tests for N=k⋅2n±c".

What he proposes seems to me already VERY great, since the 4 conjectures cover ALL numbers [TEX]N=k2^n \pm c[/TEX], c odd for sure, with simple but powerful definitions using the LLT ([TEX]S_n \equiv S_{n-1}^2-2 ~ \pmod{N}[/TEX]) but also higher LLT functions (Chebichev) for the seed and for the last term of the sequence, after [TEX]n-1[/TEX] iterations.

However, I've shown that the 4 conjectures can be generalized into only ONE conjecture which handles all kinds of these numbers.
I've provided a PARI/gp for finding counter-examples.

For sure, it is ONLY a conjecture. But this conjecture looks really powerful. I'd like to know if someone is aware about such a general conjecture. I should know, but, after years without looking at such research papers, I do not remember. However, as said RDS, I'm not a PhD, so I'd like other people to have a look and add comments.

I've read other papers of Pedrag: he has played first with smaller examples. So, I think he then spent some time for grouping several examples into a greater conjecture. So:1) he made experiments, 2) he generalized his findings in something more general. Good work !

And, for sure, what I published recently was only children' game compared to Predrag's conjectures.

Here is the PARI/gp program I've written based on work of Predrag, with code for searching counter-examples:

[CODE]CEk2c(k,c,g)=
{
a=6;
if(c>0,s=1,s=-1;c=-c);
for(n=2*c+1,g,
N=k*2^n+s*c;
e=c%4;
if(e==1,e=1,e=-1);
d=((c-e)%8)/4;
B=((-1)^d)*s;
A=(c-B)/2;
s0=Mod(2*polchebyshev(k,1,a/2),N);
sn=Mod((-1)^d*2*polchebyshev(A,1,a/2),N);
my(s=s0);
for(i=1,n-1,s=Mod(s^2-2,N));
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),1000)))[/CODE]

This comes from : Let say: [TEX]N=k \cdot 2^n + s \cdot c[/TEX], with: [TEX]s = \pm 1[/TEX] and: [TEX]c = 4 \cdot d ~\pm 1 ~ \pmod 8[/TEX] with [TEX]d=0,1[/TEX]. Then last [TEX]S_i[/TEX] can be defined as only one expression for all 4 conjectures: [TEX]S_{n-1} = {(-1)}^d \cdot P_{(c - {(-1)^d \cdot s})/2} ~~~~ (6)[/TEX] . That's quite complicated, but that shows that the 4 conjectures come from a single property depending on [TEX]k[/TEX] and on the internal structure of [TEX]c[/TEX].


Here is the final conjecture I've built after grouping Predrag's 4 conjectures all together.
That does not make the task for proving it easier ! But that's so beautiful.
And, for sure, we have the usual question: is this only a PRP tool or a true primality test ?
Anyway, this conjecture shows how powerful are the ideas that Edouard Lucas discovered about 140 years ago. [TEX]P_2(x) = x^2-2[/TEX]

[TEX]\text{Let } ~N=k\cdot 2^n+ s \cdot c ~\text{ such that }~ n>2c , k>0 , c>0 ~\text{ and }~ s = \pm 1 ~\text{ and }~ c \equiv 4 \cdot d ~ \pm 1 ~ \pmod 8 ~\text{ and }~ d=0,1[/TEX]

[TEX]\text{Let }~ S_i=P_2(S_{i-1})~ \text{ with } ~ S_0=P_k(6) ~ \text{ , thus: }[/TEX]

[TEX]\text{If } ~ N ~\text{ is prime then }~ S_{n-1} \equiv {(-1)}^d \cdot P_{(c - {(-1)^d \cdot s})/2} ~~~~ (6) \pmod{N}[/TEX]

T.Rex 2015-09-04 21:33

Thanks to primus to have warned me about Predrag's publication in StackExchange. :smile:

Batalov 2015-09-04 22:09

You didn't even consider that they are one and the same?

science_man_88 2015-09-05 01:28

[QUOTE=T.Rex;409609][CODE]CEk2c(k,c,g)=
{
a=6;
if(c>0,s=1,s=-1;c=-c);
for(n=2*c+1,g,
N=k*2^n+s*c;
e=c%4;
if(e==1,e=1,e=-1);
d=((c-e)%8)/4;
B=((-1)^d)*s;
A=(c-B)/2;
s0=Mod(2*polchebyshev(k,1,a/2),N);
sn=Mod((-1)^d*2*polchebyshev(A,1,a/2),N);
my(s=s0);
for(i=1,n-1,s=Mod(s^2-2,N));
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),1000)))[/CODE][/QUOTE]

thinking about what might speed this up I found ( I'll see which one is faster and none of this uses modern PARI/gp to my knowledge if I realized which one's I could put in parallel I might be able to see if I can speed it up more.

[CODE]CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d)
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
forstep(i=n,2,-1,s=sqr(s)-2);
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,1000)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),1000)))[/CODE]

T.Rex 2015-09-05 10:26

[QUOTE=Batalov;409612]You didn't even consider that they are one and the same?[/QUOTE]
Ha ha ha ! No ! ;) I should have considered... but too busy with other stuff.

T.Rex 2015-09-05 10:30

[QUOTE=science_man_88;409618]thinking about what might speed this up I found ( I'll see which one is faster and none of this uses modern PARI/gp to my knowledge if I realized which one's I could put in parallel I might be able to see if I can speed it up more.
[CODE]CEk2c(k,c,g)={ ... forstep(i=n,2,-1,s=sqr(s)-2); ... ) }
[/CODE][/QUOTE]
I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.

axn 2015-09-05 12:23

[QUOTE=T.Rex;409642]I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.[/QUOTE]

The s variable is a Mod() object. All operations with it will automatically work modulo N.

science_man_88 2015-09-05 13:40

[QUOTE=T.Rex;409642]I do not think that this will speed up the computation, since PARI goes in Stack overflow quickly. Modulo helps to keep s small.[/QUOTE]

you can change how much it has I can set allocatemem to 1000000000 on my machine that allocates over 950 MB

R.D. Silverman 2015-09-05 13:41

[QUOTE=Batalov;409612]You didn't even consider that they are one and the same?[/QUOTE]

Note also that numbers of the form k*2^n +/- c is the ENTIRE SET OF ODD INTEGERS!!!!!


Numbers of the form x^n +/-1 are special. (cyclotomy!!!!)

Why on Earth people think k* 2^n + c is special is beyond me.

science_man_88 2015-09-05 14:45

[QUOTE=R.D. Silverman;409659]Why on Earth people think k* 2^n + c is special is beyond me.[/QUOTE]

maybe because they care for other potential groupings around a number like sexy primes or cousin primes ?

Batalov 2015-09-05 15:09

[QUOTE=T.Rex;409641]Ha ha ha ! No ! ;) I should have considered... but too busy with other stuff.[/QUOTE]
Now, he has succeeded to use you as a sock puppet.
Think about it. If he wanted to post it himself, under three different names (and on ten other boards, just like inimitable Don Blazys), he would have! And he had already done that.
Now he used you to post this tripe once again.

Don't you feel used?

T.Rex 2015-09-05 19:41

[QUOTE=axn;409647]The s variable is a Mod() object. All operations with it will automatically work modulo N.[/QUOTE]
I should read again the documentation of PARI/gp... ;) However, I'm now involved with porting Ruby and Python3, and then Go, on AIX, so I'm fed up reading language documentation. So, I know very basic things about PARI/gp. Some time, when I have time, I'll read more ! ;) Anyway, thanks to help me understand. For now, I do not care about performance of PARI/gp programs.

paulunderwood 2015-09-05 21:58

Is there any need to run verification now "mathlove" has [URL="http://math.stackexchange.com/questions/1394160/conjectured-compositeness-tests-for-n-k-cdot-2n-pm-c"]proved this composite test[/URL]? :smile:

Does it produce fewer pseudoprimes than base-a Fermat PRP tests? :unsure:

T.Rex 2015-09-06 18:59

About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n-1 .
Finding s(n-1)==sn only after n-1 iterations and not before is important I think.
I think that it is important to add a check s!=sn after the computation of s from i=1,n-2 .

science_man_88 2015-09-06 19:32

[QUOTE=T.Rex;409742]About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n-1 .
Finding s(n-1)==sn only after n-1 iterations and not before is important I think.
I think that it is important to add a check s!=sn after the computation of s from i=1,n-2 .[/QUOTE]

if it loops multiple times it should in theory loop at multiples of a divisor of n-2 if it's going to have the final result match, but of course that would mean n = all multiples of that divisor +2, should give prime N.

T.Rex 2015-09-07 17:32

[QUOTE=paulunderwood;409706]Does it produce fewer pseudoprimes than base-a Fermat PRP tests? :unsure:[/QUOTE]
If we use the test as-is: ( if(s==sn && ! isprime(N) ), it produces pseudoprimes, like: 1*2^3+1 or 98*2^79+17 .

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : produces 34 pseudoprimes.

But, if we check that no S(i) is equal to S(sn-1) with i=1...n-2 , there are less.

... z=0; forstep(i=n,3,-1, s=sqr(s)-2; if(s==sn, z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn && ! isprime(N), print("k: ",k," c: ",c," n: ",n)))

? for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13.
k: 1 c: 1 n: 3
k: 15 c: 1 n: 3
k: 33 c: 25 n: 79
k: 35 c: 17 n: 83
k: 37 c: 17 n: 92
k: 45 c: 1 n: 3
k: 49 c: 17 n: 80
k: 66 c: 25 n: 78
k: 70 c: 17 n: 82
k: 74 c: 17 n: 91
k: 95 c: 17 n: 77
k: 97 c: 17 n: 48
k: 98 c: 17 n: 79

With c=1, 17, or 25 only, within the limits used for k, c and n.
However, there are others, like: 16*2^121+33 .

Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .

For c<0, it seems to appear only with: c= 5, 29 , like: 8*2^158-29 or 11*2^232-5 .

T.Rex 2015-09-07 18:42

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13 pseudoprimes out of 5588 numbers verifying the test; including 5575 primes: 0.23% of pseudoprimes. Out of a total of 125,000 numbers N tested.

For c<0, there are 1.22% of pseudoprimes (72 out of 5866 numbers verifying the test, including 5794 primes). Out of a total of 125,000 numbers N tested.

T.Rex 2015-09-07 21:53

[QUOTE=T.Rex;409802]
Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .
[/QUOTE]
There are also pseudo primes for c=89, but not with 81, 87, 105, with the following bounds:
for(k=1,300,CEk2c(k,89,300)) :
133*2^262+89
221*2^291+89
266*2^261+89

Batalov 2015-09-07 23:26

A few trivial things about Chebyshev polynomials replace all that "mathlove" wrote in pages of scribbles in a simple way.
One has to admire how he [STRIKE]repeated[/STRIKE] copy-pasted pages of similar arguments in each of the primus' questions (of which there are scores and the all look the same, only maybe with different values of c, or base). Do these guys ever get tired of typing?! I think not. Everyone gets their kicks of it. mathlove gets a load of stackexchange's "credits" (like PrimeGrid's, but slightly more useful perhaps) for answering the same question 20 times. Hats off to his/her stamina.

[U]Ponder these:[/U]
1. [URL]https://en.wikipedia.org/wiki/Lissajous_curve[/URL] : [TEX]x=A\sin(at+\delta),\quad y=B\sin(bt)[/TEX]
2. Lissajous figures where a=1, b=N (with N a natural number) and [TEX]\delta=\frac{N-1}{N}\frac{\pi}{2}\[/TEX] are Chebyshev polynomials
3. Chebyshev polynomial [TEX]T_n(cos \theta) = cos(n \theta)[/TEX] (one of the definitions)
4. Using renormalized [TEX]C_n(v) = 2 T_n(v/2), \ C_{km}(x) = C_k(C_m(x))[/TEX]; in particular [TEX]C_{k b^n}(x) = C_b(C_b(C_b(...C_b(C_k(x))...)))[/TEX] {n times}.

So, the whole iterated calculation is a calculation of T_{k*2^n}(a) and comparing it to T_c(a) with some a value like [TEX]a = cos \delta[/TEX] . Because of periodicity of cos, the result is obvious. In a way, this is a "Fermat" test z^N = z ("mod" N) in complex plane and with irrational complex [TEX]z = e^{i \theta}[/TEX] with imaginary half of calculations swept under the carpet, projected on real axis only. (A Frobenius PRP test?)

primus has been boring people with these trivialities for years now. Search this forum. And always it was [B]"A new conjectured primality test bla-bla-bla" :toot:[/B].
Only in 2015, he finally settled down for them as PRP tests, which they are; but as such, they are :censored: trivial!

All you need to realize is the property 4, which makes the purpose of iterations painfully obvious: you are calculating the [TEX]C_{N-c}(a)[/TEX], because N-c = k*b^n, then compare that the[TEX] cos(N {{N-c} \over N} {\pi \over 2}) = cos(N {-c \over N} {\pi \over 2})[/TEX]. Of course it is!

T.Rex 2015-09-08 20:17

[QUOTE=Batalov;409832]A few trivial things about... .... [B]"A new conjectured primality test bla-bla-bla" :toot:[/B].
O.... they are :censored: trivial!
.... Of course it is![/QUOTE]:surrender
Hummm Sometimes, I'm saying myself that I should go back to photography and forget Maths, where I was not so good even before I forgot so many things !
:surrender
Anyway, thanks for the explanations !

So, you transformed something mysterious into something nearly obvious... I'm sad ! But that's the (Math) rule/law.

Anyway, what is surprising me is that, with some modification of his algorithm, I no more can find pseudoprimes (which does NOT mean that there are no more, for sure).

In a previous post, I said that, with c>0, pseudoprimes [B]seem [/B]to be only N=k*2^n+c where c = 1 mod 8.
If you eliminate Ns such that S(i)==S(n-1) with i<n-1, and then if you eliminate Ns such that N= 0 mod(2*c-1) , I [I]no more[/I] find pseudoprimes. Last check means that remaining numbers Ns only have 2*c-1 as simple factor. The examples I have factored do confirm: they have a unic small factor (never prime) and a very big prime factor.

Examples (where N passes the test before my last filter and are pseudoprimes):
N=171*2^379+145 = 0 mod 17^2 , and 17^2=2*145-1 .
factor(171*2^379+145) : 17^2 * 728562182048384077130159586626790436923511614970760313605012778127813410783523249843408253631630684967337087623537

N=307*2^319+105 = 0 mod 11*19 and 11*19 = 2*105-1
factor(307*2^319+105) : 11*19 * 1568775167530429175347539865536010763595766240104048804721870271773735540226451313055142011218969

N=471*2^393+73 = 0 mod 5*29 and 5*29 = 2*73-1
factor(471*2^393+73): 5*29 * 65530155850158078972410448815378156940155788169319195826683219662211477907862726436991538868262118459391723814610133049

N=17*2^399+137 = 0 mod 3*7*13 and 3*7*13 = 2*137-1
factor(17*2^399+137): 3*7*13 * 80399721478896421289653161033060809274001828714463003146742141137712471747777106792498115395169126619799183010140489721

The same for a dozen of other similar pseudoprimes.

In short, the 2 filters I have added seem to remove all pseudoprimes (which are of a special form and could be used for finding other big primes).

That may hide something obvious, for sure. But, the algorithm below [I]no more[/I] finds PRPs/pseudoprimes (or I haven't tested with large-enough numbers, for sure. Or my code is wrong.).
[B]Would you mind explaining why it seems to work ?[/B]

[CODE]CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d);
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
z=0;
forstep(i=n,3,-1,s=sqr(s)-2;if(s==sn,z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn, y=Mod(N,2*c-1);if(!isprime(N)&&y!=0, print(k,"*2^",n,"+",c)))
);
}

for(k=1,100,for(c=0,100,CEk2c(k,2*c+1,200)))
for(k=1,100,for(c=101,200,CEk2c(2*k+1,2*c+1,800)))
[/CODE]

Batalov 2015-09-08 21:08

[QUOTE=T.Rex;409920]...If you eliminate Ns such that <<...>>, and then if you eliminate Ns such that <<...>>, I [I]no more[/I] find pseudoprimes. [/QUOTE]
If you eliminate more and more, finally you simply get yourself in an illusory environment when you can no longer find counterexamples, -- and so what? It simply means that no one is willing to find them, but they are still there, only larger.

Compare it with [URL="http://www.mersenneforum.org/showthread.php?t=19599"]the way this thread went[/URL],
and on to [url]http://www.mersenneforum.org/showthread.php?p=380943#post380943[/url]

This is long ago and well described by A.A. Milne as the character of Tigger.
Tigger first claims: 'Tiggers eat evertyhing'.
After being presented with honey, he "improves" his theory to 'Tiggers eat evertyhing except honey'.
After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'.
Can you blame anyone for not taking him all too seriously after that?

T.Rex 2015-09-09 13:23

[QUOTE=Batalov;409925]If you eliminate more and more, finally you simply get yourself in an illusory environment when you can no longer find counterexamples, -- and so what? It simply means that no one is willing to find them, but they are still there, only larger.
....
After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'.
Can you blame anyone for not taking him all too seriously after that?[/QUOTE]
Hummmmm I understand your point.
However, don't you think that there are other ways for finding new stuff than using pure Math proof ? Is there a place for experimenting ? Years ago, before computers were there, many mathematicians used pen, paper, and figures, for exploring something that looked weird for them at first, before they search for a math proof. Now, we have computers. Remember S. Ramanujan: he never used more than a slate since he was unable to pay for note-books and paper at first and because he had a wrong idea about what "good" maths are: find a property and PROVE it ; however his findings were remarkable and mathematicians are still studying his findings. However, there was only 1 Srinivasa...

Now, back to what I did:
- primus published 4 conjectures about a property of primes
- I generalized the conjectures into one
- someone proved the conjecture and, as you explained, it was not so difficult to prove and it is simply another way to present something already known
- however, what about pseudoprimes ?
- I found a limited number of pseudoprimes
- I used the idea: not only S(n-1) must have a special value Sn, but S(i) must not be equal to S(n) when i<n-1, because some Sn values are a dead-end, like 2 : 2^2-2=2 , and because we must not enter a cycle with length smaller than n-1, with the idea that a minimum of n-1 different steps are required for showing a prime, as for Mersenne/Fermat LLT. The other idea is that, for very simple numbers like Mersenne and Fermat, so close to 2^n, about n iterations of X^2-2 mod N is enough, though for numbers moving away from pure 2^n more steps should be required, which are the P_k and P(c) functions that add more steps before and after the (s^2-2 mod N) part. The idea is that there must be a minimum of steps to run in order to have something that can be a prime test. A number N being a prime creates a symmetric structure ; running a minimum number of steps in the structure of a number is required in order to discover if the symmetry is broken due to a factor of N. What is magic with LLT for Mersenne/Fermat is this: you run n-1 steps in the digraph, from a starting point to a ending point, and bingo! it is a prime. This should work, under more complex conditions, for other numbers, where starting and ending points are more difficult to define since they depend on other characteristics of the number than the power of n : k and c in addition, like primus did.
- then, I found that ALL the remaining pseudoprimes I can find (c>0) share the same characteristics: c= 1 mod 8 , and N=0 mod (2*c-1) .
- and then I shown that ALL these remaining pseudoprimes look strange: only 1 small factor (2c-1) and a big prime. They do NOT look like random factors as expected for random exceptions in the theory. They share a property, probably showing something deep and interesting to look at.
- and, at the end, filtering this unique class of pseudoprimes, I cannot find more pseudoprimes (up to the limits of my computer).

For sure, that does NOT provides a proof.
That is only showing "strange" properties that seem to exist with very big numbers and with a very big number of numbers tried.
And, as you say, after honey and acorns, there could be ants and mushrooms. Or not.

I remember an example from a book of JP Delahaye, where 2 sequences A(n) and B(n) generate coprime numbers ... up to n being very very big where an exception occured.

But, in our case, we are using methods that are well known and have already provided good results, like LLT for Mersenne numbers and LLT for Fermat numbers, which are true prime tests.
So, we have the expectation to find something that works, under strict conditions.

So, I have only used 2 filters.

Remind also that, for c<0, I found that all pseudoprimes I've found have the same structure.

For sure, there could be another kind of pseudoprimes with much higher values for: k, n, or c . And, in that case, the conjecture will be the Tiger you are talking about.

T.Rex 2015-09-09 20:41

Here is a modified code that shows the pseudoprimes such that N=0 mod(2*c-1) :
[CODE]
CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d);
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
z=0;
forstep(i=n,3,-1,s=sqr(s)-2;if(s==sn,z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn,
y=Mod(N,2*c-1);
if(!isprime(N),
print1(k,"*2^",n,"+",c," : ");
if(y==0,
Nf=factor(N/(2*c-1)); print(Nf),
print("New kind of pseudoprime !")
)
)
)
);
}[/CODE]

And here is the result, showing that these pseudoprimes are of a special kind since they all are: N=(2*c-1)*P where P is prime.

[CODE]for(k=0,200,for(c=0,100,CEk2c(2*k+1,2*c+1,200)))

1*2^3+1 : Mat([3, 2])
15*2^3+1 : Mat([11, 2])
27*2^158+25 : Mat([201329307183338667303568828996630824136276421737, 1])
33*2^79+25 : Mat([407087265788599620054121, 1])
35*2^83+17 : Mat([10257552408851399058113009, 1])
37*2^92+17 : Mat([5551973509522311535911223793, 1])
41*2^141+17 : Mat([3463373307347558896980925943858268264186353, 1])
45*2^3+1 : Mat([19, 2])
49*2^80+17 : Mat([1795071671548994835169777, 1])
67*2^144+41 : Mat([18446295411130268524480162027993089146922073, 1])
91*2^166+17 : Mat([257932895024702381685401832295140372923519731220977, 1])
91*2^196+17 : Mat([276953337173424460368027557581526130358940288701201037902321, 1])
95*2^77+17 : Mat([435030124482537013625329, 1])
95*2^197+17 : Mat([578254220471985137032145449895494118331853350035474694521329, 1])
97*2^48+17 : Mat([827365840634353, 1])
131*2^69+17 : Mat([2343295489605770920433, 1])
153*2^150+73 : Mat([1505992392993185253806329333281191419769380921, 1])
163*2^38+17 : Mat([1357730267633, 1])
169*2^42+17 : Mat([22523329102321, 1])
169*2^142+17 : Mat([28551711655694509931208609000587674958414321, 1])
171*2^147+25 : Mat([622600396563059029747364542795570582452677737, 1])
173*2^121+17 : Mat([13936754137623663394688401298696946161, 1])
191*2^151+41 : Mat([6730970600168847834126731362095149902447027289, 1])
197*2^169+17 : Mat([4467057610537702786112014150518035469532605454991857, 1])
215*2^35+17 : Mat([223858901489, 1])
229*2^38+17 : Mat([1907486081521, 1])
229*2^108+17 : Mat([2251962084478173346464931173089777, 1])
229*2^188+17 : Mat([2722455108718844497951507155141203805468635221178530120177, 1])
231*2^3+1 : Mat([43, 2])
235*2^62+17 : Mat([32840794373649580529, 1])
235*2^182+17 : Mat([43652903285270773541116551682463352503079235601593516529, 1])
295*2^78+17 : Mat([2701766036259966716199409, 1])
295*2^198+17 : Mat([3591263053457591903673324373035173998060983963378211260711409, 1])
299*2^163+17 : Mat([105936724742288478192218609692646938879302746751473, 1])
305*2^41+17 : Mat([20324305846769, 1])
305*2^101+17 : Mat([23432329276946058633726938038769, 1])
329*2^179+17 : Mat([7639258074922385369695396544431086688038866230278865393, 1])
335*2^121+41 : Mat([10994848854023378207969762103553467481, 1])
355*2^36+17 : Mat([739254977009, 1])
361*2^68+17 : Mat([3228739205143829398001, 1])
363*2^113+25 : Mat([76930765699924180781900823163546729, 1])
365*2^153+17 : Mat([126289795839436450081521061539167448431443034609, 1])
367*2^132+17 : Mat([60549638138174262347179869540586149626353, 1])
391*2^137+33 : Mat([1048027809209792505810152144784316027504609, 1])
395*2^89+17 : Mat([7408883568450381948259910129, 1])
401*2^179+89 : Mat([1735962462958252633338127564653316335116142338970690601, 1])[/CODE]

But there are exceptions... [B][COLOR="Red"]ants and mush-rooms.[/COLOR][/B]..

[CODE]for(k=201,400,for(c=0,100,CEk2c(2*k+1,2*c+1,200)))
413*2^35+17 : Mat([430017331697, 1])
413*2^155+17 : Mat([571591075963695932971706284007409930982859981297, 1])
419*2^117+41 : Mat([859485386163394677078233268915840089, 1])
427*2^48+17 : Mat([3642115607740913, 1])
435*2^3+1 : Mat([59, 2])
437*2^81+17 : Mat([32018217161914724202824177, 1])
437*2^111+17 : Mat([34379298896662419297997377210139121, 1])
437*2^131+17 : Mat([36049307719866692977816897805498838401521, 1])
453*2^169+25 : Mat([6917853954203679576254894803283343233610578985462889, 1])
463*2^54+17 : Mat([252747469996671473, 1])
487*2^120+33 : Mat([9958985137650062001602369820869658593, 1])
489*2^104+25 : Mat([202410169309911568108371548548201, 1])
511*2^40+17 : Mat([17025770963441, 1])
511*2^130+17 : Mat([21076883575345400585428415078501037097457, 1])
511*2^180+17 : Mat([23730461254014218382458040329509333116035627013206688241, 1])
537*2^103+25 : Mat([111139326093479051200608917761129, 1])
545*2^35+17 : Mat([567456285169, 1])
545*2^65+17 : Mat([609301546677073068529, 1])
545*2^185+17 : Mat([809900673718215202720290065257617944312448796693394604529, 1])
553*2^144+41 : Mat([152250766602314007373694471663883258182804569, 1])
559*2^38+17 : Mat([4656265150961, 1])
559*2^68+17 : Mat([4999626636219946353137, 1])
559*2^98+17 : Mat([5368308223693789662398917362161, 1])
[B]561*2^3+1 : Mat([67, 2])[/B]
565*2^72+17 : Mat([80852638267313622598129, 1])
569*2^51+17 : Mat([38826487696572913, 1])
577*2^80+17 : Mat([21137884785383061630468593, 1])
593*2^125+41 : Mat([311400375901414365484230157726911341657, 1])
611*2^185+17 : Mat([907980388333632089655224274995237732064048100513145143793, 1])
619*2^36+17 : Mat([1289010790897, 1])
619*2^46+17 : Mat([1319947049878001, 1])
619*2^66+17 : Mat([1384064797772874236401, 1])
619*2^76+17 : Mat([1417282352919423218074097, 1])
623*2^127+17 : Mat([3212059311996131253601248188333205996017, 1])
625*2^38+17 : Mat([5206020964849, 1])
635*2^41+17 : Mat([42314538402289, 1])
635*2^81+17 : Mat([46525326997290274299298289, 1])
635*2^111+17 : Mat([49956189472266902183588866197799409, 1])
635*2^99+41 : Mat([4968877352746454752780287255641, 1])
663*2^88+25 : Mat([4187521663501056746214894697, 1])
673*2^196+41 : Mat([834467055390663931666466426038273481093705721308502760924249, 1])
677*2^115+17 : Mat([852166054115897770791550549062304241, 1])
683*2^114+33 : Mat([218236231038725370479158707252758497, 1])
685*2^56+17 : Mat([1495740967150928369, 1])
[B][COLOR="Red"]699*2^8+3 : pseudoprime ![/COLOR][/B]
709*2^150+17 : Mat([30664200428137138050615901586051274293799010801, 1])
709*2^180+17 : Mat([32925434499209551532608122492411188217748061746308301297, 1])
717*2^90+25 : Mat([18114347105461584838830042217, 1])
727*2^124+17 : Mat([468532728696064891927790415914574791153, 1])
[B]741*2^3+1 : [7, 2; 11, 2][/B]
755*2^37+17 : Mat([3144436662769, 1])
755*2^167+17 : Mat([4279985400959347212581942491930351243016646089490929, 1])
761*2^183+41 : Mat([115183121639401621847970576559149164319393626862392222809, 1])
775*2^110+17 : Mat([30485076252761298576599504963224049, 1])
[B]783*2^3+1 : [5, 1; 7, 1; 179, 1][/B]
787*2^150+41 : Mat([13867209063698647239418161209342625584360760409, 1])
801*2^162+25 : Mat([95564311143024754080094004163734097856685874850921, 1])
[/CODE]

LaurV 2015-09-10 06:25

[QUOTE=Batalov;409925]Tigger first claims: 'Tiggers eat evertyhing'.
[/QUOTE]
Disclaimer: The similarity with the avatar is coincidental... :razz:

T.Rex 2015-09-11 19:13

[QUOTE=LaurV;410013]Disclaimer: The similarity with the avatar is coincidental... :razz:[/QUOTE]
I'm Hobbes ! A real Tiger !! Be afraid ! And read again all Watterson's books in order to remember how dangerous I can be !!

;)

primus 2015-09-16 17:49

[url]http://math.stackexchange.com/q/1426586[/url]

Batalov 2015-09-16 18:22

Proving these endless copy-pasted conjectures in one direction (i.e. is this a PRP test? -- the 'if' conjectures) is an exercise in copy-pasting the same solution over and over again. This direction is obvious. Maybe [I]mathlove[/I] likes calligraphy, or copy-pasting, or the "bounty points" that it brings ("This question has an open bounty worth +50 reputation from MathBot ending in 3 days.").

The 'iff' conjectures are almost obviously false - and in many previous cases [B]already proven false[/B] by a counterexample. Obviously it is a moot point to ask if you ever get tired of copy-pasting. Bots don't get tired.

T.Rex 2015-10-16 19:02

I still think that an algorithm that produces only 3 kinds of numbers:
1) primes
2) composite numbers like the ones here below (only 1 small divisor equal to 2b-1)
3) cases in bold (like 561*2^3+1) which are all of the form: 3*k*2^3+1.
deserves some study.

About the number a+b=699*2^8+3 which is said "Pseudoprime", we have: 3|a and 3|b , so that's stupid. a and b must be coprimes.

[CODE]
for(k=500,600,for(c=1,100,CEk2c(2*k+1,2*c+1,200)))
1015*2^36+17 : Mat([2113644511729, 1])
1015*2^194+57 : Mat([225531265890884282311268186355956864153766045172778585153609, 1])
1055*2^99+17 : Mat([20263202776375485129985180025329, 1])
1073*2^135+17 : Mat([1416234587951193100785264305548750704067057, 1])
1077*2^83+25 : Mat([212573568608156019780988009, 1])
1085*2^57+17 : Mat([4738332698857685489, 1])
1085*2^167+17 : Mat([6150707496742902947882659077807193508176239744500209, 1])
1109*2^169+41 : Mat([10245090391229448446659233055493422578083898090890329, 1])
1151*2^37+17 : Mat([4793704104433, 1])
1159*2^52+17 : Mat([158171877821891057, 1])
1159*2^82+17 : Mat([169835760597982450119328241, 1])
1163*2^151+17 : Mat([100599337370729172222471914089076535976553595377, 1])
1167*2^196+25 : Mat([2391960073533471494333507349186398924927820017531274539281513, 1])
1175*2^135+41 : Mat([631832938085298085245574579725159740777561, 1])
1189*2^124+17 : Mat([766279799751886047458243197417371976177, 1])
...
1203*2^53+25 : Mat([221135932723539049, 1])
1205*2^137+41 : Mat([2591859371549903634794612318532144638764121, 1])
1209*2^100+25 : Mat([31277338279100598906316615822441, 1])
...
? for(k=1000,1100,for(c=1,200,CEk2c(2*k+1,2*c+1,400)))
2001*2^59+25 : Mat([23540774803247967337, 1])
2005*2^46+17 : Mat([4275434305339889, 1])
2005*2^66+17 : Mat([4483117802156078907889, 1])
2011*2^78+17 : Mat([18417801691250145987379697, 1])
2015*2^83+17 : Mat([590541945823873402917077489, 1])
2035*2^110+41 : Mat([32612111441723377234751728487539801, 1])
2039*2^185+89 : Mat([564928073731172408080030660042391941315002769741444490281, 1])
2047*2^324+33 : Mat([1076274575392025338747719244930233397807196592557309100327777026759897545519500604528493142636103649, 1])
2047*2^348+33 : Mat([18056891026660293785643655279551430645425263587797967154964785977788581259050493854305107608524720309143521, 1])
2047*2^360+33 : Mat([73961025645200563345996412025042659923661879655620473466735763365022028837070822827233720764517254386251859937, 1])
2047*2^390+41 : Mat([63728123799719110279533981301723636510813413362285644902155185460536092812843290960248891278024234916923391601902658649, 1])
2047*2^312+137 : Mat([62562463692337782432786879471856015032505382286859950493383616231857883737880196970824796702713, 1])
2075*2^357+41 : Mat([7520410276629172759059679380151040635500835322507351437835846861002058220853105741029591700074683732702569561, 1])
2081*2^169+41 : Mat([19224556450990515976102672667702265450849947634934873, 1])
2081*2^385+41 : Mat([2024582096165355833105004504898737292058541664736755420148157989487292518678659142774150322874457023420212169082184793, 1])
2111*2^149+17 : Mat([45650301201549716801727904265270973225817850353, 1])
2111*2^269+17 : Mat([60679658373113666973114702966744324276783274698731453145161221545910673326056391153, 1])
2113*2^54+17 : Mat([1153467395470770673, 1])
2125*2^248+41 : Mat([11866232138758531793744615313631452748273472097535021150841404611150434051161, 1])
2127*2^92+25 : Mat([214946813351837048547790793833, 1])
2131*2^88+41 : Mat([8142130320114646190771709017, 1])
2135*2^97+41 : Mat([4176595727603811376844847752281, 1])
2147*2^333+17 : Mat([1138430862087060994334002977362795896100182974091570206304516240475677354977226692645062494804484014577, 1])
2149*2^112+17 : Mat([338128665120949835567031412469514737, 1])
2149*2^132+17 : Mat([354553603157865094779535530361633884324337, 1])
2149*2^292+57 : Mat([151327098767381450476731532922834405008974197247929238198875339659242443763530509595828297, 1])
2161*2^50+17 : Mat([73729384808694257, 1])
2161*2^170+17 : Mat([98003162399715489551147843444360148727512288205455857, 1])
2161*2^85+33 : Mat([1286148281199859025988945889, 1])
2161*2^253+33 : Mat([481205201618923650596801728084181863213300840120094728633207382771346679138273, 1])
2171*2^262+105 : Mat([76979024148275892138433717421278146740501171049678289616738729915767855907613721, 1])
2177*2^89+17 : Mat([40833264629155649370536264177, 1])
2177*2^117+57 : Mat([3201028038521860459415473418396360777, 1])
2177*2^191+65 : Mat([52966087123786062104149277419856937162228014738752725327809, 1])
2195*2^35+17 : Mat([2285443203569, 1])
2201*2^274+105 : Mat([319663145319140975261194352341399903821765658848217635038519670591756005662130973721, 1])
[/CODE]


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

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