The year from the indiction
Old charters and chronicles were often dated not only by year but also by numbers in three calendar cycles: the indiction, the number of the year in a fifteen-year cycle; the golden number, the number in the nineteen-year lunar cycle; and the solar cycle, the number in a twenty-eight-year cycle after which the days of the week in the Julian calendar fall on the same dates again. In 1583 Joseph Scaliger noticed that the three numbers together repeat only after 15 · 19 · 28 = 7980 years, and called this span the Julian period. Its first year, 4713 BC, is the one where all three numbers equal one.
For a year Y AD the indiction is (Y + 2) mod 15 + 1, the golden number Y mod 19 + 1, the solar cycle (Y + 8) mod 28 + 1. In 2026 they are 4, 13 and 19. An archivist needs the reverse: find the year from the three numbers. Years run from 4713 BC to AD 3267 inclusive; there is no year zero, and 1 BC is followed directly by AD 1.
Input
The first line holds the number of queries t (1 ≤ t ≤ 100,000). Each of the following lines holds the indiction i, the golden number g and the solar cycle s (1 ≤ i ≤ 15, 1 ≤ g ≤ 19, 1 ≤ s ≤ 28).
Output
For each query, the year in the form N AD for the common era or N BC before it, for example 2026 AD or 45 BC.
Examples
Example 1
3 4 13 19 11 7 24 4 2 10
2026 AD 1583 AD 1 AD
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 5 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The number of a year in the Julian period x (from 1 to 7980) gives the remainders x mod 15, x mod 19, x mod 28, which match the cycle numbers if number 15 is read as remainder 0, number 19 as zero, and so on. The moduli 15, 19, 28 are pairwise coprime. What does the Chinese remainder theorem guarantee?
2Hint 2
Year 4714 of the period is AD 1. Which year of the period corresponds to 1 BC? And to 45 BC?
3The idea
By the Chinese remainder theorem the triple of remainders determines the year of the period uniquely. It can be found by Garner's algorithm: x = c₀ + 15c₁ + 285c₂, where c₀ = i mod 15, c₁ = (g − c₀)·15⁻¹ mod 19, c₂ = ((s − c₀)·15⁻¹ − c₁)·19⁻¹ mod 28. Or by de Billy's formula: x = (6916i + 4200g + 4845s) mod 7980. Or you can fill in a table of all 7980 years in advance: there are only that many.
4Walkthrough
Find the number x from 1 to 7980; remainder 0 means year 7980, that is, AD 3267. Then convert to an era: if x > 4713, it is the year x − 4713 AD; otherwise the year 4714 − x BC. A check at the edges: x = 4714 → 1 AD, x = 4713 → 1 BC, x = 1 → 4713 BC.
Where 4714 and 4713 come from. Astronomers number years consecutively: for them 1 BC is year 0, 2 BC year −1. In this count the year of the period x is the astronomical year x − 4713, and the historical notation comes from it like this: a positive number is the same year AD, zero and negative ones are the year 1 − (x − 4713) = 4714 − x BC.
4+Solution
5Complexity
O(1) per query: a few multiplications modulo 15, 19, 28. With a table, O(1) per query and 7980 entries in advance.
6Common mistakes
- Year zero. The formula 4713 − x for years BC is off by one: 1 BC comes out as “0 BC”. Historical numbering has no year zero.
- Number 15 instead of remainder 0. Cycle numbers run from 1 to 15, remainders from 0 to 14. If 15 is put into Garner's formula as it is, the answer does not change only because 15 ≡ 0 modulo 15; with subtraction, though, it is easy to get a negative number, and in Go % of a negative number is negative.
- Year 7980. Remainder 0 modulo 7980 is not year 0 of the period but the last, the 7980th year: AD 3267.
Algorithms behind it
O(k²) operations on machine numbers
2 problems
NUM
Algorithm
Euclid's algorithm
The greatest common divisor of two numbers in O(log n) divisions with remainder.
O(log min(a, b))
2 problems