Problem 5: smallest positive number divisible by all of the numbers from 1 to 20

[ghost]

Using the maxima of the powers of prime factors dividing the numbers from 1 to 20 mySolution.

[mverbist]

and here's a one-liner:

    (1 to 20).map(primeFactors(_)).reduce((D1, D2) => D1 ++ D2.diff(D1)).product

It uses the explanation with the prime numbers, given in the problem statement.
So, the first map yields this Vector of Vectors

1   =>   (1)
2   =>   (1, 2)
3   =>   (1, 3)
4   =>   (1, 2, 2)
5   =>   (1, 5)
6   =>   (1, 2, 3)

Then we reduce it, adding up the different Vectors, but we only add the elements of the next Vector, that are not yet present in the previous result Vector:

(1) + (1, 2)   => (1, 2)    // because '1' is already present in the previous
(1, 2) + (1, 3)   => (1, 2, 3)    // because '1' is already present in the previous
(1, 2, 3) + (1, 2, 2)   => (1, 2, 2, 3)    // because '1' and one of the '2's is already present in the previous
(1, 2, 2, 3) + (1, 5)   => (1, 2, 2, 3, 5)    // because '1' is already present in the previous

and so on.
At the end, we take the product

[mverbist]

And here's an other solution, that doesn't use the prime numbers explanation, given in the problem statement.
It uses the exact problem definition to find the solution, but it takes way longer to find it.
The number we seek, has to be divisible by all numbers from 1 to 20.

It uses a function isDivisibleBy which takes 2 parameters with currying.
We then partially apply that, to create a sequence of functions :

(isDivisibleBy(1), isDivisibleBy(2), .., isDivisibleBy(20)) 

Then we filter a Stream of dividends with all of these functions, so we are sure that the numbers in the stream are divisible by all the numbers from 1 .. 20
Then we take the first, which should be the smallest.

[jamiephillips0000]

I solved it this way - maybe not the fanciest but it works.
Strange thing is if I don't mark the method testMultimplesOf20 as FINAL i get a stack overflow. Any idea why?

final def testMultimplesOf20(magicNumber : Int,
              nrsToDivBy : List[Int], multiplicationFactor : Int): Int = {
  if(nrsToDivBy.filter(x => magicNumber%x == 0).size == nrsToDivBy.size) {
    magicNumber
  } else {
    testMultimplesOf20(20*multiplicationFactor, nrsToDivBy, multiplicationFactor+1)
  }
}
euler(problem(5)) {
  testMultimplesOf20(20, List.range(2, 21), 1)
}

[eloots]

Hi Jamie,

If you move testMultimplesOf20 to the scope of your specific test such as follows:

euler(problem(5), "jamie") {

def testMultimplesOf20(magicNumber : Int, nrsToDivBy : List[Int], multiplicationFactor : Int): Int = {
  if(nrsToDivBy.filter(x => magicNumber%x == 0).size == nrsToDivBy.size){
    magicNumber
  }else{
    testMultimplesOf20(20*multiplicationFactor, nrsToDivBy, multiplicationFactor+1)
  }
}

testMultimplesOf20(20, List.range(2, 21), 1)

}

… all is well, compiles and doesn’t produce a stack overflow. Must have something to do with moving testMultimplesOf20 out of the higher scope. Haven’t figured out why this is.

When you leave testMultimplesOf20 in the location where you put it and add @annotation.tailrec just in front of it, the following compilation error message is produced:

[error] /Users/ericloots/Dropbox/Scala/ScalaCronosBlogs/EulerHackingSession/project-euler/src/test/scala/org/bescala/projecteuler/problems/Problem005.scala:96: could not optimize @tailrec annotated method testMultimplesOf20: it is neither private nor final so can be overridden
[error] def testMultimplesOf20(magicNumber : Int, nrsToDivBy : List[Int], multiplicationFactor : Int): Int = {
[error] ^
[error] one error found
error Compilation failed
[error] Total time: 1 s, completed 1-dec-2014 12:30:16

Guess that this is linked in some way to the stack overflow problem...

Haven’t understood how your solution work :-) but it seems to work (except that it’s quite slow :-)

You may wish to label your solutions as marked in red above. In this way you can easily play with different versions.

Regards, Eric

On 30-nov.-2014, at 22:13, Jamie Phillips [email protected] wrote:

I solved it this way - maybe not the fanciest but it works.
Strange thing is if I don't mark the method testMultimplesOf20 as FINAL i get a stack overflow. Any idea why?

final def testMultimplesOf20(magicNumber : Int, nrsToDivBy : List[Int], multiplicationFactor : Int): Int = {
if(nrsToDivBy.filter(x => magicNumber%x == 0).size == nrsToDivBy.size){
magicNumber
}else{
testMultimplesOf20(20*multiplicationFactor, nrsToDivBy, multiplicationFactor+1)
}
}
euler(problem(5)) {
testMultimplesOf20(20, List.range(2, 21), 1)
}

—
Reply to this email directly or view it on GitHub #10 (comment).

[jamiephillips0000]

Hi Eric
Thanks for the repy

1. I was aware that I could move it to the scope of the euler test - but I was interested in the failure because I could not explain it. I also tried annotating it with the same error.
2. The solution is based on the brute-force way. Keep trying with successive multiples of 20 until all numbers divide into it with no remainder. I am aware it is not fast ;-)
   Jamie

[samdebacker]

@jamiephillips0000 It stack overflows because, well, it stack overflows. Although the method is tail recursive, the computer cannot optimise it to a while loop, because the method can potentially be overriden in a subclass. So the compiler doesn't generate a loop but just generates recursive calls. And each function call consumes some stack memory at run time. Making it final, or define it inside a block, the compiler is sure it cannot be overriden and hence can optimise it to an iteration. And it happens that this solution generates a very deep recursion, so deep the stack overflows... You could experiment with a JVM option to allow a bigger stack, but in general it sounds like a not the best option. Making it final or turning it into a nested (unoverridable) function is better.

[jamiephillips0000]

Take a bow Sam de Becker!! ;-)
Thanks for the explanation - makes sense

[octonato]

What is happening is that you can't do tail recursive optimization on methods that can be overridden. The compiler will not optimize it and you get a stack overflow because you are indeed building a deep stack.

[octonato]

@samdebacker does gave a much detailed explanation!
+1 for @samdebacker

[eloots]

The pencil and paper solution

2L * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19

and 3 generic solutions (1, 2 and 3 ) using encode and pack functions from the package object

I show intermediate values of the calculation in comment in the first two implementations.

Maybe useful for some: note the distribution of steps over multiple lines. In this way you can avoid one-liners that require horizontal scrolling ;-) -and- you create an opportunity to document/annotate the intermediate steps/results.

Note that solution 3 is a simplification of solution 1. I realized that the simplification was possible after reading the explanation by Michel Verbist of his generic solution.

[ghost]

Hi, @mverbist,

your solution is essentially the same as mine

I use factorizeAllNumbersTo and end with a one-liner
You use primeFactors and end with a one-liner

my algorithm reduces an intermediate vector of vectors:

Vector(
Vector(2, 1, 1, 1, 1, 1, 1, 1),
Vector(1, 3, 1, 1, 1, 1, 1, 1),
Vector(4, 1, 1, 1, 1, 1, 1, 1),
Vector(1, 1, 5, 1, 1, 1, 1, 1),
Vector(2, 3, 1, 1, 1, 1, 1, 1),
Vector(1, 1, 1, 7, 1, 1, 1, 1),
Vector(8, 1, 1, 1, 1, 1, 1, 1),
Vector(1, 9, 1, 1, 1, 1, 1, 1),
Vector(2, 1, 5, 1, 1, 1, 1, 1),
Vector(1, 1, 1, 1, 11, 1, 1, 1),
Vector(4, 3, 1, 1, 1, 1, 1, 1),
Vector(1, 1, 1, 1, 1, 13, 1, 1),
Vector(2, 1, 1, 7, 1, 1, 1, 1),
Vector(1, 3, 5, 1, 1, 1, 1, 1),
Vector(16, 1, 1, 1, 1, 1, 1, 1),
Vector(1, 1, 1, 1, 1, 1, 17, 1),
Vector(2, 9, 1, 1, 1, 1, 1, 1),
Vector(1, 1, 1, 1, 1, 1, 1, 19),
Vector(4, 1, 5, 1, 1, 1, 1, 1)
)

to

Vector(16, 9, 5, 7, 11, 13, 17, 19)

using max

Cheers

Luc

[patvarilly]

Following up on the comments in the last meet-up and posts here, I came up with an explicit example of why the compiler can't optimise the tail recursion in a method that's not final. Take a look at this snippet:

class A {
def notReallyTailRec(n: Int): Int = {
if (n == 0)
0
else {
println("In A: "+ n)
notReallyTailRec(n - 1)
}
}
}

class B extends A {
override def notReallyTailRec(n: Int): Int = {
if (n == 0)
0
else {
println("In B: "+ n)
super.notReallyTailRec(n - 1)
}
}
}

println((new B).notReallyTailRec(5))

If you run it in the REPL, you'll get this output:

In B: 5
In A: 4
In B: 3
In A: 2
In B: 1
0

As you can see, you really can arrange for the method A.notReallyTailRec() to call an overridden implementation in a subclass.

[octonato]

This morning I published the code from the last session. Here goes the comments related to Problem005.

I decided to keep it in separated commits so one can see and analyse the evolution of the code.

The first commit labelled "Problem005" only adds the solutions as proposed by Vincent, Michel and Luc.

Next there are 4 commits prefixed with "P005".

P005: removing unnecessary refs to immutable vals
In which we remove vals that are not modified in the loops and therefore can reference the original method parameter

P005: using default values
We replace the named parameter 'b', by a default value. The goal here was to illustrate another way of achieving the same. It's a better of taste, choose the one you prefer.

P005: extracting boolean from the mix and using pattern matching
In this commit the 'b' flag is renamed to 'isDivisible' and we try to remove it from the computation and use it as pure guard clause.

The main code inside isDivisbleAcc is replaced by a pattern matching on the list of 'dividends'. The goal was to show how we can pattern matching on a List.
This style is particular interesting, IMO, when we want to separate the head and the tail of a List. Is such situation we often have the case where we must split 'head' and 'tail' and the case where the List is empty.

P005: making it tailrec
In which we make the call tailrec.
NOTE: to make isDivisible method tailrec we must bring the boolean 'isDivisible' back to inside the pattern matching.