# Le Monde puzzle [#29]

July 28, 2011
By

[This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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
(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. Then I started thinking rather than (merely and merrily) programming and realised that the terms of the sequence were all congruential to 8 modulo 17, hence that a power of 6, 7 or 8, also had to be congruencial to 8 if it was part of the sequence. Since $z^a\text{mod}\,17 = (z\text{mod}\,17)^a\text{mod}\,17\,,$$z^a\text{mod}\,17 = (z\text{mod}\,17)^a\text{mod}\,17\,,$ there is no solution in z if, for a given power a, all integers between 1 and 16 are not congruential to 8 modulo 17. Here is the check: > ((1:16)^6)%%17 [1] 1 13 15 16 2 8 9 4 4 9 8 2 16 15 13 1 > ((1:16)^7)%%17 [1] 1 9 11 13 10 14 12 15 2 5 3 7 4 6 8 16 > ((1:16)^8)%%17 [1] 1 1 16 1 16 16 16 1 1 16 16 16 1 16 1 1 so this eliminates the power 8 (as well as 4 and 12), but not the power 7… Now, the check for the power 7 tells us the value of z is congruencial to 15 modulo 17, hence that the term of the sequence is equal to 1517, 3217 or even more. This explains why I could not see any power equal to 7 in the first million trials. We are nonetheless lucky in that the first trial works: > 15^7 [1] 170859375 > (170859375-8)/17 [1] 10050551 > 8+10050551*17-170859375 [1] 0 > ispower(8+10050551*17)$is
[1] TRUE

$pow [1] 15 For the power 6, the value of z is congruencial to 6 modulo 17, hence the term of the sequence is equal to 66, 236 or even more. We again are lucky in that the first trial works: > ispower(8+2744*17)$is
[1] TRUE

\$pow
[1] 6

Filed under: R, Statistics Tagged: congruence, prime number, R

var vglnk = { key: '949efb41171ac6ec1bf7f206d57e90b8' };

(function(d, t) {
var s = d.createElement(t); s.type = 'text/javascript'; s.async = true;
s.src = '//cdn.viglink.com/api/vglnk.js';
var r = d.getElementsByTagName(t)[0]; r.parentNode.insertBefore(s, r);
}(document, 'script'));

Related
ShareTweet

To leave a comment for the author, please follow the link and comment on their blog:  Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or  here if you don't.

If you got this far, why not subscribe for updates from the site?  Choose your flavor: e-mail, twitter, RSS, or facebook...
Tags: congruence, prime number, R, statistics

Comments are closed.

# Never miss an update! Subscribe to R-bloggers to receive e-mails with the latest R posts.(You will not see this message again.)

Click here to close (This popup will not appear again)