Subfactorial primes

Housemouse · 2008-06-17, 13:30

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

R.D. Silverman · 2008-06-17, 14:41

Quote:

Originally Posted by Housemouse

!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.

rogue · 2008-06-17, 17:00

Quote:

Originally Posted by Housemouse

!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.

Housemouse · 2008-06-17, 17:09

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

xilman · 2008-06-17, 18:00

Quote:

Originally Posted by rogue

Based upon this post, I'm not clear what a "subfactorial" prime is.

Neither was I, but Google quickly told me.

Paul

fivemack · 2008-06-17, 18:15

Quote:

Originally Posted by Housemouse

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]

ATH · 2008-06-17, 19:57

Another formula:

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

for n>=1

Jens K Andersen · 2008-06-18, 12:15

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.

alpertron · 2008-06-18, 15:03

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$

alpertron · 2008-06-18, 15:41

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)

Jens K Andersen · 2008-06-18, 21:26

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.

2008-06-17, 13:30	#1
Housemouse Feb 2008 20₁₆ Posts	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?

2008-06-17, 19:57	#7
ATH Einyen Dec 2003 Denmark 2²×3×11×23 Posts	Another formula: !n = Floor((n!+1)/e) for n>=1 Last fiddled with by ATH on 2008-06-17 at 20:02

2008-06-18, 15:03	#9
alpertron Aug 2002 Buenos Aires, Argentina 2×11×61 Posts	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 -11 \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*

2008-06-18, 15:41	#10
alpertron Aug 2002 Buenos Aires, Argentina 2·11·61 Posts	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

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

2008-06-17, 17:09	#4
Housemouse Feb 2008 2⁵ Posts	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

2008-06-18, 12:15	#8
Jens K Andersen Feb 2006 Denmark 346₈ Posts	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.

2008-06-18, 21:26	#11
Jens K Andersen Feb 2006 Denmark 2·5·23 Posts	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.