mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2012-11-20, 19:52   #1
Mr. Odd
 
Mar 2010

5×11 Posts
Default n!-(n-1)!-(n-2)!...-1!

Playing around with number sequences, I started factoring factorial subtractions - n!-(n-1)!-(n-2)!-...-1!. It's clear there's a pattern in the numbers but my algebra is too rusty to figure it out. For n>=11 it's 3^2*11*m. Anyone have a simplified formula?
Mr. Odd is offline   Reply With Quote
Old 2012-11-20, 20:20   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23·3·59 Posts
Default

Quote:
Originally Posted by Mr. Odd View Post
Anyone have a simplified formula?
A132371(n)
R. Gerbicz is offline   Reply With Quote
Old 2012-11-20, 20:38   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

a(n) = n! - (n-1)! - ...

a(n+1) = (n+1)! - n! - (n-1)! - ... = a(n) + (n+1)! - 2*n! = a(n) + n!*[(n+1) - 2] = a(n) + (n-1)*n!

a(n) = a(n-1) + (n-2)*(n-1)! = (n-2)*(n-1)! + (n-3)*(n-2)! + a(n-2) = ...

a(1) = 1! = 1

a(2) = 2! - 1! = 1
a(2) = a(1) + 0*1! = 1 + 0 = 1, good

a(3) = 3! - 2! - 1! = 6 - 2 - 1 = 3
a(3) = 1*2! + 0*1! + a(1) = 2 + 0 + 1 = 3, good

=> a(n) = 1 + \sum_{i=2}^n{(i-2)*(i-1)!} = [j=i-1] 1 + \sum_{j=1}^{n-1}{(j-1)*j!}, but the first term is 0, so
a(n) = 1 + \sum_{j=2}^{n-1}{(j-1)*j!}

...

n! + (n-1)! + ... = \sum_{i=1}^n{\left(\prod_{j=1}^ij\right)}

Last fiddled with by Dubslow on 2012-11-20 at 21:36
Dubslow is offline   Reply With Quote
Old 2012-11-20, 22:03   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Dubslow View Post
a(n) = n! - (n-1)! - ...

a(n+1) = (n+1)! - n! - (n-1)! - ... = a(n) + (n+1)! - 2*n! = a(n) + n!*[(n+1) - 2] = a(n) + (n-1)*n!

a(n) = a(n-1) + (n-2)*(n-1)! = (n-2)*(n-1)! + (n-3)*(n-2)! + a(n-2) = ...

a(1) = 1! = 1

a(2) = 2! - 1! = 1
a(2) = a(1) + 0*1! = 1 + 0 = 1, good

a(3) = 3! - 2! - 1! = 6 - 2 - 1 = 3
a(3) = 1*2! + 0*1! + a(1) = 2 + 0 + 1 = 3, good

=> a(n) = 1 + \sum_{i=2}^n{(i-2)*(i-1)!} = [j=i-1] 1 + \sum_{j=1}^{n-1}{(j-1)*j!}, but the first term is 0, so
a(n) = 1 + \sum_{j=2}^{n-1}{(j-1)*j!}

...

n! + (n-1)! + ... = \sum_{i=1}^n{\left(\prod_{j=1}^ij\right)}
simplest I can get is: a(n)=a(n-1)+(n!-2*(n-1)!) I believe, reasoning:

a(3) = 3!-2!-1! = 3
a(4) = 4!-3!-2!-1! = 15

the lime is the same, the sign on 3! has opposite indicating a change from 1 to -1 (-1)-1=-2 the coefficient I give the other change is the addition of 4! , n=4 so n!-2*(n-1)! is the difference:

Code:
a=[1];for(x=1,100,a=concat(a,a[#a]+(#a+1)!-2*eval(#a)!));a

Last fiddled with by science_man_88 on 2012-11-20 at 22:04
science_man_88 is offline   Reply With Quote
Old 2012-11-20, 22:06   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160358 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
so n!-2*(n-1)! is the difference
Of course it is, and that's what I did. n! - 2*(n-1)! = (n-1)!*(n - 2). (If you don't believe me, distribute the latter multiplication.)


Of course, the sum I reduced it to is basically no simpler than the sum of factorials at the bottom of the post. If you can sum that, then you'll have a simple formula.

PS @OP, what do you mean by m? n! ?
Dubslow is offline   Reply With Quote
Old 2012-11-20, 22:13   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Of course it is, and that's what I did. n! - 2*(n-1)! = (n-1)!*(n - 2). (If you don't believe me, distribute the latter multiplication.)


Of course, the sum I reduced it to is basically no simpler than the sum of factorials at the bottom of the post. If you can sum that, then you'll have a simple formula.

PS @OP, what do you mean by m? n! ?
maybe I got confused since now that i look at it your last equation suggest a sum of factorials is what's wanted by the OP, but I read it as subtraction in the OP.

Last fiddled with by science_man_88 on 2012-11-20 at 22:19
science_man_88 is offline   Reply With Quote
Old 2012-11-20, 22:22   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

719710 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
maybe I got confused since now that i look at it your last equation suggest a sum of factorials is what's wanted by the OP, but I read it as subtraction in the OP.
No, it is the subtraction, but I was initially trying to see if there was a way to do the simple factorial sum, call if F(n) = sum_i=1^n of n!.

Then a(n) = n! - F(n-1), so finding a formula for F would produce an easy formula for a. Of course, as I showed by reducing a(n) to a simpler series, that manner is no more promising than finding a formula for F itself.

In shorter words, finding a simple formula for both F and a is, AFAICT, essentially equivalent. That's what I was trying to say in my previous post.
Dubslow is offline   Reply With Quote
Old 2012-11-20, 22:38   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

Quote:
Originally Posted by Dubslow View Post
No, it is the subtraction, but I was initially trying to see if there was a way to do the simple factorial sum, call if F(n) = sum_i=1^n of n!.

Then a(n) = n! - F(n-1), so finding a formula for F would produce an easy formula for a. Of course, as I showed by reducing a(n) to a simpler series, that manner is no more promising than finding a formula for F itself.

In shorter words, finding a simple formula for both F and a is, AFAICT, essentially equivalent. That's what I was trying to say in my previous post.
but if you look at the OEIS sequence for it, it doesn't start with 0 as you stated.
science_man_88 is offline   Reply With Quote
Old 2012-11-20, 22:52   #9
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160358 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
but if you look at the OEIS sequence for it, it doesn't start with 0 as you stated.
0? Who said 0? a(1) = 1 = a(2), a(3) = 3.


PS: Sums of factorials. (Hardly a simple form.)

\sum_{k=1}^n{k!} = \frac{1}{e}\left(-e + \int_\infty^{-1}{\frac{e^{-t}}{t}dt}+\pi i + (n+1)! \int_1^\infty{\frac{e^t}{t^{n+2}}dt} \right)

Last fiddled with by Dubslow on 2012-11-20 at 23:15
Dubslow is offline   Reply With Quote
Old 2012-11-20, 22:57   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Dubslow
but the first term is 0, so
thought this was part of it, apparently I'm mistaken.
science_man_88 is offline   Reply With Quote
Old 2012-11-21, 03:49   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

213448 Posts
Default

Quote:
Originally Posted by Dubslow View Post
PS @OP, what do you mean by m? n! ?
He means the decomposition of a_n into factors, last factor (prime or composite) being m. He claims after n>11, all have 3^2*11 as a common factor, which is totally true, because all factorials bigger then 10 contain 9 and 11, and the sum S=1!+2!+....+10! is divisible by 9 and 11, so their sum/difference with S is too.

(edit limit)

1. because 1!+2!=3 is divisible by 3, all a(n), n>=3, will be divisible by 3

2. because 1!+2!+3!+4!+5!=152=9*17 is divisible by 3^2, all a(n), n>=6, will be divisible by 3^2 (all factorials bigger or equal with 6 contain 3^2)

3. because 1!+2!+...+10! is divisible by 3^2*11, all a(n), n>=11, will be divisible by 3^2*11 (all factorials bigger or equal with 11 contain 3^2*11)

This probably happens an infinite number of times, but it is difficult to spot due to the rapid growth of a(n) series. The necessary condition is that the factorial sum s(n) to have factors lower then n, and the probability of this is higher, as n is higher. The next value where it is happening would look something like:

4. because 1!+2!+...+xxxxxx! is divisible by 3^2*11*yyy, with yyy<xxxxxx+1, then all a(n) for n>xxxxxx, will be divisible by 3^2*11*yyy (all factorials bigger then xxxxxx contain 3^2*11*yyy)

(tip: you don't need to factor the sums, only to TF them with primes under n, which is very fast, and you don't need to do it sequentially, just pick a very big xxxxxx, like the binary search, and if lucky, come down by halving n. I tested s(20000) and it has not other smaller factors except 9 and 11)

This only in case I don't miss some theoretic trick which forbids the factorial sums s(n) to have factors smaller than n.

Last fiddled with by Batalov on 2012-11-21 at 04:33 Reason: (merged)
LaurV is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 13:28.

Thu Nov 26 13:28:50 UTC 2020 up 77 days, 10:39, 3 users, load averages: 1.05, 1.35, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.