Archive for prime numbers

stochastic magnetic bits, simulated annealing and Gibbs sampling

Posted in Statistics with tags , , , , , , , , , on October 17, 2019 by xi'an

A paper by Borders et al. in the 19 September issue of Nature offers an interesting mix of computing and electronics and optimisation. With two preparatory tribunes! One [rather overdone] on Feynman’s quest. As a possible alternative to quantum computers for creating probabilistic bits. And making machine learning (as an optimisation program) more efficient. And another one explaining more clearly what is in the paper. As well as the practical advantage of the approach over quantum computing. As for the paper itself, the part I understood about factorising an integer F via minimising the squared difference between a product of two integers and F and using simulated annealing sounded rather easy, while the part I did not about constructing a semi-conductor implementing this stochastic search sounded too technical (especially in the métro during rush hour). Even after checking the on-line supplementary material. Interestingly, the paper claims for higher efficiency thanks to asynchronicity than a regular Gibbs simulation of Boltzman machines, quoting Roberts and Sahu (1997) without further explanation and possibly out of context (as the latter is not concerned with optimisation).

Le Monde puzzle [#1105]

Posted in Kids, R with tags , , , , , , on July 8, 2019 by xi'an

Another token game as Le Monde mathematical puzzle:

Archibald and Beatrix play with a pile of n>100 tokens, sequentially picking m tokens from the pile with m being a prime number [including m=1] or a multiple of 6, the winner taking the last tokens. If Beatrix knows n and proposes to Archibald to start, what is the value of n?

Which cannot be solved in a few lines of R code:

k<-function(n)n<4||all(n%%2:ceiling(sqrt(n))!=0)||!n%%6
g=(1:3)
n=c(4,i<-4)
while(max(n)<101){
  if(k(i)) g=c(g,i) else{
  while(i%in%g)i=i+1;j=4;o=!j
  while(!o&(j<i)){ 
    o=(j%in%n)&k(i-j);j=j+1}
  if(o) g=c(g,i) else n=c(n,i)}
  i=i+1}

since it returned no unsuccessful value above 100! With 4, 8, 85, 95, and 99 as predecessors. A rather surprising outcome and a big gap that most certainly has a straightforward explanation! Or a lack of understanding from yours truly: this post appears after the solution was published in Le Monde and I am more bemused than ever since the losing numbers in the journal are given as 4, 8, 85, … 89, and 129. With the slight hiccup that 89 is a prime number…. The other argument in the solution that there can only be five such losers is well-taken since there are only five possible non-zero remainders in the division by 6.

Le Monde puzzle [#1048]

Posted in Books, Kids, R with tags , , , , , on April 1, 2018 by xi'an

An arithmetic Le Monde mathematical puzzle:

A magical integer m is such that the remainder of the division of any prime number p by m is either a prime number or 1. What is the unique magical integer between 25 and 100? And is there any less than 25?

The question is dead easy to code

primz=c(1,generate_primes(2,1e6))
for (y in 25:10000)
  if (min((primz[primz>y]%%y)%in%primz)==1) print(y)

and return m=30 as the only solution. Bon sang but of course!, since 30=2x3x5… (Actually, the result follows by dividing the quotient of the division of a prime number by 2 by 3 and then the resulting quotient by 5: all possible cases produce a remainder that is a prime number.) For the second question, the same code returns 2,3,4,6,8,12,18,24 as further solutions. There is no solution beyond 30.

Le Monde puzzle [#1028]

Posted in Books, Kids with tags , , , on November 16, 2017 by xi'an

Back to standard Le Monde mathematical puzzles (no further competition!), with this arithmetic one:

While n! cannot be a squared integer for n>1, does there exist 1<n<28 such that 28(n!) is a square integer? Does there exist 1<n,m<28 such that 28(n!)(m!) is a square integer? And what is the largest group of distinct integers between 2 and 27 such that the product of 28! by their factorials is a square?

The fact that n! cannot be a square follows from the occurrence of single prime numbers in the resulting prime number decomposition. When considering 28!, there are several single prime numbers like 17, 19, and 23, which means n is at least 23, but then the last prime in the decomposition of 28! being 7 means this prime remains alone in a product by any n! when n<28. However, to keep up with the R resolution tradition, I started by representing all integers between 2 and 28 in terms of their prime decomposition:

primz=c(2,3,5,7,11,13,17,19,23)
dcmpz=matrix(0,28,9)
for (i in 2:28){
 for (j in 1:9){
    k=i
    while (k%%primz[j]==0){ 
      k=k%/%primz[j];dcmpz[i,j]=dcmpz[i,j]+1}}
}

since the prime number factorisation of the factorials n! follows by cumulated sums (over the rows) of dcmpz, after which checking for one term products

fctorz=apply(dcmpz,2,cumsum)
for (i in 23:28)
  if (max((fctorz[28,]+fctorz[i,])%%2)==0) print(i)

and two term products

for (i in 2:28)
for (j in i:27)
 if (max((fctorz[28,]+fctorz[i,]+fctorz[j,])%%2)==0) 
  print(c(i,j))

is easy and produces i=28 [no solution!] in the first case and (i,j)=(10,27) in the second case. For the final question,  adding up to twelve terms together still produced solutions so I opted for the opposite end by removing one term at a time and

for (a in 2:28)
  if (max(apply(fctorz[-a,],2,sum)%%2)==0) print(a)

exhibited a solution for a=14. Meaning that

2! 3! …. 13! 15! …. 28!

is a square.

Le Monde puzzle [#1009]

Posted in Books, Kids with tags , , , , on May 26, 2017 by xi'an

An incomprehensible (and again double) Le Monde mathematical puzzle (despite requests to the authors! The details in brackets are mine.):

  1. A [non-circular] chain of 63 papers clips can be broken into sub-chains by freeing one clip [from both neighbours] at a time. At a given stage, considering the set of the lengths of these sub-chains, the collection of all possible sums of these lengths is a subset of {1,…,63}. What is the minimal number of steps to recover the entire set {1,…,63}?  And what is the maximal length L of a chain of paper clips that allows this recovery in 8 steps?
  2.  A tri-colored chain of 200 paper clips starts with a red, a blue and a green clip. Removing one clip every four clips produces a chain of 50 removed clips identical to the chain of 50 first clips of the original chain and a chain of remaining 150 clips identical to the 150 first clips of the original chain. Deduce the number of green, red, and blue clips.

The first question can be easily tackled by random exploration. Pick one number at random between 1 and 63, and keep picking attached clips until the set of sums is {1,…,63}. For instance,

rebreak0]
 sumz=cumsum(sample(difz))
 for (t in 1:1e3)
  sumz=unique(c(sumz,cumsum(sample(difz))))
 if (length(sumz)<63)
    brkz=rebreak(sort(c(brkz,sample((1:63)[-brkz],1))))
 return(brkz)}

where I used sampling to find the set of all possible partial sums. Which leads to a solution with three steps, at positions 5, 22, and 31. This sounds impossibly small but the corresponding lengths are

1 1 1 4 8 16 32

from which one can indeed recover by summation all numbers till 63=2⁶-1. From there, a solution in 8 steps can be found by directly considering the lengths

1 1 1 1 1 1 1 1 9 18=9+8 36=18+17+1 72 144 288 576 1152 2303

whose total sum is 4607. And with breaks

10 29 66 139 284 573 1150 2303

The second puzzle is completely independent. Running another R code reproducing the constraints leads to

tromcol=function(N=200){
  vale=rep(0,N)
  vale[1:3]=1:3
  while (min(vale)==0){
    vale[4*(1:50)]=vale[1:50]
    vale[-(4*(1:50))]=vale[1:150]}
  return(c(sum(vale==1),sum(vale==2),sum(vale==3)))}

and to 120 red clips, 46 blue clips and 34 green clips.