# Easter Dates Different

Show that there in no natural number $n$ such that, for each year $A$, the years $A$ and $A+n$ have the Easter with the same date. Use a computer program for your proof: A number of programs of Easter Date have been set up, but to make it simple, use the following which is applicable for calculators.

Input "YEAR", A
A+1-19(int(A/19))->G
int(A/100)+1->C
int(3*C/4)-12->X
int((8*C+5)/25)-5->Z
int(5*A/4)-X-10->D
11*G+20+Z-X->B
B-30(int(B/30))->E
If ((E=25) and (G>11)) or (E=24)
E+1->E
44-E->N
If N<21
N+30->N
D+N-7*int((D+N)/7)->F
N+7-F->M
If M>31
Then
Disp M-31, "APRIL"
Else
Disp M, "MARCH"
END

• I have no idea what all that stuff in the second paragraph is supposed to do. Commented Jul 19, 2013 at 9:18
• Basically it should be enough to show that an earth year (365.25 days) and moon revolution (27.32 days) do not line up, resulting in a shift. And thanks to leap years, the only valid answer would be something like 400, cause for everything else you break with leap years. Unfortunately, in 400 years, the 1/1 is not the same as 1/1 + 400, so it will just not happen. Every other number can be broken with leap years. Commented Jul 19, 2013 at 9:28
• This If ((E=25) and (G>11) or (E=24) has unbalanced parentheses. Would I be correct to assume that you mean If ((E=25) and (G>11)) or (E=24)? The line D+N->7*int((D+N)/7)->F is unclear as well, due to the double ->. Please fix this by editing the question.
– MvG
Commented Jul 19, 2013 at 9:38
• This is Algorithm E (Date of Easter) in section 1.3.2 of Knuth's The Art of Computer Programming. Commented Jul 19, 2013 at 12:17
• The present version has no bugs I suppose. I thought of a mathematical problem relating to the algorithm which is described in the program. I still don't know the solution. My thanks to Anton Commented Jul 19, 2013 at 23:44

# My understanding of the question

I'm not entirely sure how to interpret your question, but I assume taht you take the program you quoted as your definition of the Easter date, and are asking whether or not this program will result in the same answer for $A$ and $A+n$ for a fixed and suitably chosen $n$ and for all years $A$. In other words:

$$\exists n\in\mathbb N\;\forall A\in\mathbb N:f(A) = f(A+n)$$

where $f$ denotes the function $A\mapsto M$ described by your program code, without any further relation to astronomical aspects which lead to this program.

# There is such an n

If this is the question, then the answer is that there is such an $n$, even though your question seems to imply the opposite. The smallest $n$ satisfying your requirements would be the following:

$$n = 100\cdot4\cdot25\cdot19\cdot30 = 5{,}700{,}000$$

# Proof for the existence of a period

The argument goes as follows:

• Increasing $A$ by $19$ will result in the same value of $G$
• Increasing $A$ by $100$ will increment $C$ by a fixed constant
• Increasing $A$ by $100\cdot4$ will increment $X$ by a fixed constant
• Increasing $A$ by $100\cdot25$ will increment $Z$ by a fixed constant
• Increasing $A$ by $100\cdot4$ will increment $D$ by a fixed constant
• Increasing $A$ by $100\cdot4\cdot25\cdot19$ will increment $B$ by a fixed constant
• Increasing $A$ by $100\cdot4\cdot25\cdot19\cdot30$ will result in the same value of $E$, both before and after the If
• The same holds for $N$
• Increasing $A$ by $100\cdot4\cdot25\cdot19\cdot30$ will increment $D+N$ by a fixed constant (see below for the value of that constant)
• Increasing $A$ by $100\cdot4\cdot25\cdot19\cdot30\cdot7 = 7n$ will result in the same value for $F$
• If $N$ and $F$ are the same, then so is $M$ and hence the date of Easter

So the above will give a possible period:

$$7n=100\cdot4\cdot25\cdot19\cdot30\cdot7=39{,}900{,}000$$

# Finding the shortest period

The period found in this way is seven times larger than the shortest possible period. The shortest possible period must be a divisor of the period already found. So when searching for a shorter period, concentrating on divisors helps reducing the search space, and prime factor decomposition will be a valuable tool.

The actual shortest period can be found with high probability using a computer experiment: Stripping one prime factor at a time, one can check whether the resulting number still can be a valid period, simply by comparing the results for a couple of years. For all prime factors except $7$, this fails quickly, therefore proving that the corresponding prime factor has to be present in the shortest possible period. On the other hand, when removing the unneccessary factor of seven, one will observe that for many years, the numbers will still agree.

Of course that is no proof that they will be equal for all years. To obtain such a proof, one can compute the change to $D+N$ if $A$ increases by $n$. That number is fixed, as argued above, so it can be computed for any combination of $A$ and $A+n$. The resulting difference turns out to be $7{,}082{,}250=7\cdot1{,}011{,}750$. Since this is a multiple of $7$, the value $F$ which depends on $(D+N)\bmod7$ will already repeat with a lag of $n$ years, and not only after $7n$ years.

• On cursory examination, I saw no appearance of an irrational number, so the whole mess seems to be defined over $\mathbb Q$. So it would seem that the claim of nonperiodicity has to be false. Of course the genuine period of the moon is in some philosophical sense irrational, so the given program can’t possibly be precisely correct. Maybe it would be appropriate here to point out that in the past, people have slaughtered each other over the correct date for Easter… Commented Jul 19, 2013 at 22:41
• @Lubin: It would be possible to define a non-repeating sequence using only integers. Not using dates, one could alternate zeros and ones, and increase the number of zeros between two ones by one, i.e. $1,1,0,1,0,0,1,0,0,0,1,…$. This would be clearly non-periodic. I guess this would require programming constructs not found in the presented algorithm, but I'm not quite sure where to draw the line. Probably forbidding loops and recursion might suffice. Speaking philosophically, at some time there won't be a moon, so questions about eternal truths can't refer to the real moon.
– MvG
Commented Jul 19, 2013 at 22:52
• Thanks MvG for an excellant answer! I really appreciate your reasonniong. Commented Jul 19, 2013 at 23:54
• @ChristopherSokolnicki: Glad to head that. You may show your appreciation by upvoting and accepting the answer. If a better answer should turn up one day, you can still change the accepted answer then.
– MvG
Commented Jul 20, 2013 at 19:03
• This answer concurs with the calculations on this Wikipedia page, where the exact same $5700000$ period is obtained. Commented Jul 24, 2013 at 8:55

A computer program cannot prove the non-existence of an entity.

• Sometimes it can - for example, it can prove the non-existence of a prime lying between two given integers. Also, I think your answer should better be a comment. Commented Jul 19, 2013 at 9:39
• I'd read “use a computer program” as “use this computer program as your definition of the Easter date”, on which the subsequent (possibly manual) proof can be based. By the way, proof assistants are probably the most rigorous way to prove the non-existence of anything, and they certainly are computer programs.
– MvG
Commented Jul 19, 2013 at 11:15

Actually I gave this some more thought and testing:

every 400 years the dates actually do repeat perfectly.

Now if you take the exact revolution of the moon into account, it would be:

N = days it takes the moon to orbit the earth.

Find a * 400 so that N divides this PERFECTLY (with no rest), and you have a constant n after which easter will repeat itself.

• Note: leap years will be broken again after 3200 years. Thats the deal, you will have to live with a certain uncertainty, which basically screws this program. But writing a computer program to do this, no chance. Commented Jul 19, 2013 at 9:36
• This perfect division assumes that this $N$ is rational, but given the fact that the easter date calculator cannot deal in irrational numbers, for this computation method it should work.
– MvG
Commented Jul 19, 2013 at 9:37
• It all depends on the accuracy needed. I feel like it will never work completely, since the rotational speeds of both earth and moon change, thus making every try obsolete in the first place. Commented Jul 19, 2013 at 9:38