Skip to content

Instantly share code, notes, and snippets.

@GlulkAlex

GlulkAlex/Least_common_multiple.ipynb

Last active June 3, 2016 17:41
Show Gist options
  • Save GlulkAlex/3ef9d0ed32250192e6dc436662d1e125 to your computer and use it in GitHub Desktop.
Save GlulkAlex/3ef9d0ed32250192e6dc436662d1e125 to your computer and use it in GitHub Desktop.
Download ZIP
Least_common_multiple
Raw
gcd.scala
object Solution extends App{
import scala.annotation.tailrec
import scala.io.StdIn
import scala.util.{Try, Success, Failure}
import scala.math.pow//{abs, pow, ceil, floor}
/*
The first 168 prime numbers (all the prime numbers less than 1000) are:
*/
//prime_LT1000.sliding(10, 10).map(_.toList.mkString(",")).mkString(",\n")
val primes_LT1000: Stream[Int] = Stream(
2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997
)
def direct_Trial_Divisions_Primes_Search(
up_To: Int = 1000
): List[Int] = {
///> work as expected, when primes in ascending order
@annotation.tailrec
def loop(
candidate: Int,
prime: Int,
// filtered | restricted by previously found primes
primes: List[Int],
limit: Int,
is_Condition: Boolean
): Boolean = {
if (
prime >= limit ||
primes.isEmpty
) {
///> base case 1
//condition = true
is_Condition
} else if (candidate % prime == 0) {
///> base case 2
//condition = false
false
} else {
///> recursive step
loop(
candidate = candidate,
prime = primes.head,
primes = primes.tail,
limit = limit,
is_Condition = is_Condition
)
}
}
// must be sorted in ascending order
var primes_List: List[Int] = List(2)
var test_limit: Int = 1
var condition: Boolean = true
for (candidate <- 3 to up_To by 1) {
// scala> math.pow(3, 0.5).toInt
// res2: Int = 1
//scala> math.pow(4, 0.5)
//res1: Double = 2.0
test_limit = math.pow(candidate, 0.5).toInt
condition = true
if (false) {
// work as expected
// not-filtered | restricted by previously found primes
for (trail_Val <- 2 to (test_limit + 1) by 1) {
if (candidate % trail_Val == 0) {
condition = false
//break
}
}
}
if (true) {
// work as expected
// filtered | restricted by previously found primes
condition = loop(
candidate = candidate,
prime = primes_List.head,
primes = primes_List.tail,
limit = test_limit + 1,
is_Condition = true//condition
)
}
if (condition) {
// append ?
//primes_List = candidate +: primes_List
primes_List = primes_List :+ candidate
}
}
/*
scala> (100 to 1 by -1).take(20).sorted
res11: scala.collection.immutable.IndexedSeq[Int] = Vector(
81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)
*/
//return
//primes_List.sorted
primes_List
}
def prime_Factorization(
//error: reassignment to val
number: Int,
//error: reassignment to val
prime_Factors_Map: Map[Int, Int] = Map.empty[Int, Int],
is_Debug_Mode: Boolean = false
): Map[Int, Int] = {
var primes_List: List[Int] = direct_Trial_Divisions_Primes_Search(number + 1)
var condition: Boolean = true
var get_Prime: Option[Int] = None
var factors_Map: Map[Int, Int] = prime_Factors_Map
var current_Val: Int = number
if (primes_List.contains(current_Val)) {
factors_Map = factors_Map + (current_Val -> 1)
} else {
for (prime <- primes_List) {
condition = true
while (current_Val > 1 && condition) {
if (current_Val % prime == 0) {
get_Prime = factors_Map.get(prime)
/*
if (get_Prime.nonEmpty) {
///> works as expected
///> but how pick max prime power from previous calls
//if (prime_Factors_Map.contains(prime)) {
prime_Factors_Map[prime] += 1
prime_Factors_Map = prime_Factors_Map + (prime -> (get_Prime.get + 1))
} else {
prime_Factors_Map = prime_Factors_Map + (prime -> 1)
}
*/
get_Prime match {
case Some(v) => factors_Map = factors_Map + (prime -> (v + 1))
case _ => factors_Map = factors_Map + (prime -> 1)
}
current_Val = current_Val / prime
} else {
condition = false
}
}
}
}
//return
factors_Map
}
def least_Common_Multiple(
///> Set[Int] may be better
//factors: List[Int],
factors: Array[Int],
is_Debug_Mode: Boolean = false
): Int = {
var max_Prime_Powers_Map = Map.empty[Int, Int]
var get_Prime: Option[Int] = None
var lcm: Int = 1
var number_Factors_Map = Map.empty[Int, Int]
for (number <- factors) {
number_Factors_Map = prime_Factorization(number)//, Map.empty[Int, Int])
if (max_Prime_Powers_Map.isEmpty || max_Prime_Powers_Map.size == 0) {
max_Prime_Powers_Map = number_Factors_Map
} else {
/*
scala> for ((k, v) <- myMap) yield (k, v)
res15: scala.collection.immutable.Map[String,String] = Map(MI -> Michigan, OH -> Ohio, WI -> Wisconsin)
*/
for ((k, v) <- number_Factors_Map) {
get_Prime = max_Prime_Powers_Map.get(k)
get_Prime match {
case Some(p) => if (p < v) {
max_Prime_Powers_Map = max_Prime_Powers_Map + (k -> v)
}
// None
case _ => max_Prime_Powers_Map = max_Prime_Powers_Map + (k -> v)
}
}
}
}
for ((k, v) <- max_Prime_Powers_Map) {
lcm = lcm * math.pow(k, v).toInt
}
//return
lcm
}
///> '#::' is crutial for lazy evaluation, not just append '+:' <- fail
def mult(step: Int, state: Int): Stream[Int] = state #:: mult(step, state + step)
class Mult(seed: Int) {
var accum: Int = seed
def next: Int = {
val current_State: Int = accum
accum += seed
current_State
}
}
def inc_By(seed: Int): Int => Int = (step: Int) => seed + step
def add_Next(s: => Int)(a: => Int) = s + a
///> work as expected
def min_Common_Mult_4_Pair(
int_1: Int,
int_2: Int
): Int = {
var while_Guard: Int = 100000
var generator_1: Mult = new Mult(seed = int_1)
var generator_2: Int => Int = inc_By(seed = int_2)
var val_1: Int = generator_1.next
var val_2: Int = generator_2(int_2)
if (val_1 == val_2) {
//return
val_1
} else {
while (val_1 != val_2 && while_Guard > 0) {
while_Guard -= 1
if (val_1 > val_2) {
val_2 = generator_2(val_2)
} else /*if (val_1 < val_2)*/ {
val_1 = generator_1.next
}
}
//return
val_1
}
}
///> work as expected
def find_Pair_Min_Common_Int(
int_1: Int,
int_2: Int
): Int = {
var while_Guard: Int = 100000
var stream_1: Stream[Int] = mult(step = int_1, state = int_1)
var stream_2: Stream[Int] = mult(step = int_2, state = int_2)
var val_1 = stream_1.head
var val_2 = stream_2.head
if (val_1 == val_2) {
//return
val_1
} else {
while (val_1 != val_2 && while_Guard > 0) {
while_Guard -= 1
if (val_1 > val_2) {
stream_2 = stream_2.tail
val_2 = stream_2.head
} else /*if (val_1 < val_2)*/ {
stream_1 = stream_1.tail
val_1 = stream_1.head
}
}
//return
val_1
}
}
def sequence_Min_Common_Miltiple(
int_List: Array[Int]
): Int = {
//min_Common_Miltiple
var m_C_M: Int = 1
/*
scala> (for (List(v1, v2) <- List(4,7,12,21,42).sliding(2,1)) yield (v1, v2)).toList
res15: List[(Int, Int)] = List((4,7), (7,12), (12,21), (21,42))
*/
for (Array(n1, n2) <- int_List.sliding(2, 1)) {
if (m_C_M > 1) {
//m_C_M = find_Pair_Min_Common_Int(m_C_M, n2)
m_C_M = min_Common_Mult_4_Pair(m_C_M, n2)
} else {
//m_C_M = find_Pair_Min_Common_Int(n1, n2)
m_C_M = min_Common_Mult_4_Pair(n1, n2)
}
}
//return
m_C_M
}
//gcd: [Int >: Double](a: Double, b: Double)Double
//@scala.annotation.tailrec
@tailrec
def gcd/*[Int >: Double]*/(a: Double, b: Double): Double = if (b == 0) {
///> base case
///> ??? a.abs ???
a
} else {
///> base case
// error: could not optimize @tailrec annotated method gcd:
// it is called recursively with different type arguments
gcd(b, a % b)
//gcd(b.toDouble, (a % b).toDouble) //{
//error: could not optimize @tailrec annotated method gcd:
// it contains a recursive call not in tail position
/*
b match {
case 0 => a
case _ => gcd(b, (a % b))
}
*/
}
/*
2 3 4
1,2 => 1:{1},2:{1,2}, dif:{2}, => 2
2,3 => 2:{1,2},3:{1,3}, dif:{2,3) => 2*3=6
6,4 => 6:{1,2,3,6},4:{1,2,4}, dif:{3,6,4) => 3*6*4 = 72 ???
expected (2'*3, 2'*2) => 2'*(2*3) == 12 ? intersect * difference ?
? primes only ?
Using prime factorizations
6,4 => 6:{1,2,3},4:{1,2,2}, common:{1,2} * dif:{3,2) => 1*2*3*2 = 12
*/
def find_Least_Common_Multiple(
factors: Array[Int],
is_Debug_Mode: Boolean = false
): Double = {
@tailrec
def iterator(
seq: Array[Int],
///> lcm
result_Accum: Double = 1
///> Map(1->Set(1?),2->Set(1,2?),3->Set(1,3?),4->Set(1,2,4?))
//factors_Map: Map[Int, Set[Int]]
): Double = {
if (seq.isEmpty) {
///> base case
result_Accum
} else {
///> recursive step
val current_Factor: Int = seq.head
val accum: Double = if (result_Accum == current_Factor){
result_Accum
} else /*if (result_Accum != current_Factor)*/ {
//(result_Accum.abs / gcd(current_Factor, result_Accum)) * current_Factor.abs
(result_Accum / gcd(result_Accum, current_Factor)) * current_Factor
}
/*
} else if (result_Accum < current_Factor) {
val remainder: Double = current_Factor % result_Accum
if (remainder == 0) {
current_Factor.toDouble
} else {
//current_Factor * result_Accum
/*
scala> (4.0 / 2).max(6.0 / 2)
res51: Double = 3.0
*/
//result_Accum * (current_Factor / remainder).min(result_Accum / remainder)
result_Accum * gcd(current_Factor, remainder)
}
} else /*if (result_Accum > current_Factor)*/ {
val remainder: Double = result_Accum % current_Factor
if (remainder == 0) {
result_Accum
} else {
//current_Factor * result_Accum
//current_Factor * (current_Factor / remainder).min(result_Accum / remainder)
current_Factor * gcd(current_Factor, remainder)
}
}
*/
iterator(
seq.tail,
accum
)
}
}
/*
iterations:
s:{4,7,12,21,42}
r:[]
p:{2}
4:4 % 2 == 0 => 4/2 = 2 % 2 == 0 => same p, s - 4 + 2
7:7 % 2 != 0 => 7 % 2 != 0 => next p, s | s + 7
12:12 % 2 == 0 => 12 / 2 = 6 % 2 == 0 => same p, s - 12 + 6
21:21 % 2 != 0 => 21 % 2 != 0 => next p, s | s + 21
42:42 % 2 == 0 => 42 / 2 = 21 % 2 != 0 => next p, s - 42 + 21
-> round checked && not all == 1 && at least one elem % 2 == 0 | same p
s:{2,7,6,21,21} => {2,7,6,21}
r:[2]
p:{2}
2: % p == 0 && == p => 1 <- stop checking it s - 2
7: % p != 0 => 7, next p needed, s
6: % p == 0 && != p => 6 / p = 3 % p != 0, next p needed, s - 6 + 3
///> duplicates => ??? use memorization ??? <- set
21: % p != 0 => 21, next p needed, s
21: % p != 0 => 21, next p needed, s
-> p checked, not all == 1, next p
s:{7,3,21,21} => {7,3,21}
r:[2,2]
p:{3}
7: % p != 0 => 7, next p needed, s
3: % p == 0, == p => 1, <- stop checking it, s - 3
21: % p == 0, != p => 21 / p = 7, % p => next p, s - 21 + 7
-> p checked, not all == 1, next p
s:{7,7} => {7}
r:[2,2,3]
p:{5}
7: % p != 0 => 7, next p, s
-> p checked, not all == 1, next p
s:{7}
r:[2,2,3]
p:{7}
7: % p == 0, == p => 1, <- stop checking it, s - 7
-> p checked, all == 1, Done
s:{}
r:[2,2,3,7].product = 84
p:{}
----------------------------------------------------
s_S:{2, 3, 4}
r_P:{}
ps:[2,..]
r_P:2
r_A:[]
n_P:t
*/
@tailrec
def loop(
seq_State: Set[Int],
round_Progress: Set[Int] = Set.empty[Int],
primes: Stream[Int],
round_Prime: Int = 2,
///> lcm's factors
///> head is ? current | last prime factor ?
///> changed once per round, when round_Progress.isEmpty => 100%
result_Accum: List[Int] = List(1),
//last_Checked: Boolean = false,
///> if all per round next p => true else false
///> if at least one per round same p => false else true
is_Next_Prime: Boolean = false,//true
is_Same_Prime: Boolean = true,
is_Debug_Mode: Boolean = false
): Double = {
if (
seq_State.isEmpty ||
primes.isEmpty
) {
///> base case
result_Accum.product.toDouble
} else {
///> recursive step
// until all of the numbers have been reduced to 1.
if (is_Debug_Mode) {
println(
s"""seq_State:${seq_State}""" +
s""",round_Progress:${round_Progress}""" +
s""",primes:${primes}""" +
s""",round_Prime:${round_Prime}""" +
s""",result_Accum:${result_Accum}""" +
s""",is_Next_Prime:${is_Next_Prime}"""
)
}
val (prime, primes_Left, next_Round, elem, not_Same_Prime/*, accum*/): (
Int,
Stream[Int],
Set[Int],
Int,
Boolean/*,
List[Int]*/
) = if (
round_Progress.isEmpty
) {
///> starting new (check | round) for (current) (same | next) prime
if (is_Debug_Mode) {println(s"""next round start ...""")}
if (is_Next_Prime) {
(primes.head, primes.tail, seq_State.tail, seq_State.head, true)
} else {
(round_Prime, primes, seq_State.tail, seq_State.head, true)
}
} else /*if (round_Progress.nonEmpty)*/{
(round_Prime, primes, round_Progress.tail, round_Progress.head, is_Next_Prime)
}
val (next_State, next_Prime, accum): (Set[Int], Boolean, List[Int]) = if (elem % prime == 0) {
val next_Result: List[Int] = if (not_Same_Prime) {
///> first time per round % p == 0
prime +: result_Accum
} else {
result_Accum
}
if (elem == prime || elem == 1) {
///> discard elem
(seq_State - elem, not_Same_Prime, next_Result)
} else /*if (elem != prime)*/{
val next_Elem_Val = elem / prime
///> discard old elem
///> add new elem
/*
scala> Set(2,4,3,7) - 4 + 1
res0: scala.collection.immutable.Set[Int] = Set(2, 3, 7, 1)
*/
if (is_Debug_Mode) {
println(
s"""Same Prime check: ${next_Elem_Val} % ${prime} == 0 is: ${next_Elem_Val % prime == 0}""")}
(seq_State - elem + next_Elem_Val, (next_Elem_Val % prime != 0), next_Result)
}
} else /*if (elem % prime != 0)*/{
if (elem == 1) {
///> discard elem
(seq_State - elem, not_Same_Prime, result_Accum)
} else {
(seq_State, not_Same_Prime, result_Accum)
}
}
if (is_Debug_Mode) {
println(
s""">>next_State:${next_State}""" +
s""",next_Round:${next_Round}""" +
s""",primes_Left:${primes_Left}""" +
s""",prime:${prime}""" +
s""",accum:${accum}""" +
s""",next_Prime:${next_Prime}"""
)
}
loop(
///> reduced by elements equal to 1
seq_State = next_State,
round_Progress = next_Round,
primes = primes_Left,
round_Prime = prime,
result_Accum = accum,
is_Next_Prime = next_Prime,
is_Debug_Mode = is_Debug_Mode
)
}
}
///> initialization
//iterator(factors)
loop(
seq_State = factors.toSet,
//round_Progress = seq_State,
primes = primes_LT1000,
round_Prime = 1,//2
//result_Accum
is_Next_Prime = true,
is_Debug_Mode = is_Debug_Mode
)
}
//): Int
///>>>*** unit test ***<<<///
// Print the greatest common divisor of numbers in input of size N.
// For each test case it is guaranteed that
// solution will not exceed <= 2 * 10^18 <- very big number
val is_Debug_Mode: Boolean = (
//true
false
)
val factors_Stream_Size_N: Int = Try(
StdIn.readInt()
) match {
case Success(f) => f // assert( f >= 2 && f <= 10)
case Failure(e) => /*println(e.getMessage)*/0
}
val factors_Stream: Array[/*Big*/Int] = Try(
StdIn.readLine()
) match {
case Success(str) => {
str
.split(" ")
// assert(_ >= 1 && _ <= pow(10, 6))
/*
scala> scala.math.pow(10, 6)
res64: Double = 1000000.0
*/
.map(_.toInt)
//.map(BigInt(_))
}
case Failure(e) => {
//println(e.getMessage)
//"" // <- default
//false
Array.empty[Int]
//List("-1")
//Array(BigInt(1))
}
}
///> ??? WTF ???
/*
scala> s.fold(1)(f)
<console>:13: error: type mismatch;
found : ((Int, Int)) => Int
required: (Int, Int) => Int
s.fold(1)(f)
*/
def f(p: (Int, Int)): Int = p match { case (a, b) => BigInt(a).gcd(b).toInt }
/*
test case 3-9 Terminated due to timeout
so, BigInt may be ?
*/
def min_Common_Multiple(
numbers: Array[Int]
): Int = {
/*"""
:param numbers:
:return:
"""*/
// preprocessing
//var numb_Map: Map[Int, Int] = (
// for (n <- numbers) yield (n -> n)).toMap
/*
scala> var i = -1
i: Int = -1
scala> val a_M = for (n <- Array(1,2,3,5,7,11,13)) yield {i += 1;(i, n, BigInt(n))}
a_M: Array[(Int, Int, scala.math.BigInt)] = Array(
(0,1,1), (1,2,2), (2,3,3), (3,5,5), (4,7,7), (5,11,11), (6,13,13))
scala> for (el <- a_M) {val (i, k, v) = el; a_M(i) = (i, k, v + 1)}
scala> a_M
res14: Array[(Int, Int, scala.math.BigInt)] = Array(
(0,1,2), (1,2,3), (2,3,4), (3,5,6), (4,7,8), (5,11,12), (6,13,14))
*/
var i: Int = -1
var numb_ArrayMap: Array[(Int, Int, scala.math.BigInt)] = (
for (n <- numbers) yield {
i += 1
(i, n, BigInt(n))
}
)
//var while_Guard: Int = 1000000 <- less then test 3-9 iterations
//var max_So_Far: Int = 0
var max_So_Far: BigInt = BigInt(0)
var is_All_Equal: Boolean = false
var is_Not_All_Equal: Boolean = true
//condition = true
//var balance: Int = 0
//var div_Float = 1.0
//var div_Int = 1
while (
is_Not_All_Equal //&&
//while_Guard > 0
) {
//while_Guard -= 1
// new round
// reset
//balance = 0
is_Not_All_Equal = true
is_All_Equal = true//false
/*
scala> val m = Map(1->"a",2->"b",3->"c")
m: scala.collection.immutable.Map[Int,String] = Map(1 -> a, 2 -> b, 3 -> c)
scala> for ((k, v) <- m) yield k
res5: scala.collection.immutable.Iterable[Int] = List(1, 2, 3)
scala> for ((k, v) <- m) yield v
res6: scala.collection.immutable.Iterable[String] = List(a, b, c)
scala> val a_M = for (n <- Array(1,2,3,5,7,11,13)) yield (n, BigInt(n))
a_M: Array[(Int, scala.math.BigInt)] = Array(
(1,1), (2,2), (3,3), (5,5), (7,7), (11,11), (13,13))
scala> for (el <- a_M) {val (k, v) = el; el = (k, v + 1)}
<console>:12: error: reassignment to val
for (el <- a_M) {val (k, v) = el; el = (k, v + 1)}
scala> a_M.zipWithIndex
res10: Array[((Int, scala.math.BigInt), Int)] = Array(
((1,1),0), ((2,2),1), ((3,3),2), ((5,5),3), ((7,7),4), ((11,11),5), ((13,13),6))
scala> for (el <- a_M.zipWithIndex) {val ((k, v), i) = el; a_M(i) = (k, v + 1)}
scala> a_M
res12: Array[(Int, scala.math.BigInt)] = Array(
(1,2), (2,3), (3,4), (5,6), (7,8), (11,12), (13,14))
*/
// mutation inside iterator ? <- OK
//for ((k, v) <- numb_Map) {
for (el <- numb_ArrayMap) {
val (i, k, v) = el//; a_M(i) = (i, k, v + 1)
if (v > max_So_Far) {
max_So_Far = v
//balance = -1
//is_Not_All_Equal = false//true
is_All_Equal = false
} else if (v == max_So_Far) {
// skip | pass
} else /*if (v < max_So_Far)*/ {
//balance = -1
//is_Not_All_Equal = false
is_All_Equal = false
if (max_So_Far % k == 0) {
// update
//numb_Map = numb_Map + (k -> max_So_Far)
} else /*if (max_So_Far % k != 0)*/ {
// update
max_So_Far = (max_So_Far / k + 1) * k
//numb_Map = numb_Map + (k -> max_So_Far)
}
//numb_Map = numb_Map + (k -> max_So_Far)
numb_ArrayMap(i) = (i, k, max_So_Far)
}
}
// post check
// if unchanged
if (
//is_Not_All_Equal
is_All_Equal //||
//balance == 0
) {
is_Not_All_Equal = false
} else {
is_Not_All_Equal = true
}
}
//println("""while_Guard: ${}""".format(while_Guard))
//return
max_So_Far
.toInt
}
//val result: Int = {
val result: String = {
/*
scala> BigInt(3).gcd(5)
res5: scala.math.BigInt = 1
scala> BigInt(3).gcd(5).toInt
res6: Int = 1
scala> val s = Array(1, 2, 3, 4, 5)
s: Array[Int] = Array(1, 2, 3, 4, 5)
scala> s.fold(0)(BigInt(_).gcd(_).toInt)
res7: Int = 1
scala> s.reduce(BigInt(_).gcd(_).toInt)
res8: Int = 1
scala> s.reduceRight(BigInt(_).gcd(_).toInt)
res9: Int = 1
scala> s.fold(0)({case (a: Int,b: Int) => BigInt(a).gcd(b).toInt})
res18: Int = 1
scala> s.fold[Int](1)({case (a: Int,b: Int) => BigInt(a).gcd(b).toInt})
res19: Int = 1
scala> s.fold(1)((x: Int, y: Int) => f((x, y)))
res32: Int = 1
scala> s.fold(1)((a: Int, b: Int) => BigInt(a).gcd(b).toInt)
res34: Int = 1
scala> s.fold(1){case p => BigInt(p._1).gcd(p._2).toInt}
res36: Int = 1
*/
/*
factors_Stream
.fold[Int](1)//(_ + _)
// error: missing parameter type for expanded function ((x$2, x$3) => BigInt(x$2).gcd(x$3).toInt)
//(BigInt(_).gcd(_).toInt)
{ case (a: Int, b: Int) => BigInt(a).gcd(b).toInt}
*/
//484 CPU time limit exceeded (core dumped) "$@"
//find_Least_Common_Multiple(
///> alas, but fail
//least_Common_Multiple(
///> return (6) for {1, 3}
//sequence_Min_Common_Miltiple(
min_Common_Multiple(
factors_Stream//,
//is_Debug_Mode = false
)
// assert(
// result <=
// scala> 2 * scala.math.pow(10, 18)
// res44: Double = 2.0E18
//)
//.toInt
.toString
.takeWhile(_ != '.')
}
//assert(9875 == 2)
//println(s"""${result.mkString(" ")}""")
println(s"""${result}""")
if (is_Debug_Mode){
var test_result = direct_Trial_Divisions_Primes_Search()
var expected = 168
/*
scala> (1 to 100 by 1).take(20)
res10: scala.collection.immutable.Range = Range(
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
*/
assert( test_result.size == expected,
s"""test_result.size: ${test_result.size}, \ntest_result.take(20): ${test_result.take(20)}""")
println(
s"""test_result.size: ${result.size} == expected: ${expected}, \ntest_result.take(20): ${test_result.take(20)}""")
}
if (is_Debug_Mode){
var test_result = prime_Factorization(12)
var expected = Map(2 -> 2, 3 -> 1)
/*
*/
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
var test_result = find_Pair_Min_Common_Int(4, 6)
var expected = 12
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
var test_result = min_Common_Mult_4_Pair(4, 6)
var expected = 12
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
//var test_result = sequence_Min_Common_Miltiple(List(4,7,12,21,42))
var test_result = sequence_Min_Common_Miltiple(Array(4,7,12,21,42))
var expected = 84
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
//var test_result = sequence_Min_Common_Miltiple(List(4,7,12,21,42))
var test_result = min_Common_Multiple(Array(4,7,12,21,42))
var expected = 84
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
}
Display the source blob
Display the rendered blob
Raw
Least_common_multiple.ipynb
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment