## Le Monde puzzle [#29]

Posted in R, Statistics with tags , , on July 29, 2011 by xi'an

This week, the puzzle from the weekend edition of Le Monde was easy to state: in the sequence (8+17n), is there a 6th power? a 7th? an 8th? If so, give the first occurrence. So I first wrote an R code for a function testing whether an integer is any power:

```ispower=function(x){
ispo=FALSE
logx=log(x)
i=trunc(logx/log(2))
while((i>1)&&(!ispo)){
j=t=trunc(exp(logx/i))
while (t<x) t=j*t
ispo=(x==t)
if (!ispo){
j=t=j+1
while (t<x) t=j*t
ispo=(x==t)}
i=i-1}
list(is=ispo,pow=j)}
```

(The function returns the highest possible power.) Then I ran the thing over the first million of values of the sequence:

```fib=8
for (j in 1:10^6){
fib=fib+17
tes=ispower(fib)
if (tes\$is)
print(c(fib,tes\$pow,log(fib)/log(tes\$pow)))}
```

only to find that only the powers 2,3,6,10,11,19 were present among the first terms. Continue reading

## Parallel computation [permutations]

Posted in R, Statistics, University life with tags , , , , on February 20, 2011 by xi'an

François Perron is visiting me for two months from Montréal and, following a discussion about the parallel implementation of MCMC algorithms—to which he also contributed with Yves Atchadé in 2005—, he remarked that a deterministic choice of permutations with the maximal contrast should do better than random or even half-random permutations. Assuming p processors or threads, with p+1 a prime number, his solution is to take element (i,j) of the permutation table as (ij) mod (n+1): here are a few examples

```
> ((1:10)%*%t(1:10))%%11
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    1    2    3    4    5    6    7    8    9    10
[2,]    2    4    6    8   10    1    3    5    7     9
[3,]    3    6    9    1    4    7   10    2    5     8
[4,]    4    8    1    5    9    2    6   10    3     7
[5,]    5   10    4    9    3    8    2    7    1     6
[6,]    6    1    7    2    8    3    9    4   10     5
[7,]    7    3   10    6    2    9    5    1    8     4
[8,]    8    5    2   10    7    4    1    9    6     3
[9,]    9    7    5    3    1   10    8    6    4     2
[10,]   10    9    8    7    6    5    4    3    2     1

> ((1:16)%*%t(1:16))%%17
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,]    1    2    3    4    5    6    7    8    9    10    11
[2,]    2    4    6    8   10   12   14   16    1     3     5
[3,]    3    6    9   12   15    1    4    7   10    13    16
[4,]    4    8   12   16    3    7   11   15    2     6    10
[5,]    5   10   15    3    8   13    1    6   11    16     4
[6,]    6   12    1    7   13    2    8   14    3     9    15
[7,]    7   14    4   11    1    8   15    5   12     2     9
[8,]    8   16    7   15    6   14    5   13    4    12     3
[9,]    9    1   10    2   11    3   12    4   13     5    14
[10,]   10    3   13    6   16    9    2   12    5    15     8
[11,]   11    5   16   10    4   15    9    3   14     8     2
[12,]   12    7    2   14    9    4   16   11    6     1    13
[13,]   13    9    5    1   14   10    6    2   15    11     7
[14,]   14   11    8    5    2   16   13   10    7     4     1
[15,]   15   13   11    9    7    5    3    1   16    14    12
[16,]   16   15   14   13   12   11   10    9    8     7     6
```

which show that the scheme provides an interestingly diverse repartition of the indices. We certainly have to try this in the revision.