I am trying to programmatically solve mathematical problem - get sum of all powers from $1^1$ to $1000^{1000}$. So far I have found solution by simply summing powers, but it takes way to long time and not getting any near to final 1000 integer.
Question - is there a formula for this case : get sum of all number powers $1^1 + 2^2 + 3^3 + .. 1000^{1000}$ ?
On
No I guess there is none...if you are coding then just use one of the suitable library function to do so..
On
Since you only need the last 10 digits, you can calculate the sum modulo 10^10. You can do each term individually in around logn time, using the 'fast mod-exponentiation' algorithm, and using standard 64 bit integers.
See https://en.wikipedia.org/wiki/Exponentiation_by_squaring
On
There seems to be a function $f(x)=a_0+a_1 (x-2)+ a_2 (x-2)^2 + ... $ having a power series to allow computations $$f(a) - f(b) \Rightarrow \sum_{k=a}^{b-1} k^k = a^a+ (a+1)^{a+1} + ... + (b-1)^{b-1} $$ Thus this function resembles the Faulhaber-polynomials for summing of like powers, but a series instead of polynomials.
I have estimated the first $16$ coefficients of the power series -however by a process which involved Borel-summation (this is because hypergeometric series were involved: a summation $\sum_{k=0}^\infty b_k \zeta(-k)$ where the $b_k$ come from another basic process.)
function-call \\ Pari/GP-output \\ expected value
----------\\ ----------------------- \\ ---------------
f(1)-f(2) \\ %1599 = 0.999998176060 \\ 1
f(2)-f(3) \\ %1600 = 3.99997420277 \\ 4
f(3)-f(4) \\ %1601 = 26.9802071641 \\ 27
f(1)-f(4) \\ %1602 = 31.9801795429 \\ 1+4+27 = 32
f(4)-f(5) \\ %1603 = 253.511224675 \\ 256
f(1)-f(5) \\ %1604 = 285.491404218 \\ 1+4+27+256 = 288
If all things are correct, the function call $f(1)$ should represent the value for the divergent series $1^1+2^2+3^3+ ...$ and I get
f(1) \\ %1605 = 0.920504741712
but I've no indication whether this is a good approximation to the divergent sum since the further coefficients of $f()$ must be determined ahead.
We define the following sequence $\text{(A001923)}$.
To find a formula of $S_n$ was a problem proposed by G. W. Wishard in 1945 in the American Mathematical Monthly (AMM). It would be nice to have some results like Faulhaber's formula, but unfortunately for this problem we don't have a formula like that.
Wishard was given the lower and upper bounds $n^n < S_n < 2n^n$ for $n>1$. As an answer to Wishard's problem F. Underwood was given the following better lower and an upper bounds for $S_n$ in 1946. For $n>2$, $$ n^n\left(1+\frac{1}{4(n-1)}\right) < S_n < n^n\left(1+\frac{2}{e(n-1)}\right). $$
The Euler Project Problem 48 is to find the last ten digits of $S_{1000}$. The problem was published in 2003.
It is easy to calculate the sum using computer algebra systems like Maple or Mathematica. You can run the following Mathematica code in WolframAlpha:
You can check the result here. $S_{1000}$ has $3001$ digits and these are the following.
$$\begin{align} S_{1000} = 1000368199144695177095375011227646795567793680622934654583760988\\ 1002349107477161943814286590995278459458699426431912908947203429\\ 7990640767964725986043423846803832604080969103761537037623771364\\ 8510063115732951461774246705584266865759601815843666442832284556\\ 8803131145481515391909753984854966455765134658585827123364011662\\ 2195618817344953167410268890832176466302030669977040862534076609\\ 1595022791379368098369306375602813856646358773751558775213460225\\ 7965798465833340073493586243423393329813345712378888092831033487\\ 6026136017595081560917946402687100524365210998086355214201424290\\ 3434068560936573231079342194031864413918101238151056509267393515\\ 7603928424725013915940734630015218438110737670217110263075046957\\ 3346789782186690664846982834660741296739580179779168360983472243\\ 2241952845352564681868240369569566192825555323558078061997527689\\ 9838488633747867893315815652520591726143394246009861432592331675\\ 8337107036262555453185205416611714885822950858158961433759446327\\ 7554380518380921301218836327102231407332201109740102580216469298\\ 3317669206196460837907328076273606144280851715650062897285086889\\ 6422679964719258292405858953075067457838536556187855958968575622\\ 5692348914746922810913915619834754117648358035814128670294158565\\ 6699420877362863909422415472260150044713306301130720427042889050\\ 4214262819377191859457430220214720118848634591319083375230747696\\ 6010547423928871063118783026036381319039052008252072057933666712\\ 9189462333127936970940742241878720459709764443092427821877383202\\ 5749008082433007499169869823956112581112760786390035522173784669\\ 0567707344074494145266662103839812840216303448476913957072355732\\ 7166270983722452230467929197472591131574258240648583314154009432\\ 7821304295463505357404520998451222126424190355017841682455141254\\ 8637590007779082539288247751653566899882749594405895102587985539\\ 5277094935100495464454272656174783991071882386817712159042341193\\ 9224748975107908594805594509880561796372292846955426378221762516\\ 0428008228845552540344494860195267115187092227766195753907211126\\ 6461501406147442339747652734756199643118528586141678196683401247\\ 3048771016200679352998575882065367727437956331349545452663271872\\ 3482339494825759821076401694316043456512117937935456463521463021\\ 1977266949835589291323575761885949775166307342128638694561642055\\ 2553676731129813718251149464946366307375921921305682356166777609\\ 3739425742883930712609962163464088038826569132032160692637206183\\ 0859429879736845842764917848431154720779004016925956941192735535\\ 1102599126544603936628892174358133320008371710524117150460688354\\ 3418862024047552177055263424469501298905901938158245938633694105\\ 0248151666798136891566683411977134750943899048871267944689018938\\ 5047505001120522574245555562575056021323038791033798395033324502\\ 0653238989115507013882956277763880795687210857196493893142656713\\ 1059662754221446059880589396006036042269214014020965192942504886\\ 7029798339635327946045314237554226788198919748178978067895509376\\ 3193658603690898474826976906544473978017455720367929981796023041\\ 785852626797271283465789498383642350667978127819110846700.\,\phantom{.......} \end{align}$$
From here we know that the last ten digits are
Another interesting problem is to find the prime factorization of $S_{n}$ values. The only known prime values of the sequence are $S_2, S_5, S_6, S_{10}, S_{30}$, and according to this website, there is no other prime element for $n<28000$.
According to factordb, $S_{1000}$ has the form $$S_{1000} = 2^2 \cdot 5^2 \cdot 344251 \cdot C_{\langle2993\rangle},$$ where $C_{\langle2993\rangle}$ is a composite number with $2993$ digits, without known prime factor. I've made a trial division and I've found no prime factors of $C_{\langle2993\rangle}$ upto $3.735 \cdot 10^8$.
You could find the digits of $S_{1000}$ in the factordb here, and the digits of $C_{\langle2993\rangle}$ here.