mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-06-17, 13:30   #1
Housemouse
 
Housemouse's Avatar
 
Feb 2008

25 Posts
Default Subfactorial primes

!3 = 2 is the only subfactorial prime
!2+1 = 2
!3+1 = 3
!5-1 = 43

Any other !N +1 or !N - 1 that are prime?
Housemouse is offline   Reply With Quote
Old 2008-06-17, 14:41   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Housemouse View Post
!3 = 2 is the only subfactorial prime
!2+1 = 2
!3+1 = 3
!5-1 = 43

Any other !N +1 or !N - 1 that are prime?
They should form a very thin infinite set.
R.D. Silverman is offline   Reply With Quote
Old 2008-06-17, 17:00   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·2,081 Posts
Default

Quote:
Originally Posted by Housemouse View Post
!3 = 2 is the only subfactorial prime
!2+1 = 2
!3+1 = 3
!5-1 = 43

Any other !N +1 or !N - 1 that are prime?
Based upon this post, I'm not clear what a "subfactorial" prime is.
rogue is offline   Reply With Quote
Old 2008-06-17, 17:09   #4
Housemouse
 
Housemouse's Avatar
 
Feb 2008

25 Posts
Default

N subfactorial, designated !N is calculted as follows:


N! * (1-1/1!+1/2!-1/3!+1/4!.....1/n!)

!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
Housemouse is offline   Reply With Quote
Old 2008-06-17, 18:00   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×3,529 Posts
Default

Quote:
Originally Posted by rogue View Post
Based upon this post, I'm not clear what a "subfactorial" prime is.
Neither was I, but Google quickly told me.

Paul
xilman is offline   Reply With Quote
Old 2008-06-17, 18:15   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000111011102 Posts
Default

Quote:
Originally Posted by Housemouse View Post
N subfactorial, designated !N is calculated as follows:


N! * (1-1/1!+1/2!-1/3!+1/4!.....1/n!)

!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
OK, by that definition and standard properties of alternating sequences it's also nearest_integer(exp(-1) * factorial(N))

Bring out gp:
Code:
for(t=10,264,s=floor(exp(-1)*factorial(t)+0.5);for(j=-3,3,if(isprime(s+j),print([t,j]))))
says
Code:
[11, -3]
[15, -1]
[17, -1]
[21, 3]
[149, -3]
[173, -3]
[185, 3]
[202,-2]
[264,-2]
fivemack is offline   Reply With Quote
Old 2008-06-17, 19:57   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011110101102 Posts
Default

Another formula:

!n = Floor((n!+1)/e)

for n>=1

Last fiddled with by ATH on 2008-06-17 at 20:02
ATH is offline   Reply With Quote
Old 2008-06-18, 12:15   #8
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

If N is even then N divides !N-1, and !N+1 is even.
If N is odd then N divides !N+1.
That leaves !N-1 for odd N. The only primes for N<=10000:
!5-1 = 43
!15-1 = 481066515733
!17-1 = 130850092279663

These were already computed by http://www.research.att.com/~njas/sequences/A100015 and fivemack.
I'm continuing to 20000. Candidates are computed by PARI/GP and tested by PrimeForm/GW.
Like R.D. Silverman, I expect infinitely many but rare primes.
Jens K Andersen is offline   Reply With Quote
Old 2008-06-18, 15:03   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×11×61 Posts
Default

I think it is best to use a sieve to discard many candidates.

I will prove that !N \equiv -!(N+p) \pmod p.

Let N = mp+n (0<=n<p)

Let u \equiv N! - N!/1! + N!/2! - N!/3! +... +(-1)^N \pmod p

Let v \equiv (N+p)! - (N+p)!/1! + (N+p)!/2! - (N+p)!/3! +... + (-1)^N \pmod p

When computing u, if k<mp, then that term will have more p's on the numerator than on the denominator, so it will be congruent to zero. The same occurs when computing v for k<mp+p. So discarding those terms we have:

\large u \equiv \frac{(-1)^{(mp)} N!}{(mp)!} + \frac{(-1)^{(mp+1)} N!}{(mp+1)!} + ... + (-1)^{N}

\large v \equiv \frac{(-1)^{(mp+p)} (N+p)!}{(mp+p)!} + \frac{(-1)^{(mp+p+1)} (N+p)!}{(mp+p+1)!} + ... + (-1)^{(N+p)}

From Wilson's theorem: (p-1)! \equiv -1 \pmod p

(p+1)(p-1)! \equiv -1*1 \equiv -1!
(p+2)(p+1)(p-1)! \equiv -1!*2 \equiv -2!
(p+3)(p+2)(p+1)(p-1)! \equiv -2!*3 \equiv -3!

Using induction: (p+u)!/p \equiv -u! \pmod p

Replacing the last formula on the formula for v:

\large v \equiv \frac{(-1)^{(mp+p)} (-N!)} {-(mp)!} + \frac{(-1)^{(mp+p+1)} (-N!)}{-(mp+1)!} + ... + (-1)^{(N+p)}

\large v \equiv \frac{(-1)^{(mp+p)} N!} {(mp)!} + \frac{(-1)^{(mp+p+1)} (N!)}{(mp+1)!} + ... + (-1)^{(N+p)}

So the terms of u are negatives of those of v. Thus u \equiv -v \pmod p

Last fiddled with by alpertron on 2008-06-18 at 15:05
alpertron is offline   Reply With Quote
Old 2008-06-18, 15:41   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×11×61 Posts
Default

For example, in the case !N-1 we have the following zeros:
p = 2 -> N = 0 (mod 2)
p = 3 -> N = 0, 2 (mod 6)
p = 5 -> N = 0, 2, 9 (mod 10)
p = 7 -> N = 0, 2, 13 (mod 14)
p = 11 -> N = 0, 2, 6, 10 (mod 22)
etc.

So for these congruences of N, !N-1 is composite.

Of course the even values are not needed because they are already covered by the case p=2.

Other values of N for which !N-1 is composite:
p=5 -> N = 9 (mod 10)
p=7 -> N = 13 (mod 14)
p=17 -> N = 7 (mod 34)
p=19 -> N = 13, 25 (mod 38)
p=23 -> N = 19 (mod 46)
p=29 -> N = 49 (mod 58)
p=43 -> N = 5 (mod 86) (of course when N=5, !N-1 is prime).
p=47 -> N = 27 (mod 94)
p=59 -> N = 11 (mod 118)
p=67 -> N = 63, 81 (mod 134)
p=73 -> N = 121 (mod 146)
p=79 -> N = 109, 115 (mod 158)
p=89 -> N = 103 (mod 178)
p=97 -> N = 179 (mod 194)

Last fiddled with by alpertron on 2008-06-18 at 15:55
alpertron is offline   Reply With Quote
Old 2008-06-18, 21:26   #11
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

23010 Posts
Default

I'm stopping when 20000 is reached. This is a one day search and I'm not implementing a sieve. I also think the advantage would be quite small. The primes which divide more than one value up to !20000 are so small that only little trial factoring would be spared. A trial factoring program using !n = n * !(n-1) + (-1)^n would probably be a better use of programming time but I'm not doing that either.
Jens K Andersen is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 06:11.

Thu Feb 25 06:11:37 UTC 2021 up 84 days, 2:22, 0 users, load averages: 1.95, 2.08, 2.20

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.