The Project Euler thread

[FFR4EVA_00]

for getting stargroup mad at people leaking answers EXCEPT NOT BECAUSE WE HAVE...
...SPOILER TAGS
http://projecteuler.net/

what you do is simple:
1. make an account
2. open a problem
3. solve the shit out of it
4. rinse and repeat

a lot of the problems, ESPECIALLY later on, require you to find a general solution via programming and plug some ridiculously large parameters into them

anyway, i have completed:
1-13, 16, 18, 28, 33, 52, 67, 79, 108, 110, 157, 267, 355

and i am working on something...

[Zageron]

I've completed 3 of the puzzles so far, mostly because I have very little time to complete them. I will be going in linear order from start to finish! Using C++ as my language because I'm taking a course on it right now.

Excellent idea ffr4eva.
When people run into problems they can post their questions here, just remember to hide your solutions in spoiler tags and try not to ever post the complete solution!

[YoshL]

I've completed 3 of the puzzles so far, mostly because I have very little time to complete them. I will be going in linear order from start to finish! Using C++ as my language because I'm taking a course on it right now.

Excellent idea ffr4eva.
When people run into problems they can post their questions here, just remember to hide your solutions in spoiler tags and try not to ever post the complete solution!

your welcome zageron for telling you about this first :3

i have 1-25, 28 and 30
And i work with java

[reuben_tate]

So far I've done 1,2,3,5 and 6. I just learned about the bigInteger type in Java so now I'll be using that (since the 'long' type isn't ****ing long enough -__-.)

[YoshL]

So far I've done 1,2,3,5 and 6. I just learned about the bigInteger type in Java so now I'll be using that (since the 'long' type isn't ****ing long enough -__-.)

hehe, i did all them without using the bigInteger type.

I used manual math with arrays of integers

[reuben_tate]

arrays of integers

Sounds like how the bigInteger type would be implemented. I'd rather just use that, I find no point in implementing a new data structure if one is already implemented for me to use already. :razz:

[iironiic]

This seems really interesting. I could try to do this on my free time to work on my computer skills.

[emerald000]

I'm currently at 49, using mostly Maple. I have done a couple in C++ too, where speed mattered.

I should get back into it.

Friend key is 62306152188978_1d29510ddc0c52e8c33db3cdbaf399db for interested people.

[leonid]

* Working on P83 *


http://i.imgur.com/ufqg2.png


I'm mostly using Ruby and C

My friend key: 1858629421787_a864c4e88f44e36b8023644c0f14493e

[iironiic]

I just started today and got 1, 2, 3, 5, 6, 7, 9, 10, 16, 20, 25, 45, 48, and 52 solved. I'm using Mathematica here.

Friend Key: 76814575274714_b466b39d7ef7730e66d3da5b16df2525

[reuben_tate]

By the way... Friend Key: 41335338220707_9d1fa87f00c010a47b494214e8b3416e ^_^

EDIT:
I managed to do a few today, and now I have 1-10 done. ^_^



remember to hide your solutions in spoiler tags and try not to ever post the complete solution!

I would, but I don't know how much code I could give before giving the answer away. =/

[Reincarnate]

I was into this for a while but got bored. It's a lot of fun, though. Some of the later problems are very tricky.

[iironiic]

@leonid: I got an answer to #80 but I don't understand why it's not the correct answer. Can you help me figure out the problem in my code?

Just to see if there is something wrong in my code, I tried using my program to help me determine some values. Let's define the digital sum of the first 100 digits of radical n to be f(n).

Are these values correct? I chose a few test numbers just to see if my program is telling me the right digital sum. It did tell me that f(2) = 475 which was given in the problem.

f(3) = 441
f(7) = 398
f(35) = 440
f(69) = 439
f(95) = 460

Any help would be appreciated. Thanks!

[emerald000]

From what I can see, you seem to be rounding off your 100th decimal.

[iironiic]

From what I can see, you seem to be rounding off your 100th decimal.

Well... in the case of radical 2, this is the string of digits I got from my program: {141421356237309504880...}. This is including that one digit to the left of that decimal point because the sum from that digit to the 99th decimal digit is the given 475. What confuses me is this phrase: "first one hundred decimal digits". Does this include or exclude that beginning digit? If it excludes it, the sum should've been 481.

I don't think it's a rounding error because the 100th decimal digit of radical 2 is 7, which would round the 99th decimal digit up. When I created that set of digits, 2 was the last element of that set, so that doesn't seem to be the problem in my program.

[emerald000]

Let's take f(95). Its 100 digits are: (note my program counts backwards)

7, 2, 5, 5, 6, 0, 8, 3, 0, 6, 9, 0, 2, 1, 7, 8, 4, 8, 6, 5, 3, 9, 4, 2, 0, 6, 4, 2, 7, 7, 1, 8, 0, 0, 2, 7, 5, 0, 0, 0, 5, 7, 1, 9, 9, 1, 3, 0, 1, 9, 4, 7, 3, 3, 0, 0, 9, 3, 8, 5, 2, 5, 2, 9, 9, 2, 0, 0, 6, 9, 9, 8, 9, 9, 1, 3, 1, 4, 8, 3, 8, 6, 0, 9, 3, 6, 9, 8, 0, 8, 4, 4, 3, 4, 9, 7, 6, 4, 7, 9

which gives a sum of 459. The 101st decimal is a 6, so if rounded up the 7, you would get to your answer of 460.

And yes the problem isn't clear, but thanks to the example, you can understand they mean to have 100 significant digits.

[Reincarnate]

hmm maybe I will get back into this

seeing leonid ahead of me is making my competitive core act up (by that I mean he could kick my ass at this shit but idgaf)


heh solved problem 68 in excel

[iironiic]

Let's take f(95). Its 100 digits are: (note my program counts backwards)

7, 2, 5, 5, 6, 0, 8, 3, 0, 6, 9, 0, 2, 1, 7, 8, 4, 8, 6, 5, 3, 9, 4, 2, 0, 6, 4, 2, 7, 7, 1, 8, 0, 0, 2, 7, 5, 0, 0, 0, 5, 7, 1, 9, 9, 1, 3, 0, 1, 9, 4, 7, 3, 3, 0, 0, 9, 3, 8, 5, 2, 5, 2, 9, 9, 2, 0, 0, 6, 9, 9, 8, 9, 9, 1, 3, 1, 4, 8, 3, 8, 6, 0, 9, 3, 6, 9, 8, 0, 8, 4, 4, 3, 4, 9, 7, 6, 4, 7, 9

which gives a sum of 459. The 101st decimal is a 6, so if rounded up the 7, you would get to your answer of 460.

And yes the problem isn't clear, but thanks to the example, you can understand they mean to have 100 significant digits.

Thanks! I just got 80 and 69 now! :)

[fido123]

I think I'm going to get started with this. Wanted to work on my programming skills. On my reading week and nobody else I know is so why not. Probably going to work in C or Perl.

[leonid]

Problem 96 is solving 50 sudoku problems. I'm very tempted to cheat

[danny53x]

How do I learn this stuff and become a cool programmer like you guys ; _;

[Reincarnate]

A lot of these problems are more fun if you try to figure out short, efficient codes to solve things.

For instance, here is my code for level 99:

import math

biggestCalculation, rowCounter, answerRow=0,1,0

for line in file('C:\\Users\\Reincarnate\\Desktop\\euler folder\\base_exp.txt'):
numArray = line.split(",")
calculation = math.log(float(numArray[0])) * float(numArray[1])
if calculation > biggestCalculation:
biggestCalculation, answerRow = calculation, rowCounter
rowCounter += 1

print answerRow

If you try to solve it with brute force, you just... aren't going to be able to really do that because the numbers are so big. But a knowledge of math will help you simplify your code into something a lot more palatable. Sometimes you can solve a problem by figuring out something other than what's being asked.

[TC_Halogen]

I'm interested in playing this but I have very little coding experience, haha.

[Reincarnate]

Good way to learn imo

[stargroup100]

How do I learn this stuff and become a cool programmer like you guys ; _;

Project Euler is a set of problems that encourages the use of clever math to simplify programming problems. If you're not inherently good at math, this is gonna be really hard for you no matter how someone teaches you. (Except for the first few problems, which are pretty easy.)

If, on the other hand, you just want to learn programming, this is one way of starting out. At least it gives you a goal.

Man, I need to find more time to do this.

[foilman8805]

Thanks OP for giving me something to do with my brain while I'm in between jobs. This is awesome. I'll be programming in MATLAB/Octave. I just did the first two problems as a bit of a warm up and it was a lot of fun.

Problem 1
%% Euler Project - Problem 1

% Find the sum of all multiples of 3 or 5 below 1000.

sum = 0;

for i=3:999
if rem(i,3) == 0 || rem(i,5) == 0
sum = sum + i;
end
end

sum

Problem 2
Had to first write a function to calculate the numbers in the Fibonacci sequence given any input:
function fib = fibonacci(x)

if x == 0
fib = 0;
elseif x == 1
fib = 1;
else
fib = fibonacci(x-1) + fibonacci(x-2);
end
I then implemented that function in the script file below to find the solution:
%% Euler Project - Problem 2

% By considering the terms in the Fibonacci sequence whose values do not
% exceed four million, find the sum of the even-valued terms.

% First need to find at what term the Fibonacci sequence goes over
% 4 million. I created a supplimentary function file called fibonacci.m
% that calculates the values of the Fibonacci sequence given an input.
% i.e. fibonacci(10) will output 89.

i = 0;
fib = 0;

while fib <= 4000000
i = i + 1;
fib(i) = fibonacci(i);
end

% The loop above identifies that there are 33 values in the Fibonacci sequence
% that don't exceed 4,000,000. Now we will add up each even term.

for j = 1:33
if rem(fib(j),2) == 0
sumfib(j,1) = fib(j);
else
sumfib(j,1) = 0;
end
end

answer = sum(sumfib)

[foilman8805]

Interesting, I actually had to augment the source code in MATLAB in order to do Problem 3.

For some reason MATLAB arbitrarily sets a limit on prime factoring numbers larger than 2^32. Opened up the factor.m and changed it to 2^50, so this solution pretty much became a one-liner.

Problem 3
%% Euler Project - Problem 3

% The prime factors of 13195 are 5, 7, 13 and 29.

% What is the largest prime factor of the number 600851475143?

pf = factor(600851475143);

lpf = max(pf)

[Reincarnate]

hit a wall with this problem :|

[Reshiram]

I'm not gonna use programs. :3

Problem 1:

Take the smallest multiple of 3, add the largest, and multiply by 166.5.
Take the smallest multiple of 5, add the largest, and multiply by 99.5.
Subtract the sum of the common multiples.

[stargroup100]

Upon first glance, that problem looks pretty trivial. But since Rubix is having trouble with it, it must be far from that. LOL

I'll take a crack at it.

[stargroup100]

After taking a look at the problem, here's what I have so far. (I'm sure you already figured out this much, it's all the obvious stuff.)

Problem 355:

For Co(n), let the maximal sum subset be denoted as S.
Each prime factor below n must be found in the factorization of exactly one term in S. As such, we can start off the problem with a base case by creating a subset of all the primes below n (and 1) and then raising each of these primes to the highest power possible to maximize the sum.

However, it is possible that a term has the form (p^a)(q^b), where p and q are primes, if (p^a)(q^b) > p^c + q^d. (where a,b,c,d are the highest possible powers such that each term is less than n)

So the problem becomes reduced to figuring out how to find all of the optimizations for the sum. Chances are, there's some pattern that can use the fact that they give you the values of Co(30) and Co(100).


I'll edit with more content once I figure out more. BRB FOOD LOL

[dag12]

Sounds like you could just write a script for euler's totient function and then run a for loop or something >.>
Though I'm sure there's a more elegant way of doing it.

Also, any way to check answers without registering?

[Reincarnate]

Sounds like you could just write a script for euler's totient function and then run a for loop or something >.>
Though I'm sure there's a more elegant way of doing it.

Also, any way to check answers without registering?

tried this :<

and no you have to register

[stargroup100]

UGH

okay this problem is seriously impossible tackling it the way I'm doing it unless there's some beautiful optimization trick

this is not working

[Reincarnate]

getting close but still off

the way I am tackling it is actually very similar to what you posed above (raising primes to powers) but figuring out where to fix things is tricky

For Co(10):
sorted mainlist [1, 5, 7, 8, 9]
sum of mainlist 30
primes [3, 5, 7]

this is fine

For Co(30):
sorted mainlist [1, 11, 13, 17, 19, 23, 25, 27, 28, 29]
sum of mainlist 193
primes [3, 5, 7, 11, 13, 17, 19, 23, 29]

this is correct too

But for Co(100):
sorted mainlist [1, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 98]
sum of mainlist 1248
primes [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

this is incorrect

[iironiic]

Should 99 be in your sorted mainlist for Co(100)?

I'm thinking about an approach right now, but I haven't come up with anything yet.

[Reincarnate]

Should 99 be in your sorted mainlist for Co(100)?

I'm thinking about an approach right now, but I haven't come up with anything yet.


sorted mainlist [1, 7, 11, 13, 16, 17, 19, 23, 25, 27, 29]
sum of mainlist 188
primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

This is what I get for Co(30) without that optimization and going for power-raising alone. Obviously I need to toss 28 into this beast, but in doing so I must remove 7 and 16.

EDIT: What I do now, in general is create the "naive prime-raised" solution and then add numbers to the solution and remove all coprime elements, then check to see if that sum is better than what I had before. If so, update solution. If not, kept what I had before and try a new number.

[Reincarnate]

Hm somehow it's one off, wtf


sorted mainlist [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]
sum of mainlist 1355
primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

[LongGone]

Problem 355:

However, it is possible that a term has the form (p^a)(q^b), where p and q are primes, if (p^a)(q^b) > p^c + q^d. (where a,b,c,d are the highest possible powers such that each term is less than n)


Could this be extended to cover cases of (p^a)(q^b)(r^c) > p^d + q^e + r^f etc. ? I can't think of an example though. The huge annoyance here is that the list of numbers are exhaustive, everytime you form a set of p,q there could be another set which may use them more efficiently instead (pointing out the obvious though)

[stargroup100]

I have a conjecture that a term of the form (p^a)(q^b)(r^c) is never found in a maximal sum subset, but I'm not sure if I can prove it. If this is true it would at least make the problem significantly easier. I forgot to mention this earlier.

[Reincarnate]

can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)

[stargroup100]

lurker had the same problem

I'm trying to find the error as well

[LongGone]

can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)


Since you are one off from the actual answer (changing from odd to even), it implies that one set of (p^a)(q^b) should be degrouped, or grouped (e.g. 5*19=95(odd), or 5^a+19^b=even). Swapping pairs of number products will not change the odd/even parity
The main concern are the primes <10 in this case (because obviously you can't multiply two primes >10 that will result in <100 product)
So the usable primes are 2,3,5,7
Since you used up all 4 and ended up with 1355; If 1356 was not a mistake, that means that you have to degroup one of those primes and leave one as a natural power of itself (which is counterintuitive)
...So either the 13 people who solved didnt bother checking Co(100), or I'm missing something rofl
(or a rare case of a possible product of three primes, which idk if its plausible)

For a possible general approach, to try to maximise sum, we can start by getting rid of all the small primes
So e.g. for Co(100), start with 11,13,17,19. With your current solution we got: 99 (3,11), 95 (5,19), and 92 (2,23), 91 (7,13). Could there be a possible solution using 17 in place of 23?

[stargroup100]

edit2: ok I was being stupid

EDIT: Rubix, your answer might be wrong but it looks pretty close :D

[Reincarnate]

A step-by-step runthrough of the Co(100) process:

initial naive list from prime-raising alone: [1, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97] with sum 1263

adding 99 to the list and removing non-coprimes to test [1, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 97, 99]
Updating list because biggestsum 1263 is less than 1270
adding 98 to the list and removing non-coprimes to test [1, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 98, 99]
adding 96 to the list and removing non-coprimes to test [1, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 96, 97]
adding 95 to the list and removing non-coprimes to test [1, 13, 17, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 95, 97, 99]
Updating list because biggestsum 1270 is less than 1321
adding 94 to the list and removing non-coprimes to test [1, 13, 17, 23, 29, 31, 37, 41, 43, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 94, 95, 97, 99]
adding 93 to the list and removing non-coprimes to test [1, 13, 17, 23, 29, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 93, 95, 97]
adding 92 to the list and removing non-coprimes to test [1, 13, 17, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
Updating list because biggestsum 1321 is less than 1326
adding 91 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]
Updating list because biggestsum 1326 is less than 1355
adding 90 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 90, 91, 97]
adding 88 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 88, 89, 91, 95, 97]
adding 87 to the list and removing non-coprimes to test [1, 17, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 87, 89, 91, 92, 95, 97]
adding 86 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 86, 89, 91, 95, 97, 99]
adding 85 to the list and removing non-coprimes to test [1, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 85, 89, 91, 92, 97, 99]
adding 84 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 84, 89, 95, 97]
adding 82 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 82, 83, 89, 91, 95, 97, 99]
adding 81 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 91, 92, 95, 97]
adding 80 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 80, 83, 89, 91, 97, 99]
adding 78 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 78, 79, 83, 89, 95, 97]
adding 77 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 92, 95, 97]
adding 76 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 76, 79, 83, 89, 91, 97, 99]
adding 75 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 75, 79, 83, 89, 91, 92, 97]
adding 74 to the list and removing non-coprimes to test [1, 17, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 74, 79, 83, 89, 91, 95, 97, 99]
adding 72 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 72, 73, 79, 83, 89, 91, 95, 97]
adding 70 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 70, 71, 73, 79, 83, 89, 97, 99]
adding 69 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 69, 71, 73, 79, 83, 89, 91, 95, 97]
adding 68 to the list and removing non-coprimes to test [1, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 68, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 66 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 66, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 65 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 65, 67, 71, 73, 79, 83, 89, 92, 97, 99]
adding 64 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 63 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 63, 67, 71, 73, 79, 83, 89, 92, 95, 97]
adding 62 to the list and removing non-coprimes to test [1, 17, 29, 37, 41, 43, 47, 53, 59, 61, 62, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 60 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 60, 61, 67, 71, 73, 79, 83, 89, 91, 97]
adding 58 to the list and removing non-coprimes to test [1, 17, 31, 37, 41, 43, 47, 53, 58, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 57 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 57, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 56 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 56, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 55 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 54 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 54, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 52 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 52, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 51 to the list and removing non-coprimes to test [1, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 50 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 50, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 49 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
adding 48 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 48, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 46 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 46, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 45 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 44 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 44, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 42 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 42, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97]
adding 40 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 40, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 39 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 39, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97]
adding 38 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 38, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 36 to the list and removing non-coprimes to test [1, 17, 29, 31, 36, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 35 to the list and removing non-coprimes to test [1, 17, 29, 31, 35, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 97, 99]
adding 34 to the list and removing non-coprimes to test [1, 29, 31, 34, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 33 to the list and removing non-coprimes to test [1, 17, 29, 31, 33, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 32 to the list and removing non-coprimes to test [1, 17, 29, 31, 32, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 30 to the list and removing non-coprimes to test [1, 17, 29, 30, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97]
adding 28 to the list and removing non-coprimes to test [1, 17, 28, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 27 to the list and removing non-coprimes to test [1, 17, 27, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 26 to the list and removing non-coprimes to test [1, 17, 26, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 25 to the list and removing non-coprimes to test [1, 17, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97, 99]
adding 24 to the list and removing non-coprimes to test [1, 17, 24, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 23 to the list and removing non-coprimes to test [1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 22 to the list and removing non-coprimes to test [1, 17, 22, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 21 to the list and removing non-coprimes to test [1, 17, 21, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97]
adding 20 to the list and removing non-coprimes to test [1, 17, 20, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 19 to the list and removing non-coprimes to test [1, 17, 19, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97, 99]
adding 18 to the list and removing non-coprimes to test [1, 17, 18, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 16 to the list and removing non-coprimes to test [1, 16, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 15 to the list and removing non-coprimes to test [1, 15, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 14 to the list and removing non-coprimes to test [1, 14, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 13 to the list and removing non-coprimes to test [1, 13, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
adding 12 to the list and removing non-coprimes to test [1, 12, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 11 to the list and removing non-coprimes to test [1, 11, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 10 to the list and removing non-coprimes to test [1, 10, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 9 to the list and removing non-coprimes to test [1, 9, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 8 to the list and removing non-coprimes to test [1, 8, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 7 to the list and removing non-coprimes to test [1, 7, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
adding 6 to the list and removing non-coprimes to test [1, 6, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 5 to the list and removing non-coprimes to test [1, 5, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97, 99]
adding 4 to the list and removing non-coprimes to test [1, 4, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 3 to the list and removing non-coprimes to test [1, 3, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 2 to the list and removing non-coprimes to test [1, 2, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]

sorted, final mainlist [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]
sum of mainlist 1355

[stargroup100]

Your solution is too linear. You should take into consideration the possible case that immediately adding the largest possible number won't optimize the overall total.

It's possible there is a different combination of the primes that rounds out to a better sum. I recommend this method:

- Separate primes into 3 categories: between 2 and sqrt(n), between sqrt(n) and n/2, and the others
- Add up all of the primes in the last category. These don't change.
- The terms in the second category have the most room for possible optimizations, and therefore should try to be optimized first. They obviously cannot be paired with a prime from its own category, so pair it with a prime from the first category. Try every combination here.
- The last possible case is that 2 primes from the first category might be paired together. Consider this generalization last.

Do it this way and see if you can get to 1356.


NOTE: I'm not sure if the last step is necessary, I'm trying to see if I can prove whether or not that last step is needed.

[Reincarnate]

It's not adding just the largest possible number -- here, it's adding all possible numbers from 2 to (N-1) and checking how it affects the total after removing non-coprimes

[LongGone]

For 100, we have 25 odd primes (including 1), and one even 2. The sum of 25 odd primes (raised to any power) sum up to odd, adding the power of 2 still makes it odd

However, since we can group primes, we most likely will be grouping the smallest primes. There are 4 primes <sqrt100, 2 3 5 7. By grouping, we have 22 odd numbers and 2. 2 can be combined with an odd number leaving 21 odd numbers and one even number. The sum of that is odd. 1356 is even (?????????)

Possible explanation would be that the solution for 1356 involves -not- grouping one of 3, 5 or 7 and leaving it as its natural power. The most plausible is 3^4=81. Alternatively, there may be a case where there is a coprime which is the product of 3 primes

[stargroup100]

FFFF YOU ARE RIGHT

im dumb

[Reincarnate]

.ok apparently my problem is that it risks getting caught in local optima. when it detects a better sum, it may be adding a number (and keeping it) that winds up not being a part of the final solution (or prevents another number from doing the same). Going from 1 to n gives me a diff number from n to 1.

[stargroup100]

that's what I was trying to say lol

[Reincarnate]

ah ok misunderstood what you meant

[stargroup100]

what the hell I went back to look at the problems I already solved in project euler and I cannot for the life of me remember how I did these LOL

all I remember is that I did most of these with pencil/paper

[stargroup100]

Maybe something like this (building off SG's idea)

stuff

not quite

0 <= x < sqrt(n) list: [(1), 2, 3, 5]
sqrt(n) <= x < n/2 list: [7, 11, 13]
n/2 <= x list: [17, 19, 23, 29]

however, but my idea doesn't take into account longgone's new input, the fact that some of the primes from the first group might stand by themselves. however, if you combine your method with mine it should account for both cases pretty well.

[FFR4EVA_00]

psst
{1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 88, 89, 91, 95, 97}
i went off the fact that 81 is the largest number less than 100 of the form a^b

[stargroup100]

Thanks to lurker and LG I can fix up my method a bit.

Okay, here's my updated algorithm. It seems to be pretty tight for the most part, but it is still fairly brute force and assumes two conjectures:

- A term in a maximal sum subset can never have more than two unique prime factors.
- When optimizing the sum of a subset by choosing to multiply two powers of primes, the two primes are never both below sqrt(n).

Assuming these conjectures, we use the method:
- Separate primes into 3 categories: between 2 and sqrt(n), between sqrt(n) and n/2, and the others
- Add up all of the primes in the last category. These don't change.
- Each of the terms in the first category can either be left by itself or paired with a term from the second category. Consider and test every case.

The total number of possible subsets to test for is exactly 9507!/(9421)!.

Hopefully we can do a little bit better than that, as this number is in the order of about 10^(well over 200).

[Reincarnate]

I'm trying to find something that doesn't require bruteforce (most of the problems I've solved don't require it) -- this problem is bugging the hell out of me because I can't figure out anything more elegant

[cry4eternity]

I just found this on Friday. Solved 1-22 as well as 67 now :p. This is actually pretty fun.

[stargroup100]

I'm trying to find something that doesn't require bruteforce (most of the problems I've solved don't require it) -- this problem is bugging the hell out of me because I can't figure out anything more elegant

feelin ya bro

but it's possible this is along the lines of what they want. after all, they ARE programming problems.

[FFR4EVA_00]

i'm gonna go ahead and drop a gigantic hint for 354 since the upper bound is so insane i have no chance of programming it correctly:
2L^2/3 = 2*3^(any non-negative integer)*n^2*(6p+1)^4*(6q+1)^4*(6r+1)^2
n must only be a multiple of 2 and any primes of the form 6k-1
6p+1, 6q+1 and 6r+1 are distinct prime numbers; p, q and r are integers

[stargroup100]

Right now I'm trying to figure out methods to significantly reduce the number of calculations needed to solve this, whether it's skipping possible subsets or finding a totally new method.

However, it's getting late and I'm getting sleepy, difficult to focus. I'll work more on this tomorrow.

[FFR4EVA_00]

i'm seriously advocating that the quickest method would be starting at the set for Co(100) and drawing each Co(n+1) from Co(n)

[FFR4EVA_00]

it's predictable though
basically it comes down to an iterative process
i think the hardest part would be how to arrange the arrays for optimal speed
i was thinking that you would basically set it up like this:
[a_2, a_3, a_5, a_7, ..., a_p]
p is the largest prime below n, and the a_i are not necessarily distinct, so that when you actually wanted to find Co(n) you'd remove duplicates and add 1

[FFR4EVA_00]

5 : [4, 3, 5]
6 < 4+3, don't insert
6 : [4, 3, 5]
7 has one prime factor, insert
7 : [4, 3, 5, 7]
8 has one prime factor, insert
8 : [8, 3, 5, 7]
9 has one prime factor, insert
9 : [8, 9, 5, 7]
10 < 8+5, don't insert
10 : [8, 9, 5, 7]
11 has one prime factor, insert
11 : [8, 9, 5, 7, 11]
12 is skipped, prime factors are too small
12 : [8, 9, 5, 7, 11]
13 has one prime factor, insert
13 : [8, 9, 5, 7, 11, 13]
14 < 8+7, don't insert
14 : [8, 9, 5, 7, 11, 13]
15 > 9+5, insert
15 : [8, 15, 15, 7, 11, 13]
16 has one prime factor, insert
16 : [16, 15, 15, 7, 11, 13]
17 has one prime factor, insert
17 : [16, 15, 15, 7, 11, 13, 17]
18 is skipped, prime factors are too small
18 : [16, 15, 15, 7, 11, 13, 17]
19 has one prime factor, insert
19 : [16, 15, 15, 7, 11, 13, 17, 19]
20 gets a bit more complex
20 drags in 16 and 15, but 15 is also a multiple of 3
it quickly becomes apparent that the only thing one could do with the 3 is use 9
20+9 < 16+15, don't insert
20 : [16, 15, 15, 7, 11, 13, 17, 19]
21+5 > 15+7, insert
[16, 21, 5, 21, 11, 13, 17, 19]
20 < 16+5, don't attempt
21 : [16, 21, 5, 21, 11, 13, 17, 19]
22 < 16+11, don't insert
22 : [16, 21, 5, 21, 11, 13, 17, 19]
23 has one prime factor, insert
23 : [16, 21, 5, 21, 11, 13, 17, 19, 23]
24 is skipped, prime factors are too small
24 : [16, 21, 5, 21, 11, 13, 17, 19, 23]
25 has one prime factor, insert
25 : [16, 21, 25, 21, 11, 13, 17, 19, 23]
26 < 16+13, don't insert
26 : [16, 21, 25, 21, 11, 13, 17, 19, 23]
27 has one prime factor, insert, 7 is left over
[16, 27, 25, 7, 11, 13, 17, 19, 23]
14 < 16+7, don't attempt
27 : [16, 27, 25, 7, 11, 13, 17, 19, 23]
28 > 16+7, insert
28 : [28, 27, 25, 28, 11, 13, 17, 19, 23]
29 has one prime factor, insert
29 : [28, 27, 25, 28, 11, 13, 17, 19, 23, 29]
30 is skipped, too many prime factors
30 : [28, 27, 25, 28, 11, 13, 17, 19, 23, 29]

[FFR4EVA_00]

like i said: the set doesn't have to be distinct in this arrangement
i could easily just leave empty spaces but hey, programming doesn't really like those
and 16 only has one factor i have no idea what you're talking about
what's going on with 21 is this: if a < b < c, then ac+b > ab+c
i just threw in the snippet about testing 20 because i figured a program would try it

[LongGone]

#1. I think because he's listing the numbers in order of smallest prime factors, and some numbers are made up of two prime factors so he repeated them
#2. Probably "set 1" (i.e. primes below sqrt n for Co(n), using the product of two numbers from set 1 would be a waste

I had this thought, but I don't know if its useful. See if anyone finds a use of it.
As Stargroup listed 3 sets of numbers, for Co(n^2), where set 1 is for primes<n and set 2 between n and (n^2)/2. I propose listing numbers of set 1 in the form of n-a, and set 2 in the form n+b

For products not involving powers higher than 1 for each term, we have to fulfill this condition (n-a)(n+b)≤n^2 [e.g. for Co(100), (10-5)(10+9)<10^2]

Expand to n^2-na+nb-ab≤n^2

hence n(b-a)≤ab (but we don't know if a or b is bigger or smaller)
or b≤na/(n-a)

ok now what

[FFR4EVA_00]

longgone is correct on 1 and 2
here's what you're confused about if i am right:

[a_2, a_3, a_5, a_7, ..., a_p]
p is the largest prime below n, and the a_i are not necessarily distinct, so that when you actually wanted to find Co(n) you'd remove duplicates and add 1

20 gets a bit more complex
20 drags in 16 and 15, but 15 is also a multiple of 3
it quickly becomes apparent that the only thing one could do with the 3 is use 9
20+9 < 16+15, don't insert
20 : [16, 15, 15, 7, 11, 13, 17, 19]
21+5 > 15+7, insert
[16, 21, 5, 21, 11, 13, 17, 19]
20 < 16+5, don't attempt

i have no idea why you're confused
what's going on is i give the program a number and its one or two prime factors
if there's 1, it automatically goes into the list (and the consequences of said action are played out)
if there's 2, i retrieve the numbers in the list that share the two factors
so for 20, i grab a_2 and a_5, while for 21, i grab a_3 and a_7
the idea is we're seeing if a set with n in it produces a larger sum than just copying over the previous set
of course, i can't forget that one or both of the numbers i retrieved might be duplicates
in both cases, i find that a_3 = a_5

i now need to find whether i can shuffle around the three primes ((2, 3, 5) for 20, (3, 5, 7) for 21) and produce a sum larger than that of the a_i i retrieved

for 20, i already know i'm using 2 and 5 as part of 20, so i need to figure out what to do with 3
i could simply choose to multiply it by itself, giving 3*3 = 9
so now i check to see if (a_2, a_3, a_5) = (20, 9, 20) is better than (a_2, a_3, a_5) = (16, 15, 15); in the quote i find it is not
i can't multiply 3 by 7 because 21 is larger than 20, so i am done

as for 21, i already know i'm using 3 and 7 as part of 21, so i need to figure out what to do with 5
i could simply leave it as 5, so i'm testing if (a_3, a_5, a_7) = (21, 5, 21) is better than (15, 15, 7); in the quote i find that it is
however, there's also the possibility that i could combine a_2 and a_5, making both 20; in the quote i find it doesn't work, and i can't mess with a_3 now since i changed it, so i am done

[Knut.Angstrom]

A step-by-step runthrough of the Co(100) process:

initial naive list from prime-raising alone: [1, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97] with sum 1263

adding 99 to the list and removing non-coprimes to test [1, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 97, 99]
Updating list because biggestsum 1263 is less than 1270
adding 98 to the list and removing non-coprimes to test [1, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 98, 99]
adding 96 to the list and removing non-coprimes to test [1, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 96, 97]
adding 95 to the list and removing non-coprimes to test [1, 13, 17, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 95, 97, 99]
Updating list because biggestsum 1270 is less than 1321
adding 94 to the list and removing non-coprimes to test [1, 13, 17, 23, 29, 31, 37, 41, 43, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 94, 95, 97, 99]
adding 93 to the list and removing non-coprimes to test [1, 13, 17, 23, 29, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 93, 95, 97]
adding 92 to the list and removing non-coprimes to test [1, 13, 17, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
Updating list because biggestsum 1321 is less than 1326
adding 91 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]
Updating list because biggestsum 1326 is less than 1355
adding 90 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 90, 91, 97]
adding 88 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 88, 89, 91, 95, 97]
adding 87 to the list and removing non-coprimes to test [1, 17, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 87, 89, 91, 92, 95, 97]
adding 86 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 86, 89, 91, 95, 97, 99]
adding 85 to the list and removing non-coprimes to test [1, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 85, 89, 91, 92, 97, 99]
adding 84 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 84, 89, 95, 97]
adding 82 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 82, 83, 89, 91, 95, 97, 99]
adding 81 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 91, 92, 95, 97]
adding 80 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 80, 83, 89, 91, 97, 99]
adding 78 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 78, 79, 83, 89, 95, 97]
adding 77 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 92, 95, 97]
adding 76 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 76, 79, 83, 89, 91, 97, 99]
adding 75 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 75, 79, 83, 89, 91, 92, 97]
adding 74 to the list and removing non-coprimes to test [1, 17, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 74, 79, 83, 89, 91, 95, 97, 99]
adding 72 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 72, 73, 79, 83, 89, 91, 95, 97]
adding 70 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 70, 71, 73, 79, 83, 89, 97, 99]
adding 69 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 69, 71, 73, 79, 83, 89, 91, 95, 97]
adding 68 to the list and removing non-coprimes to test [1, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 68, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 66 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 66, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 65 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 65, 67, 71, 73, 79, 83, 89, 92, 97, 99]
adding 64 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 63 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 63, 67, 71, 73, 79, 83, 89, 92, 95, 97]
adding 62 to the list and removing non-coprimes to test [1, 17, 29, 37, 41, 43, 47, 53, 59, 61, 62, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 60 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 60, 61, 67, 71, 73, 79, 83, 89, 91, 97]
adding 58 to the list and removing non-coprimes to test [1, 17, 31, 37, 41, 43, 47, 53, 58, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 57 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 57, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 56 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 56, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 55 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 54 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 53, 54, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 52 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 52, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 51 to the list and removing non-coprimes to test [1, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 50 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 50, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 49 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
adding 48 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 47, 48, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 46 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 46, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 45 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 44 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 43, 44, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 42 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 41, 42, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97]
adding 40 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 40, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 39 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 39, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97]
adding 38 to the list and removing non-coprimes to test [1, 17, 29, 31, 37, 38, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 36 to the list and removing non-coprimes to test [1, 17, 29, 31, 36, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 35 to the list and removing non-coprimes to test [1, 17, 29, 31, 35, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 97, 99]
adding 34 to the list and removing non-coprimes to test [1, 29, 31, 34, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 33 to the list and removing non-coprimes to test [1, 17, 29, 31, 33, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 32 to the list and removing non-coprimes to test [1, 17, 29, 31, 32, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 30 to the list and removing non-coprimes to test [1, 17, 29, 30, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97]
adding 28 to the list and removing non-coprimes to test [1, 17, 28, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 27 to the list and removing non-coprimes to test [1, 17, 27, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 26 to the list and removing non-coprimes to test [1, 17, 26, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 25 to the list and removing non-coprimes to test [1, 17, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97, 99]
adding 24 to the list and removing non-coprimes to test [1, 17, 24, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 23 to the list and removing non-coprimes to test [1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 22 to the list and removing non-coprimes to test [1, 17, 22, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 21 to the list and removing non-coprimes to test [1, 17, 21, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97]
adding 20 to the list and removing non-coprimes to test [1, 17, 20, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 19 to the list and removing non-coprimes to test [1, 17, 19, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97, 99]
adding 18 to the list and removing non-coprimes to test [1, 17, 18, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 16 to the list and removing non-coprimes to test [1, 16, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 15 to the list and removing non-coprimes to test [1, 15, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97]
adding 14 to the list and removing non-coprimes to test [1, 14, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 99]
adding 13 to the list and removing non-coprimes to test [1, 13, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
adding 12 to the list and removing non-coprimes to test [1, 12, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 11 to the list and removing non-coprimes to test [1, 11, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 10 to the list and removing non-coprimes to test [1, 10, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99]
adding 9 to the list and removing non-coprimes to test [1, 9, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 8 to the list and removing non-coprimes to test [1, 8, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 7 to the list and removing non-coprimes to test [1, 7, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 92, 95, 97, 99]
adding 6 to the list and removing non-coprimes to test [1, 6, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97]
adding 5 to the list and removing non-coprimes to test [1, 5, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 97, 99]
adding 4 to the list and removing non-coprimes to test [1, 4, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]
adding 3 to the list and removing non-coprimes to test [1, 3, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97]
adding 2 to the list and removing non-coprimes to test [1, 2, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 95, 97, 99]

sorted, final mainlist [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]
sum of mainlist 1355

Your sum 1355 is not correct since you use 99 instead of 88 giving 1356

[Knut.Angstrom]

1+64+81+25+49+11+13+17+19+23+29+31+37+41+43+47+53+ 59+61+67+71+73+79+83+89+97+
(95-25-19)+(91-49-13)+(88-64-11) =1356

[fido123]

Worked on this for a little bit one night. Did 1, 2, and 6 all in C:


Question 1:
#include <stdio.h>

int main() {
int sum=0, x;
for (x=1; x < 1000; x++) if (x % 3 == 0 || x % 5 == 0) sum += x;
printf ("%d\n", sum);
}


Question 2:

#include <stdio.h>

int main() {
int sum=0, x=0, y=1, z;
do {
z = x + y;
x = y;
y = z;
if (y % 2 == 0) sum += y;
} while (y < 4000000);
printf ("%d\n", sum);
}


Question 6:

#include <stdio.h>
#include <math.h>

int main() {
int x, sq=0, sum=0;
for (x = 1; x <= 100; x++) {
sq += pow (x, 2);
sum += x;
}
sum = pow (sum, 2);
x = sum - sq;
printf ("%d\n", x);
}

Easy stuff so far but I'm not really all that knowledgeable about math at all so I'm not sure how far I'll get with this lol.

[FFR4EVA_00]

Okay but what about needing to retrieve something lost? For instance, the solution to Co(100) includes a 17, which gets removed back in Co(51)
17 is brought back as part of Co(95)
95+17 > 85+19
it's the exact same phenomenon that occurs with 21 and 5 replacing 15 and 7

Also some numbers will have more than 1 unique prime factor
i heard whispers that this is true but i am trying to rigorously disprove it

[FFR4EVA_00]

yeah, i never said what those were, i'm sorry
a_p is just the number that is divisible by p in whatever set we're looking at (since we're supposed to be looking at coprime sets there is exactly one a_p for every p but not all a_p are unique)
the reason why i'm duplicating the terms is that i think it will be easier for a computer to traverse

[LongGone]

Also some numbers will have more than 1 unique prime factors (e.g. 30 -> unique primes 2, 3, and 5)

Stargroup originally came up with the idea that having a composite being a product of 3 primes isn't efficient and will never be part of the maximum set. I had a thought and will back this up by saying that, in order for a composite to be in the set it has to have at least two terms from group 1 (otherwise it will exceed n). And it is intuitively known to be not efficient to group together two sets of numbers from set 1 (as you remove the chance of it being paired up with a set 2 number, which is more efficient to produce larger composites. So I'll assume that the solution set involves composites with at most two distinct primes (raised to whatever power). So in this case, 30 which has 3 prime factors will not be part of the solution set of Co

[Reincarnate]

Stargroup originally came up with the idea that having a composite being a product of 3 primes isn't efficient and will never be part of the maximum set. I had a thought and will back this up by saying that, in order for a composite to be in the set it has to have at least two terms from group 1 (otherwise it will exceed n). And it is intuitively known to be not efficient to group together two sets of numbers from set 1 (as you remove the chance of it being paired up with a set 2 number, which is more efficient to produce larger composites. So I'll assume that the solution set involves composites with at most two distinct primes (raised to whatever power)

I think this is a reasonable assumption to make

[FFR4EVA_00]

@Reincarnate- that is correct, yes
now i'm messing around with a brute-force solution of sorts though, NOTHING like what i was doing before

[FFR4EVA_00]

!!!!!!!!!
http://imageshack.us/photo/my-images/90/355v.png/

[Reincarnate]

congrats FFR4, nicely done

[stargroup100]

http://img268.imageshack.us/img268/5532/eulero.jpg

I got 0 eulerian points for this. mad

[iironiic]

Got #71 with pencil and paper xD

EDIT: Nice FFREva!

[FFR4EVA_00]

http://projecteuler.net/eulerians
"For the twelve most recent problems the difference, d, in the length of time to solve the problem (in minutes) between each member and the slowest in the table is calculated and log2(max(d,2)) points are awarded."
so every time someone solves the problem, the points of everyone who already solved it go up
in other words cosmovibe has 8 points now

[Reincarnate]

I suck at this problem pretty hard, admittedly. It's always a split between making some assumption about the composite set (which yields the wrong answer) or trying all possible combinations (too large to run in this lifetime) -- the same problem that's been knocking at me from the beginning of this damn problem -_-

[Reincarnate]

someone shoot me please

[leonid]

don't worry you are not alone

[pmonibuv1]

I have 2 answered. Go me! \o/

[XCV]

I saw this about a week ago and I'm up to 8 or 9...impressive right? xD

[stargroup100]

dude rubix just use my conjectures

they're pretty much correct

here I'll even repost them again


1. A term in a maximal sum subset can never have more than two unique prime factors.
2. When optimizing the sum of a subset by choosing to multiply two powers of primes, the two primes are never both below sqrt(n).
3. For high values of n, no term in a maximal sum subset can be composed of only a single prime factor below sqrt(n) raised to a power, except for values close to sqrt(n).

[iironiic]

I got #72 in about two seconds. Only took one line of coding in Mathematica haha. I'll look into the most recent problem when I have more time.

[Reincarnate]

dude rubix just use my conjectures

they're pretty much correct

here I'll even repost them again


1. A term in a maximal sum subset can never have more than two unique prime factors.
2. When optimizing the sum of a subset by choosing to multiply two powers of primes, the two primes are never both below sqrt(n).
3. For high values of n, no term in a maximal sum subset can be composed of only a single prime factor below sqrt(n) raised to a power, except for values close to sqrt(n).


I'm aware of all these -- it doesn't address the problem I'm having unfortunately

[Reincarnate]

omfg

http://i.imgur.com/AMkOe.png

Unfortunately had to do some manual work (it COULD be automated but it just wasn't worth the headache)

[stargroup100]

gj

right now I'm workin on uh, 351 I believe


the only roadblock I ran into is the fact that the summatory of the euler totient function is retardedly slow to calculate for very high values

if I can find an easy way to compute that then I have my answer

[Reincarnate]

Actually SG the totient function is fine for that problem (that's what I used and I solved it earlier today) -- you just need a more efficient function

[stargroup100]

for the summation of totient? really?

[Reincarnate]

for the summation of totient? really?


yes

[stargroup100]

okay I made a small improvement on the speed of computation but it's not anything significant. what the hell did you do

[Reincarnate]

Try messing around with http://pari.math.u-bordeaux.fr/

[leonid]

yeeeeessssshhhhh

http://i.imgur.com/QFUIm.png

[hondaracer600]

Reincarnate

I have been lurking on this thread for a few days. I wanted to see if I could pick your brain a bit on problem 355.

I have been getting close by implementing FFR4EVA_00's method of [a_2,a_3,a_5...a_p]. It is basically bumping the exponent of all primes < N

But alas, the answer is incorrect.

Did you use a method like this? Or did you go down a different path?

[stargroup100]

You have to do a lot more with that because the method for checking optimization possibilities from there is much too broad and will take forever.

If you try to optimize that you'll be doing well over 10^(300+) calculations, which your program will not finish within the lifespan of the universe.

[Reincarnate]

Reincarnate

I have been lurking on this thread for a few days. I wanted to see if I could pick your brain a bit on problem 355.

I have been getting close by implementing FFR4EVA_00's method of [a_2,a_3,a_5...a_p]. It is basically bumping the exponent of all primes < N

But alas, the answer is incorrect.

Did you use a method like this? Or did you go down a different path?


Raising the exponents of the initial "<N" prime list is just a starting point -- from there you need to create prime composites that you can add into the list. Just a matter of determining which composites are worth adding and which are useless. Some of them will be ambiguous -- which is what was tripping me up for the better part of 1.5 days. I ultimately had to do that part manually. I'm not sure if FFR4EVA had a fully automated solution or not, but mine wasn't.

[stargroup100]

holy crap pari/gp lololol

this thing rules lololololololol

****in hell

[hondaracer600]

Raising the exponents of the initial "<N" prime list is just a starting point -- from there you need to create prime composites that you can add into the list. Just a matter of determining which composites are worth adding and which are useless. Some of them will be ambiguous -- which is what was tripping me up for the better part of 1.5 days. I ultimately had to do that part manually. I'm not sure if FFR4EVA had a fully automated solution or not, but mine wasn't.


Define "Manually". Are we talking pen and pad here?

[stargroup100]

Yes, the four of us that solved it all did the last part manually.

[Reincarnate]

Solved 190 with Excel... <3

[hondaracer600]

Solved 190 with Excel... <3

Wow you guys really are gods among men. What is your education? I am working on a MS in CS.

I am working on the < 100 problems. My Advanced Algorithms teacher is giving a massive amount of extra credit if you can show you solved one of them.

I am using the 3 conjectures and the way FFREVA started to get a pretty good start, but I am still falling short.

[stargroup100]

Undergraduate sophomore. Took a basic course in programming and that's it.

Honestly, I just love Project Euler problems because you don't need to be super crazy good at programming to solve them, as long as you have a good sense with math.

My code for problem 355 (excluding the last part which was manual) was completely done with the most basic programming concepts and nothing else. For loops, while loops, a small handful of dedicated functions, and that's it.

[hondaracer600]

Undergraduate sophomore. Took a basic course in programming and that's it.

Honestly, I just love Project Euler problems because you don't need to be super crazy good at programming to solve them, as long as you have a good sense with math.

My code for problem 355 (excluding the last part which was manual) was completely done with the most basic programming concepts and nothing else. For loops, while loops, a small handful of dedicated functions, and that's it.

Where did the pen and pad come in? I find it hard that in ~18k elements, your pen is going to make a difference.

[Reincarnate]

There is no literal pen and pad needed -- just some manual fudging to the program

EDIT: Solved all the triangle-numbered (http://www.mathematische-basteleien.de/triangularnumber.htm) problems

http://i.imgur.com/40zeV.png

Almost got 354 solved... just one piece missing but I'm too tired to fiddle with it tonight. night yall

[foilman8805]

Took a stab at a few more problems tonight:

Problem 28
MATLAB is a little cheap with respect to creating a spiral function - it already has one built in, so I utilized it to find my solution. Also, most of my codes for Project Euler are scripts, but for some reason I decided to actually make this one a function. No real reason.
%% Project Euler - Problem 28

% What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral
% formed in the same way?

function diag_sum = eulerproject28(n)
tic
spiral_matrix_a = spiral(n);
spiral_matrix_b = rot90(spiral_matrix_a);

trace_a = zeros(n,1);
trace_b = zeros(n,1);

for i = 1:n
trace_a(i) = spiral_matrix_a(i,i);
trace_b(i) = spiral_matrix_b(i,i);
end

trace_array = [trace_a; trace_b];
trace_array = trace_array(:);
trace_array_unique = unique(trace_array);

diag_sum = sum(trace_array_unique);
toc
end

Problem 29
This one turned out to be pretty easy. Just used a nested for loop and then eliminated all of the elements I didn't want in my vectors (i.e. repeating values).
%% Project Euler - Problem 29

% How many distinct terms are in the sequence generated by ab for 2 <= a <=
% 100 and 2 <= b <= 100?
tic
for a = 2:100
for b = 2:100
a_b(a,b) = a^b;
end
end
a_b_lin = a_b(:);
a_b_unique = unique(a_b_lin);
[c,d] = find(a_b_unique <= 0);
a_b_final = a_b_unique(c+1:end)';
distinct_terms = length(a_b_final)
toc

I also came up with brute force solutions to Problems 71-73, which actually work with small sample sizes, but MATLAB is pretty horrible with big numbers as well as large volumes of numbers, so it takes a crap when I run it and says it doesn't have enough memory. I bought an 8GB flashdrive online today that's ReadyBoost enabled, so hopefully when I get it I can run my programs.

[FFR4EVA_00]

solved 108 in notepad
solved 110 in a spreadsheet

[hondaracer600]

Undergraduate sophomore. Took a basic course in programming and that's it.

Honestly, I just love Project Euler problems because you don't need to be super crazy good at programming to solve them, as long as you have a good sense with math.

My code for problem 355 (excluding the last part which was manual) was completely done with the most basic programming concepts and nothing else. For loops, while loops, a small handful of dedicated functions, and that's it.

What principles/theories did you end up trying to use? Or did you just use heuristics and the conjectures put forth earlier in the thread?

So is the best place to start a bumped set of Primes < N? Then start doing prime compositions and replacing?

Also, what method did you use to determine if a composite was useful? I am struggling with that aspect. I can't seem to find a pattern.

[Reincarnate]

What principles/theories did you end up trying to use? Or did you just use heuristics and the conjectures put forth earlier in the thread?

So is the best place to start a bumped set of Primes < N? Then start doing prime compositions and replacing?

Also, what method did you use to determine if a composite was useful? I am struggling with that aspect. I can't seem to find a pattern.






Are you sure? Big spoilers ahead...



You can always turn back, you know.






Alright, here goes...

The question is asking you to maximize the sum of pairwise-coprime integers from 1 to N. So Co(100) represents the maximal sum of a set of pairwise coprime integers.

Numbers are coprime if their greatest common divisor is 1 (i.e. no shared factors otherwise). Not all numbers in a pairwise-coprime list need to be prime numbers themselves -- they just need to have unique prime factors that no other numbers share. For instance, neither 26 nor 27 are prime, but they are coprime because they share no factors between their prime factorizations (compare [13,2] versus [3], respectively). So, since you're looking to maximize these numbers, you're basically looking for a maximal combination/alteration of prime factors (composites).

Most of us here made the same assumptions. Namely, it's a reasonable assumption to make that for high N, all numbers in the optimal set will consist of two unique prime factors each. This is because you can look at the prime factors for various N's, and you'll notice that there are a LOT more primes above sqrt(N) than there are for below sqrt(N) for high N (this is intuitive though). In the optimal solution, an optimal number COULD consist of three prime factors, but at least two of them would need to be from the sub-sqrt(N) set (because multiplying two or more numbers from the set of primes above sqrt(N) will give you something higher than N) -- this means you forgo pairing a lower prime with a higher one and you prevent it from being used elsewhere, which is likely to be inefficient when you consider how many higher primes come with larger N's. And, similarly, an optimal number probably isn't composed of a single prime raised to a high power by itself because it tends to fall short (this also becomes more apparent as you solve higher and higher N's). So, odds are, every number in the solution set will consist of a prime number from the >sqrt(N) group and a prime number from the <sqrt(N) group raised to some higher power.

In other words, a composite number will be in the form pq^a where p and q are prime numbers from each side of the sqrt(N) fence. Remember that adding a composite means you must remove the pre-existing higher prime p from your list as well as any power-raised lower-prime q (in order to preserve the pairwise-comprime status of your list).

The tough part is figuring out a good way to do all this. Hope this helps get you on the right track.

[hondaracer600]

Is cursing allowed on this forum? Because #$@# problem 355.

I am not a math guy, I can normally get these using CS algorithms, but there just isn't a solid method I can come up with to solve this. Did your solutions work for all the examples? e.g. Co(10),Co(30) & Co(100)


So what I am doing is breaking the problem into 3 "ranges"
range 1: 0 < x < sqrt(n)
range 2: sqrt(n) <= x < n/2
range 3: n/2 <= x <= n

So for range 1, I find all primes in that range (not many) and then start to augment them like Reincarnate mentioned. I find a list of prime compositions such the equation (p^a)(q) > p^c+q. where p < sqrt(n) and q > sqrt(n)

For range 2: IDFK. THis is where I am pretty screwed.

For range 3: I add all the primes in that set to my solution set, since there is no way to optimally augment the elements.

[Reincarnate]

I'll give you an example using Co(30), where the sqrt is 5.47722558
Here are the primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. Primes below the sqrt are 2, 3, and 5, so these are your q's.
So now you want to grow each prime as high as it can go exponentially. You get:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 29] (for a sum of 187)

So how can we maximize the q's? You need to pair them with p's, or the primes between sqrt(N) and N/2, or [7, 11, 13]

So it's a matter of testing [2, 3, 5] with [7, 11, 13], keeping in mind that adding a composite prime will change the value sum of the entire list by pq^a-p-q^b, because by adding a composite prime, you must remove the original p and your max-power-raised q.

So, take the q's versus the p's and take a look at which combinations yield more value (making sure that your pq^a values are <=N of course). We discard solutions that don't work (either they take away value or the composites will be larger than N):

2 vs. 7: 7*2^a-7-2^4, maximized when a=2, for a value of +5
2 vs. 11: 11*2^a-11-2^4, does not work for any positive value of a, discard
2 vs. 13: 13*2^a-13-2^4, does not work for any positive value of a, discard
3 vs. 7: 7*3^a-7-3^3, does not work for any positive value of a, discard
3 vs. 11: 11*3^a-11-3^3, does not work for any positive value of a, discard
3 vs. 13: 13*3^a-13-3^3, does not work for any positive value of a, discard
5 vs. 7: 7*5^a-7-5^2, does not work for any positive value of a, discard
5 vs. 11: 11*5^a-11-5^2, does not work for any positive value of a, discard
5 vs. 13: 13*5^a-13-5^2, does not work for any positive value of a, discard

Luckily, this one's easy to figure out. The only viable choice is 2 vs. 7, where the maximum composite is 7*2^2 or 28 for an added value of +5.

So we pop in 28 to our list:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 28, 29]
Subtract your p (7) and your q^b (16), and pop in the final 1 to the start of the list (1 is in every solution set):
[1, 11, 13, 17, 19, 23, 25, 27, 28, 29]
And voila, the sum is 193.

For higher N's, such as 100, you will find that certain composites won't be coprime with each other, so you can't just pop everything into the list that contributes the highest value.

[iironiic]

I'll give you an example using Co(30), where the sqrt is 5.47722558
Here are the primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. Primes below the sqrt are 2, 3, and 5, so these are your q's.
So now you want to grow each prime as high as it can go exponentially. You get:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 29] (for a sum of 187)

So how can we maximize the q's? You need to pair them with p's, or the primes between sqrt(N) and N/2, or [7, 11, 13]

So it's a matter of testing [2, 3, 5] with [7, 11, 13], keeping in mind that adding a composite prime will change the value sum of the entire list by pq^a-p-q^b, because by adding a composite prime, you must remove the original p and your max-power-raised q.

So, take the q's versus the p's and take a look at which combinations yield more value (making sure that your pq^a values are <=N of course). We discard solutions that don't work (either they take away value or the composites will be larger than N):

2 vs. 7: 7*2^a-7-2^4, maximized when a=2, for a value of +5
2 vs. 11: 11*2^a-11-2^4, does not work for any positive value of a, discard
2 vs. 13: 13*2^a-13-2^4, does not work for any positive value of a, discard
3 vs. 7: 7*3^a-7-3^3, does not work for any positive value of a, discard
3 vs. 11: 11*3^a-11-3^3, does not work for any positive value of a, discard
3 vs. 13: 13*3^a-13-3^3, does not work for any positive value of a, discard
5 vs. 7: 7*5^a-7-5^2, does not work for any positive value of a, discard
5 vs. 11: 11*5^a-11-5^2, does not work for any positive value of a, discard
5 vs. 13: 13*5^a-13-5^2, does not work for any positive value of a, discard

Luckily, this one's easy to figure out. The only viable choice is 2 vs. 7, where the maximum composite is 7*2^2 or 28 for an added value of +5.

So we pop in 28 to our list:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 28, 29]
Subtract your p (7) and your q^b (16), and pop in the final 1 to the start of the list (1 is in every solution set):
[1, 11, 13, 17, 19, 23, 25, 27, 28, 29]
And voila, the sum is 193.

For higher N's, such as 100, you will find that certain composites won't be coprime with each other, so you can't just pop everything into the list that contributes the highest value.


Interesting approach here. I will look more into this and I will try to implement this in my current Mathematica program.

In the meanwhile, I solved a few more problems :)

[hondaracer600]

I'll give you an example using Co(30), where the sqrt is 5.47722558
Here are the primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. Primes below the sqrt are 2, 3, and 5, so these are your q's.
So now you want to grow each prime as high as it can go exponentially. You get:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 29] (for a sum of 187)

So how can we maximize the q's? You need to pair them with p's, or the primes between sqrt(N) and N/2, or [7, 11, 13]

So it's a matter of testing [2, 3, 5] with [7, 11, 13], keeping in mind that adding a composite prime will change the value sum of the entire list by pq^a-p-q^b, because by adding a composite prime, you must remove the original p and your max-power-raised q.

So, take the q's versus the p's and take a look at which combinations yield more value (making sure that your pq^a values are <=N of course). We discard solutions that don't work (either they take away value or the composites will be larger than N):

2 vs. 7: 7*2^a-7-2^4, maximized when a=2, for a value of +5
2 vs. 11: 11*2^a-11-2^4, does not work for any positive value of a, discard
2 vs. 13: 13*2^a-13-2^4, does not work for any positive value of a, discard
3 vs. 7: 7*3^a-7-3^3, does not work for any positive value of a, discard
3 vs. 11: 11*3^a-11-3^3, does not work for any positive value of a, discard
3 vs. 13: 13*3^a-13-3^3, does not work for any positive value of a, discard
5 vs. 7: 7*5^a-7-5^2, does not work for any positive value of a, discard
5 vs. 11: 11*5^a-11-5^2, does not work for any positive value of a, discard
5 vs. 13: 13*5^a-13-5^2, does not work for any positive value of a, discard

Luckily, this one's easy to figure out. The only viable choice is 2 vs. 7, where the maximum composite is 7*2^2 or 28 for an added value of +5.

So we pop in 28 to our list:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 28, 29]
Subtract your p (7) and your q^b (16), and pop in the final 1 to the start of the list (1 is in every solution set):
[1, 11, 13, 17, 19, 23, 25, 27, 28, 29]
And voila, the sum is 193.

For higher N's, such as 100, you will find that certain composites won't be coprime with each other, so you can't just pop everything into the list that contributes the highest value.


Thanks for that. It has gotten me so close. SO So so VERY close.

I have a function that does the primeCompositions, which returns a map of the following form:
{prime: (exponent, max, midPrime)}
Where "prime" is the prime from < sqrt(N), "exponent" is the exponent of that prime ((p^exponent)*q), "max" is the value, and midPrime is from the middlePrime group. So I put every element from the (p^a*q) equation into the map and then attempt to manipulate it later.

Basically if pq^a-p-q^b > 0, I put all those elements into the list.

I know that "88" is part of the solution set for Co(100), but I can't figure out from this method out 88 gets into the set. For Co(100) my primeCompositions function returns:

{2: (2, 92, 23), 3: (2, 99, 11)}

((2^2)*23 > 64+23) and (3^2)*11 > 27+11)

Right now Co(10) = 30, Co(30)=193, Co(100)=1275 :(

[Reincarnate]

Thanks for that. It has gotten me so close. SO So so VERY close.

I have a function that does the primeCompositions, which returns a map of the following form:
{prime: (exponent, max, midPrime)}
Where "prime" is the prime from < sqrt(N), "exponent" is the exponent of that prime ((p^exponent)*q), "max" is the value, and midPrime is from the middlePrime group. So I put every element from the (p^a*q) equation into the map and then attempt to manipulate it later.

Basically if pq^a-p-q^b > 0, I put all those elements into the list.

I know that "88" is part of the solution set for Co(100), but I can't figure out from this method out 88 gets into the set. For Co(100) my primeCompositions function returns:

{2: (2, 92, 23), 3: (2, 99, 11)}

((2^2)*23 > 64+23) and (3^2)*11 > 27+11)

Right now Co(10) = 30, Co(30)=193, Co(100)=1275 :(





I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.

[hondaracer600]

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.


AHHH i'm so close! I got Co(10), Co(30) and Co(100). I just need to mess around a bit more. I am gonna freak when I get this

Thanks again.

[Teddy_scfa]

I turned back.

[hondaracer600]

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.



Does 829,241,239 mean anything to you? I think I found what you mean by "Manual"

[stargroup100]

that's nowhere near the answer to 355, if that's what you're referring to

[hondaracer600]

that's nowhere near the answer to 355, if that's what you're referring to

Nonono. Im on the order of 1.7e9 right now. I was just saing those numbers near sqrt(n) are requiring a little work

[stargroup100]

Nonono. Im on the order of 1.7e9 right now. I was just saing those numbers near sqrt(n) are requiring a little work

oh

then yes, yes they do

[hondaracer600]

oh

then yes, yes they do

Were you on the 1.7 bill range?

[FFR4EVA_00]

level 1 get!

[iironiic]

Problem 356 will be accessible in 1 day, 9 hours, 5 minutes (Sat, 29 Oct 2011, 08:00 [America/New_York])
Current date/time on server: Fri, 28 Oct 2011, 03:55

Hahaha I'm excited!!

[FFR4EVA_00]

So Much Bullshit

[hondaracer600]

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.


I keep getting 1726269243. Which is wrong. High or low? there are 4 numbers that are giving me grief, and I can't figure out what to do.

[leonid]

(Quote post to avoid clicking so many buttons)
I don't like how this thread essentially gives out major hints for the last problems.
Can we stop giving hints and/or wrong attempts if a couple of posts are not enough?

hondaracer600, no offense but could you stop asking people to feed you with direct hints?? It defeats the whole purpose of project euler.

[hondaracer600]

[spoiler]
Again, it's collision testing. What I did, after creating my list of viable pq^a candidates, was a lazy "greedy" approach of just arranging my list of prime composites by the value they add (pq^a-p-q^b), and then, for a given q, take the composite that contributed the most value.

Obviously, this results in a few p-collisions.
So, it would appear you're still not sure what to do in the event of p-collisions?
Well, I'll tell you.
Alright. This is where my "manual" work came in. When I had a p-collision between two composites, I looked at their q values. For a shared p, one composite will have a bigger q than the other. You want to modify the one with a lower q.
You're wondering how to modify it, aren't you?
Quite literally, I looked at the value that the composite prime contributed for that composite of lower q, and I hardcoded it into an if-statement. If the value a composite is about to add to my list equals that, then don't add it. It'll find the next-best pq^a naturally. If you're dealing with the smallest prime p above sqrt(200k), then just remove the worse of the duplicates in terms of value added. I did this like 10 times or so and eventually my list was optimized without any p-collisions.

That's why I did it manually -- it was easier to just kick out the conflicting primes instead of coding and testing a collision subroutine.


That's what I do. Not correctly apparently. FUUUUU. thanks again.

[leonid]

BAM!!

http://i.imgur.com/WoyuU.png

[iironiic]

Nice leonid. I'm stuck on it haha.

EDIT: On another note:

Yesssss!!

http://www.flashflashrevolution.com/images/uploads/iironiic1319997452EULER.png

[Reincarnate]

Problems like 356 are annoying because they're battles against the precision of your programming language... in huge ways

aka you need some other method to solve it because rounding errors will be the death of you no matter what.


Personally I am trying to find a clever way to express a cubic polynomial root as a series that I can apply some exponent/modulus math to.

[iironiic]

Personally I am trying to find a clever way to express a cubic polynomial root as a series that I can apply some exponent/modulus math to.


That's what I'm doing too, but I can't figure anything out for it yet.

I'm also trying to figure out some useful properties of the floor function but none of them seems useful.

[Reincarnate]

That's what I'm doing too, but I can't figure anything out for it yet.

I'm also trying to figure out some useful properties of the floor function but none of them seems useful.

There's nothing particularly interesting about floor function as far as I can tell -- that's just there to make it clear that the decimals need to be lopped off so that you can take the last 8 digits of the end result. The tough part is getting the right value for x^987654321 because the right value is heavily dependent on how precise x is -- but the level of precision you'd need is stupidly high.

[stargroup100]

There's nothing particularly interesting about floor function as far as I can tell -- that's just there to make it clear that the decimals need to be lopped off so that you can take the last 8 digits of the end result. The tough part is getting the right value for x^987654321 because the right value is heavily dependent on how precise x is -- but the level of precision you'd need is stupidly high.

Stupidly high is an understatement. You'd need several billion digits if you were to brute force it LOL.

in other words i cant solve this problem and it's pissing me the hell off

[Reincarnate]

leonid, you're a beast

[Reincarnate]

This was the code for my "naive" attempt (note: does not work because it requires more precision than we have access to, doing it this way. Still works great for smaller powers, though):


import os, sys
from math import sqrt, acos, cos, pi


def bigRoot(a,b,c):
return (2 * sqrt(-(b - a*(a / 3.0))/3.0)) * cos(((acos((-((2*(a / 3.0)**2- b)*((a / 3.0)) + c)/2.0/ (sqrt(-(b - a*(a / 3.0))**3/27.0)))))/3.0)) - (a / 3.0)

def powRed(a,b,m):
if b==1:
return a
if b%2==0:
return powRed((a*a)%m,b/2,m)
else:
return (a*powRed((a*a)%m,(b-1)/2,m)) % m


sumTotal=0

for n in range(1,31):
a, b, c = -pow(2,n), 0, n #corresponds to x^3+ax^2+bx+c
print "N=" + str(n) + ", biggest root = " + str(bigRoot(a,b,c))
sumTotal=sumTotal+ int(powRed(bigRoot(a,b,c),987654321,10**8))

print "Last eight digits of power-sum: " + str(sumTotal % 10**8)

[iironiic]

Got #205 with pencil and paper. Took forever but at least I didn't have to sleep through my english class hahaha.

EDIT: Just got #53 with pencil and paper :)

[stargroup100]

The problems that I have found to be the most rewarding to solve with pencil/paper rather than coding are: ("*" following the number indicates a high difficulty, "#" following a number represents a fairly tedious problem in terms of manual work)

6, 9, 26*, 28, 29#, 33, 39, 69, 108, 138*#

I have obviously not looked at every problem between 1 and 108, but when I find more problems that can be done with pencil/paper I'll edit this.

[leonid]

Join #euler in irc.chatspike.net

[Knut.Angstrom]

Do you know the definition of triangle numbered problem?

[iironiic]

Do you know the definition of triangle numbered problem?

Anything of the form k(k+1)/2 for some k in the natural numbers:

1, 3, 6, 10, 15, 21, etc.

Also, got #216 and #218 (o: Thinking about #241 now.

[Reincarnate]

I've been cranking down hard on some of the easier problems (I'm still stuck on a few of the 300's that I find interesting) -- just did 216 myself and pretty much bruteforced it (lame).

[iironiic]

I've been cranking down hard on some of the easier problems (I'm still stuck on a few of the 300's that I find interesting) -- just did 216 myself and pretty much bruteforced it (lame).

I did the same thing. Felt lame as well but hey, at least we got the answer haha.

EDIT: Got #179 just now.

[Reincarnate]

stuck on 126 ffffuuuu

nvm got it

[Reincarnate]

Pumped out a few more today... 137 was a bit of a challenge, but the solution is an interesting one. I'm only on page 4/8 of total problems (when arranging them by # solved) and the questions are definitely getting tougher. Problems 338's been out since May 2011 and it still hasn't reached 100 solvers yet. 344 looks beastly, too.

Hit level 7, going to bed.

[x_lambourghini_x]

I tried, but because I can't do math for the life of me, I ragequit.

[leonid]

Just solved p357. Could've solved it faster but I was being dumb... oh well.

[iironiic]

Got 357 as well. I should try thinking of more efficient ways of solving it.

[Izzy]

This looks cool, I might start working on these when I have time.

[FFR4EVA_00]

has anyone solved problem 44 and if so
is the answer less than 1 million

[iironiic]

has anyone solved problem 44 and if so
is the answer less than 1 million

No

[FFR4EVA_00]

goddamnit

[Reincarnate]

has anyone solved problem 44 and if so
is the answer less than 1 million

Nope.

Hint below for generalized elaboration, however:

I remember this problem, though -- IMO it's a poorly-designed one. You can make a really stupid assumption about the answer and it'll turn out to be correct and save you a hell of a lot of runtime. Similarly, the problem is more programmatical than mathematical. You can brute force it (using a non-naive approach) in just a couple seconds (given the stupid assumption).



Stuck on 152, which is silly because it should be easy

[reuben_tate]

Just did number 15. I thought it was a little too easy; there wasn't even any programming needed to do this problem.


Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20x20 grid?

[Reincarnate]

Solved 349 -- posted my solution in the thread (check if out if you get the chance -- it has a nice pretty text output, haha)

[stargroup100]

Yeah the earlier problems are kinda stupid simple sometimes, but only because they're the early problems.

[leonid]

level 7 !! \o/

http://i.imgur.com/00swO.png

[Reincarnate]

I still don't have 356 or 152 :<

[leonid]

Got 358 \o/

[Reincarnate]

saaaaaaame, what a ffffffffuuu problem

[Reincarnate]

We need more people to be in on this -- come join us in chat!

irc.chatspike.net
room Euler

[iironiic]

I haven't been doing these problems lately. I"ll get back to them when I have the time

[reuben_tate]

We need more people to be in on this -- come join us in chat!

irc.chatspike.net
room Euler

I would, but I'm not as pr0 as you guys and I would feel left out. :<

Anyhow, just got 20 and 48. ^_^

EDIT: And 18! :razz:

18)
20) Find the sum of digits in 100!
48) Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.

[Choofers]

lol I'm reinstalling visual basic for this

[stargroup100]

I would, but I'm not as pr0 as you guys and I would feel left out. :<

Anyhow, just got 20 and 48. ^_^

EDIT: And 18! :razz:

I don't know about the other guys, but I'm willing to help anyone who is having trouble with problems I know how to do.

If you ever want to talk to me on irc, just type any form of my name and it'll ping me.

[Reincarnate]

fffffffffffffffffffffffff---

[Reincarnate]

you better check yourself









































http://i.imgur.com/U0MfQ.png

BEFORE YOU WRECK YOURSELF >:O

[leonid]

359 is going to be REALLY tough. 27 minutes in and nobody has solved yet wtf ??


EDIT: GET OWNED !!!!!!!!!!!!!!!

http://i.imgur.com/OOmhl.png

[FFR4EVA_00]

I COMPLETELY forgot about 359 happening today

[Reincarnate]

http://i.imgur.com/DTBtc.png

w00t

[LongGone]

I obtained the general formula for 359 but idk how to code/program (and 358 too)

):

[Reincarnate]

Learn either Python or C++ (Python is my baby although Ruby is leonid's) -- both come in handy depending on the problem.

C++ is better for speed (if I know the problem is going to require ugly bruteforce), but stuff like Python/Ruby is easy to script with.

[Reincarnate]

fffff some of these are getting pretty tough

[Reincarnate]

welp

360 is pretty much 353 on steroids

[leonid]

360 ;_;

[leonid]

http://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gif

http://i.imgur.com/9jhYB.png
http://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gifhttp://www.flashflashrevolution.com/vbz/customavatars/avatar1585800_139.gif

[yelm]

Gosh, can anybody give any hint about 360? I made an optimized bruteforce and it's still slow :( Anything I can do is prove that answer is divisible by 6 :(
357,358 and 359 was much simpler.

[linky123456]

well this looks like fun :D

[leonid]

now I'm level 8 :') (200 problems solved)

http://i.imgur.com/7Onr5.png

[reuben_tate]

now I'm level 8 :') (200 problems solved)

http://i.imgur.com/7Onr5.png

Congrats! I'd have more problems solved, if only I could stop coming up with algorithms that takes O(2^n) time. >_<

[Reincarnate]

http://i.imgur.com/ljYrY.png

awwww yeah

[leonid]

dam nice

[PriestREA]

For the sake of adding to the Project Euler thread, finished 1-10 so far.

[Reincarnate]

http://i.imgur.com/9pe4t.png
Made it from level 10 to level 12 (50 more problems, or 300 total solved) -- and that's at a nonstop rate. I got a LOT of easy problems knocked out today (including a few brute-forcers that I've been letting run on my desktop while I work on the laptop).

What a rush ;-; Taking a break for now. My brain's frazzled and I feel like I've been a slave to this site for eons now.

[iironiic]

Congrats Marcus! I haven't have the time to tackle this lately, but I'll change that in the next few days!

[Reincarnate]

Some of my solutions suck though.

leonid, remember that question with the 2000x2000 matrix thing? I brute-forced it with squaring ;-;

One guy had a hilarious solution to... can't remember which problem, but he brute-forced it in 500+ hours in VBA, lmfao.

[stargroup100]

why have so few people solved 177? looks pretty easy to me

gonna attempt that next I think

[Reincarnate]

I've been working on 177 for like a week. It's hard. It was one of those annoying "low-numbered but crazy" problems like 152 that give a lot of trouble and are hard to get out of the way.

Also the inverse phi one was kinda cool.

[PriestREA]

Done some work on Project Euler, well on my way to level 3 with 53 problems solved.

[Reincarnate]

http://i.imgur.com/FJzRc.png

YEEEEEEEEESSSSSSSSSSSSSS!!!!!!!

This was such a hard problem, it's not even funny. ;-;

[Reincarnate]

doot doot doot

http://i.imgur.com/UxyI8.png

procrastinated on this one pretty hard

[robertsona]

starting this right now, have no idea what to expect

edit: (feeling really stupid but) do you need, like, a computer input type program for this. guh

[Izzy]

I haven't started it, but I think you would normally write a program that spits out text into a console and then you copy and paste that as your answer.

[Reincarnate]

starting this right now, have no idea what to expect

edit: (feeling really stupid but) do you need, like, a computer input type program for this. guh

You just need any programming language.

I usually use either Python or C++ (mostly Python).

[Reincarnate]

http://i.imgur.com/LhE8V.png

Bam! Oh how I have wanted this badge for so very long

[Reincarnate]

Almost forgot to post this one:

http://i.imgur.com/2kDzF.png

[Reincarnate]

100 paasento

[C1004A]

project euler dominated :o

[Reincarnate]

great, now i have that feeling i did when i was on kongregate
with nothing left to work on, things become a slow-trickle waiting game


what have i done

[Reincarnate]

lucked out getting the Perfection badge just in time... this new one is a doozy.

[FFR4EVA_00]

383 looks easy as ****
EDIT: as of 5:29 i have a formula for T5(5^n)
EDIT: as of 5:38 i have a general formula for T5(n)... sorta
EDIT: BAM
http://i46.tinypic.com/wa3jwk.png
the most coding i did was with spreadsheets and i found the answer about 2 hours from starting work on it

[Reincarnate]

Haven't even looked at 383 yet... tried 382 for a bit and couldn't solve it, so I took a break, haha.

[Reincarnate]

Decided to try 383. Got a working approach for T5(n) very quickly but I don't think it's scalable yet

EDIT: Figured out T5(5^n)

[iironiic]

I'm working on 383 too. I got a formula for f5(n!) but nothing for T5(n) yet :(

[Reincarnate]

Just gotta knock back 382 and that's that
Not really a fan of recurrence-relation problems but meh

[Reincarnate]

Got 382 earlier then 385 and 386 this weekend once some free time opened up -- still need 384 to re-100%

[Reincarnate]

Weeee, got it -- 100% again

http://i.imgur.com/KNAD7.png

[Reincarnate]

390 should be ok, but I am fearing 391. it's likely going to be brutal

[Reincarnate]

ffffffffuuuuuuuuucccccccccckkk

[Reincarnate]

I've got a program that will solve for M(n) but is not scalable to higher levels

You know it's a tough problem when very few of the usual heavy hitters have solved it, even 24 hours after its release.

[Reincarnate]

391 solved, back to 100%. That one was tricky.

[Reincarnate]

damn it now I have to find something else to sink time into when I'm at home

[Bluearrowll]

Until 392..

[Reincarnate]

decided to get into SPOJ recently in the meantime

[Choofers]

So I'm teaching myself BASIC and I figure that this would be a good way to learn
Unfortunately, I can't even solve problem 1 because I'm a dumb shit rofl (I could solve on paper, but that'd take forever)

There's something wrong with my code.
Don't hate, I haven't touched a programming language since high school (so 2008)


count = 0
addNumber = 0
a$ = ""

[loop]
count = count + 1
if (count mod 3 = 0) or (count mod 5 = 0) then
addNumber = addNumber + count
print "Count = "; count
print "addNumber ="; addNumber
else
print "Count = "; count
print "addNumber ="; addNumber
end if

if count < 1000 then
goto [loop]
else
print addNumber
end if
stop



Some info regarding my code:
The a$ was a variable I used to make the code stop during the first if-then statement. It originally looked like this:

print "Count = "; count
print "addNumber ="; addNumber
print "press any button and enter to continue"
input a$
else

I know using goto makes me look like a newb programmer, but that's fine. I'm not too keen on streamlining my code just yet.

[Choofers]

Shit, I think I know what's wrong with my code. 2 mod 3 would end being 0. So it's adding to addNumber before it should be.

[Reincarnate]

2 mod 3 is 2

(x mod y is the remainder of x / y)

PS use Python instead, it's cooler



sumTotal = 0
num = 1
while num < 1000:
if (num % 3 == 0) or (num % 5 == 0):
sumTotal = sumTotal + num
num = num + 1
print sumTotal


Damn thing doesn't save formatting but w/e

[Choofers]

I am obviously retarded, because I'm still stuck on problem 1. I mirrored that code into BASIC (took me a bit to figure out while loops), and now I'm getting a huge number, literally twice as large as my original code. I downloaded Python though, let's see how that goes.

ugh I can't wait to go back to school rofl

edit: python's gay, going back to BASIC

[leonid]

ur gay

[Choofers]

thank you for your help

edit: Took a break from problem 1 and went onto a random problem under 10. Solved 6 after a bit of trouble, I was finding the difference for the first 1000 natural numbers and not 100. Whoops.

[Reincarnate]

What is your current code for problem 1

and seriously stop using BASIC, aaaaoooogugughghhh

[Choofers]

whats wrong with basic rofl, I download python 2.whatever and wanted to kill the lady making my chai latte.

I'll post my code tonight after I mess with it a bit.

[Choofers]

I actually never touched my code that night...

i touched myself.................

[Reincarnate]

100% again. Last problem was tough.

[Reincarnate]

Anyone else still playing any?

Eagerly awaiting #402

[infinity.]

i started on tuesday. i've got 17 correct answers so far, but i only know a semester's worth of python haha. the problems are starting to get out of my threshold

my account name is lpauley if you can do anything with it

[infinity.]

whats wrong with basic rofl

also

EVERYTHING

[Reincarnate]

You use friend codes instead of usernames

[Reincarnate]

fuck

[infinity.]

74432925402977_edc6e913519320b2bbdef524348d21cc

[Reincarnate]

403/404 were tricky, but quite fun in the end

[kaiten123]

started this a little while ago (i think registered years ago lol, but never solved anything til just recently), a few days of work and i'm at lvl 2.
probably wont solve much for a couple weeks because finals but some of these are pretty interesting.

[axith]

Just stumbled across this thread. I have 38 problems solved. I learned a bit of python for these problems. My problem is that I can often see an easy, brute force solution, but I don't have the math knowhow to get stuff solved in less than a few weeks (or at least such math isn't that intuitive to me). I think it's time to revisit these torturous problems.

[Reincarnate]

Practice makes perfect -- the more you solve, the more you'll learn

[axith]

for all it's worth, here's my friend key: 83532459359302_e704d4c6b1d37a7739410f38da156b2a

[axith]

So which keywords make python read from a text file? My eyes are buggy from looking though online reference stuff and there's several problems that require it..

[emerald000]

You will want to use:

file = open('/path/to/file')

file.read() # Returns whole file.
file.readline() # Will return line by line.
file.readlines() # Returns a list of every line.

file.close() # Close the file after you have read everything you need.

[Reincarnate]

added you, emerald

[Reincarnate]

406 was a kick in the face for me -- I was making it harder than it needed to be

[kaiten123]

just did 96 which was cool since i never really used recursion in a way that was non-trivial before
no idea how you guys do some of the higher numbered ones, highest one i did was 243, which for some reason is many times easier than everything around it, didnt even write any code.

edit: got to lvl 3 :)

[kaiten123]

brute forced 407 lol
never saw that box at the bottom right before, is that new? or does it pop up when you solve something recent?
http://i259.photobucket.com/albums/hh308/kaiten1/p407_zps22bf8279.png

[Reincarnate]

tis new

[leonid]

i should get back to solve rest of the problems

[Reincarnate]

Managed to squeak onto the 408 list; hard one

[Arkuski]

This is pretty awesome I'm giving some of these a go

[Reincarnate]

I think 411 will be on the easier side this week... I hope.

[Reincarnate]

411 wasn't too bad -- pretty much an exercise in programming

[Reincarnate]

414: Got this one somewhat quickly but it took me forever to bring it down to under a minute, lol. In the end got it to 10 seconds.

[Reincarnate]

415... only 3 solvers after 7 and a half hours.

Yeah I can pretty much kiss my 100% goodbye

It's been fun, PE :(