# the largest chain of number

I found this problem on the internet: What is the largest chain of numbers that complies with that every number in the chain/list is a divisor divisor in the next number. For example 1 - 6 - 18 - 72 (this one is a chain of 4 numbers) and 5 - 25 - 100 (this one is a chain of 3 number) So the question is how many numbers do the longest chain contain - IF you may not use numbers higher than 1000?

I think it is 1 - 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 - 512, which contains 10 numbers. What do you think?

• How about find the number with the largest primefactor? – Nick Podowalski Dec 7 '14 at 13:06
• Consider the quotients $q_{n+1} = \frac{a_{n+1}}{a_n}$ Then $a_n = a_1\cdot q_2 \cdot q_3 \cdot \dotsc \cdot q_n$. So you are looking for the longest sequence $(q_2,q_3,\dotsc,q_m)$ such that $q_2\cdot q_3\cdot \dotsc\cdot q_m \leqslant 1000$, where you have the constraint $q_k \geqslant 2$. – Daniel Fischer Dec 7 '14 at 13:18

There is no longer chain because if the chain length is $11$ or more, the last number is at least $2^{10}=1024>1000$.
• Yes. That is correct, but there are then actually two different chains with the same number. One with the last number$2^9$ og one with the last number $2^8 \cdot 3$. – Nick Podowalski Dec 7 '14 at 13:25
• The biggest number is indeed $2^8*3$, you only have to replace yout $512$ by $768$ to get such a chain. – Peter Dec 7 '14 at 13:26
• In fact even more because the multiplication with $3$ can happen anywhere. The last number must be $768$. – Peter Dec 7 '14 at 13:30
• Aha. That is right! So we have 9 different ways to made the chain with $2^8 \cdot 3$ + 1 way with $2^9$, which gives us 10 different solution. – Nick Podowalski Dec 7 '14 at 13:32