Fun Math Problems!

Xenia

So guys, lately I've been spending a bit of time going through math problems and solving them. I personally have found it fun and think it'd be enjoyable to discuss solutions and such to the problems with others similarly inclined. Below is the link!

https://projecteuler.net/archives

Shachalai

Hi! I was working through these a while back, and didn't get very far - other things came up. While I think the solutions to the first couple were pretty straightforward, I'd like to pick your brain for your solution to problem #3. Looking back at my solution, I approached it using a for, and dividing out all values that came out to x % i = 0 - this reduced the time it took, but there was still a significant amount of time before I got a solution. If I get the time later I might try to implement a sieve of Eratosthenes and attack it that way. What are your thoughts?

Xenia

@Shachalai I honestly did something similar and it took a while. Did a huge array and then looked for remainders...etc. I'm unfamiliar with the method you are referencing so I looked it up! I'd be very interested to see a solution that involves this, should you find one. I may try it myself

Shachalai

@Xenia - So I wasted some time on problem #3, and I ended up with a recursive, iterative algorithm that seems to be able to crunch up any given number and find its highest prime component in mere tenths of a second. I'll give the code below (Java, but straightforward enough that it should make good enough sense!)

The main appeal of this is that it saves on the memory required by Eratosthenes' sieve. I also decided to begin the iteration at 3 and add in increments of 2, so as only to test odd numbers and further reduce the time spent on calculation. As each prime factor is found, the problem recurses, until it reaches a base case where a given number is the maximum prime factor, as determined by the square root test - this is then passed back upward to the top. I've tested it on smaller numbers as well as 600851475143, 67280421310721, and 67280421310719 - good results in all cases.

As solutions go, I'm proud of this one.

public static long getPrimeFactor(long n) { System.out.println("Initial Input: " + n); long test = n; /* We initialize the max as the number itself - if, in the loop below, we reach the bound without this value having changed, we know it's time to stop. */ long max = n; boolean stripped = false; if (test % 2 == 0) { System.out.println("Stripping out factors of 2."); } while (test % 2 == 0) { test /= 2; stripped = true; } if (stripped) { if (test == 1) { max = 2; } else { max = test; } System.out.println("Value stripped down to " + test); } /* The square root is important for cases in which this function actually does handle a prime. Why? Because the square root is the cutoff at which we must have found a multiple by now, and it's conveniently a mere fraction of the larger number. If our maximum (see below) remains the number itself, we're not going to find anything above the square root that will cleanly divide out of it. */ long bound = (long)Math.sqrt(test); System.out.println("Bound: " + bound); /* The bound is offset by one to account for rounding issues that might have resulted from the cast above. Math.sqrt returns a double - we need a whole number. */ for (long i = 3; i <= bound + 1; i += 2) { if (test % i == 0) { test /= i; System.out.println("Divisor Found: " + i + " divides out for " + test); System.out.println("\nRecursing Once More"); max = getPrimeFactor(test); break; } if (test < i) { System.out.println("Breaking - testing number now under iterative value; highest factor found. Passing " + max + " to higher function.\n"); return max; } if (i >= bound && max == n) { System.out.println("Breaking - bound reached; highest factor found. Passing " + max + " to higher function.\n"); return max; } } return max; }

Aishia

I almost wanna disagree with u guys just for suggesting math is fun but I don't wanna be a jerk.

Xenia

@Aishia, we'll just stay in our own little corner of the forums and pretend you never said that.

Shachalai

I took some time away from homework to attack problem #5. This one was pretty easy to do by hand. You just needed the smallest possible number out of which all of the factors of the numbers from 1 to 20 could be taken out - so I broke down the numbers from 1 to 20 into their prime factors and found the overlap. In the end, I got this:

(2^4)*(3^2)*5*7*11*13*17*19 = 232792560