View Single Post
Old 10-24-2011, 03:58 PM   #66
FFR4EVA_00
FFR Player
 
FFR4EVA_00's Avatar
 
Join Date: Aug 2005
Location: Banned
Posts: 1,770
Default Re: THE project euler thread

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

Quote:
[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
Quote:
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
__________________
~*~Lurkadurk - 1134-7796-6967~*~
FFR4EVA_00 is offline   Reply With Quote