I read that the C style for loop is discouraged in Perl, but it doesn’t seem like there’s a natural way to modify your step length in the Perl style loop.
If we’re only checking threes and fives then it’d be a waste to use a single step.
Yeah there is no way I’ll be bothered to write code for this.
There’s a neat theorem in probability theory, the name of which i can’t remember, which tells you that if you want the joint probability of N discrete events, its the sum of their individual probabilities minus the sum of their pairwise joint probabilities, plus the sum of their tripletwise joint probabilities, minus the sum… etc. The rationale being that in the first round, when counting 3’s and 5’s, you count the 15’s twice, so you got to subtract them. If you have more than two sets, you then end up subtracting too much, and so on. Actually, does anyone know what the theorem is called? It’s kinda grinding my gears that I can’t remember, and my google skills have shown insufficient to retrieve it.
Calculation
So between 1 and 1000 there’s floor(999/3)=333 multiples of 3, floor(999/5)=199 multiples of 5 and floor(999/15)=66 multiples of 15, and 333+199-66=466, unless I miscalculated somewhere, which is quite possible, since I didn’t check with a calculator.
WAIT NOT DONE YET
Oh, okay and I got to sum them all up. Well for this we have Gauss’ Theorem, so the multiples of 3 will be 3*((333*334)/2)) = 999*167 = 166’833 (okay i started using a calculator, touché)
5’s:
5*((199*200)/2) = 199*500 = 99’500 (okay that worked without calculator again)
15’s:
15*((66*67)/2) = 15*33*67 = 33’165 (calculator back at it again)
yielding 166’833 + 99’500 - 33’165 = 233’168
Sanity check, the entire sum of all eligible numbers is (999*1’000/2) = 499’500, and the ratio of our summation, 233’168/499’500 yields ~.4668, so almost converged to the 466 in 1’000 that is the frequency of multiples of 3 and 5 below 1’000 that we calculated above.
1 Like
It’s an eternal topic of readability, accessibility and maintainability versus algorithmical complexity (not this case) and cpu or memory optimization.
For example benjito’s first solution would be an “industry standard” in terms of readability and maintainability. In almost all cases it would desirable over cutting a few Ns in an O(n) algorithm.
1 Like
This is the count of matching values between 0 and 1000. The problem is to find the sum
1 Like
yeah yeah, I realized that the second I hit reply 
see edit
1 Like
4 Likes
Common Lisp
(defun problem-1 ()
(let ((sum-n 0))
(loop for i from 3 below 1000 by 3
do (incf sum-n i))
(loop for i from 5 below 1000 by 5
do (unless (eql (mod i 3) 0)
(incf sum-n i)))
sum-n))
Maybe it would be fun to come up with some go-themed problems?
Find the smallest natural number N such that the decimal representation of 19*N contains only 9’s.
(if big numbers are a hassle, try the same with 13 instead of 19)
On a perfectly square 19*19 goban, how many pairs of intersections are an integer distance apart?
(e. g. 1-1 and 4-5 are exactly 5 units apart)
5 Likes
How ‘curated’ are the problems in this Project Euler? When posing such questions, it’s always hard to estimate if the problem doesn’t end up either trivial or virtually unsolvable, until someone spends the time.
1 Like
Well, we’re starting at #1 so it won’t pay to be offended by some triviality.
The “island problem” and variations of it are pretty Go-esque IMO:
1 Like
hmm, so basically find the number of groups. I feel like, framing go programming problems like that would eventually converge to ‘develop a competitive go AI’
Each problem has a difficulty rating, and one can always view them first to get an idea of what it’s about. You can solve them in any order, and ignore the ones that you don’t want to do.
They range from quite trivial to very difficult, so there’s probably an interesting and appropriate level of difficulty for everyone.
1 Like
It’s not the end of the world if you want to use a C style loop in Perl. It’s just that it is worth learning how to also do it the other way, since it is often more convenient and less error-prone.
Here are some other ways to do it with loops in a more Perl-ish style:
for (1..999) {
$sum += $_ if ($_ % 5 == 0 || $_ % 3 == 0);
}
print $sum . "\n";
It’s not a huge burden to skip over some numbers, but if you insist on looping over fewer things:
$sum += 5 * $_ for (1..int(999 / 5));
$sum += 3 * $_ for (1..int(999 / 3));
$sum -= 15 * $_ for (1..int(999 / 15));
print $sum . "\n";
However, as pointed out by others
The neat trick about this problem is applying the triangle number formula to avoid “brute-force” iteration altogether. For the easier Project Euler problems, one can usually get away with the brute-force approach, however, for more difficult ones, the complexity of brute-force, or just a poorly designed algorithm, often makes the computation a bit impractical, if not outright intractable. These problems become more about understanding and solving some mathematics, rather than just programming.
4 Likes
Project Euler was fun, did the first 50 or so in C, don’t quite remember if I used a bignum library or not. But the problems were fun and quite a few built on solutions from previous ones.
Hardest part is figuring out a solution on paper and then the coding was straight forward enough.
They start to get a bit math heavy and not so fun after a while though. good times.
2 Likes
How about moving onto #2?
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
I wonder how long this’ll take with just a while loop. My laptop is pretty cheap.
I don’t know any tricks…
It should run quite fast just taking the brute force approach of generating all of the numbers and summing them up. I don’t know of any tricks to do it faster than that.
Here is the Fibonacci sequence under four million
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578
3 Likes
Ah, yeah, although the upper bound is fairly high, only a very small amount of operations are actually being done. So should be fast.
I found a trick: the Fibonacci sequence repeats twice odd to once even. So you don’t have to do any modulus checking.
1 Like