fork download

copy

package eulerProject
 
/**
 * Problem 221: Alexandrian Longegers<br>
 * 13 December 2008<br>
 * <br>
 * We shall call a positive integer A an "Alexandrian integer", if there 
 * exist integers p, q, r such that:<br>
 * <br>
 * A = p * q * r    and   1 / A = 1 / p + 1 / q + 1 / r <br>
 * <br>
 * For example, 630 is an Alexandrian integer (p = 5, q = -7, r = -18). 
 * In fact, 630 is the 6^(th) Alexandrian integer, the first 6 Alexandrian 
 * integers being: 6, 42, 120, 156, 420 and 630.<br>
 * <br>
 * <b>Find the 150000<sup>th</sup> Alexandrian integer.</b><br>
 * <br>
 * <hr>
 * <pre>
 * p * q * r = A (1)
 * 1/p + 1/q + 1/r = 1/A (2)
 * From (2):
 * (q * r + p * r + p * q)/(p * q * r) = 1 / A (3)
 * So
 * p * q + p * r + q * r = p * (q + r) + q * r = p * s + q * r = 1 (4)
 * Where 
 * s = q + r (5)
 * From (1)
 * q * r = A / p  = d (6)
 * Appling (6) in (4)
 * p * s + d = 1 (7)
 * s = (p - A) / p ^ 2 (8)
 * How p > 0, A > 0 and A > p
 * s < 0 (9)
 * From (6), for (A / p) be a integer, p must be a divisor of A
 * 
 * Para resumir
 * 
 * -> p é divisor de A
 * -> s = q + r = (p - A) / p^2, deve ser um inteiro negativo
 * -> q e r são a solução da equação (s +- sqrt(s^2 - 4 * d)) / 2, onde d = A / p
 * <pre>
 */
object Problem221a {
 
  type Alexandrian = (Long, Long, Long, Long)
 
  import Utils._
 
  def getQR(s: Long, d: Long): Option[(Long, Long)] = {
    val delta = s * s - 4 * d
    var result: Option[(Long, Long)] = None
    if(delta > 0) {
      val rootDelta = getSqrt(delta)
      if(rootDelta.isRight) {
        val (q, remQ) = /%(s + rootDelta.right.get, 2)
        val (r, remR) = /%(s - rootDelta.right.get, 2)
        if(remQ == 0 && remR == 0) {
          result = Some((q, r))
        } 
      } 
    } 
    result
  }
 
  def testP(A: Long, p: Long): Option[Alexandrian] = {
    val (s, remainder) = /%(p - A, p * p)
    var result: Option[Alexandrian] = None
    if(remainder == 0) {
      val qr = getQR(s, A / p)
      if(qr.isDefined) {
        result = Some((A, p, qr.get._1, qr.get._2))
      } 
    } 
    result
  }
 
  def evaluateA(A: Long, candidate: Long, limitCandidate: Long): Option[Alexandrian] = {
    if(candidate > limitCandidate) {
      None
    } else {
      val (quocient, remainder) = /%(A, candidate)
      if(remainder == 0) {
        val alex = testP(A, candidate)
        if(alex.isDefined) {
          alex
        } else {
          val alex1 = testP(A, quocient)
          if(alex1.isDefined) {
            alex1
          } else {
            evaluateA(A, candidate + 1, limitCandidate)
          }
        }
      } else {
        evaluateA(A, candidate + 1, limitCandidate)
      }
    }
  }
 
  def getNthAlexandrian(quantity: Int): Long = {
 
    def eval(A: Long, qty: Int): Long = {
      val alex = evaluateA(A, 1, Math.sqrt(A.toDouble).toLong)
      if(alex.isDefined) {
        val nextQty = qty + 1
        log("%,7d -> %,11d, %,7d, %,7d, %,7d".format(nextQty, alex.get._1, alex.get._2, alex.get._3, alex.get._4))
        if(nextQty == quantity) {
          A
        } else {
          eval(A + 1, nextQty)
        }
      } else {
        eval(A + 1, qty)
      }
    }
 
    eval(1, 0)
  }
 
  def main(args : Array[String]) : Unit = {
    val max = 1000
 
    val t0 = System.currentTimeMillis
    val result = getNthAlexandrian(max)
    val deltaT = System.currentTimeMillis - t0
 
    println("==============================")
    log(result)
    log("Total Time: " + deltaT + " ms")
  }
}

Main.scala:48: error: not found: value Utils
  import Utils._
         ^
Main.scala:54: error: not found: value getSqrt
      val rootDelta = getSqrt(delta)
                      ^
Main.scala:56: error: not found: value /%
        val (q, remQ) = /%(s + rootDelta.right.get, 2)
                        ^
Main.scala:57: error: not found: value /%
        val (r, remR) = /%(s - rootDelta.right.get, 2)
                        ^
Main.scala:59: error: type mismatch;
 found   : Any
 required: Long
          result = Some((q, r))
                         ^
Main.scala:59: error: type mismatch;
 found   : Any
 required: Long
          result = Some((q, r))
                            ^
Main.scala:67: error: not found: value /%
    val (s, remainder) = /%(p - A, p * p)
                         ^
Main.scala:70: error: type mismatch;
 found   : Any
 required: Long
      val qr = getQR(s, A / p)
                     ^
Main.scala:82: error: not found: value /%
      val (quocient, remainder) = /%(A, candidate)
                                  ^
Main.scala:88: error: type mismatch;
 found   : Any
 required: Long
          val alex1 = testP(A, quocient)
                               ^
Main.scala:107: error: not found: value log
        log("%,7d -> %,11d, %,7d, %,7d, %,7d".format(nextQty, alex.get._1, alex.get._2, alex.get._3, alex.get._4))
        ^
Main.scala:129: error: not found: value log
    log(result)
    ^
Main.scala:130: error: not found: value log
    log("Total Time: " + deltaT + " ms")
    ^
13 errors found
Usage: scalac <options> <source files>
where possible standard options include:
  -Dproperty=value                Pass -Dproperty=value directly to the runtime system.
  -J<flag>                        Pass <flag> directly to the runtime system.
  -P:<plugin>:<opt>               Pass an option to a plugin
  -X                              Print a synopsis of advanced options.
  -bootclasspath <path>           Override location of bootstrap class files.
  -classpath <path>               Specify where to find user class files.
  -d <directory|jar>              destination for generated classfiles.
  -dependencyfile <file>          Set dependency tracking file.
  -deprecation                    Emit warning and location for usages of deprecated APIs.
  -encoding <encoding>            Specify character encoding used by source files.
  -explaintypes                   Explain type errors in more detail.
  -extdirs <path>                 Override location of installed extensions.
  -feature                        Emit warning and location for usages of features that should be imported explicitly.
  -g:<level>                      Set level of generated debugging info. (none,source,line,vars,notailcalls) default:vars
  -help                           Print a synopsis of standard options
  -javabootclasspath <path>       Override java boot classpath.
  -javaextdirs <path>             Override java extdirs classpath.
  -language:<_,feature,-feature>  Enable or disable language features: `_' for all, `-language:help' to list
  -no-specialization              Ignore @specialize annotations.
  -nobootcp                       Do not use the boot classpath for the scala jars.
  -nowarn                         Generate no warnings.
  -optimise                       Generates faster bytecode by applying optimisations to the program
  -print                          Print program with Scala-specific features removed.
  -sourcepath <path>              Specify location(s) of source files.
  -target:<target>                Target platform for object files. All JVM 1.5 targets are deprecated. (jvm-1.5,jvm-1.6,jvm-1.7,jvm-1.8) default:jvm-1.6
  -toolcp <path>                  Add to the runner classpath.
  -unchecked                      Enable additional warnings where generated code depends on assumptions.
  -uniqid                         Uniquely tag all identifiers in debugging output.
  -usejavacp                      Utilize the java.class.path in classpath resolution.
  -usemanifestcp                  Utilize the manifest in classpath resolution.
  -verbose                        Output messages about what the compiler is doing.
  -version                        Print product version and exit.
  @<file>                         A text file containing compiler arguments (options and source files)

spoj: The program compiled successfully, but Main.class was not found.
      Class Main should contain method: def main(args: Array[String]).

Standard output is empty