User pedja - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:20:36Z http://mathoverflow.net/feeds/user/17600 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91350/primality-criteria-for-specific-class-of-wagstaff-numbers Primality criteria for specific class of Wagstaff numbers ? pedja 2012-03-16T05:28:51Z 2012-07-12T11:22:01Z <p>I asked this question on mathstackexchange but didn't get any answer .</p> <blockquote> <p>Definition :</p> <p>Let $W_p$ be a Wagstaff number of the form :</p> <p>$W_p=\frac{2^p+1}{3}$ , with $p\equiv 1 \pmod 4$</p> </blockquote> <p>Next , define sequence $S_i$ as :</p> <p>$S_i =8S^4_{i-1}-8S^2_{i-1}+1$ , with $S_0=\frac{3}{2}$</p> <p>How to prove following statement :</p> <blockquote> <p>Conjecture :</p> <p>$W_p$ is a prime iff $S_{\frac{p-1}{2}} \equiv \frac{3}{2} \pmod {W_p}$</p> </blockquote> <p>I checked statement for following Wagstaff primes :</p> <p>$W_5 , W_{13} , W_{17} , W_{61} , W_{101} , W_{313} , W_{701} , W_{1709} , W_{2617} , W_{10501} , W_{42737} ,W_{95369} , W_{138937} ,W_{267017}$</p> <p>Also , for $~p &lt; 15000~$ there is no composite $W_p$ that satisfies relation from conjecture .</p> <p>P.S.</p> <p>I am interested in hints (not full solution) .</p> http://mathoverflow.net/questions/94610/lucasian-criteria-for-the-primality-of-repunit-numbers Lucasian Criteria for the Primality of Repunit numbers pedja 2012-04-20T07:37:19Z 2012-04-21T12:36:29Z <p><strong>Def 1.</strong></p> <p>Let's define repunit number $R_n$ in base $10$ as :</p> <p>$R_n=\frac{10^n-1}{9}$ , with $n \geq 1$</p> <p><strong>Def 2.</strong></p> <p>Next , define polynomial $P_n(x)$ as :</p> <p>$P_n(x)=2^{-n} \cdot \left(\left (x-\sqrt{x^2-4} \right )^n+\left (x+\sqrt{x^2-4}\right )^n \right )$</p> <p><strong>Def 3.</strong></p> <p>Let's define sequence $S_i$ as :</p> <p>$S_i=P_{10}(S_{i-1})$ with $S_0=15127$</p> <blockquote> <p><strong>Conjecture :</strong></p> <p>$R_n ; (n > 5) ~\text{is a prime iff }~ S_{n-1}\equiv S_0 \pmod {R_n}$</p> </blockquote> <p>I have checked statement for following repunit primes :</p> <p>$R_{19} , R_{23} , R_{317} , R_{1031} , R_{49081}$</p> <p><strong>Question :</strong></p> <p>I am interested in approaches which can be used to prove this conjecture .</p> <p><strong>P.S.</strong></p> <p>One can formulate similar conjectures for repunits in all other bases .</p> http://mathoverflow.net/questions/92662/conjecture-on-primality-of-wagstaff-numbers Conjecture on Primality of Wagstaff Numbers pedja 2012-03-30T09:13:02Z 2012-03-30T09:13:02Z <p>This question is related to my <a href="http://mathoverflow.net/questions/91350/primality-criteria-for-specific-class-of-wagstaff-numbers" rel="nofollow">previous question</a> .</p> <p><strong>Definition :</strong></p> <p>Let $W_p$ be a Wagstaff number of the form :</p> <p>$W_p=\frac{2^p+1}{3}$ , where $p$ is a prime number .</p> <p><strong>Definition :</strong></p> <p>Let's define starting seed $S$ as :</p> <p>$S = 3 ~\text{ if }~ p\equiv 1 \pmod 4$</p> <p>$S=11 ~\text{ if }~ p\equiv 1 \pmod 6$</p> <p>$S=27 ~\text{ if }~ p\equiv 11 \pmod {12} \text{ and } p \equiv 1,9 \pmod {10}$</p> <p>$S=33 ~\text{ if }~ p\equiv 11 \pmod {12} \text { and } p \equiv 3,7 \pmod {10}$</p> <p><strong>Definition :</strong></p> <p>Let's define sequence $S_i$ as :</p> <p>$S_i=S^4_{i-1}-4 \cdot S^2_{i-1}+2 ~\text{ with }~ S_0=S$</p> <blockquote> <p><strong>Conjecture :</strong></p> <p>$W_p ~; (p>3) ~\text{ is a prime iff }~ S_{\frac{p-1}{2}} \equiv S \pmod {W_p}$</p> </blockquote> <p>I checked statement for following Wagstaff primes :</p> <p>$W_5 , W_7 , W_{11} ,W_{13} , W_{17} , W_{19} , W_{23} , W_{31} , W_{43} ,W_{61} , W_{79} , W_{101} ,W_{127} , W_{167} , W_{191} , W_{199} ,W_{313} , W_{347} ,$ $W_{701} , W_{1709} ,W_{2617} , W_{3539} , W_{5807} , W_{10501} ,W_{10691} , W_{11279} ,W_{12391} , W_{14479} ,W_{42737} ,W_{83339} ,W_{95369} ,$ $W_{127031} , W_{138937} , W_{141079} , W_{267017} , W_{269987} ,W_{374321}$</p> <p>According to this criteria probable prime $W_{117239}$ is a composite number .</p> <p>Also , for $p &lt; 15000$ there is no composite $W_p$ that satisfies relation from conjecture .</p> <blockquote> <p><strong>Question :</strong> Are there similar primality criteria for Wagstaff numbers in the literature ?</p> </blockquote> <p><strong>P.S.</strong></p> <p>According to <a href="http://en.wikipedia.org/wiki/Wagstaff_prime#Primality_testing" rel="nofollow">this</a> Wikipedia article the fastest algorithm for proving the primality of Wagstaff numbers is ECCP .</p> http://mathoverflow.net/questions/91990/primality-criteria-for-fermat-numbers-using-quartic-recurrence-equation Primality criteria for Fermat numbers using quartic recurrence equation pedja 2012-03-23T10:05:22Z 2012-03-23T18:04:16Z <p>Let's define sequence $S_i$ as :</p> <p>$S_i= S^4_{i-1}-4\cdot S^2_{i-1}+2 ~\text{with}~ S_0=8$</p> <p>I have found that :</p> <p>$F_2 \mid S_1 , ~F_3 \mid S_3 ,~F_4 \mid S_7$</p> <p>where $F_2 , F_3 , F_4$ are Fermat numbers .</p> <blockquote> <p><strong>Conjecture :</strong></p> <p>$F_n = 2^{2^n}+1 ,(n \geq 2) ~\text{is a prime iff}~F_n \mid S_{2^{n-1}-1}$</p> </blockquote> <p>In <a href="https://docs.google.com/open?id=0B9GIk5AfjFmSbDE1X185ZV9TYy04M3o0Um43NTJhQQ" rel="nofollow">this document</a> you can find my proof of this conjecture .</p> <p><strong>Question :</strong></p> <p>Is my proof acceptable ? Are there similar criteria in the literature ?</p> http://mathoverflow.net/questions/91511/primality-criterion-for-generalized-fermat-numbers-similar-to-the-llt Primality criterion for generalized Fermat numbers similar to the LLT ? pedja 2012-03-18T06:28:21Z 2012-03-18T06:28:21Z <p>I asked this question on mathstackexchange but didn't get any answer .</p> <blockquote> <p>Definition 1 :</p> <p>Let $F_n(b)$ be a generalized Fermat number of the form :</p> <p>$F_n(b) = b^{2^n}+1$ , where $b$ is a positive even integer .</p> <p>Definition 2 :</p> <p>Let $T_n(S_{i-1})$ be a Chebyshev polynomial of the first kind , i.e.</p> <p>$T_n(S_{i-1}) = 2^{-1} \cdot \left(\left(S_{i-1}+\sqrt{S^2_{i-1}-1}\right)^n+\left(S_{i-1}-\sqrt{S^2_{i-1}-1}\right)^n\right )$</p> </blockquote> <p>How to prove following statements :</p> <p>Example 1 :</p> <p>Let's define sequence $S_i$ as :</p> <p>$S_i = T_{78} (S_{i-1} ) \text{ with } S_{0} = 6$</p> <p>I have found that :</p> <p>$F_1(156) \mid S_2 , ~ F_4(156) \mid S_{30} , ~ F_5(156) \mid S_{62}$</p> <p>Also , no composite $F_n(156)$ up to $n= 10$ divides corresponding $S_i$ .</p> <blockquote> <p>Conjecture :</p> <p>$F_{n}(156) , (n \geq 1) \text{ is a prime iff } F_n(156) \mid S_{2^{n+1}-2}$</p> </blockquote> <p>Example 2 :</p> <p>Let's define sequence $S_i$ as :</p> <p>$S_i = T_{18} (S_{i-1} ) \text{ with } S_{0} = 8$</p> <p>I have found that :</p> <p>$F_2(288) \mid S_{17} , ~ F_3(288) \mid S_{37} , ~ F_4(288) \mid S_{77}$</p> <p>Also , no composite $F_{n}(288)$ up to $n=10$ divides corresponding $S_i$ .</p> <blockquote> <p>Conjecture :</p> <p>$F_{n}(288) , (n \geq 1) \text{ is a prime iff } F_n(288) \mid S_{5 \cdot 2^n-3}$</p> </blockquote> <p>Example 3 :</p> <p>Let's define sequence $S_i$ as :</p> <p>$S_i = T_{2222}(S_{i-1}) \text{ with } S_{0}=4$</p> <p>I have found that :</p> <p>$F_1(4444) \mid S_{2} , ~ F_2(4444) \mid S_{6} , ~ F_4(4444) \mid S_{30}$</p> <p>Also , no composite $F_{n}(4444)$ up to $n=10$ divides corresponding $S_i$ .</p> <blockquote> <p>Conjecture :</p> <p>$F_{n}(4444) , (n \geq 1 ) \text{ is a prime iff } F_n(4444) \mid S_{2^{n+1}-2}$</p> </blockquote> <p>P.S.</p> <p>I am interested in hints (not full solution) .</p> http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers Are these polynomials irreducible over ring Z of integers ? pedja 2011-11-10T08:40:04Z 2011-11-10T09:15:17Z <p>Is it true that polynomials of the form :</p> <blockquote> <p>$f(x)= x^n+x^{n-1}+...+x^{k+1}+ax^k+ax^{k-1}+...a$</p> <p>where $gcd(n+1,k+1)=1$ and $a\in \mathbb{Z^{+}}$</p> </blockquote> <p>are irreducible over ring $\mathbb{Z}$ of integers ?</p> <p>Neither of <a href="http://en.wikipedia.org/wiki/Eisenstein%27s_criterion" rel="nofollow"> Eisenstein's criterion</a> and <a href="http://en.wikipedia.org/wiki/Cohn%27s_irreducibility_criterion" rel="nofollow">Cohn's criterion</a> cannot be applied on the polynomials of this form. I have checked a lot of cases and it seems to be true.</p> http://mathoverflow.net/questions/74576/infinite-number-of-prime-pairs/74636#74636 Answer by pedja for infinite number of prime pairs pedja 2011-09-06T08:48:40Z 2011-09-06T09:19:12Z <p>maybe there is,it is not proved yet. It is a particular case of a general conjecture concerning linear equations in primes :</p> <p>Conjecture : Let $a$ and $b$ two integers such that $a>0$, the product $ab$ is even and $a$ and $b$ are coprime. Then the equation $p' =ap+b$ has infinitely many solutions in pairs of prime $(p,p')$.</p> http://mathoverflow.net/questions/74576/infinite-number-of-prime-pairs infinite number of prime pairs pedja 2011-09-05T12:21:13Z 2011-09-06T09:19:12Z <p>Is there infinite number of prime pairs `$(p_k,p_n)$ that satisfy equality $p_n=2p_k-3$</p> http://mathoverflow.net/questions/94610/lucasian-criteria-for-the-primality-of-repunit-numbers Comment by pedja pedja 2012-04-20T12:55:58Z 2012-04-20T12:55:58Z @MarkSapir Starting seed $S_0$ isn't chosen randomly... http://mathoverflow.net/questions/94610/lucasian-criteria-for-the-primality-of-repunit-numbers Comment by pedja pedja 2012-04-20T10:31:25Z 2012-04-20T10:31:25Z @FranzLemmermeyer You can formulate same criterion for Mersenne numbers if you set $S_i=P_2(S_{i-1})$ , $S_0=34$ , and $n&gt;5$ http://mathoverflow.net/questions/94610/lucasian-criteria-for-the-primality-of-repunit-numbers Comment by pedja pedja 2012-04-20T08:11:21Z 2012-04-20T08:11:21Z @MarkSapir Because this test is fast and deterministic... http://mathoverflow.net/questions/91990/primality-criteria-for-fermat-numbers-using-quartic-recurrence-equation/92001#92001 Comment by pedja pedja 2012-04-06T04:14:23Z 2012-04-06T04:14:23Z @EmilJerabek On my computer Java implementation of this test is approximately $1.5$ time faster than Java implementation of Inkeri's test... http://mathoverflow.net/questions/92788/contigous-prime-numbers-with-mpi-want-more-ideas-for-efficient-algorithm-to-veri Comment by pedja pedja 2012-04-01T04:50:45Z 2012-04-01T04:50:45Z <a href="http://codereview.stackexchange.com/questions?sort=newest" rel="nofollow">codereview.stackexchange.com/&hellip;</a> http://mathoverflow.net/questions/91990/primality-criteria-for-fermat-numbers-using-quartic-recurrence-equation/92001#92001 Comment by pedja pedja 2012-03-23T11:58:00Z 2012-03-23T11:58:00Z I didn't know that such test exists . As you can see my test uses lesser number of iterations . http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers/80571#80571 Comment by pedja pedja 2011-11-10T09:37:01Z 2011-11-10T09:37:01Z yes $k$ must be greater than $1$ http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers/80571#80571 Comment by pedja pedja 2011-11-10T09:35:28Z 2011-11-10T09:35:28Z yes but $a_1=1$ and I am asking what if $a_1=a &gt;1$ http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers/80571#80571 Comment by pedja pedja 2011-11-10T09:32:36Z 2011-11-10T09:32:36Z in example above $a_0=a=21$ http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers/80571#80571 Comment by pedja pedja 2011-11-10T09:29:41Z 2011-11-10T09:29:41Z no, $a_1$ is coefficient of the linear term...example: $x^2+3x+3$ where $a_1=a=3$ http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers/80571#80571 Comment by pedja pedja 2011-11-10T09:20:47Z 2011-11-10T09:20:47Z you are right.what if $a_1 \neq 1$ and $a$ is odd number greater than $1$ ? http://mathoverflow.net/questions/80569/are-these-polynomials-irreducible-over-ring-z-of-integers Comment by pedja pedja 2011-11-10T09:10:20Z 2011-11-10T09:10:20Z @Carnahan,what if a is odd and greater than 1 http://mathoverflow.net/questions/75377/how-to-determine-which-one-of-the-two-conjectures-is-more-difficult-to-prove Comment by pedja pedja 2011-09-14T05:55:13Z 2011-09-14T05:55:13Z @WillJagy,Thanks for advice http://mathoverflow.net/questions/75377/how-to-determine-which-one-of-the-two-conjectures-is-more-difficult-to-prove Comment by pedja pedja 2011-09-14T05:30:46Z 2011-09-14T05:30:46Z @WillJagy,I passed the exams which are called &quot;algebra&quot;,&quot;calculus 1&quot;,&quot;calculus 2&quot; at the university of electrical engineering http://mathoverflow.net/questions/74973/subset-x-of-set-n-such-that-any-natural-number-except-1-can-be-expressed-as-sum-o Comment by pedja pedja 2011-09-09T10:23:08Z 2011-09-09T10:23:08Z GH,Richards (1974) proved that the first and second Hardy-Littlewood conjectures are incompatible with each other