#!/usr/bin/env python

'''
016.py: https://projecteuler.net/problem=16

Power digit sum

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?
'''
import os
import pytest
import time
import math


def power_digit_sum(N, P):
	"""
	Calculates the sum of digits for a number 'N' raise to power 'P'. Basic
	algorithm is to apply long multiplication, storing the results in two
	arrays, one for current digits, and other a tmp. 
	"""
	# To calculate the size of the array that can hold all our digits, I used
	# the following formula (P * Log10(N))
	d_size = math.ceil(P * math.log(N, 10))
	digits = [None] * d_size
	tmp_digits = [None] * d_size

	# Set our ones column for long multiplication, and assign our first value
	ones_place = d_size - 1
	digits[ones_place] = N

	# Multiply N P-1 times, since we set our initial N in ones_place
	for i in range(1, P):
		j = ones_place
		carry = 0
		while digits[j] != None and j >= 0:
			product = digits[j] * N
			if product >= 10:
				tmp_digits[j] = carry + (product % 10)
				carry = math.floor(product / 10)
				tmp_digits[j-1] = carry
			else:
				tmp_digits[j] = carry + product
				carry = 0
			j -= 1

		tmp = digits
		digits = tmp_digits
		tmp_digits = tmp


	
	return sum(filter(None, digits))


def test_solution():
	'''Test'''
	assert 25 == power_digit_sum(5, 8)
	assert 26 == power_digit_sum(2, 15)

def main():
	'''Main runner, delegates to solution.'''
	print(power_digit_sum(9, 1000))


if __name__ == '__main__':
	start_time = time.time()
	main()
	print("--- %s seconds ---" % (time.time() - start_time))

@@ -481,16 +481,48 @@
  a tmp. 
+%0A%0A%09N must be between 2 %3C= N %3C= 9
 %0A%09%22%22%22%0A%09#
@@ -634,16 +634,60 @@
 g10(N))%0A
+%09if N %3E 9 or N %3C 2 or P %3C 1:%0A%09%09return None%0A%0A
 %09d_size 
@@ -1070,16 +1070,25 @@
 oduct = 
+carry + (
 digits%5Bj
@@ -1092,16 +1092,17 @@
 s%5Bj%5D * N
+)
 %0A%09%09%09if p
@@ -1135,25 +1135,16 @@
 ts%5Bj%5D = 
-carry + (
 product 
@@ -1147,17 +1147,16 @@
 uct %25 10
-)
 %0A%09%09%09%09car
@@ -1241,24 +1241,16 @@
 its%5Bj%5D =
- carry +
  product
@@ -1336,11 +1336,8 @@
 mp%0A%0A
-%0A%09%0A
 %09ret
@@ -1530,16 +1530,48 @@
 ion.'''%0A
+%09#4,782,969%0A%09# 5, 3, 1, 4, 4, 1%0A
 %09print(p
@@ -1585,17 +1585,17 @@
 git_sum(
-9
+2
 , 1000))

Fix carrying on higher N values.