Archive for congruence

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.

Follow

Get every new post delivered to your Inbox.

Join 673 other followers