How old is the ship of Theseus?

Question

The ship of Theseus consists of n parts. The first part needs to be replaced every day, the second part every second day, the third part every three days and so on.

Theseus is concerned that replacing all parts on the same day may cause the ship to lose its identity, and become something different than the ship of Theseus. But he has a strategy to avoid this situation: whenever all parts are scheduled for replacement on the same day, before starting to replace the old parts, he adds a new part to his ship, which only needs to be replaced in $n + 1$ days.

The ship originally consisted of only one part and today Theseus has announced that he's added the 100th part to it.

How old is the ship of Theseus?

Answer 1

First parts

Starting from the first day, Theseus has a single-part ship: this means that this part can only work for a day before being replaced, so Theseus should replace the first part on the second day. Given that replacing the first and only part will let the ship "lose its identity", then before replacing the first part, Theseus adds a second part: so the second part of his ship is added on the second day, before removing the first one.

On the second day, the first part has got to be changed again, but the second part has still got one day. On the third day the parts will be changed together, meaning that Theseus will have to add a third part.

Adding the nth part

When will Theseus have to change all the $n$ parts together again? It is easy to understand that Theseus will have to change all the parts when the number of days becomes equal to $lcm(1, 2, 3, ..., n-1, n) + 1$, which is the least common multiple of the duration of each part plus one, because the first day the only existing part doesn't have to be changed.

We can write a table representing the day when Theseus has to change all the $n$ parts together based on $n$:

n       day

1       2
2       3
3       7
4       13
5       61
6       61
7       421
8       841
9       2521
10      2521
...     ...
60      9690712164777231700912801
61      591133442051411133755680801

We can clearly see that this number becomes dramatically large when dealing with these amounts of parts.

---

Solution

When Theseus adds the $100$th part, this means that he already changed all the parts together $99$ times (adding a new part every time), and that it has come the day to change all the parts together again. So the age $A$ of the ship can be obtained solving the following equation:

$A = 1 + \sum \limits_{i=1}^{99} lcm(1, 2, ..., i) \simeq 2.149 \times 10^{41}$

The ship is $214959977860203405582463952869483994880562$ days old.

Which is around $588.93$ billions of billions of billions of billions of years, WOW!

Program

I created a small Python 2.7 script to calculate the number of days, here it is:

from fractions import gcd

def lcm(a, b):
    return (a/(gcd(a, b))*b)

age = 1 
for i in xrange(1, 100):
    age += reduce(lcm, range(1, i+1))

print "Theseus' ship is", age, "days old!"

Answer 2

Very old indeed - Theseus is effectively immortal, and his ship is almost certainly space-faring, as the number of days is rather more than the current age of the universe, and probably more than the expected life of most suns.

The actual answer is more than $32\times 27\times 35\times 97\#$, where $97\#$ (97 primorial) is the product of all primes up to $97$.

This number is the least common multiple of all the numbers up to $100$. However there are some extra multiples in there too, so the actual age is larger than this, although it is less than $100!$ (100 factorial).

By way of concrete example, when Theseus added the 22nd part, the ship was approximately 2 million years old.

Answer 3

The ship is

214959977860203405582463952869483994880561

days old.

Explanation:

If the nth part is added today, the (n+1)th part will be added after lcm(1…n) days. Thus the 100th part gets added on day number $\sum_{i=1}^{99} \mathrm{lcm}(1,\ldots i)$.