Project euler上的题目，帮忙看看

object Euler110 extends Application {
    def find(bound:Int):BigInt = {
        import scala.Math._
        val ps = Array(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53)
        val lp = ps.subArray(0,ceil(log(2*bound-1)/log(3)).toInt-3).map{ n => n:BigInt}
        var min = ps.subArray(0,ceil(log(2*bound-1)/log(3)).toInt).foldLeft(1:BigInt){ _*_ }
        def find0(v:BigInt,mul:Int,upper:Int,idx:Int){
            if(v >= min) return
            if(mul > 2*bound-1){
                min = v
                return
            }
            if(idx >= lp.length) return
            for(n <- 0 to upper) find0(v*lp(idx).pow(n),mul*(2*n+1),upper,idx+1)
        }
        find0(1,1,4,0)
        min
    }
    println(find(4000000))
}

30 Dec 2005 11:04 pm
euler (PHP) euler is from England

Quote
You're right about the number of unit fraction sums, but it would need to be the number of divisors of n2 which are less than or equal to n, otherwise we would include symmetrically equivalent solutions.

Xaphiosis, you're right about not finding Diophantine equations with negative indices, so in problems like this the trick is to eliminate the denominators...

From 1/x + 1/y = 1/n we get nx + ny = xy.
ny = xy - nx = x(y - n)
x = ny/(y - n)

Let k = y - n (y = k + n).

So x = n(k + n)/k = n + n2/k.

If x is integer then k must divide n2. However...

Without loss of generality, let us assume that y ≤ x.

Therefore y = k + n ≤ x = n + n2/k.
k ≤ n2/k
k2 ≤ n2

Hence k ≤ n.

For example, if n = 6, n2 = 36, so k = {1,2,3,4,6,9,12,18,36}.

But we only want k ≤ n; that is, k = {1,2,3,4,5,6}.

We can use this set of k to find x and y...

Recall that y = n + k, and x = ny/(y - n) = ny/k.

So we get (7,42), (8,24), (9,18), (10,15), (12,12).

If we included k = {9,12,18,36} it would give (15,10), (18,9), (24,8), and (42,7).


Based on this symmetry it should be clear why the closed formula (which I had completely missed until RogerHui kindly provided the link) is: (d(n2)+1)/2, where d(n) is number of divisors function. Because you will recall that n2 has an odd number of divisors, so we add one before dividing by 2 (subtracting one would lose the "middle" divisor).

31 Dec 2005 01:26 am
neverforget (PARI/GP) neverforget is from USA

Quote
From Sloane's A018892:

If n = (p1^a1)(p2^a2)...(pt^at),
2-partitions = ((2 a1 + 1)(2 a2 + 1) ... (2 at + 1) + 1)/2.

We want ((2 a1 + 1)(2 a2 + 1) ... (2 at + 1) + 1)/2 > 1000
(2 a1 + 1)(2 a2 + 1) ... (2 at + 1) >= 2000