mersenneforum.org Search primes of form 2*n^n ± 1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-04-03, 22:43 #1 JeppeSN     "Jeppe" Jan 2016 Denmark 5×37 Posts Search primes of form 2*n^n ± 1 $$2n^n\pm 1$$ may be prime. I just noticed two sequences in OEIS: 0, 1, 12, 18, 251, ... (A110932) 2, 3, 357, 1400, ... (A110931) which list all $$n$$ such that $$2n^n+1$$, respectively $$2n^n-1$$, is prime. The search limit given in OEIS is $$n=35000$$ and $$n=4000$$, respectively. Has anyone who reads this searched these forms before, and to what limit? Maybe a new prime can be found (incredible optimist)? And clearly it will be a provable prime (as a neighbor to a number whose full factorization is trivial). /JeppeSN
2018-04-03, 23:24   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

Quote:
 Originally Posted by JeppeSN which list all $$n$$ such that $$2n^n+1$$, respectively $$2n^n-1$$, is prime.
No, haven't
But, mod 3 we get:

n=1 mod 3; 1ⁿ is always 1 mod 3 so 2*1ⁿ+1 is 0 mod 3
n= 2 mod 3
Case1 n is even, 2*2ⁿ+1 is 0 mod 3
Case2 n is odd, 2*2ⁿ-1 is 0 mod 3

Etc.

2018-04-04, 00:56   #3
Dylan14

"Dylan"
Mar 2017

2·33·11 Posts

I did a small n range of 2*n^n-1 (ie n = 4000 to n = 5000) to get a gauge of the speed of a PRP test of this form and to see how many tests would have to be run. Using the following command line

Code:
pfgw64 -f -lresidues.txt 2ktothekminus1.pfgw
I found no primes of that form, so a(5) > 5000 for A110931. The residue file and factors found are attached to this post. Just 90 PRP tests were needed with the default factoring limit in PFGW, so I wonder if an efficient sieve program could be made for the form 2*n^n+/-1?
Attached Files
 residues.txt (36.3 KB, 304 views)

 2018-04-04, 01:23 #4 rogue     "Mark" Apr 2003 Between here and the 2×34×43 Posts I believe that my old MultiSieve sieved numbers of this form, k*b^b+/-1.
 2018-04-04, 21:57 #5 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 2·3·23·61 Posts For easy elimination, it comes down to when (p+1)/2 or (p-1)/2 can be residue a power can take on mod prime p. Last fiddled with by science_man_88 on 2018-04-04 at 22:15
 2018-04-06, 22:00 #6 Dr Sardonicus     Feb 2017 Nowhere 185316 Posts For odd primes p, the behavior of nn (mod p) is kind of interesting. We have (n+p)n+p == nn+p == nn+1 (mod p), so that (n+k*p)n+k*p == nn+k*p == nn+k (mod p), so that (n+(p-1)*p)n+(p-1)*p == nn+(p-1)*p == nn+p-1, so that (n+(p-1)*p)n+(p-1)*p == nn (mod p) for every positive integer n. That is, nn (mod p) is periodic, and (p-1)*p is a period. For any k, 0 < k < p, there will be solutions to nn - 1 == 0 (mod p) with n == k (mod p). If k (mod p) has even multiplicative order, there will be solutions to nn + 1 == 0 (mod p) with n == k (mod p).
2018-04-07, 13:47   #7
Dr Sardonicus

Feb 2017
Nowhere

13·479 Posts

Quote:
 Originally Posted by science_man_88 For easy elimination, it comes down to when (p+1)/2 or (p-1)/2 can be residue a power can take on mod prime p.
We see from my last post to this thread, that for each integer r, 0 < r < p, the residues

(r + k*p)r+k*p (mod p) are r1+k (mod p).

These residues form a group. So the question of whether

2*nn == 1 (mod p) for some n == r (mod p)

is, whether 2 (mod p) is in the group generated by r (mod p). Since the multiplicative group of nonzero residues (mod p) is cyclic, the question becomes whether the multiplicative order of 2 (mod p) divides the multiplicative order of r (mod p).

Similarly, the question of whether

2*nn == -1 (mod p) for some n == r (mod p)

becomes whether the multiplicative order of -2 (mod p) divides the multiplicative order of r (mod p).

 2018-04-08, 16:19 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 1005910 Posts How 'bout this one? 2*82992^82992+1 is prime.
2018-04-08, 16:56   #9
rogue

"Mark"
Apr 2003
Between here and the

154668 Posts

Quote:
 Originally Posted by Batalov How 'bout this one? 2*82992^82992+1 is prime.
I see that you used MultiSieve. I hope that it saved you some time. Is sieving this form a candidate for mtsieve? It would probably take me only a day or two to write it.

 2018-04-08, 17:49 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 1005910 Posts I am not sure how frequent this use for this code branch would be. The depth was around 29.3 bits after a day or two sieving (on 1 core up to n<=250k) so I am sure that it did save some time; factors for these are general, so I now checked a default PFGW sieving would have been ~26 bits (~83,000 candidates times 0-4 minutes = ...quite a bit of time saved).
2018-04-08, 21:12   #11
JeppeSN

"Jeppe"
Jan 2016
Denmark

18510 Posts

Quote:
 Originally Posted by Batalov How 'bout this one? 2*82992^82992+1 is prime.
Good one! I hoped this would catch your interest.

Are you continuing the search? And did you consider the minus form as well?

/JeppeSN

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 164 2022-03-06 16:19 carpetpool carpetpool 3 2017-01-26 01:29 PawnProver44 Homework Help 1 2016-03-15 22:39 YuL Math 21 2012-10-23 11:06 Dougy Math 8 2009-09-03 02:44

All times are UTC. The time now is 02:52.

Mon Feb 6 02:52:34 UTC 2023 up 172 days, 21 mins, 1 user, load averages: 1.21, 0.98, 0.87

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔