For a more advanced example, we take the following problem from the ‘Project Euler’ website.
Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:
- 1634 = 1^4 + 6^4 + 3^4 + 4^4
- 8208 = 8^4 + 2^4 + 0^4 + 8^4
- 9474 = 9^4 + 4^4 + 7^4 + 4^4
As 1 = 1^4 is not a sum it is not included.
The sum of these numbers is 1634 + 8208 + 9474 = 19316.
Exercise: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
A bit of thought tells us that there must be an upper bound, above which there are no solutions. Given the fact that 9^5 = 59049, it is possible that there are six figure solutions.
We could also write the inequality n*9^5 >= (10^n) -1 (where the rhs indicates numbers like 9,99,999,9999 etc)
To a degree of approximation we then have:
log n +(5-n)log10 >=0: (using the approximation log9 = log10) which is clearly true up until n=5 but not for n=6 i.e. our solution may contain five 9s but not six. Since 5*59049 is very close to 300,000, the use of 299,999 as an upper limit seems sensible.
Having identified a suitable upper bound, we could solve this problem at this point with some ‘brute force’ code.
But we want to be a bit more elegant, so we press on. Since 2^5 =32, 3^5 =243, 4^5 = 1024 and 5^5 =3125, it is clear, for example, that there are very unlikely to be 2 or 3 digit solutions, given that they could only contain 2s and/or 3s. (322 looks like the only remotely possible one.) At the same time, any five digit solution must contain either at least two, even three 5s, or at least one of something bigger.
It seems like we could also do with not having to calculate fifth powers constantly. Therefore we want to:
- create a vector of fifth powers for checking.
- depending on the size of the number, apply different tests of the digit content.
This is easier if the number is represented as a both a numeric and a string.
Therefore let us cycle through all the numbers up to 299,999, but create a function that checks each one for eligibility as we go.
The (three) arguments will be the vector of powers, and both string and numeric representations of each number.
Input:
#beginning of function definition, three arguments are the vector of digit powers, and the test number in two forms.
fifth_power_sums<-function(powers,n_as_string, n_as_integer){
suitable<-0
if(n_as_integer<1024){
result1<-sapply("4", function(x) length(grep(x,n_as_string)),USE.NAMES =FALSE) #we don't want small numbers with 4s in
if(result1==1){
suitable<-0
}else {
suitable<-1
}
}else{
suitable<-1
}
null_vector<-rep(0,5)
test_vector10000) {
result2<-sapply(test_vector, function(x) length(grep(x,n_as_string)),USE.NAMES=FALSE) #checks all of test vector against the number
if(all.equal(result2,null_vector)==1){
suitable<-0
}else {
suitable<-1
}
}
return(suitable)
} #end of function definition and start of function call code.
power<- 5 #we could set this to 4 to check our code, with suitable modifications to the conditions.
powers<-vapply(seq(1,9),function(x) x^power,numeric(1))
for (i in 12222:12235) {
instance<-fifth_power_sums(powers,toString(i), i)#function call. The variable 'instance' receives the value of 'suitable'
if(instance==1){
cat(i, "is a suitable number")
#here we want to calculate the relevant sum for any suitable number
#we can look up the entries of powers for this purpose
}else{
cat(i, "failed the tests. Move on!")#move straight to the next number in the loop
}
}
Output:
12222 failed the tests. Move on!12223 failed the tests. Move on!12224 failed the tests. Move on!12225 is a suitable number12226 is a suitable number12227 is a suitable number12228 is a suitable number12229 is a suitable number12230 failed the tests. Move on!12231 failed the tests. Move on!12232 failed the tests. Move on!12233 failed the tests. Move on!12234 failed the tests. Move on!12235 is a suitable number
We now have a workable function to which we could apply some code to do the calculations on the relevant numbers. This would involve breaking the test number into its digits. There are fundamentally two ways of doing this, one is to represent it as a string and take it apart, and then convert the characters to numbers. The other way is to treat it as a number, breaking it down arithmetically by e.g. division mod 10 and subtracting the result.
Another sophistication would be to expand the small number sieve, by
- testing for digits greater than 4
- Relate the range of digits tested for to the size of the integer. We don't want to bother with 2015, for example. One way to do this would be to incorporate the integer itself into the power vector and sort the resulting vector by size. The code in the first set of if statements could then be related both to the vector position of the number, and the entry immediately above it. Alternatively, we might use the append function to place the value in the correct part of the vector.
R for healthcare 