#### 1. Multiples of 3 and 5

*If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.*

A key result needed to solve this problem is the sum of all the integers between \({\color{black}{1}}\) and some number \({\color{black}{N}}\); it was derived by Gauss when he was in elementary school: \begin{equation} \label{gauss} {\color{black}{ \sum_{i=1}^{N} i = \frac{N(N+1)}{2}. }}\end{equation} Suppose \({\color{black}{x}}\) is a multiple of \({\color{black}{3}}\) and that \({\color{black}{y}}\) is a multiple of \({\color{black}{5}}\). Then, we can write \({\color{black}{x = 3n}}\) and \({\color{black}{y = 5m}}\) for some positive integers \({\color{black}{n}}\) and \({\color{black}{m}}\). From Equation (\ref{gauss}) we can construct the sum of the multiples of \({\color{black}{3}}\) less than \({\color{black}{1000}}\) as follows: \begin{equation} \label{1} {\color{black}{ \sum_{n=1}^{333} 3n = \frac{3\times 333 \times 334 }{2}; }}\end{equation} likewise, the sum of the multiples of \({\color{black}{5}}\) less than \({\color{black}{1000}}\) is \begin{equation} \label{2} {\color{black}{ \sum_{m=1}^{199} 5m = \frac{5\times 199 \times 200 }{2}. }}\end{equation} Now, if we just add these two sums we won't arrive at the correct answer -- it will be much too large. Can you see why? Consider the number \({\color{black}{15}}\): it is a multiple of both \({\color{black}{3}}\) and \({\color{black}{5}}\). If we simply add Equations (\ref{1}) and (\ref{2}) we will count these numbers that are multiples of both \({\color{black}{3}}\) and \({\color{black}{5}}\) twice! So how do we correct for this? A number \({\color{black}{z}}\) that is a multiple of both \({\color{black}{3}}\) and \({\color{black}{5}}\) can be written \({\color{black}{z = xy = (3}}\times 5) n \times m = 15k\) for some positive integer \({\color{black}{k}}\). These are the numbers that are counted twice when we sum Equations (\ref{1}) and (\ref{2}) and so we need to subtract them off to arrive at our answer: \begin{equation} {\color{black}{ \boxed{\sum_{n=1}^{333} 3n + \sum_{m=1}^{199} 5m- \sum_{k=1}^{66} 15k= 233\,168.} }}\end{equation}

#### 2. Even Fibonacci numbers

*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.*

Notice first that every 3rd Fibonacci number is even (and no others). Next, observe the following: \begin{eqnarray} F_6 = 8 &=& 4\times 2 \nonumber \\ F_9 = 34 &=& 4 \times 8 + 2 \nonumber \\ F_{12} = 144 &=& 4 \times 34 + 8 \nonumber \\ F_{15} = 610 &=&4 \times 144 + 34 \nonumber \\ &\vdots& \nonumber \end{eqnarray} By playing around with ways of writing the even Fibonnaci numbers, we discover an interesting pattern that they all seem to follow, \begin{equation} \label{recur} {\color{black}{ F_{3i} = 4 \times F_{3i-3} + F_{3i - 6}. }}\end{equation} Consider the sum, \({\color{black}{S}}\), of the first \({\color{black}{i}}\) even Fibonacci numbers, \begin{equation} {\color{black}{ S = F_{3i} + F_{3i-3} + \cdots + 34 + 8 + 2. }} \end{equation} This is what we're after. Proceed by rewriting the sum by replacing each term with its recursive definition, Eq. (\ref{recur}),

*i.e.*, write \begin{equation} {\color{black}{ S = (4\times F_{3i-3} + F_{3i-6}) + (4\times F_{3i-6} + F_{3i-9}) + (4\times F_{3i-9} + F_{3i-12}) + \cdots }} \end{equation} Next, regroup terms: \begin{eqnarray} S &=& (4\times F_{3i-3} + 4\times F_{3i-6}+ 4\times F_{3i-9} + \cdots) + (F_{3i-6} +F_{3i-9} + F_{3i-12} + \cdots) \nonumber \\ &=&4(S-F_{3i}) + (S-F_{3i} - F_{3i-3}) \end{eqnarray} This gives an equation involving only two Fibonacci numbers -- all the rest have been nicely absorbed into the two \({\color{black}{S}}\)'s on the right hand side. This means we can solve for \({\color{black}{S}}\) to obtain a simple, closed-form expression for the sum of the first \({\color{black}{i}}\) even Fibonacci numbers, \begin{equation} \label{sum} {\color{black}{ S = F_{3i} + \frac{1}{4}\left(F_{3i} + F_{3i-3}\right). }} \end{equation} In order to answer the question: what is the sum of the even Fibonacci numbers

*less than*4 million, we need only know the two greatest even Fibonacci numbers less than 4 million. A quick search reveals these to be \({\color{black}{F_{33}=3}}\,524\,578\) and \({\color{black}{F_{30} = 832}}\,040\). Plugging into Eq. (\ref{sum}) gives \begin{equation} {\color{black}{ \boxed{S = 4\,613\,732.} }} \end{equation}

#### 3. Largest prime factor

*The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?*

The fundamental theorem of arithmetic guarantees the unique factorization of any integer into primes. Factorization is a computational problem with major applications to modern cryptology: while no analytic procedure exists, sophisticated numerical approaches have been developed in recent years. We will not be employing any of these! Below is a simple C code that uses trial division to factor integers into primes; the largest such factor can then be read off.

#includeSince all primes aside from 2 are odd, divisibility of the input integer, \({\color{black}{n}}\), by 2 is tested first, separately. If \({\color{black}{n}}\) is divisible by 2, a second trial division by 2 is attempted on \({\color{black}{n_1 = n/2}}\), and so on until \({\color{black}{n_k = n/2^k}}\) is no longer divisible by 2.#include #include /* * Generates a list of prime factors of input integer. * Returns nothing if input is prime. */ int main(int argc, char * argv[]) { long long n = atoll(argv[1]); int i,j, noprime = 0; int count = 1; int k = 0; long long part = 1; FILE * out; out = fopen("out_fac.dat","w"); /* Start trial divisions of each prime. * First, check the number 2 separately*/ while(1) { if((n%((long long)pow(2,count++)))==0) // 2 divides n { fprintf(stderr,"2\n"); part = 2*part; if(part==n) { fclose(out); return 0; // we're done } } else { break; } } for(i = 3; i < n; i = i+2) // test only the odds { // First, check if the number is prime noprime = 0; for(j = 3; j <= (long long)ceil(sqrt(i)) ; j=j+2) { if((i%j == 0)) { noprime = 1; break; // not prime } } if(!noprime) // if prime, attempt trial division { count = 1; while(1) { if((n%((long long)pow(i,count++)))==0) // prime i divides n { fprintf(stderr,"%d\n",i); part = part*i; if(part==n) { fclose(out); return 0; // we're done } } else { break; } } } } }

We next move on to test the odd primes. The code does not ``know''

*a priori*what the prime numbers are (besides 2, a small concession we've made to improve the efficiency of the algorithm). Starting with 3, we check each odd integer \({\color{black}{i}}\) for primality by trial divisions of integers \({\color{black}{j < \sqrt{i}}}\).

^{1}If \({\color{black}{i=p_i}}\) is prime, we check if it is a factor of \({\color{black}{n}}\) by trial division into \({\color{black}{n/2^{k}\cdot p_2^{k_2} \cdots \cdot p_{i-1}^{k_{i-1}}}}\), repeating until \({\color{black}{p_i}}\) fails to divide \({\color{black}{n/2^k\cdot p_2^{k_2} \cdots \cdot p_{i-1}^{k_{i-1}}p_i^{k_i}}}\). This process is continued for all primes \({\color{black}{i < \sqrt{n}}}\). Applying this algorithm to 600851475143, we find the prime factors 71, 839, 1471, and 6857. And so, the largest prime factor of 600851475143 is \begin{equation} {\color{black}{ \boxed{6857.} }} \end{equation}

#### 4. Largest palindrome product

*A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 \({\color{black}{\times}}\) 99. Find the largest palindrome made from the product of two 3-digit numbers.*

This is exercise is another computational problem. The product of two 3-digit numbers is either 5- or 6-digits. The code is easy: the interesting part is figuring out how to access the individual digits of 5- and 6-digit numbers to check for palindromicity (is that a word?)

Consider 5-digit numbers in the form \({\color{black}{n = abcde}}\). The first digit \({\color{black}{a}}\) can be gotten as follows: divide \({\color{black}{n}}\) by \({\color{black}{10^4}}\) so that \({\color{black}{n/10^4 = a.bcde}}\). By making use of the floor function in C, we can round this down to the nearest integer: floor\({\color{black}{(n/10^4) = a}}\). The second digit, \({\color{black}{b}}\), can be gotten similarly but with an additional step. Consider floor\({\color{black}{(n/10^3) = }}\)floor\({\color{black}{(ab.cde) = ab}}\). Then, from above, \({\color{black}{10 \times}}\) floor\({\color{black}{(n/10^4) = a0}}\) and we can take the difference \({\color{black}{ab - a0 = b}}\). The remaining digits can be gotten using similar maneuvers.

#includeThe code cycles through the products of integers between 100 and 999, inspecting 5-digit numbers of the form \({\color{black}{abcde}}\) for the condition \({\color{black}{a=e}}\) and \({\color{black}{b=d}}\) and 6-digit numbers of the form \({\color{black}{abcdef}}\) for the condition \({\color{black}{a=f}}\), \({\color{black}{b=e}}\), and \({\color{black}{c=d}}\). The largest palindromic number is found to be \begin{equation} {\color{black}{ \boxed{906609.} }} \end{equation}#include int main() { int i,j; int a,b,c,d,e,f; int largest = 1; FILE * out; out = fopen("palindrome.out","w"); for(i=100; i < 999; i++) { for(j = i; j < 999; j++) // j=i so we don't overcount { if(i*j/1e5 < 1) // if we've got a 5-digit number { a = (int)floor(i*j/1e4); e = (int)(i*j - 10*floor(i*j/10)); b = (int)(floor(i*j/1e3)-10*floor(i*j/1e4)); d = (int)(floor(i*j/10)-10*floor(i*j/100)); if((a==e)&&(b==d)) { fprintf(out,"%d %d %d\n",i,j,i*j); } } else // we've got a 6-digit number { a = (int)floor(i*j/1e5); f = (int)(i*j - 10*floor(i*j/10)); b = (int)(floor(i*j/1e4)-10*floor(i*j/1e5)); e = (int)(floor(i*j/10)-10*floor(i*j/100)); c = (int)(floor(i*j/1000) - 10*floor(i*j/1e4)); d = (int)(floor(i*j/100) - 10*floor(i*j/1000)); if((a==f)&&(b==e)&&(c==d)) { fprintf(out,"%d %d %d\n",i,j,i*j); if(i*j > largest) { largest = i*j; } } } } } fprintf(stderr,"Largest palindrome = %d\n",largest); fclose(out); return 0; }

#### 5. Smallest multiple

*2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?*

An integer \({\color{black}{x}}\) that is divisible by an integer \({\color{black}{a}}\) must contain a factor of \({\color{black}{a}}\): \({\color{black}{x = ma}}\) for some integer \({\color{black}{m}}\). For example, the smallest number that is divisible by the integers 3 and 2 is \({\color{black}{6 = 3 \times 2}}\). Naively, then, one might be tempted to construct the number in question by forming the product of all integers up to and including 20. The reason this fails is clear: if this number is divisible by 4 and 2, isn't it then also necessarily divisible by 8? Yes, and 8 in this case should not be included as a separate factor.

The idea is to build this number piecewise as follows. Starting with the smallest nontrivial integer, it must include a factor of 2 to be divisible by 2. Ditto for 3. That gives \({\color{black}{x = 2 \times 3 \times \cdots}}\). We need a factor of 4 as well, but we don't just stick this on: there is already a factor of 2 and so only one additional factor needs to be included. This gives \({\color{black}{x = 2^2 \times 3 \times \cdots}}\). The factor 5 needs to be explicitly included, as, in fact, do all the primes up to 20 since these cannot be accounted for by other factors, \({\color{black}{x = 2^2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times \cdots}}\). We proceed to consider the remaining composite integers. The number 6 is already included in our product in the factors 2 and 3; the number 8, however, is not -- we need an additional factor of 2, giving \({\color{black}{x = 2^3 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times \cdots}}\). To recap and emphasize: the factor \({\color{black}{2^3}}\) is divisible by 2, 4, and 8 and so the integers 4 and 8 do not explicitly appear in the product. Similar situation for 9 -- we need only an additional factor of 3 on top of the one already present: \({\color{black}{x = 2^3 \times 3^2 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times \cdots}}\). The number 10 is accounted for (\({\color{black}{2 \times 5}}\)) as are 12 (\({\color{black}{2^2 \times 3}}\)), 14 (\({\color{black}{2 \times 7}}\)), 18 (\({\color{black}{2\times 3^2}}\)), and 20 (\({\color{black}{2^2 \times 5}}\)). That leaves \({\color{black}{16 = 4^2 = 2^4}}\), so we need to add one more factor of 2, giving our final answer, \begin{equation} {\color{black}{ \boxed{2^4 \times 3^2 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 232792560} }} \end{equation} This is a prime factorization of the number 232792560, and by the fundamental theorem of arithmetic is

*the unique*prime factorization. And, while it is the smallest positive number divisible by all integers up to and including 20, it is also the smallest positive number divisible by all integeres up to an including 19, 21, and 22. This is because the factors of the composite numbers 20, 21, and 22 are included in the product. Inspection of the product reveals a prescription for generating the smallest multiple of integers less than some number, \({\color{black}{n}}\): for each prime number \({\color{black}{p_i}}\) less than \({\color{black}{n}}\), include as many powers as possible without going over \({\color{black}{n}}\). In other words, each prime should satisfy \({\color{black}{p_i^k}}\) such that \({\color{black}{p_i^{k+1} > n}}\).

#### 6. Sum of square difference

*The sum of the squares of the first ten natural numbers is, \({\color{black}{12 + 22 + ... + 102 = 385}}\). The square of the sum of the first ten natural numbers is, \({\color{black}{(1 + 2 + ... + 10)\times 2 = 552 = 3025}}\). Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is \({\color{black}{3025-385 = 2640.}}\) Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum?*

When Carl Friedrich Gauss was a little boy, he derived a formula for the sum of natural numbers between \({\color{black}{1}}\) and \({\color{black}{n}}\), \begin{equation} \label{gauss_sum} \sum_{i = 1}^n i = \frac{n\times(n+1)}{2}. \end{equation} A discussion and derivation of this well-known formula can be found in many places (see the discussion surrounding Figure 3 here). The square of the sum of the first \({\color{black}{n}}\) natural numbers is then the square of Eq. (\ref{gauss_sum}). Easy. What about the sum of the squares?

Consider the graphical representation of the first few squares, Figure 1.

**Fig. 1**Geometric representation of the first few square numbers -- the red discs are those that must be added to the \({\color{black}{(i-1)^{st}}}\) figure to obtain the \({\color{black}{i^{th}}}\).

Denoting \({\color{black}{i^2}}\) by \({\color{black}{S_i}}\) (for square number \({\color{black}{i}}\)), the figure shows \({\color{black}{S_1}}\), \({\color{black}{S_2}}\), \({\color{black}{S_3}}\), and \({\color{black}{S_4}}\). We are interested in finding a closed form expression for the sum \({\color{black}{\sum_{i=1}^n S_i = \sum_{i=1}^n i^2}}\), like Eq. (\ref{gauss_sum}) above. The key is to focus on the red discs in the figure: these are the discs that must be added to \({\color{black}{S_{i-1}}}\) to obtain \({\color{black}{S_i}}\). They are awesomely called

*gnomons*, and have the values: 3, 5, 7, 9, \({\color{black}{\cdots}}\) -- the odd natural numbers greater than 1. The strategy is to use these gnomons to find a

*recursion relation*between \({\color{black}{S_{i-1}}}\) and \({\color{black}{S_i}}\).

First, we can write \begin{equation} \label{S_i} S_i = S_{i-1} + 2i-1. \end{equation} Continuing on, \begin{eqnarray} S_{i-1} &=& S_{i-2} + 2(i-1) -1 \nonumber \\ &=& S_{i-2} + 2i - 3. \end{eqnarray} Putting this into Eq. (\ref{S_i}) gives \begin{equation} S_i = S_{i-2} + (2i -1) + (2i - 3). \end{equation} Next, we examine the first few terms of the sum \({\color{black}{\sum_i^j S_i}}\), \begin{eqnarray} S_i + S_{i-1} + S_{i-2} + \cdots &=& S_{i-1} + (2i-1) + S_{i-1} + S_{i-2} \cdots \nonumber \\ &=&S_{i-2} + (2i-3) + (2i-1) + \cdots \nonumber \\ &=& 3S_{i-3} + 3\times(2i-5) + 2\times(2i-3) + (2i-1) + \cdots \end{eqnarray} The idea is to continue doing this until we have summed all the way down to \({\color{black}{S_1 = 1}}\) so that there are no \({\color{black}{S}}\)'s left on the right-hand side of the equation, except that that would take an eternity since \({\color{black}{i}}\) is arbitrarily large. The key is to identify the pattern emerging in the sum and

*guess*the expression. The terms are of the general form \({\color{black}{j\times(2i - 2j + 1)}}\), where \({\color{black}{j}}\) runs from \({\color{black}{1}}\) to \({\color{black}{i}}\), so that \begin{equation} \label{sumsquare} \sum_{j=1}^i S_j = \sum_{j=1}^i j\times (2i - 2j + 1) = \sum_{j=1}^i j^2. \end{equation} Solving for \({\color{black}{\sum j^2}}\) gives \begin{equation} \sum_{j=1}^i j^2 = \frac{i(i+1)(2i+1)}{6}, \end{equation} where we've used the earlier result Eq. (\ref{gauss_sum}). With \({\color{black}{i=100}}\), we solve \({\color{black}{(\sum^i j)^2 - \sum^i j^2}}\) using the square of Eq. (\ref{gauss_sum}) and Eq. (\ref{sumsquare}) giving \begin{equation} {\color{black}{ \boxed{25\,164\,150} }} \end{equation}

#### 7. 10001st prime

*By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?*

The solution requires a simple program that computes prime numbers. Here is one that does so through trial division:

#include <stdio.h> #include <math.h> int main(int argc,char *argv[]) { int n = atoi(argv[1]); int i=0,j=0,k=0,prime; FILE * out; out = fopen("out_primes.dat","w"); fprintf(out,"2\n"); // small cheat /* * For each i, perform trial divisions for all numbers less than * sqrt(i). */ for(i=3; i<n ;i=i+2) { prime = 1; for(j=3; j<=(int)ceil(sqrt(i)); j=j+2) { if(i%j == 0) // j divides i { prime = 0; break; // not prime, break } } if(prime) { fprintf(out,"%d\n",i); k++; } } fclose(out); fprintf(stdout,"There are %d primes smaller than %d\n",k+1,n); return 0; }It computes the \({\color{black}{n^{th}}}\) prime number. This is essentially the code inside the for loop in Problem 3; a description of how it works is given there. For an input of 10001, we find \begin{equation} {\color{black}{ \boxed{104\,743} }} \end{equation}

#### 8. Largest product in a series

*The four adjacent digits in the 1000-digit number that have the greatest product are 9 x 9 x 8 x 9 = 5832.*

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

This is a straight-forward coding exercise: the idea is to read this massive number in as a string and step through it in blocks of 13 digits, computing the product of each block. There will be many strings of 13 digits that contain zeros and these can be discarded from the outset; however, with only 988 products to compute this efficiency measure is probably not warranted. One caveat is that 64-bit data types are needed since the products can be quite large. In C, we therefore need long long int types, but these are painful to use

^{2}. Python has a much more forgiving handling of integer types, and so Python it is:

import sys import os str = """7316717653133062491922511967442657474235534919493496983520 3127745063262395783180169848018694788518438586156078911294949545950 1737958331952853208805511125406987471585238630507156932909632952274 4304355766896648950445244523161731856403098711121722383113622298934 2338030813533627661428280644448664523874930358907296290491560440772 3907138105158593079608667017242712188399879790879227492190169972088 8093776657273330010533678812202354218097512545405947522435258490771 1670556013604839586446706324415722155397536978179778461740649551492 9086256932197846862248283972241375657056057490261407972968652414535 1004748216637048440319989000889524345065854122758866688116427171479 9244429282308634656748139191231628245861786645835912456652947654568 2848912883142607690042242190226710556263211111093705442175069416589 6040807198403850962455444362981230987879927244284909188845801561660 9791913387549920052406368991256071760605886116467109405077541002256 98315520005593572972571636269561882670428252483600823257530420752963450""" biggest = 0 for i in range(0,988): x = 1 for j in range(0,13): x = int(str[i+j])*x # print("%s %s" % (x,str[i+j])) if x > biggest: biggest = x k = i print("Digits: %s\nProduct: %s" % (str[k:k+13],biggest))This script identifies 5576689664895 as the 13 consecutive digits. Their product is \begin{equation} {\color{black}{ \boxed{23\,514\,624\,000} }} \end{equation}

#### 9. Special Pythagorean triple

*A Pythagorean triplet is a set of three natural numbers, \({\color{black}{a < b < c}}\), for which, \({\color{black}{a^2 + b^2 = c^2}}\). For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.*

Euclid in his

*Elements*discovered that integers that satisfy the equation \({\color{black}{a^2 + b^2 = c^2}}\) can be written \begin{eqnarray} \label{9euclid} a &=& k\cdot(m^2 - n^2) \nonumber \\ b &=& k\cdot2mn \nonumber \\ c &=& k\cdot(m^2 + n^2) \end{eqnarray} where \({\color{black}{m}}\), \({\color{black}{n}}\), and \({\color{black}{k}}\) are positive integers with \({\color{black}{m > n}}\), \({\color{black}{m-n}}\) odd, and \({\color{black}{m}}\) and \({\color{black}{n}}\) coprime (they share no common factors). In terms of these integers, the condition \({\color{black}{a+b+c = 1000}}\) becomes \({\color{black}{km\cdot(m+n)= 500}}\). We have written \({\color{black}{500}}\) as essentially a product of two factors: \({\color{black}{km}}\) and \({\color{black}{(m+n)}}\). There are not many ways to write \({\color{black}{500}}\) as a product of two factors, only 10 actually: \({\color{black}{500\times 1}}\), \({\color{black}{250\times 2}}\), \({\color{black}{125\times 4}}\), \({\color{black}{100\times 5}}\), \({\color{black}{50\times 10}}\) and their commutated forms. The idea is to match \({\color{black}{km}}\) and \({\color{black}{(m+n)}}\) with one of these factorizations. It's lucky that there are only 10, or else we'd likely need to use a computer. The first two don't work: \({\color{black}{(m+n) > 2}}\) since \({\color{black}{m > n}}\). The third is also no good: while we can arrange for \({\color{black}{m+n = 4}}\) with \({\color{black}{m=3}}\) and \({\color{black}{n=1}}\), \({\color{black}{3k \neq 125}}\) for any \({\color{black}{k}}\) since 125 is not a multiple of 3. We hit pay dirt with the fourth factorization: \({\color{black}{100 \times 5}}\). We have \({\color{black}{m+n=5}}\) with \({\color{black}{m=4}}\) and \({\color{black}{n=1}}\), and \({\color{black}{4k = 100}}\) with \({\color{black}{k = 25}}\).

Using these values of \({\color{black}{m}}\), \({\color{black}{n}}\), and \({\color{black}{k}}\) in Eq. (\ref{9euclid}) gives \({\color{black}{a = 375}}\), \({\color{black}{b=200}}\), and \({\color{black}{c=425}}\). It is easy enough to check that \({\color{black}{(a,b,c)}}\) forms a Pythagorean triplet, \({\color{black}{a^2+b^2 = c^2}}\). Their product is \begin{equation} {\color{black}{ \boxed{abc = 31\,875\,000} }} \end{equation}

#### 10. Summation of primes

*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million..*

We can use a code very similar to the one written to solve Problem 7, but one that computes and sums all the primes less than some number \({\color{black}{n}}\) rather than the \({\color{black}{k^{th}}}\) prime.

#includeThe sum of the first 2 million primes is \begin{equation} {\color{black}{ \boxed{142\,913\,828\,922} }} \end{equation}#include /* * This program takes a single integer command line argument. * It writes a file containing all the primes less than the input integer and outputs their sum and the number of primes less than this number. */ int main(int argc,char *argv[]) { int n = atoi(argv[1]); int i=0,j=0,k=0; int noprime = 0; FILE * out; out = fopen("out_trial.dat","w"); long long int sum; fprintf(out,"2 "); sum = 2; /* * For each i, perform trial divisions for all numbers less than * sqrt(i). */ for(i=3;i<=n;i=i+2) { noprime = 0; for(j=1;j<=(int)ceil(sqrt(i));j=j+2) { if((i%j == 0)&&(j!=1)) // j divides i { noprime = 1; break; // not prime, break } } if(!noprime) { sum = sum + i; fprintf(out,"%d ",i); k++; } } fclose(out); fprintf(stderr,"largest prime = %d, sum of primes = %lld\n",k+1,sum); return 0; }

Download as PDF