Disproven Primality Test for Specific Class of kb^n-1

primus · 2014-08-15, 05:33

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

science_man_88 · 2014-08-15, 12:40

Quote:

Originally Posted by primus

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.

primus · 2014-08-15, 13:27

Quote:

Originally Posted by science_man_88

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 .

Batalov · 2014-08-16, 02:52

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

Ergo, your test is a PRP test. $\qed$

Batalov · 2014-08-16, 02:58

68761*50^3-1 is another counterexample.

primus · 2014-08-16, 05:35

Quote:

Originally Posted by Batalov

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$ ?

R.D. Silverman · 2014-08-16, 06:02

Quote:

Originally Posted by primus

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.

Batalov · 2014-08-20, 17:43

Quote:

Originally Posted by primus

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.

primus · 2014-08-21, 15:16

Thanks for help and references !

2014-08-15, 05:33	#1
primus Jul 2014 Montenegro 2·13 Posts	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:2chebyshev_t(bk/2,chebyshev_t(b/2,2)),N:kb^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)))$

2014-08-21, 15:16	#9
primus Jul 2014 Montenegro 11010₂ Posts	Thanks for help and references ! Last fiddled with by primus on 2014-08-21 at 15:36

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

2014-08-16, 02:52	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×17³ Posts	4103*10^7-1 is a counterexample. 41029999999 = 47743 · 859393. Passes the test. Ergo, your test is a PRP test. $\qed$

2014-08-16, 02:58	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·17³ Posts	68761*50^3-1 is another counterexample.