1
$\begingroup$

I was doing a question from a site,project euler specifically.I came to a question in which I was asked to calculate sum of digits in number 2^1000.Since I program very often I was able to do that question by making array and calculating as We used to do in elementary school.But I was not convinced because How a student calculate that if he/she don't know programming.I mean it is completely biased question isn't it ?

I am asking if there is any way to calculate digit sum in general (a^b)[a to the power b].For student who don't have programming background.

P.S:- If anybody wants to see implementation.I can post here

$\endgroup$
  • $\begingroup$ You mean a single iteration of digit sum or over and over until it's less than 10? $\endgroup$ – Zelos Malum Nov 1 '15 at 6:51
  • 1
    $\begingroup$ @ZelosMalum : no, it's the sum of the digits. It's this problem : projecteuler.net/index.php?section=problems&id=016. About the question : Project Euler problems are problems where you need to use a computer. Now the question is : is your algorithm efficient, would you be able to calculate the digit sum of $2347^{789524642}$ with it? $\endgroup$ – Tryss Nov 1 '15 at 6:53
  • $\begingroup$ @Tryss Looks like my algorithm cannot make it :)Atleast c++ cannot make it.I have to switch to java or python for that $\endgroup$ – thoughtful me Nov 1 '15 at 6:58
  • $\begingroup$ @thoughtfulme : I'm not surprised, this number is very big, it would take around 2Go to store the number as a string ;) By the way, I don't know if there exists an efficient algorithm to do this 0:) $\endgroup$ – Tryss Nov 1 '15 at 7:07
2
$\begingroup$

It's a one-liner in Maple:

convert(convert(2^1000, base, 10),`+`);

You could look up OEIS sequence A001370. Or you could just ask Wolfram Alpha.

But if you're asking for a way of doing it by hand, I very much doubt that there is any.

$\endgroup$
0
$\begingroup$

Well there is a way to find the sum of the digits of $a^b$ when written in base $p$ where $p$ is prime and $p$ is a divisor of $a^b$. Denote by $v_p(n)$ the exponent of $p$ in the prime factorisation of $n$ and $S_p(n)$ the sum of the digits of $n$ when written in base $p$. By Legendre's Formula,

\begin{align*} v_p(a^b!)=\dfrac{a^b-S_p(a^b)}{p-1} &=\sum_{i=1}^{\infty}\lfloor{ \dfrac{a^b}{p^i} \rfloor} \\ \implies{}S_p(a^b)&=a^b-(p-1)\sum_{i=1}^{\infty}\lfloor{ \dfrac{a^b}{p^i} \rfloor}. \end{align*}

But this formula cannot give a way to solve it by hand and even if there was one its going to be large and messy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.