Archive for prime factor decomposition

riddle of the seats

Posted in Statistics with tags , , , on November 8, 2019 by xi'an

An arithmetic quick riddle from The Riddler:

If an integer n is a multiple of every integer between 1 and 200, except for two consecutive ones, find those consecutive integers.

Since the highest power of 2 less than 200 is 2⁷=128 and since 127 is a prime number, the number

2^6\times \prod_{i=0,i\ne 63}^{99} (2i+1)

should work in that it contains all odd integers but 127, and all even numbers, but 128. Of course a smaller number that avoids duplicates by only considering the 44 primes other than 127 and 2 to a power that keep them less than 200 is also valid. Which gives a number of the order of 1.037443 10⁸⁵.

missing digit in a 114 digit number [a Riddler’s riddle]

Posted in R, Running, Statistics with tags , , , , , , , on January 31, 2019 by xi'an

A puzzling riddle from The Riddler (as Le Monde had a painful geometry riddle this week): this number with 114 digits

530,131,801,762,787,739,802,889,792,754,109,70?,139,358,547,710,066,257,652,050,346,294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000

is missing one digit and is a product of some of the integers between 2 and 99. By comparison, 76! and 77! have 112 and 114 digits, respectively. While 99! has 156 digits. Using WolframAlpha on-line prime factor decomposition code, I found that only 6 is a possible solution, as any other integer between 0 and 9 included a large prime number in its prime decomposition:

However, I thought anew about it when swimming the next early morning [my current substitute to morning runs] and reasoned that it was not necessary to call a formal calculator as it is reasonably easy to check that this humongous number has to be divisible by 9=3×3 (for else there are not enough terms left to reach 114 digits, checked by lfactorial()… More precisely, 3³³x33! has 53 digits and 99!/3³³x33! 104 digits, less than 114), which means the sum of all digits is divisible by 9, which leads to 6 as the unique solution.

 

Le Monde puzzle [#1063]

Posted in Books, Kids, R with tags , , , , , , on August 9, 2018 by xi'an

lemondapariA 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…

[1] 8
[1] 288
[1] 675
[1] 9800
[1] 235224
[1] 332928
[1] 1825200
[1] 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.)

Le Monde puzzle [#857]

Posted in Books, Kids, R with tags , , , , , , , on March 22, 2014 by xi'an

A rather bland case of Le Monde mathematical puzzle :

Two positive integers x and y are turned into s=x+y and p=xy. If Sarah and Primrose are given S and P, respectively, how can the following dialogue happen?

  • I am sure you cannot find my number
  • Now you told me that, I can, it is 46.

and what are the values of x and y?

In the original version, it was unclear whether or not each person knew she had the sum or the product. Anyway, the first person in the dialogue has to be Sarah, since a product p equal to a prime integer would lead Primrose to figure out x=1 and hence s=p+1. (Conversely, having observed the sum s cannot lead to deduce x and y.) This means x+y-1 is not a prime integer. Now the deduction of Primrose that the sum is 46 implies p can be decomposed only once in a product such that x+y-1 is not a prime integer. If p=45, this is the case since 45=15×3 and 45=5×9 lead to 15+3-1=17 and 5+9-1=13, while 45=45×1 leads to 45+1-1=45.  Other solutions fail, as demonstrated by the R code:

 > for (x in 1:23){
 + fact=c(1,prime.factor(x*(46-x)))
 + u=0;
 + for (i in 1:(length(fact)-1))
 + u=u+1-is.prim(prod(fact[1:i])+prod(fact[-(1:i)])-1)
 + if (u==1) print(x)}
 [1] 1
 

Busser and Cohen argue much more wisely in their solution that any non-prime product p other than 45 would lead to p+1 as an acceptable sum s, hence would prevent Primrose from guessing s.

bug in schoolmath

Posted in R with tags , , , , on June 14, 2010 by xi'an

Neil Gunther has pointed out on his blog that the prime number decomposition R package schoolmath contains mistakes in the function primes, listing 1 as a prime number but also including decomposable numbers like 133 in its list of prime numbers:

> primes(100,140)
[1] 101 107 111 113 123 129 131 137
> primes(50,140)
[1]  51  53  59  61  67  71  73  79  83  89  97 101 103 107 109 113 127 131 133
[20] 137 139
> is.prim(primes(133)
[1] FALSE
> is.prim(primes(200,300))
[1] FALSE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE FALSE TRUE
[13] TRUE TRUE TRUE TRUE TRUE TRUE
> sum(1-is.prim(primes(1,1000)))
[1] 10
> data(primlist)
> sum(1-is.prim(primlist[1:25000]))
[1] 3309

This is rather annoying and I hope it gets quickly fixed!

schoolmath

Posted in R with tags , , , on March 7, 2010 by xi'an

In connection with the Le Monde puzzle of last week, I was looking for an R function that would give me the prime factor decomposition of any integer. Such a function exists within the package schoolmath, developped by Joerg Schlarmann and Josef Wienand. It is called prime.factor and it returns the prime factors of any integer:

> prime.factor(2016)
[1] 2 2 2 2 2 3 3 7
> prime.factor(2032)
[1]   2   2   2   2 127
> prime.factor(2031)
[1]   3 677
> prime.factor(2039)
2039 is a prime!
[1] 2039

Warning [06/14/10]! As pointed out in this blog by Neil Gunther, schoolmath contains mistakes in the function primes, listing 1 as a prime number but also including decomposable numbers like 133.