Archive for int2bits

Fermat’s Riddle

Posted in Books, Kids, R with tags , , , , , , , , , , on October 16, 2020 by xi'an

·A Fermat-like riddle from the Riddler (with enough room to code on the margin)

An  arbitrary positive integer N is to be written as a difference of two distinct positive integers. What are the impossible cases and else can you provide a list of all distinct representations?

Since the problem amounts to finding a>b>0 such that

N=a^2-b^2=(a-b)(a+b)

both (a+b) and (a-b) are products of some of the prime factors in the decomposition of N and both terms must have the same parity for the average a to be an integer. This eliminates decompositions with a single prime factor 2 (and N=1). For other cases, the following R code (which I could not deposit on tio.run because of the packages R.utils!) returns a list

library(R.utils)
library(numbers)
bitz<-function(i,m) #int2bits
  c(rev(as.binary(i)),rep(0,m))[1:m]
ridl=function(n){
a=primeFactors(n)
if((n==1)|(sum(a==2)==1)){
  print("impossible")}else{
  m=length(a);g=NULL
  for(i in 1:2^m){
    b=bitz(i,m)
    if(((d<-prod(a[!!b]))%%2==(e<-prod(a[!b]))%%2)&(d<e))
      g=rbind(g,c(k<-(e+d)/2,l<-(e-d)/2))}
  return(g[!duplicated(g[,1]-g[,2]),])}}

For instance,

> ridl(1456)
     [,1] [,2]
[1,]  365  363
[2,]  184  180
[3,]   95   87
[4,]   59   45
[5,]   40   12
[6,]   41   15

Checking for the most prolific N, up to 10⁶, I found that N=6720=2⁶·3·5·7 produces 20 different decompositions. And that N=887,040=2⁸·3²·5·7·11 leads to 84 distinct differences of squares.

Le Monde puzzle [#1076]

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

A cheezy Le Monde mathematical puzzle : (which took me much longer to find [in the sense of locating] than to solve, as Warwick U does not get a daily delivery of the newspaper [and this is pre-Brexit!]):

Take a round pizza (or a wheel of Gruyère) cut into seven identical slices and turn one slice upside down. If the only possibly moves are to turn three connected slices to their reverse side, how many moves at least are needed to recover the original configuration? What is the starting configuration that requires the largest number of moves?

Since there are ony N=2⁷ possible configurations, a brute force exploration is achievable, starting from the perfect configuration requiring zero move and adding all configurations found by one additional move at a time… Until all configurations have been visited and all associated numbers of steps are stable. Here is my R implementation

nztr=lengz=rep(-1,N) #length & ancestor
nztr[0+1]=lengz[0+1]=0 
fundz=matrix(0,Z,Z) #Z=7
for (i in 1:Z){ #only possible moves
  fundz[i,c(i,(i+1)%%Z+Z*(i==(Z-1)),(i+2)%%Z+Z*(i==(Z-2)))]=1
  lengz[bit2int(fundz[i,])+1]=1
  nztr[bit2int(fundz[i,])+1]=0}
while (min(lengz)==-1){ #second loop omitted
  for (j in (1:N)[lengz>-1])
  for (k in 1:Z){
    m=bit2int((int2bit(j-1)+fundz[k,])%%2)+1
    if ((lengz[m]==-1)|(lengz[m]>lengz[j]+1)){
      lengz[m]=lengz[j]+1;nztr[m]=j}
      }}

Which produces a path of length five returning (1,0,0,0,0,0,0) to the original state:

> nztry(2)
[1] 1 0 0 0 0 0 0
[1] 0 1 1 0 0 0 0
[1] 0 1 0 1 1 0 0
[1] 0 1 0 0 0 1 0
[1] 1 1 0 0 0 0 1
[1] 0 0 0 0 0 0 0

and a path of length seven in the worst case:

> nztry(2^7)
[1] 1 1 1 1 1 1 1
[1] 1 1 1 1 0 0 0
[1] 1 0 0 0 0 0 0
[1] 0 1 1 0 0 0 0
[1] 0 1 0 1 1 0 0
[1] 0 1 0 0 0 1 0
[1] 1 1 0 0 0 0 1
[1] 0 0 0 0 0 0 0

Since the R code was written for an arbitrary number Z of slices, I checked that there is no solution for Z being a multiple of 3.