Project Euler 16: Power digit sum
Peter Prevos |
341 words | 2 minutes
Share this content
Project Euler 16 is reminiscent of the fable of wheat and chess. Lahur Sessa invented the game of chess for King Iadava. The king was delighted with the game and asked Lahur to name his reward. Lahur asked the king to place one grain of rice on the first square of a chessboard, two on the next square, four on the third square and so on until the board is filled.
The king was happy with his humble request until his mathematicians worked out that it would take millions of tonnes of grain. Assuming there are 25 grains of wheat in a gramme, the last field will contain more than 461,168,602,000 tonnes of grain.
Project Euler 16 Definition
\(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}\)?
Possible Solutions
The most straightforward solution uses the GMP package for Multiple Precision Arithmetic to calculate big integers. The as.bigz() function results in a special class of arbitrarily large integer numbers. To add the digits, the results is converted to a string and split into numbers.
## Project Euler 16: Power digit sum
library(gmp)
digits <- as.bigz(2^1000) # Define number
answer <- sum(as.numeric(unlist(strsplit(as.character(digits), ""))))
print(answer)
We can also solve this problem in base-R with the bigg.add() used for Euler Problem 13. This function uses basic string operations to add to arbitrarily large numbers. Raising a number to the power of two can also be written as a series of additions:
$$2^4 = 2 \times 2 \times 2 \times 2 = ((2+2)+(2+2)) + ((2+2)+(2+2))$$
The solution to this problem is to add 2 + 2 then add the outcome of that equation to itself, and so on. Repeat this one thousand times to raise the number two to the power of one thousand.
## Base-R Method
source("problem013.R", echo = FALSE)
pow <- 2
for (i in 2:1000)
pow <- big.add(pow, pow)
answer <- sum(as.numeric(unlist(strsplit(pow, ""))))
print(answer)Share this content
