Summer Challenge #1

[leoandru]

well i havent downloaded the D language tools yet, so you have to run it and tell us your result. but for starts let us say the limit was 19.
the answer would be 3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 = 78

public extern(D) uint ChallengeSolution(uint limit)
{
	asm
	{
		naked;
		mov ECX, EAX; // store the limit which was in EAX somewhere else
		xor EAX, EAX;  // set EAX to 0
		xor EDX, EDX;  // set EDX to 0
	     X0:                        // mark where loop should start
		add EDX, 15;   // set EDX+= 15
		cmp EDX, ECX;// some flag = EDX  limit
		ja X1;            // if we can end then break out of the loop
		add EAX, EDX;// set EAX+= EDX
		jmp X0;         // goto the start of the loop
	     X1:
		ret;
	}
}

is that equivalent? i dont think it right still.

yeah the comments are right.. I misunderstood the question then. I though the number should be divisible by 3 and 5 not 3 or 5. cause that what ur question said. If u had given that example before It would have be a bit clear.

[icymint3]

/*function return the sum of all numbers n | [0,limit) and n is a multiple of 3 or 5 or both*/

i was wondering how i could have made such a mistake until i re-read my post, shoud have put it in the spec and not in the code (especially since you have to scroll over to see it, cant the CODE take up as much space as is allocated to it like QUOTE because i can see the entire thing in my quote)

[crosswire]

Ok later,

Here is the basic math

For the sum of all factors of 3 only, and within the range 0 - 100, there are
3 * 0
3 * 1
3 * 2
…
3 * 33
where the 33 is the limit calculated from 100/3 as integer

The arithmic progression is basically the average times number of factors
{0, 3, 6, …, 99} has 34 factors and average (0+99)/2 = 49.5, therefore sum is 34* 49.5

workout
0,3 has avg = 1.5
0,3,6 has avg = 3
0, 3, 6, 9 has avg = 4.5
so clearly avg is first + last so long as the first is zero

Solution
Sum3only(limit)
{
Nfactors = limit/3
}

[recursion]

Ok later,

Here is the basic math

For the sum of all factors of 3 only, and within the range 0 - 100, there are
3 * 0
3 * 1
3 * 2
…
3 * 33
where the 33 is the limit calculated from 100/3 as integer

The arithmic progression is basically the average times number of factors
{0, 3, 6, …, 99} has 34 factors and average (0+99)/2 = 49.5, therefore sum is 34* 49.5

workout
0,3 has avg = 1.5
0,3,6 has avg = 3
0, 3, 6, 9 has avg = 4.5
so clearly avg is first + last so long as the first is zero

Solution
Sum3only(limit)
{
Nfactors = limit/3
}

int Sum(limit)
{
   int Nfactors = limit/3;
   int sum = (Nfactors/2 * (Nfactors -1) * 3) ;
   Nfactors = limit/5;
   sum += (Nfactors/2 * (Nfactors -1) * 5) ;
   Nfactors = limit/15;
   sum -= (Nfactors/2 * (Nfactors -1) * 15) ;
}

n(A U B) = n(A) + n(B) - N(A intersect B)

uhm soon check it

[icymint3]

ok, i'll show my solution soon, but heres the remaining logic

there are multiples of 3 and there are multiples of 5, and there are multiples of both.

we will sum all multiples of 3 lower than the limit
and add to that
the sum of all multiples of 5 lower than the limit

we will notice however, that multiples of 3 and 5 are accounted for twice
...one in the sum of 3's and one in 5's

so we need to remove the extra sum of on extra multiples of 15

answer = sum3s(...) + sum5s(...) - sum15s(...).

if we assume the first term in the progression is 0 ( for 3 and 5 ... and 15 ), then we can use the formula Sum(a,d,n) = n/2 ( 2a + (n - 1)d)

we can conveniently find n by using an integer division of the limit term (as previously stated by crosswire).

since we know a = 0, the formula becomes

Sum(0,d,n) = n/2 ( 2(0) + (n - 1)d)

we know the number of times d will go into limit, but that does not compensate for the first term 0
19 / 3 = 6
and not 7 which is the number of terms ( so we add 1 to n to compensate for this)

yielding

Sum(0,d, limit/d + 1) = (limit/d + 1)/2 (((limit/d + 1) - 1)d) ...
Sum(0,d, limit/d + 1) = (limit/d + 1)/2 ((limit/d)d) ...
Sum(0,d, limit/d + 1) = (limit/d + 1) (limit/d) * d / 2

notice however that it includes the last term which we want to eliminate, so we subtract one from the limit to satisfy this.

Sum(0,d, (limit - 1)/d + 1) = ((limit - 1)/d + 1) ((limit - 1)/d) * d / 2

we apply this routine for all three sums, but to avoid subtracting from limit six times, we store the value

limitX = limit - 1

and to prevent dividing by d twice, we also store that
multiples = limitX/d

limitX = limit - 1

Sum(d, limitX) = 
   multiples = limitX / d,
   (multiples + 1) multiples * d / 2

[icymint3]

i saw your post after my lengthy explanation, good job.
your code is shorter that mine uses less space and is more intact.
the only problem is your inclusion of the last term... [0,limit), ) means dont include it. but you're correct all the way.

n(A U B) = n(A) + n(B) - N(A intersect B)

i was hoping somebody would see that

my code

#include <iostream>	

inline unsigned nByNext(unsigned value) { return value * ( value + 1 ); }

/*function return the sum of all numbers n | [0,limit) and n is a multiple of 3 or 5 or both*/
unsigned ChallengeSolution(unsigned limit)
{
	unsigned adjustedLimit = limit - 1;
	unsigned numberOfMultiplesOf3 = adjustedLimit / 3;
	unsigned numberOfMultiplesOf5 = adjustedLimit / 5;
	unsigned numberOfMultiplesOf15 = adjustedLimit / 15;

	return (nByNext(numberOfMultiplesOf3) * 3 + nByNext(numberOfMultiplesOf5) * 5 - nByNext(numberOfMultiplesOf15) * 15 ) / 2;
}

int main()
{
    unsigned limit;

	std::cin >> limit;

	std::cout << ChallengeSolution(limit);

    return 0;
}

[icymint3]

the iterative idea is correct, the coding ...

the upper limit should not be included in the sum
the Nfactors/2 will give an incorrect result when Nfactors is odd (divide last)
the (Nfactors - 1) instead of Nfactors + 1, because we are summing terms
the sum is not returned.

...Nfactors should be Nmultiples, but thats english
i guess you didnt compile and test, best attempt i've seen none the less

[recursion]

the (Nfactors - 1) instead of Nfactors + 1, because we are summing terms

Not sure if I get that.............., however I do see a flaw with my previous post......, maybe the same thing........, Nfactors should include zero for each summation (Nfactors)++.

the iterative idea is correct, the coding ...
...Nfactors should be Nmultiples, but thats english

I feel so dumb.........
I'll give myself 1000 lines.....

for(int i = 0;i < 100;i++)
{
Console.WriteLine("I will not call multiples factors , even if I'm quoting a previous post");
}

[crosswire]

ehem, no "\n", no i < 1000, hmph

Anyway, I disagree with some of what you say ice and that nFactor / 2 is not needed if we work in 'double' as in calculate everything at 2twice their true value and in the end we can do one scale down of a half. Later.

[recursion]

ehem, no "\n", no i < 1000, hmph

Note (WriteLine() and not Write() so no "\n")
..............

for(int i = 0;i < 900;i++)
{
Console.WriteLine("I will not call multiples factors , even if I'm quoting a previous post");
}

Happy now!!!!!!!!!!!