Programming Challenges

Quote: ThatDonGuy

I think this is the most efficient one I found - it's hard to tell as they all run so fast:

Click Here for Code

int A = 999;
int ASquared = 998001;  // 999 x 999
int B;
BestResult = 0;
while (ASquared > BestResult && A >= 100)
{
    B = 0;
    AB = ASquared;
    while (A + B < 1000 && AB > BestResult)
    {
        if (AB >= 100000 && AB / 100000 == AB % 10 && (AB % 100000) / 10000 == (AB % 100) / 10 && (AB % 10000) / 1000 == (AB % 1000) / 100)
        {
            BestResult = AB;
            S.AppendLine((A + B).ToString() + " x " + (A - B).ToString() + " = " + BestResult.ToString());
        }
        else if (AB < 100000 && AB / 10000 == AB % 10 && (AB % 10000) / 1000 == (AB % 100) / 10)
        {
            BestResult = AB;
            S.AppendLine((A + B).ToString() + " x " + (A - B).ToString() + " = " + BestResult.ToString());
        }
        B++;
        AB -= (B + B - 1);
    }
    A--;
    ASquared -= (A + A + 1);
}

I get 993 x 913 = 906609

The way it works is:
First, check 999 x 999
Next, check 998 x 998, then 999 x 997
Next, check 997 x 997, then 998 x 996, then 999 x 995
Keep checking N squared, then (N + 1)(N - 1), then (N + 2)(N - 2), and so on
Since N squared is the largest product in each "group", stop checking when N squared is less than the highest number already found.
To make it more efficient, multiplications are replaced by additions.

Quote: gamerfreak

You got the correct answer, however, and I didn't trace your code in depth, but I believe you can further optimize your solution with some math.

Hint

Since 11 is prime, at least one of the values A or B must have a factor of 11.

Quote: ThatDonGuy

That assumes the answer has 6 digits. 12321 = 111 x 111, but 111 is not a multiple of 11.

Quote: ThatDonGuy

The problem with brute force is, you have to do 13 multiplications in each step. Mine starts with 13, then does a multiplication and a division in each step - that is, until the 13th digit is a zero, at which point you know the next 13 products will all be zero, so you can skip ahead 13 digits.

Quote: ThatDonGuy

The problem with brute force is, you have to do 13 multiplications in each step. Mine starts with 13, then does a multiplication and a division in each step - that is, until the 13th digit is a zero, at which point you know the next 13 products will all be zero, so you can skip ahead 13 digits.

Quote: DRich

For challenge #2, since multiplication is commutative shouldn't the largest sum of the sequence of 13 numbers with no zeros also be the largest product? Is there any point in doing any multilpication?

Quote: ThatDonGuy

9991111111111 has product 729 and sum 37
2222222222222 has product 8192 and sum 26

Quote: ThatDonGuy

My Solution

T(12375) = 76,576,500 = 2² x 3² 5³ x 7 x 11 x 13 x 17 has 576 divisors
Each divisor is the product of {1, 2, 4} {1, 3, 9} {1, 5, 25, 125} {1, 7} {1, 11} {1, 13} {1. 17}

The number of factors a positive integer N has = (P(2) + 1) (P(3) + 1) (P(5) + 1) (P(7) + 1) P((11) + 1)...
where P(K) is the number of times the prime K appears in N's prime factorization
For example, 25,200 = 2⁴ x 3² x 5² x 7, so P(2) = 4, P(3) = 2, P(5) = 2, P(7) = 1, and P(N) = 0 for all other primes

// This assumes int Primes[] is defined as a constant array of all primes < 10,000
int PrimesCount = Primes.Length;

int[] Factors = new int[PrimesCount];

int FactorCount = 0;
int TCount = 1;
int T = 1;
// int P;
while (FactorCount < 500)
{
    for (N = 0; N < PrimesCount; N++)
    {
        Factors[N] = 1;
    }
    TCount++;
    T += TCount;
    N = T;
    for (P = 0;  Primes[P] * Primes[P] <= N; P++)
    {
        while (N % Primes[P] == 0)
        {
            Factors[P]++;
            N /= Primes[P];
        }
    }
    for (P = 0; P < PrimesCount && Primes[P] != N; P++) ;
    if (P < PrimesCount)
    {
        Factors[P]++;
    }
    FactorCount = 1;
    for (N = 0; N < PrimesCount; N++)
    {
        FactorCount *= Factors[N];
    }
}

Quote: gamerfreak

Challenge #4

Since many of these problems have a recurring theme of involving prime numbers, 
this challenge is to create the fastest primality test you can.

The function IsPrime(N) should take any integer N as a parameter, and return true/false.

Heuristic and Probabilistic tests are acceptable.

public static bool IsPrime(int number)
{
    if (number == 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0)  return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));

    for (int i = 3; i <= boundary; i+=2)
    {
        if (number % i == 0)  return false;
    }

    return true;        
}

Quote: Romes

Quote: gamerfreak

Challenge #4

Since many of these problems have a recurring theme of involving prime numbers, 
this challenge is to create the fastest primality test you can.

The function IsPrime(N) should take any integer N as a parameter, and return true/false.

Heuristic and Probabilistic tests are acceptable.

My Answer

So let's find out if this is cheating... Because here's my real world application of this. If I needed to find out if a number was a prime number for an application I'm working on, the first thing I would do is take to google and type "c# check for prime number" which led me to the following stack overflow page and answer:

https://stackoverflow.com/questions/15743192/check-if-number-is-prime-number

public static bool IsPrime(int number)
{
    if (number == 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0)  return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));

    for (int i = 3; i <= boundary; i+=2)
    {
        if (number % i == 0)  return false;
    }

    return true;        
}

So all said and done this literally took me about 30 seconds. I believe that's the most efficient you could be.

Quote: Romes

Yeah, but I didn't modify it at all and it took me 30 seconds to find lol... I like the challenges you post and I start thinking about "okay you'd just have to do this, then that, then this, etc..." but then I don't want to write out the code =P. You should allow pseudo-code, as it can clearly show the understanding of the concepts! Or are all of these questions just homework questions we're answering for someone?? =D

Quote: Dalex64

90% of coding is actually problem solving, figuring out how to solve a problem, and the best way to solve a problem. 10% is writing the code to do it...

Quote: Romes

In the real world, this all day.

Another fun thing to reminisce over, since this is mainly a "programming" thread. I just had an error, a very simple one, in an application I'm working on. It made me laugh because I personally believe it's the most common error that finally compilers caught up to pointing out. Back in the day you would just get an error or even worse the program would WORK and you'd get the wrong output... the good 'ol double equals.

if (code == x) works for comparison... if(code = x) reassigns and evaluates as true (at least it used to, the compiler I'm working with now in the .NET framework just caught this and threw an error to me). I remember back in college this not being the case... the program would run fine, setting the value of code = x, then evaluating that as a true statement and running the if block. Man, finding that missing = was PAINFUL back then.

Quote: Romes

In the real world, this all day.

Another fun thing to reminisce over, since this is mainly a "programming" thread. I just had an error, a very simple one, in an application I'm working on. It made me laugh because I personally believe it's the most common error that finally compilers caught up to pointing out. Back in the day you would just get an error or even worse the program would WORK and you'd get the wrong output... the good 'ol double equals.

if (code == x) works for comparison... if(code = x) reassigns and evaluates as true (at least it used to, the compiler I'm working with now in the .NET framework just caught this and threw an error to me). I remember back in college this not being the case... the program would run fine, setting the value of code = x, then evaluating that as a true statement and running the if block. Man, finding that missing = was PAINFUL back then.

Quote: gamerfreak

I also loathe recursion. Fortunately I haven't run into many real-world scenarios where it was required. Iterative solutions are usually more efficient anyway.

Quote: gamerfreak

Challenge #4

Since many of these problems have a recurring theme of involving prime numbers, 
this challenge is to create the fastest primality test you can.

The function IsPrime(N) should take any integer N as a parameter, and return true/false.

Heuristic and Probabilistic tests are acceptable.

Quote: DRich

I would guess that I have used recursion about five times in my 34 years of professional programming.

Quote: ThatDonGuy

Quote: gamerfreak

Challenge #4

Since many of these problems have a recurring theme of involving prime numbers, 
this challenge is to create the fastest primality test you can.

The function IsPrime(N) should take any integer N as a parameter, and return true/false.

Heuristic and Probabilistic tests are acceptable.

By "integer," is it limited to 64-bit or smaller integers, or are unlimited-sized integers (what .NET calls BigInteger) allowed?

In fact, I was just working on this sort of problem - I wanted to see if 10⁶⁵⁵³⁶ + 1 was prime or not, using Miller-Rabin (a probabilistic method).

However, the first step involves calculating 2^(565536) mod (10⁶⁵⁵³⁶ + 1), which takes God's own number of forevers. The second step would be to take that number squared, mod (10⁶⁵⁵³⁶ + 1), and then do that 65,534 more times.

Quote: gamerfreak

I meant integer just as any whole number. You can use any datatype you like.

Quote: gamerfreak

I'm sure it comes up more in particular niches like 3D rendering. But anything that's done recursively can also be done iteratively, and the latter usually makes way more sense to me. There's a few classic problems they gave us in school, like n-queens or Towers of Hanoi where the recursive solutions were much simpler and more readable than their iterative counterparts.

Quote: RS

Quote: gamerfreak

I'm sure it comes up more in particular niches like 3D rendering. But anything that's done recursively can also be done iteratively, and the latter usually makes way more sense to me. There's a few classic problems they gave us in school, like n-queens or Towers of Hanoi where the recursive solutions were much simpler and more readable than their iterative counterparts.

I had an old computer and decided to see how far along it'd get if I let it run all year, recursively getting the next Fibonacci number, without cache(?). By coincidence, I had also run the nyan cat website for whatever reason. I closed the computer, but it under my bed, and let it run. I guess the cord got unplugged sometime and thus, the Fibonacci program failed (or else the number got too big).

So I open the computer on one of the last days of school, because I totally forgot about it. Turns out, the nyan cat website's timer goes off of your system clock, or something like that, so it said I had been watching the nyan cat for like 300,000+ seconds, even though the computer was off most/all of that time.

Quote: ThatDonGuy

As I said in an earlier post, even probabilistic methods can be quite time-consuming for relatively small numbers.

This is one reason why searches tend to be restricted to things like Mersenne primes, where the formula is much faster:

To determine if N = 2^P - 1 is prime, where P is a prime:
S₀ = 4
S_K = (S_K-1² - 2) mod N
N is prime if and only if S_P-2 is zero.

For example, for 2⁵ - 1 = 31:
S₀ = 4
S₁ = 14 mod 31 = 14
S₂ = 194 mod 31 = 8
S₃ = 62 mod 31 = 0
31 is prime

Although, again, it does take a while; on my old 3 GHz processor laptop, it would take 4 weeks of nonstop processing to check a number where P was around 40 million.

Quote: gamerfreak

...I also loathe recursion. Fortunately I haven't run into many real-world scenarios where it was required. Iterative solutions are usually more efficient anyway.

Quote: gamerfreak

It looks like Wolfram Alpha uses the Rabin-Miller test: http://mathworld.wolfram.com/PrimalityTest.html

I'm not sure how they do it so fast on their engine. Maybe they have precalculated tables? There doesn't seem to be a limit to how many digits you can enter, though.

Quote: RS

Bruh, you should write x^2 instead of x2. Makes comprehending this much easier....assuming that's what you mean.

Is this the proper interpretation of the "For example:"

3^2 + 4^2 = 9 + 16 = 25 and that's equal to 5^2 ?

ie: a, b, c = 3, 4, 5 respectively?

Also, should use QUOTE or even SPOILER instead of CODE, because on some of the challenges you have to scroll right to read rest of description.

Quote: RS

I said SOME of the previous challenges, ie: challenge #1.

And putting it in CODE within a SPOILER doesn't halp. Obvii in this case it doesn't matter b/c he's not too long, width-wise. But the earlier ones would still be wonky.

Quote: gamerfreak

Prime challenge is still open (or any other if you can do better). It's a very difficult problem to solve once you get into big numbers.

Challenge #5

A Pythagorean triplet is a set of three natural numbers where a < b < c, for which a^2 + b^2 = c^2

For example:
3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Quote: CrystalMath

Show Spoiler

a=200
b=375
c=425
a*b*c=31875000

public class FindPythagoreanTriplets {

	public static void main(String[] args) {
		new FindPythagoreanTriplets();
	}

	public FindPythagoreanTriplets() {
		boolean solutionFound = false;
		int a = 3;
		int b = 0;
		int c = 0;

		while (1000 % (a + b + c) >0) {
			a++;
			if (a % 2 == 0) // even
			{
				b = a * a / 4 - 1;
				c = b + 2;
			} else {
				b = (a * a - 1) / 2;
				c = b + 1;
			}
		}
		int mult = 1000 / (a + b + c);
		a *= mult;
		b *= mult;
		c *= mult;
		System.out.println(a + " " + b + " " + c + " " + a * b * c);
	}
}

Quote: ThatDonGuy

Quote: gamerfreak

Prime challenge is still open (or any other if you can do better). It's a very difficult problem to solve once you get into big numbers.

Challenge #5

A Pythagorean triplet is a set of three natural numbers where a < b < c, for which a^2 + b^2 = c^2

For example:
3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Who needs programming?

Sometimes, just some good old-fashioned math will do.

C = 1000 - (A + B)
A^2 + B^2 = C^2 = (1000 - (A + B))^2
A^2 + B^2 = 1,000,000 - 2000 A - 2000 B + A^2 + 2AB + B^2
0 = 1,000,000 - 2000 A - 2000 B + 2AB
1000 A + 1000 B = 500,000 + AB
This means AB is a multiple of 1000

1000 B - AB = 500,000 - 1000 A
B = (500,000 - 1000 A) / (1000 - A)
= 1000 (500 - A) / (1000 - A)
= 1000 ((1000 - A) - 500) / (1000 - A)
= 1000 - 500,000 / (1000 - A)
(1000 - A) must be a factor of 500,000
Also, 500,000 / (1000 - A) < 1000, as otherwise B <= 0
This means 500,000 < 1,000,000 - 1000 A
1000 A < 500,000
A < 500
1000 - A > 500

The only integers between 500 and 1000 that are factors of 500,000 = 2^5 x 5^6 are 625 and 800
1000 - A = 625 -> A = 375 -> B = 200, but A < B is given
1000 - A = 800 -> A = 200 -> B = 375 -> C = 425
200^2 + 375^2 = 40,000 + 140,625 = 180,625 = 425^2 = (1000 - (200 + 375))^2