## another attempt at code golf

Posted in Books, Kids, R with tags , , , on June 12, 2019 by xi'an I had another lazy weekend go at code golf, trying to code in the most condensed way the following task. Provided with a square matrix A of positive integers, keep iterating the steps

• take the highest square $$𝑥²$$ in A.
• find the smallest adjacent neighbour $$𝑛$$
• replace with x and n with nx

until no square is left (with neighbour defined as either horizontally or vertically and without wrapping around). While I managed a 217 bytes solution, compared with Robin’s 179b improvement, which remains surprising readable!, the puzzle offers two further questions:

1. is there a non-iterative way to find the final matrix B?
2. the puzzle assumes that A satisfies that at each step, the highest square and the smallest neighbour n will be unique, and that the sequence will not repeat forever. Is there a fool-proof way to check this is the case?

## an attempt at code golf

Posted in Kids, R with tags , , , , , , , , , on May 15, 2019 by xi'an Having discovered codegolf on Stack Exchange a few weeks ago, I spotted a few interesting puzzles since then but only got the opportunity at a try over a quiet and rainy weekend (and Robin being on vacation)! The challenge was to write an R code for deciding whether or not a given integer n is congruent or not, when congruent means that it is the surface of a rectangle triangle with all three sides rational. The question included a pointer to the Birch and Swinnerton-Dyer conjecture as a mean to check congruence although the real solution was provided by Tunnell’s Theorem, which states that n is congruent if and only if the number of integer solutions to 2x²+y²+8z²=n is twice as much as the number of integer solutions to 2x²+y²+32z²=n if n is odd and  the number of integer solutions to 8x²+y²+16z²=n is twice as much as the number of integer solutions to 8x²+y²+64z²=n if n is even. Although this is only true for squared-free integers. (I actually spent more time on figuring out the exact wording of the theorem than on optimising the R code!)

My original solution

p=function(n){
for (i in(n:2)^2)if(n%%i<1)n=n/i
if(n%%2){d=8;f=2;g=16}else{d=2;f=1;g=8}
A=0;b=(-n:n)^2
for(x in d*b)for(y in x+f*b)for(z in g*b)
A=A+(y+z==n)-2*(y+4*z==n)
A==0}


was quite naïve, as shown by the subsequent improvements by senior players, like the final (?) version of Guiseppe:

function(n){b=(-n:n)^2
for(i in b[b>0])n=n/i^(!n%%i)
P=2^(n%%2)
o=outer
!sum(!o(y<-o(8/P*b,2*b,"+")/P-n,z<-16/P*b,"+"),-2*!o(y,4*z,"+"))}


exhibiting a load of code golf tricks, from using an anonymous function to renaming functions with a single letter, to switching from integers to booleans and back with the exclamation mark.

## Le Monde puzzle [#1083]

Posted in Books, Kids, R, Travel with tags , , , , , , on February 7, 2019 by xi'an A Le Monde mathematical puzzle that seems hard to solve without the backup of a computer (and just simple enough to code on a flight to Montpellier):

Given the number N=2,019, find a decomposition of N as a sum of non-trivial powers of integers such that (a) the number of integers in the sum is maximal or (b) all powers are equal to 4.  Is it possible to write N as a sum of two powers?

It is straightforward to identify all possible terms in these sums by listing all powers of integers less than N

pool=(1:trunc(sqrt(2019)))^2
for (pow in 3:11)
pool=unique(c(pool,(2:trunc(2019^(1/pow)))^pow))


which leads to 57 distinct powers. Sampling at random from this collection at random produces a sum of 21 perfect powers:

 1+4+8+9+16+25+27+32+36+49+64+81+100+121+125+128+144+169+196+243+441

But looking at the 22 smallest numbers in the pool of powers leads to 2019, which is a sure answer. Restricting the terms to powers of 4 leads to the sequence

1⁴+2⁴+3⁴+5⁴+6⁴ = 2019

And starting from the pools of all possible powers in a decomposition of 2019 as the sum of two powers shows this is impossible.

## Le Monde puzzle [#1075]

Posted in Books, Kids, R with tags , , , , on December 12, 2018 by xi'an

Find the largest number such that each of its internal digits is strictly less than the average of its two neighbours. Same question when all digits differ.

For instance, n=96433469 is such a number. When trying pure brute force (with the usual integer2digits function!)

le=solz=3
while (length(solz)>0){
solz=NULL
for (i in (10^(le+1)-1):(9*10^le+9)){
x=as.numeric(strsplit(as.character(i), "")[])
if (min(x[-c(1,le+1)]<(x[-c(1,2)]+x[-c(le,le+1)])/2)==1){ print(i);solz=c(solz,i); break()}}
le=le+1}


this is actually the largest number returned by the R code. There is no solution with 9 digits. Adding an extra condition

le=solz=3
while (length(solz)>0){
solz=NULL
for (i in (10^(le+1)-1):(9*10^le+9)){
x=as.numeric(strsplit(as.character(i), "")[])
if ((min(x[-c(1,le+1)]<(x[-c(1,2)]+x[-c(le,le+1)])/2)==1)&
(length(unique(x))==le+1)){ print(i);solz=c(solz,i); break()}}
le=le+1}


produces n=9520148 (seven digits) as the largest possible integer.

## Le Monde puzzle [#1063]

Posted in Books, Kids, R with tags , , , , , , on August 9, 2018 by xi'an A simple (summertime?!) arithmetic Le Monde mathematical puzzle

1. A “powerful integer” is such that all its prime divisors are at least with multiplicity 2. Are there two powerful integers in a row, i.e. such that both n and n+1 are powerful?
2.  Are there odd integers n such that n² – 1 is a powerful integer ?

The first question can be solved by brute force.  Here is a R code that leads to the solution:

isperfz <- function(n){
divz=primeFactors(n)
facz=unique(divz)
ordz=rep(0,length(facz))
for (i in 1:length(facz))
ordz[i]=sum(divz==facz[i])
return(min(ordz)>1)}

lesperf=NULL
for (t in 4:1e5)
if (isperfz(t)) lesperf=c(lesperf,t)
twinz=lesperf[diff(lesperf)==1]


with solutions 8, 288, 675, 9800, 12167.

The second puzzle means rerunning the code only on integers n²-1…

 8
 288
 675
 9800
 235224
 332928
 1825200
 11309768


except that I cannot exceed n²=10⁸. (The Le Monde puzzles will now stop for a month, just like about everything in France!, and then a new challenge will take place. Stay tuned.)

## seven digit addition

Posted in Kids, R with tags , , , on July 6, 2018 by xi'an

Another quick riddle from the riddler: solve the equation

EXMREEK + EHKREKK = ?K?H?X?E

which involves every digit between 0 and 9. While the puzzle can be unravelled by considering first E and K, which must be equal to 6 and 3, a simple R code also leads to the conclusion

isok <- function(a,b){
s=as.numeric(unlist(strsplit(as.character(sum(10^(6:0)*a)+
sum(10^(6:0)*b)),"")))
if (length(s)==7){ goal=FALSE}else{
goal=(length(unique(c(a,b,s)))==10)&(a==s)&
(s==a)&(s==a)&(b==s)}
return(goal)}

pasok <- function(T=1e3){
for (t in 1:T){
a=a=a=6;a=3
digs=sample(c(0:2,4,5,7:9),4)
a[2:4]=digs[1:3] b=a;b=digs;
b=a;b=a;b=a;b[6:7]=a
if (isok(a=a,b=b))
print(rbind(a,b))}}

> pasok()
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
a    6    2    4    7    6    6    3
b    6    8    3    7    6    3    3


which sum is 13085296.

## Le Monde puzzle [#1018]

Posted in Books, Kids, R with tags , , , , , on August 29, 2017 by xi'an An arithmetic Le Monde mathematical puzzle (that first did not seem to involve R programming because of the large number of digits in the quantity involved):

An integer x with less than 100 digits is such that adding the digit 1 on both sides of x produces the integer 99x.  What are the last nine digits of x? And what are the possible numbers of digits of x?

The integer x satisfies the identity $10^{\omega+2}+10x+1=99x$

where ω is the number of digits of x. This amounts to

10….01 = 89 x,

where there are ω zeros. Working with long integers in R could bring an immediate solution, but I went for a pedestrian version, handling each digit at a time and starting from the final one which is necessarily 9:

#multiply by 9
rap=0;row=NULL
for (i in length(x):1){
prud=rap+x[i]*9
row=c(prud%%10,row)
rap=prud%/%10}
row=c(rap,row)
#multiply by 80
rep=raw=0
for (i in length(x):1){
prud=rep+x[i]*8
raw=c(prud%%10,raw)
rep=prud%/%10}
#find next digit
y=(row+raw+(length(x)>1))%%10


returning

7 9 7 7 5 2 8 0 9


as the (only) last digits of x. The same code can be exploited to check that the complete multiplication produces a number of the form 10….01, hence to deduce that the length of x is either 21 or 65, with solutions

 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 9
 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 8 9 8 8 7 6 4 0 4 4 9 4 3 8 2 0 2 2
 4 7 1 9 1 0 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 9


The maths question behind is to figure out the powers k of 10 such that $10^k\equiv -1 \text{ mod } (89)$

For instance, 10²≡11 mod (89) and 11¹¹≡88 mod (89) leads to the first solution ω=21. And then, since 10⁴⁴≡1 mod (89), ω=21+44=65 is another solution…