Rosetta Code

Sum multiples of 3 and 5: Difference between revisions

Page Discussion

Sum multiples of 3 and 5 (view source)

Revision as of 13:15, 30 October 2013

878 bytes added ,  10 years ago
→‎{{header|C#}}
Line 45:
 
=={{header|C#}}==
The following code is an <i>efficient</i> solution in that it does not iterate through the numbers 1 ... n - 1 in order to calculate the answer. <i>However</i>, in C# the ulong (64-bit unsigned integer) type is insufficient to store the whole result of the larger calculations such that even for n = 1E+10 the final result is incorrectly reported. This is effectively a binary overflow - the upper bits are truncated. If there were a 128-bit integer type available, this would be able to calculate the result for n = 1E+20. Changing all instances of ulong to double will present an <i>approximation</i> of the correct answer, but double precision numbers are inherently imprecise. Implementing a 128-bit integer type in this context may be considered out of scope of the problem at hand.
For "extra credit" one should seek an <i>efficient</i> algorithm, and I suspect few - if any - of the proposed answers employ such a mechanism. I have done some investigation, and suspect this would be similar to the well-known task of adding <i>all</i> numbers between 1 and 1000 (where there are 500 pairs whose sums are 1001, making a sum of 500500.) I hope to update this (C#) section shortly with a proposed <i>correct</i> answer.
 
On a single core of an Intel Xeon X3450 at 2.8Ghz, calculating with "brute-force" for 1E+9 takes roughly 20 seconds, thus calculating for 1E+20 would take roughly 2000000000000 seconds, or approximately 63 millenia, 419 years, 213 days, 3 hours and 30 minutes. Thus, this - in any language - is not efficient.
 
<lang csharp>
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace RosettaCode
Line 59 ⟶ 54:
class Program
{
static void Main(string[] args)
{
ulong[] candidates = { 1000, 100000, 10000000, 10000000000, 1000000000000000 };
Func<double, double> mulsum35 = (n) =>
 
foreach (ulong candidate in candidates)
{
doubleulong sc = 0.0dcandidate - 1;
forulong (double ianswer3 = 1.0d;GetSumOfNumbersDivisibleByN(c, i < n3); i += 1.0d)
ulong answer5 s += i % 3.0d == 0.0d || i %GetSumOfNumbersDivisibleByN(c, 5.0d == 0.0d ? i : 0.0d);
returnulong sanswer15 = GetSumOfNumbersDivisibleByN(c, 15);
 
};▼
Console.WriteLine("The sum of numbers divisible by 3 or 5 between 1 and {0} is {1}", c, answer3 + answer5 - answer15);
Console.Write("Give n: ");▼
▲ };
double nInput = double.Parse(Console.ReadLine());
 
Console.WriteLine("Sum is {0} for n = {1}", mulsum35(nInput), nInput);
▲ Console.WriteReadKey("Give n: "true);
}
 
private static ulong GetSumOfNumbersDivisibleByN(ulong candidate, uint n)
{
ulong largest = candidate;
while (largest % n > 0)
largest--;
ulong totalCount = (largest / n);
ulong count = totalCount / 2;
bool unpairedNumberOnFoldLine = (totalCount % 2 == 1);
ulong pairSum = largest + n;
return count * pairSum + (unpairedNumberOnFoldLine ? pairSum / 2 : 0);
}
 
}
}
</lang>
{{out}}
The sum of numbers divisible by 3 or 5 between 1 and 999 is 233168
Give n: 1000
The sum of numbers divisible by 3 or 5 between 1 and 99999 is 2333316668
Sum is 233168 for n = 1000
The sum of numbers divisible by 3 or 5 between 1 and 9999999 is 23333331666668
Extra credit still calculating at the time of writing
The sum of numbers divisible by 3 or 5 between 1 and 9999999999 is 4886589257957115052
The sum of numbers divisible by 3 or 5 between 1 and 999999999999999 is 12252500107296959148
 
=={{header|C++}}==
Hugh
23

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/231705"