by Dr. Irv Bromberg, University of Toronto, Canada
[Click here to go back to the Calendar Leap Cycles web page]
Calendars LISTSERVFixed Leap Cycle Finder uses the brute force
method to find leap cycles within a specified target mean year range, that is it finds cycles by arithmetically testing all possible permutations and combinations of leap years per cycle and years per cycle up to the specified maximum number of years per cycle. It is surprisingly fast, considering that most of the cycles that it tests are actually discarded because their mean year falls outside the target range. The continued fraction method just discussed is more direct, but depending on the starting target value it often misses useful calendar cycles that are just nearby. An alternative, much more elegant and efficient method to find all possible leap cycles is the mediant fraction method:
For any given fractions a/c and b/d, their mediant fraction is (a+b) / (c+d), that is the sum of their numerators divided by the sum of their denominators.
A sequence of such fractions, generated for example starting from 0/1 and 1/1 and including fractions up to a specified maximum denominator, is known as an nth order Farey sequence, where n is the maximum denominator, even though the British geologist John Farey, Sr. himself only mentioned the mediant fraction arithmetic briefly in a letter published in Philosophical Magazine in 1816. Charles Haros was the French mathematician who originally published the mediant fraction method in 1801. Haros was charged with producing a list of all fractions having denominators less than 100 (there are 3003 such fractions) along with their decimal equivalents, because at the time France was in the process of switching from using fractional to decimal denominations.
Any fractions a/c and b/d are nth order Farey sequence neighbours if bc – ad = 1. If so, then all fractions between them having lower or higher denominators can be generated using the mediant fraction method. Cycles corresponding to such fractions are the same as the mixer
cycles that Fixed Leap Cycle Finder reports. The mediant fraction method is very useful for finding all possible leap cycles within a target mean year range. One need only find the Farey sequence neighbours that are closest to the target mean year range, then calculate all of the mediant fractions between them up to a specified maximum denominator.
For lunar calendars the cycle fraction is the number of full months per cycle divided by the number of months per cycle. A 17-month yerm is composed of alternating full (30 day) and deficient (29 day) months in the pattern FDFDFDFDFDFDFDFDF, having a mean month of 29+9/17 days = 29 days 12 hours 42 minutes and 21+3/17 seconds. A 15-month yerm drops one FD pair = FDFDFDFDFDFDFDF, which has a mean month of 29+8/15 days = 29 days 12 hours and exactly 48 minutes. For fixed arithmetic lunar cycles the appropriate long mean month mixer to use is 29/49, which is the same as the most common 49-month lunar subcycle, containing only 3 yerms of 17+17+15 months respectively, having a mean month of 29+29/49 days = 29 days 12 hours 44 minutes and 4+44/49 seconds, and the appropriate short mean month mixer to use is 9/17, which contains only one 17-month yerm. For more information see the yerm concept and calendar as defined by Karl Palmen at Yerm Lunar Calendar
<http://www.hermetic.ch/cal_stud/palmen/yerm1.htm>.
For other types of calendar cycles, to find the mixer cycles we need only execute a loop, where MaxLimit and MinLimit are the longest and shortest mean year fractions for our desired list of leap cycles. For lunar cycles these limits are directly ready to use, but for solar and lunisolar cycles convert them to the minimum and maximum allowable cycle fraction, numerator / denominator, which corresponds to the inverse of the average interval between leap or skip years:
IF CycleType = Lunar THEN
MinCycleFraction = MinLimit
MaxCycleFraction = MaxLimit
ELSE IF DaysPerLeap < 0 THEN ' skip short
YearLessNominal = LengthOfLongYear – floor( MeanYear )
DaysPerSkip = DaysPerLeap
MinCycleFraction = (MaxLimit – YearLessNominal) / DaysPerSkip
MaxCycleFraction = (MinLimit – YearLessNominal) / DaysPerSkip
ELSE ' leap long
YearLessNominal = LengthOfShortYear – floor( MeanYear )
MinCycleFraction = (MinLimit – YearLessNominal) / DaysPerLeap
MaxCycleFraction = (MaxLimit – YearLessNominal) / DaysPerLeap
END IF
Start the following loop with the long mixer initiated to a one-year cycle in which every year is long and the short mixer initiated a one year cycle in which every year is short by setting the starting mixers to 1/1 and 0/1, respectively.
DO
numerator = sum of mixer numerators
denominator = sum of mixer denominators(Because we are building up the mediants starting from 1/1 and 0/1 and will stop before the denominator gets particularly high, there is never any need to reduce the mediant while looping to find the mixer cycles. For some calendar types the loop may approach 30 iterations.)
Calculate the simple ratio of numerator to denominator. For lunar cycles this represents the ratio of full months to the total number of months per cycle. For solar and lunisolar cycles it represents the inverse of the average leap or skip year interval. Either way the arithmetic is the same.
CycleFraction = numerator / denominator
IF CycleFraction >= MaxCycleFraction THEN
Long mixer is too long, change it to numerator / denominator
ELSEIF CycleFraction <= MinCycleFraction THEN
Short mixer is too short, change it to numerator / denominator
END IF
LOOP UNTIL CycleFraction >= MaxCycleFraction AND CycleFraction <= MinCycleFraction
The loop exits as soon as it finds a mediant fraction within the target range.
Before using the mixer cycles, if the calendar type employs skip short cycles then swap the mixers.
The above algorithm for finding the mixer cycles is courtesy of K.E.V. (Karl) Palmen, formerly of the Rutherford Appleton Laboratory in the United Kingdom, now retired, based on correspondence via the CALNDR LISTSERV
during Janary 2011. It was also Karl’s prompting in October 2010 that got the Ford circles workbook started (but not until December 2010, see below), and he provided critically helpful guidance at several points during that project.
After finding appropriate mixer cycles, the following loops can calculate all of the desired mediant fractions that are within the target range, up to the specified maximum denominator. The loop will discard a few fractions that are outside the target range, depending on how far away the mixer cycles are from the target range. Provided that the loop starts with appropriate mixer cycles, none of the generated mediant fractions need to be reduced.
The mediant fraction method inherently inserts each generated fractions in its proper position in the sequence, sorted descending by the cycle mean year (or month). The algorithm as written below requires that the starting mixers must be arranged in descending mean year (or month) order.
The mediant fraction generation algorithm shown next checks whether each mediant fraction is within the target range, based upon the simple cycle fraction. This is optional because, depending on the programming environment, it may be more efficient to insert all mediants whose denominator is not beyond the maximum, and then either keep all of the generated fractions or discard the out-of-range fractions after the generation phase is complete. To keep all of the fractions, omit all statements concerning the CycleFraction or the in-range row numbers, highlighted in brown, like this paragraph.
For best performance, I suggest implementing the list of cycles as a doubly-linked list in memory, containing the following fields:
When inserting
a cycle into such a list, no previously generated entries are moved, the new entry is simply appended to the list and linked into the current working position in the list. In a computer programming language such as C, each element of the list will probably be allocated as needed. In a language like BASIC, it will be more efficient to dimension an array that is large enough to hold the longest desired list (like 4000 elements, if memory permits), or check the MediantCount as the list grows, and when necessary redimension the array larger by a good chunk (like 1000 elements), preserving its contents.
Starting with an empty list, put the long mixer into the first row of the list and the short mixer in the second row of the list, marking them both as 0th order, then put their first mediant into the third row of the list, marking it as first order and linking it appropriately between the first and second rows. Initialize MediantCount = 3 and nthOrderNumber = 1 to indicate that the list is starting with these 3 fractions already in place and that nth orders 0 and 1 have already been used.
As the algorithm executes, it will track the first and last in-range row numbers. If the mixers were appropriately selected as per the algorithm above, then by definition the first mediant must be within the target range, so initialize the first and last in-range row numbers to point to that first mediant fraction.
FirstInRangeRow = 3
LastInRangeRow = 3
DO (begin outer loop, which repeatedly executes the inner loop until no more cycles are inserted)
Clear the InsertedCycles counter to zero. The inner loop will increment this count whenever a within-range cycle is inserted, and this outer loop will exit when it finds that the count is still zero after the inner loop exits.
Increment the nthOrderNumber.
acRow = Mediants(FirstInRangeRow).PrevCycle
Get set up for the first mediant fraction calculation of the next pass through the inner loop.
It is impossible to have already reached the end of the list at this point.Assign variables
aandcequal to the numerator and denominator of the mediant at acRow, respectively.bdRow = Mediants(FirstInRangeRow).NextCycle
Assign variables
banddequal to the numerator and denominator of the mediant at bdRow, respectively.DO (begin inner loop, which executes a single top-down pass down the list of cycles)
Calculate the next mediant fraction. We can do the denominator first because we only need the numerator if the denominator is within the specified maximum denominator limit:
denominator = c + d
(As mentioned above, there is never any need to reduce this new mediant fraction, provided that the long and short mixer cycles were properly selected.)
IF the mediant fraction’s denominator is less than or equal to the specified maximum denominator THEN
InsertedCycles = InsertedCycles + 1
Here we use MediantCount to refer to the row number of the element position that we will use for this new mediant fraction. In a language like C one would instead allocate a new element in memory and track its memory address.
MediantCount = MediantCount + 1
At this point, if allocating list elements individually then do so, or if allocating the list in chunks than check if it is necessary to expand the list, and so then allocate another chunk.
numerator = a + b
Calculate the simple ratio of numerator to denominator:
CycleFraction = numerator / denominator
(For non-lunar cycles, the inverse ratio denominator / numerator is simply the average number of years between leap or skip years. For lunar cycles, numerator is the number of full 30-day months per cycle and denominator is the total number of months per cycle.)
The following IF ... THEN expression eliminates out-of-range cycles from further consideration, except those that are just outside, to avoid wasting computation time. If there are no in-range low order cycles between the initial mixers, as occurs in the case of a leap day calendar with leap long mixers 1/4 and 0/1 or skip short mixers 3/4 and 1/1, then the algorithm will keep generating mediants oscillating around a mean year of 365.2 days, until it reaches the maximum specified denominator. Normally this is not a practical problem because 1/4 is an inappropriately long mean year fraction, and as a workaround it is easy to specify a shorter (or perhaps a longer) maximum mean year length (one second suffices). If you really must use such leap day mixers then substitute IF TRUE THEN.
IF CycleFraction >= MinCycleFraction AND CycleFraction <= MaxCycleFraction THEN
The new mediant fraction is within the target range. Remember it as the first or last in-range row if its CycleFraction is closer to either limit. The cycle fractions go in descending sequence for leap long cycles, but they go in ascending sequence for skip short cycles. It is impossible for this CycleFraction to qualify as both the first and last in range row because the only cycle that that condition can apply to is the first mediant fraction, which was generated before entry into the outer loop.
IF DaysPerLeap < 0 THEN ' solar skip short
IF CycleFraction < Mediants(FirstInRangeRow).CycleFraction THEN
FirstInRangeRow = MediantCount
ELSE IF CycleFraction > Mediants(LastInRangeRow).CycleFraction THEN
LastInRangeRow = MediantCount
END IF
ELSE ' solar leap long, or lunar
IF CycleFraction > Mediants(FirstInRangeRow).CycleFraction THEN
FirstInRangeRow = MediantCount
ELSE IF CycleFraction < Mediants(LastInRangeRow).CycleFraction THEN
LastInRangeRow = MediantCount
END IF
END IF
END IF ' within target range
Add the new mediant fraction to the list. Here we use MediantCount to access the new element of the mediant array, but in a language like C one would employ the element’s memory pointer instead.
Mediants(MediantCount).nthOrderNumber = nthOrderNumber
Mediants(MediantCount).numerator = numerator
Mediants(MediantCount).denominator = denominator
Mediants(MediantCount).CycleFraction = CycleFraction
Mediants(MediantCount).PrevCycle = acRow
Mediants(MediantCount).NextCycle = bdRow
Maintain a doubly linked list by adjusting the next and previous cycle pointers of the elements before and after this new element. The new mediant becomes the next cycle for the cycle ahead of it, which has a longer mean year (or month), and becomes the previous cycle for the cycle after it, which has a shorter mean year (or month):
Mediants(acRow).NextCycle = MediantCount
Mediants(bdRow).PrevCycle = MediantCount
Optionally one can save additional information about the cycle here, if you have reserved fields for that, or can do it later after it is certain that this cycle will be kept.
END IF
Avoid wasting time inserting any mediants beyond the row after the last row that is within range. If acRow is already pointing to the LastInRangeRow then we have already used it to attempt to find a mediant that might extend the range to a shorter CycleFraction so there is no point in going any further. This is the normal way to exit from the loop, because before entering the outer loop we applied the first and last in-range row to the first mediant fraction, and therefore the last in-range row is guaranteed to exist if the starting mixers were appropriately selected as per the algorithm given above. Alternatively, if not bothering with limiting the generated mediants to only those that are within the target range, omit the following statement and the loop will terminate after the short mixer.
IF acRow = LastInRangeRow THEN EXIT DO
acRow = bdRow
bdRow = Mediants(bdRow).NextCycleThe following statement is normally never True because the outer loop always includes the first order mediant fraction, which must be an in-range cycle, hence the loop must exit at the last in-range row above, so it should never actually reach the point where bdRow = 0. Nevertheless, keep this here as a precaution to prevent an endless loop in case inappropriate starting mixers are used.
IF bdRow = 0 THEN EXIT DO ' terminate after the short mixer
Otherwise, get ready for generating the next mediant fraction:
c = d
d = Mediants(bdRow).denominator
a = b
b = Mediants(bdRow).numeratorLOOP
Execute repeated passes down the list, each time around incrementing the nthOrderNumber, until no more qualifying cycles get inserted.
LOOP UNTIL InsertedCycles = 0
Even if checking for in-range cycles is included, the algorithm above does generate a few low nth order out-of-range mediant fractions, which optionally can be discarded after it exits.
It doesn’t matter what type of calendar cycle this is (leap day, leap week, leap month, lunisolar, lunar, Martian, or whatever), because if the limits are set as appropriate for the target mean year range then this method will generate only the leap cycles that are of the appropriate type. When appropriate starting mixers are selected, the above mediant fraction algorithm will find all of the possible leap cycles of the desired calendar type having a mean year (or month) within the specified target range and having denominators not exceeding the specified maximum.
Updated 11 Tammuz 5782 (Traditional) = 11 Tammuz 5782 (Rectified) = Jul 7, 2022 (Symmetry454) = Jul 7, 2022 (Symmetry010) = Jul 10, 2022 (Gregorian)