Flash Flash Revolution: Community Forums

Flash Flash Revolution: Community Forums (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)
-   -   The Project Euler thread (http://www.flashflashrevolution.com/vbz/showthread.php?t=120818)

FFR4EVA_00 10-24-2011 07:27 AM

Re: THE project euler thread
 
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

Re: THE project euler thread
 
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

Re: THE project euler thread
 

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

Re: THE project euler thread
 
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

Re: THE project euler thread
 

#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

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

Knut.Angstrom 10-24-2011 05:18 PM

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3556057)
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

Re: THE project euler thread
 
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

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


Question 1:
Code:

#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:

Code:

#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:

Code:

#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

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3556421)
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


Quote:

Originally Posted by Reincarnate (Post 3556421)
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

Re: THE project euler thread
 
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

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3556421)
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

Re: THE project euler thread
 
Quote:

Originally Posted by LongGone (Post 3556451)

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

Re: THE project euler thread
 
@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

Re: THE project euler thread
 
!!!!!!!!!
http://imageshack.us/photo/my-images/90/355v.png/

Reincarnate 10-24-2011 09:19 PM

Re: THE project euler thread
 
congrats FFR4, nicely done

stargroup100 10-25-2011 01:44 AM

Re: THE project euler thread
 
http://img268.imageshack.us/img268/5532/eulero.jpg

I got 0 eulerian points for this. mad

iironiic 10-25-2011 09:53 AM

Re: THE project euler thread
 
Got #71 with pencil and paper xD

EDIT: Nice FFREva!

FFR4EVA_00 10-25-2011 10:41 AM

Re: THE project euler thread
 
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

Re: THE project euler thread
 
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 -_-


All times are GMT -5. The time now is 10:26 AM.

Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution