by Edmund Marshall
Published Sunday May 16 2021
My daughter and I once played a game based on the number 13 and the following rule:
Think of a positive whole number greater than 1. If it is even, halve it. If it is odd multiply it by 13 and add 1. Either of these operations is to be regarded as one step. Apply another step to the outcome of the first step, and then further steps successively.
For our game, we chose different starting numbers that were odd, and the winner was the person who by the fewer number of steps reached the number 1. My daughter won because she started with the number that leads to 1 in the fewest number of steps.
What was my daughter’s starting number?
Sunday Times Teasers Discussion Group 
Bit of reverse engineering needed this week and awareness of difference of squares. About 6 lines needed but interesting teaser.
I’m sure I’ve seen this puzzle before. I certainly knew how to find the answer staight away.
I got to an answer very quickly but it took a little longer to convince myself that there was no more ingenious way to get there with fewer steps. But I eventually concluded that my answer was THE answer.
An interesting question, that I’m not sure if I have the ability or time to answer, is, are there any starting numbers that will never reach 1 at all?
Hi Nicky,
There is a problem, closely related to this one, for which the question you pose will make you famous if you are able to solve it!
Hi Brian,
I am almost sure that, starting with an odd number s, the base number b must be a prime to reach 1.
But I do not know how to prove it, even with the help of the simple expression of s in terms of b that follows from xgha’s ‘reverse engineering’.
PS: Brian, is my unproven claim what you had in mind as a problem?
HI Peter,
The closely related problem I was thinking of in my reply to Nicky was the Collatz Conjecture. Mathematicians have been trying without success for over 80 years to decide whether it always ends with a 1.
By the way, I don’t understand what you mean by the ‘base number’.
Thanks, Brian
I meant base number = 13 for the present Teaser which is ‘based on the number 13,.
Peter
The base number doesn’t have to be prime. Try setting it to 9. (The positive whole number only needs to be 7)
Thanks, Robert
The final number to be = 1 requires that one must get 2^n at some intermediate step, in your example at the first step:
b = 9 and s = 7 gives 9×7+1 = 2^6.
One needs to look for products giving 2^n – 1. Example b = 51 and s = 5 gives 5 x 51 = 2^8 -1.
That is very interesting! I suspected the question I posed would be beyond my ability but never guessed quite how far beyond! At least the teaser itself was simple.
I think the version I remembered was based on 11 instead of 13. It works for some other numbers (try 19 for example).
The last part of the route in this case is not random at all, as xgha’s hints to. But moving forwards from the odd number thought of, I got associations to the problem of ‘the drunken man’s random walk’. Seems like he sobered up when the target appeared in sight.
Just visited Brian’s link. Fascinating to stumble upon unsolved problems in mathematics like this!
This was meant to be reply to Peter’s post (May 15, 7:24) but there’s a limit on how many nested replies we can have!
You can easily solve the problem with a spreadsheet. 1st column = successive 2^n -1 values, next column divides that by 13. Successive columns for any odd base number that you fancy.
This doesn’t help with the Collatz conjecture though!
I’ve tried to submit this a few times…
Obviously the halvings start from a power of 2
(2^p)-1 = 0{mod13}
Smallest p = 0 (trivial) or 12
(2^12) – 1 = 4095 = 13 X 315
2^n = 1 mod 13. Fermat’s little theorem places an upper bound on n, almost makes this teaser a one-liner Then one has to check that no factors of n work. There are not many to check and it can be done in one’s head.
The Collatz conjecture is very interesting.
Defining S, M and (K+1) as starting number, multiplier and steps needed to reach 1, respectively, we need to find integer solutions satisfying SM = (2^K -1) . At once, we see that for S and M are ODD and interchangeable. As clear now, the lowest value of K yielding S or M to be 13 is K=12.
My original post about difference of squares was wrong as I assume K should be EVEN to allow factors [2^(K/2) + 1] and [2^(K/2) – 1]. This is not the case as K = 9, 11, 15 etc show.
For me, the most curious thing to arise from this teaser is that for any prime number P the expression [2^P – 2]/[2P] is always an integer (ODD and not always prime) – as far as my calculator can test! Maybe there is a rigorous proof for this observation?
As John Crabtree has commented, Fermat’s little theorem works here. It states that a^p == a (mod p) so (a^p – a) is divisible by p if p is prime. And if a = 2 it is also divisible by 2.
Hi Brian, Thanks for that. I just noticed the curious property and wondered if it could be proven to always be true – but now I see I was more than 300 years too late ☹️. I hadn’t followed up on John’s earlier comment but have now learned about Fermat’s Little Theorem on Wickipedia. The “rotating necklace” argument/proof is fairly straightforward to grasp. Thanks again 👍
Hi xgah
I found early on that s = (2^(b-1) – 1) / b is a whole number if b = p = prime, as far as my calculator permitted to evaluate. s is the start number, b corresponds to the number the teaser is “based on”.
This observation is the same to your “most curious thing”, somewhat differently written.
It led me initially to the belief that the “base b” must always be prime, until Robert pointed out my error.
if the base number is 11, the start number is 93.
Base number 17. start number 3855.
Base number 19, start number 13797
Base number 23, start number 182361.
Just showing off!
Based on an elementary result in number theory.
?????. For base number 17, the lowest start number is 15. Try it and see. And my post of May 16 warns of this issue.
Your other start numbers are correct.
For 23 the lowest number would be 89.
Assuming base number is back at 13, and Edmund chooses a number larger than his daughter’s, I wondered how small that could be. I found a 7 digit number that works, is this really the smallest possible?
The next smallest number of steps is given by a 4 digit odd number.
The next number that works is 6,203 in 22 steps.
Thanks guys, I see how that works. My larger number was suffering from the James Coombes effect!
i had a shrewd idea that my claims for
lowest start numbers may have been
too high.
I shall have to investigate what I have
overlooked. But the numbers do work.