1

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

thoughtful me
  • 11
  • You mean a single iteration of digit sum or over and over until it's less than 10? – Zelos Malum Nov 01 '15 at 06:51
  • 1
    @ZelosMalum : no, it's the sum of the digits. It's this problem : https://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? – Tryss Nov 01 '15 at 06:53
  • @Tryss Looks like my algorithm cannot make it :)Atleast c++ cannot make it.I have to switch to java or python for that – thoughtful me Nov 01 '15 at 06:58
  • @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:) – Tryss Nov 01 '15 at 07:07

2 Answers2

2

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.

Robert Israel
  • 448,999
0

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.

Jack Frost
  • 1,246