To celebrate the new year (assuming it is worth celebrating!), Le Monde mathematical puzzle came up with the following:
Two sequences (x¹,x²,…) and (y¹,y²,…) are defined as follows: the current value of x is either the previous value or twice the previous value, while the current value of y is the sum of the values of x up to now. What is the minimum number of steps to reach 2016 or 2017?
By considering that all consecutive powers of 2 must appear at least one, the puzzles boils down to finding the minimal number of replications in the remainder of the year minus the sum of all powers of 2. Which itself boils down to deriving the binary decomposition of that remainder. Hence the basic R code (using intToBits):
[sourcecode language=”r” gutter=”false”]
deco=function(k=2016){
m=trunc(log2(k))
while (sum(2^(0:m))>k) m=m-1
if (sum(2^(0:m))==k){ return(rep(1,m+1))
}else{
res=k-sum(2^(0:m))
return(rep(1,m+1)+as.integer(intToBits(res))[1:(m+1)])
[/sourcecode]
which produces
[sourcecode language=”r” gutter=”false”]
> sum(deco(2016))
[1] 16
> sum(deco(2017))
[1] 16
> sum(deco(1789))
[1] 18
[/sourcecode]
