Archive for prime numbers

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.

Le Monde puzzle [#1008]

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

An arithmetic Le Monde mathematical puzzle (or two independent ones, rather):

  1. The set of integers between 1 and 2341 is partitioned into sets such that a given set never contains both n and 3n. What is the largest possible size of one of these sets?
  2.  Numbers between 1 and 2N are separated in two sets A and B of size N. Alice takes the largest element out of A and the smallest element out of B, records the absolute difference as S, and then repeats the sampling, adding the absolute difference to S at each draw. Bob does the same with numbers between 1 and 2P, with P<N, obtaining a total value of R. Alice points out that S-R=2341. What are the values of N and P?

The first question seems hard to solve by brute force simulation. My first idea is to take all prime numbers [except 3!] less than 2341, which is itself a prime number, and all combinations of these numbers less than 2341, since none of those is divisible by 3. Adding 3 as a final item keeps the constraint fine if 1 is not part of it (but 1 is not a prime number, so this is under control). Adding instead 1 to the set has the same impact but seems more natural. The number of prime numbers is 346, while the total size of the set thus constructed is 1561. Equal to 1+2×2340/3. However, the constraint in the puzzle does not exclude m and 9m. Or m and 9²m, or m and 9³m. Considering such multiples within {1,…,2341} leads to a set with 1765 integers.

The second puzzle is indeed independent and actually straightforward when one realises that the sums S and R are always equal to N² and P², respectively. (This is easily proven by invariance under a permutation turning the lowest entries to B and the largest ones to A. But there must be a rank statistic identity behind this result!) Hence it boils down to figuring out a pair (N,P) such that N²-P²=2341. Since 2341=(N-P)(N+P) is prime, this implies N=P+1. And N²-(N-1)²=N²-N²+2N-1=2341. Which leads to (N,P)=(1171,1170) as the only solution.

randomness in coin tosses and last digits of prime numbers

Posted in Books, Kids, R, Statistics, University life with tags , , , on October 7, 2014 by xi'an

A rather intriguing note that was arXived last week: it is essentially one page long and it compares the power law of the frequency range for the Bernoulli experiment with the power law of the frequency range for the distribution of the last digits of the first 10,000 prime numbers to conclude that the power is about the same. With a very long introduction about the nature of randomness that is unrelated with the experiment. And a call to a virtual coin toss website, instead of using R uniform generator… Actually the exact distribution is available, at least asymptotically, for the Bernoulli (coin tossing) case. Among other curiosities, a constant typo in the sign of the coefficient β for the power law. A limitation of the Bernoulli experiment to 10⁴ simulations, rather than the 10⁵ used for the prime numbers. And a conclusion that the distribution of the end digits is truly uniform which relates only to this single experiment!

Le Monde puzzle [#840]

Posted in Books, Kids, R with tags , , , , on November 23, 2013 by xi'an

Another number theory Le Monde mathematical puzzles:

Find 2≤n≤50 such that the sequence {1,…,n} can be permuted into a sequence such that the sum of two consecutive terms is a prime number. 

Now this is a problem with an R code solution:

library(pracma)
foundsol=TRUE
N=2
while (foundsol){

  N=N+1
  noseq=TRUE
  uplim=10^6
  t=0
  while ((t<uplim)&&(noseq)){

    randseq=sample(1:N)
    sumseq=randseq[-1]+randseq[-N]
    noseq=min(isprime(sumseq))==0
    t=t+1
    }

  foundsol=!noseq
  if (!noseq){
   lastsol=randseq}else{ N=N-1}
  }

which returns the solution as

> N
[1] 12
> lastsol
 [1]  6  7 12 11  8  5  2  1  4  3 10  9

and so it seems there is no solution beyond N=12…

However, reading the solution in the next edition of Le Monde, the authors claim there are solutions up to 50. I wonder why the crude search above fails so suddenly, between 12 and 13! So instead I tried a recursive program that exploits the fact that subchains are also verifying  the same property:

findord=function(ens){

  if (length(ens)==2){
    sol=ens
    foundsol=isprime(sum(ens))}
  else{
    but=sample(ens,1)
    nut=findord(ens[ens!=but])
    foundsol=FALSE
    sol=ens
    if (nut$find){
      tut=nut$ord
      foundsol=max(isprime(but+tut[1]),
         isprime(but+tut[length(tut)]))
      sol=c(tut,but)
      if (isprime(but+tut[1]))
         sol=c(but,tut)
      }
  }
  list(find=foundsol,ord=sol)
}

And I ran the R code for N=13,14,…

> stop=TRUE
> while (stop){
+   a=findord(1:N)
+   stop=!(a$find)}

until I reached N=20 for which the R code would not return a solution. Maybe the next step would be to store solutions in N before moving to N+1. This is just getting  me too far from a mere Saturday afternoon break.

Le Monde puzzle [#820]

Posted in Books, Kids, R with tags , , , , , on May 15, 2013 by xi'an

The current puzzle is… puzzling:

Given the set {1,…,N} with N<61, one iterates the following procedure: take (x,y) within the set and replace the pair with the smallest divider of x+y (bar 1). What are the values of N such that the final value in the set is 61?

I find it puzzling because the way the pairs are selected impacts the final value. Or not, depending upon N. Using the following code (with factors() from the pracma package):

library(pracma)
endof=function(N){
  coll=1:N
  for (t in 1:(N-1)){

    pair=sample(1:length(coll),2)
    dive=min(factors(sum(coll[pair])))
    coll=coll[-pair]
    coll=c(coll,dive)
    }
  print(dive)
  }

I got:

> for (t in 1:10) endof(10)
[1] 5
[1] 3
[1] 3
[1] 5
[1] 7
[1] 5
[1] 5
[1] 7
[1] 3
[1] 3> for (t in 1:10) endof(16)
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2

For N of the form 4k or 4k-1, the final number is always 2 while for N‘s of the form 4k-2 and 4k-3, the final number varies, sometimes producing 61’s. Although I could not find solutions for N less than 17…  Looking more closely into the sequence leading to 61, I could not see a pattern, apart from producing prime numbers as, in, e.g.

61 = 2 + [12 +  (4 + {14 + [13 + 16]})]

for N=17.  (Another puzzle is that 61 plays no particular role: a long run of random calls to endof() return all prime numbers up to 79…)

Udate: Looking at the solution in today’s edition, there exist a solution for N=13 and a solution for N=14. Even though my R code fails to spot it. Of course, an exhaustive search would be feasible in these two cases.  (I had also eliminated values below as not summing up to 61.) The argument for eliminating 4k and 4k-1 is that there must be an odd number of odd numbers in the collection, otherwise, the final number is always 2.

odd prime numbers

Posted in Books with tags , , , , on February 9, 2013 by xi'an

Just read a puzzling fact in Le Monde science leaflet: someone at the “Great Internet Mersenne Prime Search” (GIMPS) just found a prime number with 17 million digits and…it is the 48th prime number of the form 2p-1. Which just means it is an odd number. How odd a remark!!! And how wrong. In fact, the short news item meant that this is a Mersenne number, of the form 2p-1! Another victim of a hasty cut&paste, I presume…