Tag Archives: integers

Euler 142 – Rearrange the variables

This is is just a bunch of algebraic relationships. One could use brute force, but it would take several hours.
Instead, reassign these variables:

a = x + y
b = x – y
c = x + z
d = x – z
e = y + z
f = y – z

Then playing around with them, we get:

x = (a+b)/2 = (c+d)/2 because b = c – e and e = a – d
y = (e+f)/2 = (2a-d-c)/2 because e = a – d and f = a – c
z = (c-d)/2
x + y + z = (2a-d+c)/2

So now we just iterate on a,c,d over a list of squares testing for:
a > c > d;
c-d is even;
b,e,f are squares;
and x > y > z > 1

Routine runs in about 120 seconds on a single core 3Ghz system.

import Data.List

isSqr :: Int -> Bool
isSqr n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)
	
slist :: [Int]
slist = [x | x <- [2..1000000], isSqr x]

test :: Int -> Int -> Int -> Bool
test a c d =
	a > c && c > d && even (c-d) && isSqr(c-a+d) && isSqr(a-d) && isSqr(a-c) && x > y && y > z && z > 1
	where
		x = (c+d) `div` (fromIntegral 2)
		y = ((2*a)-d-c) `div` (fromIntegral 2)
		z = (c-d) `div` (fromIntegral 2)

main = print $ head $ sort [((2*a)-d+c) `div` (fromIntegral 2)| a<-slist,c<-slist,d<-slist,test a c d]

Euler Problem 131 – Prime Numbers

Now that I’m on a Haskell kick, I opted to solve this one because of the need for calculating prime numbers. I found tons of resources online that detail different ways to calculate it. I settled on a modified Sieve of Eratosthenes that also takes into account squares, making it faster. Calculating the 78K prime numbers under a million, only takes a few seconds.

The other part of the solution comes from the fact that by playing with the values of the relationship from the problem, we see that n^2 and (n+p) have to be cubes. This makes the prime number a difference of cubes such that prime = (a+1)^3–a^3. This new value stays under a million when a is less than 600. So we just test over this smaller series and count the number of resulting primes. This solution runs in less than 10 secs.

Oh by the way, just for kicks the above image represents the distribution of prime numbers. The source code can be found here.

import Data.List
import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m] where
    sieve [] = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..m])

testEquation :: Integer -> Bool
testEquation a = (((a+1)^3)-(a^3)) `elem` (primes 1000000)

main = print $ length [(((a+1)^3)-(a^3))| a <- [1..600], testEquation a ]

Euler Problem 63

Ummm, am I missing something here? This worked first try.

public String algorithm ()
    {
        int count = 0;
        for (int power = 1; power <= 100; power++)
        {
            for (int base = 1; base <= 100; base++)
            {
                BigInteger Big = new BigInteger(String.valueOf(base));
                Big = Big.pow(power);
                if (Big.toString().length() == power)
                {
                    count++;
                    v.appendText(String.format("Count:%d Base:%d Power:%d Value:%s\n", count, base, power, Big.toString()));
                }
            }
        }
        return String.format("\nAnswer = %s\n", String.valueOf(count));
    }

Euler Problem 56

Easy. Used BigInteger class and long variables just to be on the safe side. Didn’t need to be. Small answer.

    import java.math.*;

    public class Euler56
    {
        public static void main(String[] args)
        {
            Euler56 e = new Euler56();
            System.out.format(“Problem: %s\n”, e.getClass().getName());
            System.out.format(“Answer = %s\n”, e.Problem());
        }
        public String Problem ()
        {
            long max = 0;
            for (int a = 1; a < 100; a++)
                for (int b = 1; b  max)
                        max = GooSum;
                }
            return String.valueOf(max);
        }
        public long digitalSum(String number)
        {
            long sum = 0;
            for (int n = 0; n <= number.length()-1; n++)
                sum += (number.charAt(n)-48);
            return sum;
        }
    }

Euler Problem 55

Not too tricky. Use the BigInteger class.

    import java.math.*;

    public class Euler55
    {
        public static void main(String[] args)
        {
            Euler55 e = new Euler55();
            System.out.format(“Problem: %s\n”, e.getClass().getName());
            System.out.format(“Answer = %s\n”, e.Problem());
        }
        public String Problem ()
        {
            int count = 0;
            for (int n = 1; n < 10000; n++)
            {
                BigInteger N = new BigInteger (String.valueOf(n));
                boolean flag = true;
                for (int i = 1; i <= 50; i++)
                {
                    N = N.add(new BigInteger (Rev(N.toString())));
                    System.out.format(“Number:%d Iteration:%d Sum:%s\n”,n, i, N.toString());
                    if (N.toString().equals(Rev(N.toString())))
                    {
                        System.out.format(“Palindrome in %d. Count = %d\n”,i,count);
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    count++;
            }
            return String.valueOf(count);
        }
        public String Rev (String n)
        {
            return new StringBuffer(n).reverse().toString();
        }
    }

Euler Problem 53

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ^(5)C_(3) = 10.

In general,

^(n)C_(r) =
n!
r!(n−r)!
,where r ≤ n, n! = n×(n−1)××3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ^(23)C_(10) = 1144066.

How many, not necessarily distinct, values of  ^(n)C_(r), for 1 ≤ n ≤ 100, are greater than one-million?

Just do it all with the BigInteger class.

import java.math.*;

public class Euler53
{
    public static void main(String[] args)
    {
        Euler53 e = new Euler53();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        int count = 0;
        for (int n = 1; n <= 100; n++)
            for (int r = 1; r <= n; r++)
            {
                BigInteger c = C(n,r);
                System.out.format(“n:%d r:%d C(n,r):%d\n”, n, r, c);
                if (c.compareTo(BigInteger.valueOf(1000000)) == 1)
                    count++;
            }
        return String.valueOf(count);
    }
    public BigInteger C (int n, int r)
    {
        BigInteger calc = new BigInteger(“1”);
        calc = calc.multiply(F(n));
        calc = calc.divide(F(r));
        calc = calc.divide(F(n-r));
        return calc;
    }
    public BigInteger F (int d)
    {
        BigInteger sum = new BigInteger(“1”);
        if (d > 0)
            for (int i = d; i >= 1; i–)
                sum = sum.multiply(BigInteger.valueOf(i));
        return sum;
    }
}