## Le Monde puzzle [#919]

Posted in Books, Kids, Statistics, University life with tags , , , , on July 19, 2015 by xi'an A rather straightforward Le Monde mathematical puzzle:

Find 3 digit integers x such that the integer created by collating x with (x+1) gives a 6 digit integer that is a perfect square.

Easy once you rewrite the constraint as 1000x+x+1 being a perfect square a², which means that x is equal to (a-1)(a+1)/1001, hence that 1001=7x11x13 divides either a+1 or a=1.

sol=NULL
vals=as.vector(outer(c(7,11,13),1:999,"*"))
vals=c(vals-1,vals+1)
for (a in vals){
x=round((a-1)*(a+1)/1001)
if ((1000*x+x+1==a^2)&(x<999)&(x>99)) sol=c(sol,x)}


which returns four solutions:

> unique(sol)
 183 328 528 715


An addendum to the puzzle is

Find 4 digit integers x such that the integer created by collating x with (x+1) gives an 8 digit integrer that is a perfect square.

Similarly easy once you rewrite the constraint as 10,000x+x+1 being a perfect square a², which means that x is equal to (a-1)(a+1)/10,001, hence that 10,001=73×137 divides either a+1 or a=1.

sol=NULL
vals=as.vector(outer(c(73,137),(1:9999),"*"))
vals=c(vals-1,vals+1)
for (a in vals){
x=round((a-1)*(a+1)/10001)
if ((10000*x+x+1==a^2)&(x<9999)&(x>999)) sol=c(sol,x)}


leading to the conclusion there is a single solution:

> unique(sol)
 6099


## Le Monde puzzle [#899]

Posted in Books, Kids, Statistics, University life with tags , , , , , on February 8, 2015 by xi'an An arithmetics Le Monde mathematical puzzle:

For which n’s are the averages of the first n squared integers integers? Among those, which ones are perfect squares?

An easy R code, for instance

n=10^3
car=as.integer(as.integer(1:n)^2)
sumcar=as.integer((cumsum(car)%/%as.integer(1:n)))
diff=as.integer(as.integer(cumsum(car))-as.integer(1:n)*sumcar)
print((1:n)[diff==00])


which produces 333 values

     1   5   7  11  13  17  19  23  25  29  31  35  37  41  43  47  49  53
  55  59  61  65  67  71  73  77  79  83  85  89  91  95  97 101 103 107
 109 113 115 119 121 125 127 131 133 137 139 143 145 149 151 155 157 161
 163 167 169 173 175 179 181 185 187 191 193 197 199 203 205 209 211 215
 217 221 223 227 229 233 235 239 241 245 247 251 253 257 259 263 265 269
 271 275 277 281 283 287 289 293 295 299 301 305 307 311 313 317 319 323
 325 329 331 335 337 341 343 347 349 353 355 359 361 365 367 371 373 377
 379 383 385 389 391 395 397 401 403 407 409 413 415 419 421 425 427 431
 433 437 439 443 445 449 451 455 457 461 463 467 469 473 475 479 481 485
 487 491 493 497 499 503 505 509 511 515 517 521 523 527 529 533 535 539
 541 545 547 551 553 557 559 563 565 569 571 575 577 581 583 587 589 593
 595 599 601 605 607 611 613 617 619 623 625 629 631 635 637 641 643 647
 649 653 655 659 661 665 667 671 673 677 679 683 685 689 691 695 697 701
 703 707 709 713 715 719 721 725 727 731 733 737 739 743 745 749 751 755
 757 761 763 767 769 773 775 779 781 785 787 791 793 797 799 803 805 809
 811 815 817 821 823 827 829 833 835 839 841 845 847 851 853 857 859 863
 865 869 871 875 877 881 883 887 889 893 895 899 901 905 907 911 913 917
 919 923 925 929 931 935 937 941 943 947 949 953 955 959 961 965 967 971
 973 977 979 983 985 989 991 995 997


which are made of all odd integers that are not multiple of 3. (I could have guessed the exclusion of even numbers since the numerator is always odd. Why are the triplets excluded, now?! Jean-Louis Fouley gave me the answer: the sum of squares is such that $\frac{1+2^2+\cdots+m^2}{m}=\frac{m(m+1)(2m+1)}{6m}=\frac{(m+1)(2m+1)}{6}$

and hence m must be odd and 2m+1 a multiple of 3, which excludes multiples of 3.)

sole=sumcar[(1:n)[diff==0]]
scar=as.integer(as.integer(sqrt(sole))^2)-sole
sum(scar==0)


with the final result

> sum(scar==0)
 2
> ((1:n)[diff==0])[scar==0]
 1 337


since  38025=195² is a perfect square. (I wonder if there is a plain explanation for that result!)

## Le Monde puzzle [#887]

Posted in Books, Kids, R, Statistics with tags , , , on November 15, 2014 by xi'an A simple combinatorics Le Monde mathematical puzzle:

N is a golden number if the sequence {1,2,…,N} can be reordered so that the sum of any consecutive pair is a perfect square. What are the golden numbers between 1 and 25?

Indeed, from an R programming point of view, all I have to do is to go over all possible permutations of {1,2,..,N} until one works or until I have exhausted all possible permutations for a given N. However, 25!=10²⁵ is a wee bit too large… Instead, I resorted once again to brute force simulation, by first introducing possible neighbours of the integers

  perfect=(1:trunc(sqrt(2*N)))^2
friends=NULL
le=1:N
for (perm in 1:N){
amis=perfect[perfect>perm]-perm
amis=amis[amis<N]
le[perm]=length(amis)
friends=c(friends,list(amis))
}


and then proceeding to construct the permutation one integer at time by picking from its remaining potential neighbours until there is none left or the sequence is complete

orderin=0*(1:N)
t=1
orderin=sample((1:N),1)
for (perm in 1:N){
friends[[perm]]=friends[[perm]]
[friends[[perm]]!=orderin]
le[perm]=length(friends[[perm]])
}
while (t<N){
if (length(friends[[orderin[t]]])==0)
break()
if (length(friends[[orderin[t]]])>1){
orderin[t+1]=sample(friends[[orderin[t]]],1)}else{
orderin[t+1]=friends[[orderin[t]]]
}
for (perm in 1:N){
friends[[perm]]=friends[[perm]]
[friends[[perm]]!=orderin[t+1]]
le[perm]=length(friends[[perm]])
}
t=t+1}


and then repeating this attempt until a full sequence is produced or a certain number of failed attempts has been reached. I gained in efficiency by proposing a second completion on the left of the first integer once a break occurs:

while (t<N){
if (length(friends[[orderin]])==0)
break()
orderin[2:(t+1)]=orderin[1:t]
if (length(friends[[orderin]])>1){
orderin=sample(friends[[orderin]],1)}else{
orderin=friends[[orderin]]
}
for (perm in 1:N){
friends[[perm]]=friends[[perm]]
[friends[[perm]]!=orderin]
le[perm]=length(friends[[perm]])
}
t=t+1}


(An alternative would have been to complete left and right by squared numbers taken at random…) The result of running this program showed there exist permutations with the above property for N=15,16,17,23,25,26,…,77.  Here is the solution for N=49:

25 39 10 26 38 43 21 4 32 49 15 34 30 6 3 22 42 7 9 27 37 12 13 23 41 40 24 1 8 28 36 45 19 17 47 2 14 11 5 44 20 29 35 46 18 31 33 16 48

As an aside, the authors of Le Monde puzzle pretended (in Tuesday, Nov. 12, edition) that there was no solution for N=23, while this sequence

22 3 1 8 17 19 6 10 15 21 4 12 13 23 2 14 11 5 20 16 9 7 18

sounds fine enough to me… I more generally wonder at the general principle behind the existence of such sequences. It sounds quite probable that they exist for N>24. (The published solution does not bring any light on this issue, so I assume the authors have no mathematical analysis to provide.)