mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2014-08-15, 05:33   #1
primus
 
Jul 2014
Montenegro

2·13 Posts
Default Disproven Primality Test for Specific Class of kb^n-1

Definition : \text{Let} P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right) , \text{where} m \text{and} x \text{are nonnegative integers .}

Conjecture : \text{Let} N=k\cdot b^n-1 \text{such that} n>2 ,  k \text{is odd positive number ,} 3 \not\mid k , b \text{is even positive number ,} 3 \not\mid b ,  k<b^n .

\text{Let} S_i=P_b(S_{i-1}) \text{with} S_0=P_{bk/2}(P_{b/2}(4)) , \text{thus}

N \text{is prime iff} S_{n-2} \equiv 0 \pmod{N}

Maxima implementation of the test

Maxima code to test this conjecture :

Code:
/* input numbers b,k,
b must be an even positive number not divisible by 3 , 
k must be an odd positive number not divisible by 3 , k<b^n */

k:5;b:10;
for n from 3 thru 300 do
(s:2*chebyshev_t(b*k/2,chebyshev_t(b/2,2)),N:k*b^n-1,
for i from 1 thru n-2 do (s:mod(2*chebyshev_t(b,s/2),N)),
(if((s=0) and not(primep(N))) then print(n)))$
primus is offline   Reply With Quote
Old 2014-08-15, 12:40   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by primus View Post
Definition : \text{Let} P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right) , \text{where} m \text{and} x \text{are nonnegative integers .}

Conjecture : \text{Let} N=k\cdot b^n-1 \text{such that} n>2 ,  k \text{is odd positive number ,} 3 \not\mid k , b \text{is even positive number ,} 3 \not\mid b ,  k<b^n .

\text{Let} S_i=P_b(S_{i-1}) \text{with} S_0=P_{bk/2}(P_{b/2}(4)) , \text{thus}

N \text{is prime iff} S_{n-2} \equiv 0 \pmod{N}

Maxima implementation of the test

Maxima code to test this conjecture :

Code:
/* input numbers b,k,
b must be an even positive number not divisible by 3 , 
k must be an odd positive number not divisible by 3 , k<b^n */

k:5;b:10;
for n from 3 thru 300 do
(s:2*chebyshev_t(b*k/2,chebyshev_t(b/2,2)),N:k*b^n-1,
for i from 1 thru n-2 do (s:mod(2*chebyshev_t(b,s/2),N)),
(if((s=0) and not(primep(N))) then print(n)))$
One question why use 4 for the general form but 3 for your b=6 form ? Also I don't see why this generalization couldn't be put in the other thread.
science_man_88 is offline   Reply With Quote
Old 2014-08-15, 13:27   #3
primus
 
Jul 2014
Montenegro

110102 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
One question why use 4 for the general form but 3 for your b=6 form ? Also I don't see why this generalization couldn't be put in the other thread.
I started a new thread because this conjecture uses 4 for starting value , not 3 , as you noticed , and that's why it couldn't be named as generalization of the conjecture for k\cdot 6^n-1 . This is rather some sort of generalization of the Riesel primality test .
primus is offline   Reply With Quote
Old 2014-08-16, 02:52   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32×1,069 Posts
Default

4103*10^7-1 is a counterexample. 41029999999 = 47743 · 859393.
Passes the test.

Ergo, your test is a PRP test. \qed
Batalov is offline   Reply With Quote
Old 2014-08-16, 02:58   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101100101012 Posts
Default

68761*50^3-1 is another counterexample.
Batalov is offline   Reply With Quote
Old 2014-08-16, 05:35   #6
primus
 
Jul 2014
Montenegro

2610 Posts
Default

Quote:
Originally Posted by Batalov View Post
4103*10^7-1 is a counterexample. 41029999999 = 47743 · 859393.
Passes the test.

Ergo, your test is a PRP test. \qed
Can you find counterexample for 5\not\mid b ?
primus is offline   Reply With Quote
Old 2014-08-16, 06:02   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by primus View Post
Can you find counterexample for 5\not\mid b ?
As with all mathematical results, reviews stop when the first error
is found.

It is *your* job to perform a thorough review of your work before
publishing it (presenting it here is a form of publishing). It is NOT the
job of referees to find errors.

Find your own counterexamples before asking others to do it for you.

Responsibility for correctness of a result lies with the author, not
the referees.
R.D. Silverman is offline   Reply With Quote
Old 2014-08-20, 17:43   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

259516 Posts
Default

Quote:
Originally Posted by primus View Post
Can you find counterexample for 5\not\mid b ?
[sarcasm]
Why? All you need to do is add a condition n>7 and your test will be all good and shining again.
[/sarcasm]

Frankly, though, no one will take either of these tightened conditions (either 5 \not\mid b or n>7) seriously without an explanation why they are relevant.

You are just fishing. As though if counterexamples didn't exist this conjecture would have been not wrong.

For a simple, down-to-earth example how a very specific test becomes a proven prime test, read e.g. Berrizbeitia, Iskra, Math. Comp. 79 (2010), 1779-1791.

Or read about Konyagin-Pomerance test (e.g. in PN-ACP, 2006) -- why is this a valid test? Because all proper divisors > 1 are proven to be non-existent if the test passes.
Batalov is offline   Reply With Quote
Old 2014-08-21, 15:16   #9
primus
 
Jul 2014
Montenegro

110102 Posts
Default

Thanks for help and references !

Last fiddled with by primus on 2014-08-21 at 15:36
primus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1 primus Miscellaneous Math 14 2015-07-04 15:42
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers primus Miscellaneous Math 1 2015-03-25 22:18
Conjectured Primality Test for Specific Class of Mersenne Numbers primus Miscellaneous Math 1 2014-10-12 09:25
Conjectured Primality Test for Specific Class of k6^n-1 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15
How do I test a specific 2^p-1? Alex Information & Answers 1 2011-01-12 22:46

All times are UTC. The time now is 00:00.


Tue Dec 7 00:00:51 UTC 2021 up 136 days, 18:29, 1 user, load averages: 1.32, 1.21, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.