Consecutive Prime Sum: Project Euler

As proposed in my previous post, I decided to tackle another problem from Project Euler. This is Problem 50:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one hundred.

The longest sum of consecutive primes below one thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

So far I've completed eight out of the 723 problems currently available. This latest problem proved a difficult one to attack mainly because any recourse to subsets or partitions generated numbers so large that SageMathCell timed out. Even the method I developed of slicing the list of primes into progressively shorter lists caused a time out but for the upper limits of 100 and 1000 it worked fine:

upper_limit=100

P=[n for n in [2..upper_limit] if is_prime(n)]

record=0

for i in [i..len(P)-1]:

    for j in [i+1..len(P)-1]:

        Q=[p for p in P if p>=P[i] and p<=P[j]]

        if sum(Q)<upper_limit and is_prime(sum(Q)):

            if len(Q)>record:

                record=len(Q)

                print((P[i],P[j],sum(Q),len(Q)))

 (2, 3, 5, 2)

(2, 7, 17, 4)

(2, 13, 41, 6)

In the preceding code, we see that the six primes from 2 to 13 add to the prime 41.

upper_limit=1000

P=[n for n in [2..upper_limit] if is_prime(n)]

record=0

for i in [0..len(P)-1]:

    for j in [i+1..len(P)-1]:

        Q=[p for p in P if p>=P[i] and p<=P[j]]

        if sum(Q)<upper_limit and is_prime(sum(Q)):

            if len(Q)>record:

                record=len(Q)

                print((P[i],P[j],sum(Q),len(Q))) 

(2, 3, 5, 2)

(2, 7, 17, 4)

(2, 13, 41, 6)

(2, 37, 197, 12)

(2, 43, 281, 14)

(3, 53, 379, 15)

(3, 61, 499, 17)

(7, 89, 953, 21)

In the preceding code, we see that the 21 primes from 7 to 89 add to the prime 953.

Once the upper limit is set to 1000000, the time out problems began. I needed to set the \(i\) values manually starting with 0 and working up:

• starting with \(i=0\), I got a result of (2, 3863, 958577, 536)
• starting with \(i=1\), I got a result of (3, 3779, 920291, 525)
• starting with \(i=2\), I got a result of (5, 3911, 978037, 539)
• starting with \(i=3\), I got a result of (7, 3931, 997651, 543)

I submitted this last result to Project Euler and it proved the correct result so there was no need to keep going. Thus the answer to the question of which prime, below one-million, can be written as the sum of the most consecutive primes is 997651. It is the sum of 543 consecutive primes, beginning with 7 and ending with 3931. Line 4 of the code (as shown in Figure 1) reads: 

for i in [3 .. len(P)-1]: 

Here is the permalink to the code shown in the screenshot (Figure 1):

Figure 1

Lucas' Problem of the Married Couples

I've seen this problem before but I thought it interesting to revisit it and look at its historical background. This is Problem 8 in "100 Great Problems of Elementary Mathematics" by Heinrich Dörrie. The problem is stated as follows:

How many ways can \(n\) married couples be seated about a round table in such a manner that there is always one man between two women and none of the men is ever next to his own wife?

This problem appeared (probably for the first time) in 1891 in the Theorie des Nombres of the French mathematician Edouard Lucas (1842-1891), author of the famous work Récréations mathématiques. The English mathematician Rouse Ball has said of this problem, “The solution is far from easy.” The problem has been solved by the Frenchmen M. Laisant and M. C. Moreau and by the Englishman H. M. Taylor. A solution based upon modern viewpoints is to be found in MacMahon’s Combinatory Analysis. The approach adopted here is essentially that of Taylor (The Messenger of Mathematics, 32, 1903).

I spent quite some time, on and off, attempting my own solution before coming up short. It was a useful exercise however, because I explored various approaches and the most promising to me seemed to be one involving Cartesian products, so I got a fair bit of practice in working with these products. Once again I was trying for a brute force approach using SageMathCell to create all possible permutations and then imposing progressive restrictions on these permutations. However, the number of permutations quickly become huge and SageMathCell timed out for \(n=5\) and beyond.

According to WolframMathWorld, a closed form expression for \(n>1\) in terms of a sum due to Touchard (1953) is:$$A_n=\sum_k ^n \frac{2n}{2n-k} \binom{2n-k}{k} (n-k)! \, (-1)^k$$Once the formula is known it's easy enough to execute in SageMathCell. Here is the permalink to the calculation up to \(n=10\). The reason I'm quoting from WolframMathWorld and not the original book is that the explanation runs for several pages. Quite simply, as Rouse Ball put it, "the solution is far from easy". Wikipedia gives a simple, four-term recurrence (here is a permalink to the SageMathCell execution of it): $$ A_n = n \, A_{n-1}+2 \, A_{n-2}-(n-4) \, A_{n-3} - A_{n-4} $$ $$ \text{ with } A_2=0, A_3=1,A_4=2,A_5=13$$Wikipedia refers to this sequence of numbers as the mènage numbers and they form OEIS A000179, shown here for \(n=2 \text{ to } 10\):$$0, 1, 2, 13, 80, 579, 4738, 43387, 439792, ... $$It's clear that the number of arrangements increases at a very rapid rate. For just ten couples, there are almost half a million possibilities. The problem has connections with graph theory, knot theory and even chess (see Rooks Problem) but overall I found the problem rather too daunting and didn't have the patience or motivation to wade through the explanation in the book.

However, I'll quote the basis of the book's explanation:

The wives will then all have to be seated on the even- or odd-numbered chairs. In each of these two cases there are \(n!\) dif­ferent possible seating arrangements, so that there are \(2n!\) different possible seating arrangements for the women alone. We will assume that the women have been seated in one of these arrangements and we will maintain this seating arrangement through­ out the following. The nucleus of the problem then consists of deter­mining the number of possible ways of seating the men between the women.

Let us designate the women in the assumed seating sequence as \(F_1, F_2, ..., F_n \), their respective husbands \(M_1, M_2, ...,M_n\), the couples \( (F_1, M_1), (F_2,M_2),...,\) as \(1,2,...\) and the arrangements in which there are \(n\) married couples as \(n\)-pair arrangements. Let us designate the husbands about whom we have no further information as \(X_1, X_2, ...\).

Let \(F_1X_1F_2X_2,...,F_nX_n,F_{n+1}X_{n+1} \) be an (\(n+1)\)-pair arrangement in which none of the husbands sits beside his own wife. It must be remembered that the arrangement is circular, so that \(X_{n+1}\) is seated between \(F_{n+1}\) and \(F_1\). If we take \(F_{n+1}\) and \(M_{n+1}=X_{\nu}\) out of the arrangement and replace \(X_{\nu} \) with \(X_{n+1}=M_{\mu}\), we obtain the \(n\)-pair arrangement: $$F_1X_1F_2X_2...F_{\nu}M_{\mu}F_{\nu+1}...F_nX_n $$This arrangement can occur in three ways:

1. No man sits next to his wife (thus \( M_{\mu} \neq M_{\nu},M_{\mu} \neq M_{\nu+1}, X_n \neq M_1\)).

1. One man sits next to his own wife (namely when \(M_{\mu}=M_{\nu}\) or \(M_{\mu}=M_{\nu+1}\) or else \(X_n=M_1\)).

1. Two men sit next to their own wives (when \(M_{\mu}=M_{\nu}\) or \(M_{\mu}=M_{\nu+1}\) and at the same time \(X_n=M_1\), that is, when in our arrangement the order \(M_1F_1\) occurs.

It goes on and on from there but that's the start of the explanation anyway. On looking further ahead in the book, it seems that in general the problems are rather too difficult for a recreational mathematician to approach. For that reason, I may go back to Project Euler of which I've solved only 8 out of the 723 available problems. These problems are mathematical and require a programming solution.

The Weight Problem of Bachet de Meziriac

I have accumulated a great many mathematical ebooks and I decided that it was high time to make more use of them. To that end, I dusted off (so to speak) an old tome that was first published in 1958. It's titled "100 Great Problems of Elementary Mathematics" by Heinrich Dörrie. I settled on Problem 2 with title and exposition as follows:

The Weight Problem of Bachet de Meziriac

A merchant had a forty-pound measuring weight that broke into four pieces as the result of a fall. When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds. What were the weights of the pieces?

The observation is made by the author that:

This problem stems from the French mathematician Claude Gaspard Bachet de Méziriac (1581-1638), who solved it in his famous book Problèmes plaisants et délectables qui se font par les nombres, published in 1624. We can distinguish the two scales of the balance as the weight scale and the load scale. On the former we will place only pieces of the measuring weight; whereas on the load scale we will place the load and any additional measuring weights. If we are to make do with as few measuring weights as possible it will be necessary to place measur­ing weights on the load scale as well. For example, in order to weigh one pound with a two-pound and a three-pound piece, we place the two-pound piece on the load scale and the three-pound piece on the weight scale. 

Clearly this problem has some history. My first impulse was to devise an algorithm in SageMath that would provide a solution. This is really a brute force approach and does not involve much mathematical reasoning. The text book provides a carefully reasoned solution which I haven't looked at yet. However, I did skip ahead in the book to check that the solution provided by SageMathCell was the correct one. It was.

Here was my approach. The three smallest weights possible are 1, 2 and 3 pounds and so the maximum possible weight is 34 pounds. Thus a possible combination of weights would be 1, 2, 3 and 34 pounds for a total of 40 pounds. There are \(^{34}C_4 = 297 \) ways of choosing four different weights in a range from 1 to 40 in such a way that they total 40. Let's represent these weights by the list items \(w[0], w[1], w[2], w[3] \). Because we can place weights on the weight scale and the load scale, this means that weights can be subtracted from one another as well as added to one another. The best way to represent this is by coefficients \(a_0, a_1, a_2, a_3\) that can take values of -1, 0, 1. This means the possible weights are given by:$$weight=a_0 \times w[0] + a_1 \times w[1] + a_2 \times w[2] + a_3 \times w[3] $$It doesn't matter if some of these possible weights are negative or exceed 40 as this can be taken care of in the algorithm by restricting the range of possibilities. Here is the algorithm that I developed along with its output (permalink):

L=[ ]
N=[n for n in [1..34]]
C=Combinations(N,4)
for c in C:
    if sum(c)==40:
        L.append(c)
a0,a1,a2,a3=var('a0,a1,a2,a3')
for w in L:
    N=[ ]
    for a0 in [-1..1]:
        for a1 in [-1..1]:
            for a2 in [-1..1]:
                for a3 in [-1..1]:
                    weight=a0*w[0]+a1*w[1]+a2*w[2]+a3*w[3]
                    if weight>0 and weight<41:
                        N.append(weight)
    if Set(N).cardinality()==40:
        print(w) 

[1, 3, 9, 27]

It's interesting that only one set of weights covers all the possibilities from 1 to 40. Figure 1 is a plot of the combinations and the numbers from 1 to 40 that they cover. For example, it can be seen only one combination covers just 10 of the possible numbers and that is the combination of 1, 2, 3 and 34. No combination covers 11, 12, 13, 14, 15 or 16 possible numbers but 6, 8, 12 and 14 cover 17 of the numbers. Each blue dot represents a combination. It can be seen that 31 of the possible numbers are covered by a large number of different combinations.

Figure 1: permalink

Now the question that arises is why 1, 3, 9 and 27? What strikes me at first glance is that these weights can be represented as \( 3^0, 3^1, 3^2,3^3 \). In base 3 we have \(40_3=1111\) and each 1 represent represents one of the weights and a 0 would represent the absence of that weight. For example \( 39_3=1110\). With 38 however, we have a problem because \( 38_3=1102\) and the 2 would mean that two weights, each of 1 pound, would be needed. The solution is to move the 1 pound weight to the load scale so that:$$ \text{weight scale --> }39=1110_3 \equiv 1102_3+1_3 =38+1\text{ <-- load scale }$$Another example is 33 that has a representation of 1020 in base 3.$$\text{weight scale --> }36=1020_3 \equiv 1020_3+10_3 = 33+3 \text{ <-- load scale}$$By moving one or more of the weights to the load scale where necessary, all the possibilities from 1 to 40 can thus be covered. Similarly, if we had five weights of 81, 27, 9, 3 and 1, then all whole-numbered weight from \(1 =00001_3 \) pound to \(121=11111_3 \) pounds could be measured.

At this point, I haven't looked at the solution in the text book and that's what I'll do now. I've cheated a little I know because I worked out the solution by brute force and then sought to justify it. Here is the text book solution:

IF we have a series of measuring weights \(A, B, C, ... \) which when properly distributed upon the scales enable us to weigh all the integral loads from 1 through \(n\) lbs, and if \(P\) is a new measuring weight of such nature that its weight \(p\) exceeds the total weight \(n\) of the old measuring weights by 1 more than that total weight:$$p-n=n+1 \text{ or } p=2n+l$$THEN it is then possible to weigh all integral loads from 1 through \(p + n = 3n + 1\) by addition of the weight \(P\) to the measuring weights \(A, B, C, ...\).

In fact, the old pieces are sufficient to weigh all loads from 1 to \(n\) lbs. In order to weigh a load of \(p + x) \text{ and/or } (p —x)\) lbs, where \(x\) is one of the numbers from 1 to \(n\), we place the measuring weight \(P\) on the weight scale and place weights \(A, B, C, ...\) on the scales in such a manner that these pieces give either the weight scale or the load scale a preponderance of \(x \) lbs. 

This being established, the solution of the problem is easy. In order to carry out the maximum possible number of weighings with two measuring weights, \(A \) and \(B\), \(A\) must weigh 1 lb and \(B\) 3 lbs. These two pieces enable us to weigh loads of 1, 2, 3, 4 lbs. If we then choose a third piece \(C\) such that its weight \(c\) = 2 x 4 + 1 = 9 lbs, it then becomes possible to use the three pieces \(A, B, C\) to weigh all integral loads from 1 to \(c\)+ 4 = 9 + 4= 13.

Finally, if we choose a fourth piece \(D\) such that its weight \(d\) = 2 x 13 + 1 = 27 lbs, the four weights \(A, B, C, D\) then enable us to weigh all loads from 1 to 27 + 13 = 40 lbs. 

Conclusion. The four pieces weigh 1, 3, 9, 27 lbs.

I really can't quite grasp this rather verbose text book explanation and, naturally enough, find my base 3 explanation much simpler to understand. Overall, this has been an interesting exercise and really got me thinking so I'll probably attempt more of these.