Kindly provided by UKMT ## Peter wishes to write down a list of
different positive integers less than or equal to 10 in such a way that, for each pair of adjacent numbers, one of the numbers is divisible by the other.
11 Comments
phil
4/6/2014 04:00:49 pm
9:
Reply
Tom
4/6/2014 05:20:38 pm
Phil beat me to it. Same reasoning, to eliminate , but my easy sequence came out differently because I started by puting 10 between 2 and 5 and got 8,4,2,10,5,1,6,3,9.
Reply
My best score for integers 1-1000 is a length of 258. Is there a limit on the length based on the size of the list of integers?
Reply
Phil
8/6/2014 05:43:20 pm
The comments from Tom and gindc got me thinking about what happens for bigger N and how many solutions exist for any particular N. I tried writing a program to search exhaustively and rather optimistically set it looking for all solutions up to N=50. It found solutions for 1, 1-2, 1-3, ..., 1-20 almost immediately the over a few minutes it gradually got up to 1-33. I left it going a few hours before giving up so never made it to 1-34. I'm certainly never getting to 1000 this way! The solutions I managed to get are summarized at the end of this comment. The numbers on each line are N, max sequence length, number of maximal solutions and first solution found. There are 40 solutions for N=10 (or 20 if you count reversing a solution as the same answer).
Reply
Phil
8/6/2014 09:23:46 pm
N=10:
Reply
Phil
8/6/2014 09:31:46 pm
Well I've done all that now and got the following results:
Reply
Phil
8/6/2014 09:50:48 pm
With a slight tweak I got solutions with 27,980 numbers for 1-100,000 and 53,688 for 1-200,000. But that starts to take a minute or two and a LOT of memory!
Reply
Paul
8/6/2014 11:08:36 pm
Phil, I'm honoured to have you as a regular contributor on my puzzle page. Many Thanks
Reply
Phil
9/6/2014 12:26:24 am
Thanks Paul,
Reply
Paul
10/6/2014 11:51:44 pm
:) ## Leave a Reply. |
## Puzzle Ideas
If you have an idea for puzzle of the month, then please do let me know. ## Archives
March 2017
Don't forget to check out 'Teach Further Maths' - PowerPoints for Teachers and Students of A-Level Further Maths ...and the brilliant NEW educational card game 'Maths Trumps' |