0
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ How about find the number with the largest primefactor? $\endgroup$ – Nick Podowalski Dec 7 '14 at 13:06
  • 1
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer♦ Dec 7 '14 at 13:18
3
$\begingroup$

There is no longer chain because if the chain length is $11$ or more, the last number is at least $2^{10}=1024>1000$.

Improve this answer
$\endgroup$
  • $\begingroup$ I assumed that equal numbers are not allowed in the chain, otherwise the length could be arbitary large. $\endgroup$ – Peter Dec 7 '14 at 13:23
  • $\begingroup$ 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$. $\endgroup$ – Nick Podowalski Dec 7 '14 at 13:25
  • $\begingroup$ The biggest number is indeed $2^8*3$, you only have to replace yout $512$ by $768$ to get such a chain. $\endgroup$ – Peter Dec 7 '14 at 13:26
  • 2
    $\begingroup$ In fact even more because the multiplication with $3$ can happen anywhere. The last number must be $768$. $\endgroup$ – Peter Dec 7 '14 at 13:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Nick Podowalski Dec 7 '14 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.