PDA

View Full Version : The Project Euler thread

Pages : [1] 2

FFR4EVA_00
10-19-2011, 10:41 PM
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
10-19-2011, 11:43 PM
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
10-20-2011, 12:54 AM
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!

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

reuben_tate
10-20-2011, 06:09 AM
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
10-20-2011, 10:30 AM
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
10-20-2011, 08:51 PM
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
10-20-2011, 09:03 PM
This seems really interesting. I could try to do this on my free time to work on my computer skills.

emerald000
10-20-2011, 11:45 PM
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
10-20-2011, 11:47 PM
* Working on P83 *

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

I'm mostly using Ruby and C

My friend key: 1858629421787_a864c4e88f44e36b8023644c0f14493e

iironiic
10-21-2011, 12:24 AM
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
10-21-2011, 02:20 AM
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
10-21-2011, 09:39 AM
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
10-21-2011, 01:00 PM
@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
10-21-2011, 01:35 PM
From what I can see, you seem to be rounding off your 100th decimal.

iironiic
10-21-2011, 02:47 PM
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
10-21-2011, 03:17 PM
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
10-21-2011, 07:20 PM
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
10-21-2011, 08:37 PM
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
10-21-2011, 10:58 PM
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
10-21-2011, 11:25 PM
Problem 96 is solving 50 sudoku problems. I'm very tempted to cheat

danny53x
10-21-2011, 11:48 PM
How do I learn this stuff and become a cool programmer like you guys ; _;

Reincarnate
10-22-2011, 12:06 AM
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

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:
rowCounter += 1

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
10-22-2011, 03:16 AM
I'm interested in playing this but I have very little coding experience, haha.

Reincarnate
10-22-2011, 02:20 PM
Good way to learn imo

stargroup100
10-23-2011, 03:38 AM
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
10-23-2011, 03:53 AM
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

foilman8805
10-23-2011, 04:11 AM
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
10-23-2011, 11:23 AM
hit a wall with this problem :|

Reshiram
10-23-2011, 01:33 PM
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
10-23-2011, 02:04 PM
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
10-23-2011, 02:18 PM
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
10-23-2011, 03:27 PM
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
10-23-2011, 03:28 PM
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
10-23-2011, 04:11 PM
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
10-23-2011, 04:24 PM
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
10-23-2011, 04:38 PM
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
10-23-2011, 04:42 PM
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
10-23-2011, 05:36 PM
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
10-23-2011, 05:51 PM
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
10-23-2011, 05:56 PM
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
10-23-2011, 06:00 PM
can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)

stargroup100
10-23-2011, 06:03 PM

I'm trying to find the error as well

LongGone
10-23-2011, 07:00 PM
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
10-23-2011, 07:10 PM
edit2: ok I was being stupid

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

Reincarnate
10-23-2011, 07:13 PM
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
10-23-2011, 07:21 PM
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
10-23-2011, 07:24 PM
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
10-23-2011, 07:37 PM
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
10-23-2011, 07:40 PM
FFFF YOU ARE RIGHT

im dumb

Reincarnate
10-23-2011, 07:51 PM
.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
10-23-2011, 07:56 PM
that's what I was trying to say lol

Reincarnate
10-23-2011, 07:59 PM
ah ok misunderstood what you meant

stargroup100
10-23-2011, 08:12 PM
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
10-23-2011, 08:37 PM
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
10-23-2011, 09:37 PM
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
10-23-2011, 10:02 PM
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
10-23-2011, 10:15 PM
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
10-23-2011, 10:26 PM
I just found this on Friday. Solved 1-22 as well as 67 now :p. This is actually pretty fun.

stargroup100
10-23-2011, 10:43 PM
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
10-23-2011, 11:45 PM
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
10-24-2011, 12:49 AM
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
10-24-2011, 07:27 AM
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
10-24-2011, 11:26 AM
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
10-24-2011, 02:29 PM
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
10-24-2011, 02:50 PM
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
10-24-2011, 04:26 PM
#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
10-24-2011, 04:58 PM
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
10-24-2011, 05:18 PM
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
10-24-2011, 05:24 PM
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
10-24-2011, 05:25 PM
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
10-24-2011, 05:28 PM
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
10-24-2011, 05:56 PM
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
10-24-2011, 06:18 PM
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
10-24-2011, 06:22 PM
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
10-24-2011, 07:04 PM
@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
10-24-2011, 08:42 PM
!!!!!!!!!
http://imageshack.us/photo/my-images/90/355v.png/

Reincarnate
10-24-2011, 09:19 PM
congrats FFR4, nicely done

stargroup100
10-25-2011, 01:44 AM
http://img268.imageshack.us/img268/5532/eulero.jpg

I got 0 eulerian points for this. mad

iironiic
10-25-2011, 09:53 AM
Got #71 with pencil and paper xD

EDIT: Nice FFREva!

FFR4EVA_00
10-25-2011, 10:41 AM
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
10-25-2011, 11:58 AM
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
10-25-2011, 03:07 PM

leonid
10-25-2011, 04:58 PM
don't worry you are not alone

pmonibuv1
10-25-2011, 06:08 PM
I have 2 answered. Go me! \o/

XCV
10-25-2011, 06:24 PM
I saw this about a week ago and I'm up to 8 or 9...impressive right? xD

stargroup100
10-25-2011, 06:25 PM
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
10-25-2011, 06:36 PM
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
10-25-2011, 06:42 PM
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
10-25-2011, 07:01 PM
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
10-25-2011, 07:39 PM
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
10-25-2011, 07:44 PM
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
10-25-2011, 07:48 PM
for the summation of totient? really?

Reincarnate
10-25-2011, 07:53 PM
for the summation of totient? really?

yes

stargroup100
10-25-2011, 08:00 PM
okay I made a small improvement on the speed of computation but it's not anything significant. what the hell did you do

Reincarnate
10-25-2011, 08:22 PM
Try messing around with http://pari.math.u-bordeaux.fr/

leonid
10-25-2011, 08:22 PM
yeeeeessssshhhhh

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

hondaracer600
10-25-2011, 08:32 PM
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
10-25-2011, 08:44 PM
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
10-25-2011, 08:45 PM
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
10-25-2011, 08:57 PM
holy crap pari/gp lololol

this thing rules lololololololol

****in hell

hondaracer600
10-25-2011, 09:11 PM
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
10-25-2011, 09:20 PM
Yes, the four of us that solved it all did the last part manually.

Reincarnate
10-25-2011, 10:40 PM
Solved 190 with Excel... <3

hondaracer600
10-25-2011, 10:43 PM
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
10-25-2011, 10:48 PM
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
10-25-2011, 11:43 PM
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
10-26-2011, 12:28 AM
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
10-26-2011, 04:30 AM
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
10-26-2011, 07:07 AM

hondaracer600
10-26-2011, 11:06 AM
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
10-26-2011, 03:08 PM
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
10-26-2011, 10:21 PM
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
10-26-2011, 11:59 PM
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
10-27-2011, 09:29 AM
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
10-27-2011, 12:47 PM
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
10-27-2011, 01:18 PM
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
10-27-2011, 02:19 PM
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
10-27-2011, 02:23 PM
I turned back.

hondaracer600
10-27-2011, 03:48 PM
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
10-27-2011, 07:16 PM
that's nowhere near the answer to 355, if that's what you're referring to

hondaracer600
10-27-2011, 07:34 PM
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
10-27-2011, 09:16 PM
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
10-27-2011, 09:31 PM
oh

then yes, yes they do

Were you on the 1.7 bill range?

FFR4EVA_00
10-27-2011, 09:45 PM
level 1 get!

iironiic
10-27-2011, 10:56 PM
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
10-28-2011, 12:20 PM
So Much Bullshit

hondaracer600
10-28-2011, 01:02 PM
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
10-28-2011, 02:36 PM
(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
10-28-2011, 02:46 PM
[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
10-30-2011, 04:06 AM
BAM!!

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

iironiic
10-30-2011, 10:38 AM
Nice leonid. I'm stuck on it haha.

EDIT: On another note:

Yesssss!!

Reincarnate
10-31-2011, 10:11 AM
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
10-31-2011, 01:24 PM
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
10-31-2011, 01:38 PM
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
10-31-2011, 04:22 PM
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
11-1-2011, 12:11 PM
leonid, you're a beast

Reincarnate
11-1-2011, 12:48 PM
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
11-1-2011, 02:25 PM
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
11-1-2011, 05:07 PM
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
11-1-2011, 08:28 PM
Join #euler in irc.chatspike.net

Knut.Angstrom
11-3-2011, 02:36 PM
Do you know the definition of triangle numbered problem?

iironiic
11-3-2011, 02:45 PM
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
11-3-2011, 03:45 PM
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
11-3-2011, 04:06 PM
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
11-3-2011, 04:59 PM
stuck on 126 ffffuuuu

nvm got it

Reincarnate
11-4-2011, 01:26 AM
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
11-5-2011, 01:51 PM
I tried, but because I can't do math for the life of me, I ragequit.

leonid
11-5-2011, 02:51 PM
Just solved p357. Could've solved it faster but I was being dumb... oh well.

iironiic
11-5-2011, 03:11 PM
Got 357 as well. I should try thinking of more efficient ways of solving it.

Izzy
11-5-2011, 03:22 PM
This looks cool, I might start working on these when I have time.

FFR4EVA_00
11-8-2011, 01:13 AM
has anyone solved problem 44 and if so
is the answer less than 1 million

iironiic
11-8-2011, 01:20 AM
has anyone solved problem 44 and if so
is the answer less than 1 million

No

FFR4EVA_00
11-8-2011, 01:22 AM
goddamnit

Reincarnate
11-8-2011, 08:50 AM
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
11-8-2011, 08:18 PM
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
11-9-2011, 12:48 AM
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
11-9-2011, 09:52 AM
Yeah the earlier problems are kinda stupid simple sometimes, but only because they're the early problems.

leonid
11-9-2011, 05:27 PM
level 7 !! \o/

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

Reincarnate
11-10-2011, 02:44 PM
I still don't have 356 or 152 :<

leonid
11-12-2011, 08:45 PM
Got 358 \o/

Reincarnate
11-12-2011, 08:51 PM
saaaaaaame, what a ffffffffuuu problem

Reincarnate
11-12-2011, 11:07 PM
We need more people to be in on this -- come join us in chat!

irc.chatspike.net
room Euler

iironiic
11-12-2011, 11:22 PM
I haven't been doing these problems lately. I"ll get back to them when I have the time

reuben_tate
11-13-2011, 07:42 AM
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
11-13-2011, 09:53 AM
lol I'm reinstalling visual basic for this

stargroup100
11-15-2011, 07:36 PM
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
11-15-2011, 10:07 PM
fffffffffffffffffffffffff---

Reincarnate
11-17-2011, 10:21 AM
you better check yourself

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

BEFORE YOU WRECK YOURSELF >:O

leonid
11-19-2011, 05:18 PM
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
11-19-2011, 08:36 PM
I COMPLETELY forgot about 359 happening today

Reincarnate
11-19-2011, 09:32 PM
http://i.imgur.com/DTBtc.png

w00t

LongGone
11-19-2011, 09:41 PM
I obtained the general formula for 359 but idk how to code/program (and 358 too)

):

Reincarnate
11-19-2011, 10:19 PM
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
11-22-2011, 08:05 PM
fffff some of these are getting pretty tough

Reincarnate
11-27-2011, 01:32 AM
welp

360 is pretty much 353 on steroids

leonid
11-27-2011, 02:23 AM
360 ;_;

leonid
11-27-2011, 03:41 AM
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
11-27-2011, 09:31 AM
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.

11-27-2011, 09:38 AM
well this looks like fun :D

leonid
11-28-2011, 07:34 AM
now I'm level 8 :') (200 problems solved)

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

reuben_tate
12-4-2011, 07:20 PM
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
12-6-2011, 04:09 PM
http://i.imgur.com/ljYrY.png

awwww yeah

leonid
12-6-2011, 04:13 PM
dam nice

PriestREA
12-10-2011, 09:32 PM
For the sake of adding to the Project Euler thread, finished 1-10 so far.

Reincarnate
12-21-2011, 06:24 PM
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
12-21-2011, 06:26 PM
Congrats Marcus! I haven't have the time to tackle this lately, but I'll change that in the next few days!

Reincarnate
12-21-2011, 06:29 PM
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
12-22-2011, 01:13 AM
why have so few people solved 177? looks pretty easy to me

gonna attempt that next I think

Reincarnate
12-22-2011, 11:16 AM
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
12-26-2011, 02:55 PM
Done some work on Project Euler, well on my way to level 3 with 53 problems solved.

Reincarnate
12-31-2011, 02:01 AM
http://i.imgur.com/FJzRc.png

YEEEEEEEEESSSSSSSSSSSSSS!!!!!!!

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

Reincarnate
02-24-2012, 12:25 PM
doot doot doot

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

procrastinated on this one pretty hard

robertsona
02-24-2012, 09:51 PM
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
02-24-2012, 10:03 PM
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
02-24-2012, 10:22 PM
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
03-16-2012, 12:42 AM
http://i.imgur.com/LhE8V.png

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

Reincarnate
04-16-2012, 05:37 PM
Almost forgot to post this one:

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

Reincarnate
04-24-2012, 07:59 PM
100 paasento

C1004A
04-24-2012, 08:08 PM
project euler dominated :o

Reincarnate
04-26-2012, 12:03 AM
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
04-29-2012, 12:18 AM
lucked out getting the Perfection badge just in time... this new one is a doozy.

FFR4EVA_00
05-10-2012, 03:43 PM
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
05-10-2012, 05:36 PM
Haven't even looked at 383 yet... tried 382 for a bit and couldn't solve it, so I took a break, haha.

Reincarnate
05-10-2012, 05:44 PM
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
05-10-2012, 06:22 PM
I'm working on 383 too. I got a formula for f5(n!) but nothing for T5(n) yet :(

Reincarnate
05-11-2012, 01:15 AM
Just gotta knock back 382 and that's that
Not really a fan of recurrence-relation problems but meh

Reincarnate
05-29-2012, 01:08 AM
Got 382 earlier then 385 and 386 this weekend once some free time opened up -- still need 384 to re-100%

Reincarnate
05-30-2012, 06:46 PM
Weeee, got it -- 100% again

Reincarnate
06-21-2012, 01:05 AM
390 should be ok, but I am fearing 391. it's likely going to be brutal

Reincarnate
07-1-2012, 04:27 PM
ffffffffuuuuuuuuucccccccccckkk

Reincarnate
07-1-2012, 04:42 PM
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
07-5-2012, 12:34 AM
391 solved, back to 100%. That one was tricky.

Reincarnate
07-5-2012, 07:29 PM
damn it now I have to find something else to sink time into when I'm at home

Bluearrowll
07-5-2012, 08:20 PM
Until 392..

Reincarnate
07-11-2012, 07:46 PM
decided to get into SPOJ recently in the meantime

Choofers
07-26-2012, 04:25 PM
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
a\$ = ""

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

if count < 1000 then
goto [loop]
else
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 "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
07-26-2012, 04:57 PM
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
07-26-2012, 10:25 PM
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
07-27-2012, 03:46 PM
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
07-27-2012, 03:56 PM
ur gay

Choofers
07-27-2012, 03:58 PM

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
07-27-2012, 08:28 PM
What is your current code for problem 1

and seriously stop using BASIC, aaaaoooogugughghhh

Choofers
07-27-2012, 11:16 PM
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
08-12-2012, 07:21 AM
I actually never touched my code that night...

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

Reincarnate
10-13-2012, 10:30 AM
100% again. Last problem was tough.

Reincarnate
11-17-2012, 12:42 AM
Anyone else still playing any?

Eagerly awaiting #402

infinity.
11-17-2012, 01:23 AM
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.
11-17-2012, 01:24 AM
whats wrong with basic rofl

also

EVERYTHING

Reincarnate
11-17-2012, 12:03 PM

Reincarnate
11-24-2012, 11:45 PM
fuck

infinity.
11-25-2012, 12:53 AM
74432925402977_edc6e913519320b2bbdef524348d21cc

Reincarnate
12-7-2012, 11:29 AM
403/404 were tricky, but quite fun in the end

kaiten123
12-10-2012, 07:48 PM
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
12-10-2012, 09:35 PM
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
12-10-2012, 09:46 PM
Practice makes perfect -- the more you solve, the more you'll learn

axith
12-13-2012, 01:21 PM
for all it's worth, here's my friend key: 83532459359302_e704d4c6b1d37a7739410f38da156b2a

axith
12-18-2012, 10:31 PM
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
12-18-2012, 11:00 PM
You will want to use:

file = open('/path/to/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
12-19-2012, 10:13 AM

Reincarnate
12-19-2012, 10:17 PM
406 was a kick in the face for me -- I was making it harder than it needed to be

kaiten123
12-21-2012, 09:13 PM
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
12-28-2012, 11:24 PM
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
12-29-2012, 04:18 PM
tis new

leonid
12-30-2012, 01:11 AM
i should get back to solve rest of the problems

Reincarnate
01-1-2013, 09:35 PM
Managed to squeak onto the 408 list; hard one

Arkuski
01-4-2013, 03:36 PM
This is pretty awesome I'm giving some of these a go

Reincarnate
01-17-2013, 11:07 PM
I think 411 will be on the easier side this week... I hope.

Reincarnate
01-22-2013, 08:52 PM
411 wasn't too bad -- pretty much an exercise in programming

Reincarnate
02-12-2013, 08:43 PM
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
02-17-2013, 12:40 PM
415... only 3 solvers after 7 and a half hours.

Yeah I can pretty much kiss my 100% goodbye

It's been fun, PE :(