Skip to content

Sunday Times Teaser 3038 – Progressive Raffle

by BRG on December 11, 2020

by Danny Roth

Published Sunday December 13 2020 (link)

George and Martha were participating in the local village raffle. 1000 tickets were sold, numbered normally from 1 to 1000, and they bought five each. George noticed that the lowest-numbered of his tickets was a single digit, then each subsequent number was the same multiple of the previous number, eg, 7 21 63 189 567. Martha’s lowest number was also a single digit, but her numbers proceeded with a constant difference, eg, 6 23 40 57 74. Each added together all their numbers and found the same sum. Furthermore, the total of all the digits in their ten numbers was a perfect square.

What was the highest numbered of the ten tickets?

From → Uncategorized

8 Comments Leave one →
  1. Brian Gladman permalink

  2. John Z permalink

  3. John Z permalink

    I’ve noticed a mild bug in my code: if a ticket number is 1000 then the ‘digits’ function, which is designed for numbers of 3 digits or less, gives an incorrect result. This happens when Martha’s initial ticket is 4 with a constant difference of 249, or 8 with a constant difference of 248. It doesn’t prevent the code from finding the correct solution. The correction is simple enough but I will leave my above post as is.

  4. Brian Gladman permalink

    HI John,

    I am not convinced that it is desirable to write such functions for only a limited number of digits when it is so easy and just as fast to write them in a way that handles any number of digits:

    Can I hence suggest I update it using this so it is correct?

  5. John Z permalink

    Yes, thanks. I had initially written ‘digits’ for a situation where the input parameter was to be exactly 3 digits. I was trying to avoid using string operations and also to minimise the number of divisions, assuming divmod() only makes one division.

    This function based on your recursive version uses divmod() and combines the spirit of both:

    But it’s only worth it if divmod() really does carry out only one division.

    I am not altogether happy with my use of floating point operations (i.e. ** 0.25 and ** 0.5) in what is an otherwise totally integer problem. Your thoughts?

  6. Brian Gladman permalink

    @John, Your variation is significantly slower because the extra cost of doing both a divide and and a mod operation is far smaller than the cost of the variable assignment and multiple indexing going on in your version. I also think it is harder to see clearly what the function is doing. In arriving at the version I suggested I did test a lot of variations and it came out fastest.

    You are right to be suspicious of roots when dealing with integers as the results will introduce errors when the numbers involved are large (there is no problem above as the numbers are small). There is often a good reason to use round() rather than int() when converting to an integer because int() truncates the fractional part, which means that it a value is microscopically less than an integer, the result will be the next lower integer and this is often not the result needed. In contrast round() gives the nearest integer value so tests such as “round(s ** 0.5) ** 2 == s” for a perfect square are much safer with round() instead of int().

  7. John Z permalink

    Brian: if you remove the two pairs of square brackets from your digits lambda function it will return the sum of the individual digits rather than the list of digits in a number, removing an intermediate step in determining the sum of the digits of the 5 tickets.

  8. Brian Gladman permalink

    Thanks John, an interesting observation. I tested this out but it didn’t make a difference to the speed so I will leave it alone for the moment. But it is certainly worth remembering for the future.

Leave a comment to John Z Cancel reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS