Teaser 3060: Even or odd
From The Sunday Times, 16th May 2021 [link] [link]
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?
[teaser3060]
Brian Gladman, 
Tony Brooke-Taylor, 
Frits, and 1 other are discussing. 
S2T2 
Jim Randell 4:31 pm on 14 May 2021 Permalink |
Working backwards from 1 we can find numbers that require increasing numbers of steps to reach 1, and then look for the first odd number.
This Python program runs in 49ms.
Run: [ @replit ]
from enigma import (div, join, printf) # consider increasing numbers of steps k = 0 ns = [1] while True: # take 1 step back even = list() odd = list() for n in ns: even.append(2 * n) x = div(n - 1, 13) if x is not None and x > 1 and x % 2 == 1: odd.append(x) k += 1 ns = sorted(even + odd) printf("[{k} steps -> {ns}]") if odd: printf("solution = {odd} [in {k} steps]", odd=join(odd, sep=", ")) breakSolution: Her starting number was 315.
Which takes 13 steps to arrive at 1 (as 315×13 + 1 = 4096 = 2^12).
The first odd number can easily be found by looking for the smallest power of 2 that has a residue of 1 when divided by 13:
And you can find the answer with a calculator in a few seconds. Just repeatedly multiply 1/13 by 2 until you get an answer of the form x + 1/13, and the answer is x.
I feel the setter could have had more fun with this sequence. See: [ @wikipedia ]
As an extra puzzle, you might like to find the two different odd numbers, that would lead to a draw in the fewest number of steps.
The answer to my additional puzzle is: 977211 and 25407803.
These both reach 1 after 34 steps:
After the first 13 steps both sequences have reached 80640, which after another 8 steps reaches 315. And then 315 takes a further 13 steps to reach 1.
LikeLike
Frits 9:51 pm on 14 May 2021 Permalink |
In order to reach 1 you have to reach a power of 2 first.
from enigma import irange, inf for i in irange(2, inf): (d, r) = divmod(2 ** i - 1, 13) if r == 0: print("daughter's starting number", d) breakLikeLike
Tony Brooke-Taylor 8:55 am on 15 May 2021 Permalink |
My solution is similar to Frits’, and I have extended it to find the corresponding number of steps. I then put this in a loop to find a set of starting points that would give us a path through the solution. I failed to find a solution beyond the 18th in a reasonable time. I can’t decide whether this is because there is no further solution or my algorithm is too inefficient.
def solve(d): p=d*2 while (p-1)%13!=0: p*=2 return (p-1)//13, len(bin(p//d))-1 i=1 dest=1 while i<19: res=solve(dest) print(res) dest=res[0] i+=1Regarding Jim’s bonus question, my approach above provides one possible set of starting points, each of which passes through its successors. The total number of steps is then the sum of the steps from each to its immediate successor. An alternative path is to find the first solution, but continue multipying by 2 and recording each multiple that would also derive from an odd starting point. I found that these increased in units of 2**12. So one possible solution to Jim’s challenge is to find a starting point in the list my code generates, with a cumulative number of steps to our first solution which is a multiple of 12, n. A starting point that draws this number of steps is 2**n times the first solution.
LikeLike
Brian Gladman 11:14 pm on 15 May 2021 Permalink |
HI Tony,
You pose the question of whether your algorithm is too inefficient to find further solutions or whether there are none. But there is another possibility, namely that the algorithm you are using can only find a subset of the solutions. And this turns out to be true.
Your approach (which I also used) is fine for finding solutions that are reached in the minimum number of steps but it only finds solutions where the forward process lands on a power of two immediately after the initial ’13 step’ .
But there are solutions where this doesn’t happen. For example, the forward sequence for 6203 starts 6203, 80640, 40320, 20160, 10080, 5040, 2520, 1260, 630, 315, 4096, 2048, .. with a number after the initial forward step (80640) that is not a power of two.
This means that to answer Jim’s extra question, you have to use an algorithm such as the one Jim uses that finds all solutions for a given number of steps. This turns out to be very efficient because (somewhat to my surprise) the number of solutions only grows at a modest rate as the number of steps increase.
LikeLike
Brian Gladman 11:48 pm on 15 May 2021 Permalink |
PS. I have quoted a sequence that your approach does find – I should have quoted one it doesn’t find.
LikeLike
Tony Brooke-Taylor 12:33 pm on 17 May 2021 Permalink |
Thanks Brian. I get your point about the powers of two. I had been too interested in exploring larger numbers of steps when really we only need to look at a few handfuls – and in more detail. I believe my path routine hangs beyond the 18th step because by then I am at such high powers of 2 my machine is struggling to compute.
I have to conclude that Jim’s approach is much slicker than what I was trying to do. Nevertheless, out of pig-headedness I have extended my approach in an attempt to emulate the results from Jim’s algorithm. I still struggle to be certain of exhaustivity beyond a certain number of steps but my list is ALMOST the same as Jim’s: the first disagreement arises at 38 steps; where Jim produces a solution that I cannot replicate. To anyone who has not already moved on: I’d be grateful for any insight into what’s gone wrong.
import itertools from functools import reduce #Finds the first odd starting point that produces input number d #Also reports the number of steps def solve(d): rungs=[] step=1 p=d*2 # while (p-1)%13!=0 and step<=50: while step<=13: p*=2 step+=1 if (p-1)//13 == (p-1)/13: rungs+=((p-1)//13, len(bin(p//d))-2) return ((p-1)//13, len(bin(p//d))-2) # return rungs #Finds the ladder of starting points that produce the input number r #Each step in the ladder results in its predecessor in the list, with #the reported number of steps def ladder(r): i=1 dest=r points=[] while i<50: res=solve(dest) if res == None:break points.append(res) dest=res[0] i+=1 return points #Exploits Fermat's little theorem to generate a series of solutions from a single solution def project(rslt): rs = rslt[0]*13+1 RS = [((rs*(2**(12*n))-1)//13) for n in range(1,6)] LT = [rslt[1]+12*n for n in range(1,6)] return [(rl,st) for rl,st in zip(RS,LT)] #Runs the ladder algorithm for each solution in a list def ladder_vector(vec): lad_vec=[] for v in vec: X=[l[0] for l in ladder(v[0])] Y=[v[1]+sum([l[1] for l in ladder(v[0])[:j+1]]) for j in range(len(ladder(v[0])))] lad_vec+=[(x,y) for x,y in zip(X,Y)] return lad_vec #Runs the project algorithm for each solution in a list def project_vector(vec): prj_vec=[] for v in vec: prj_vec+=project(v) return prj_vec #Using Fermat's little theorem to guarantee a list of starting points #Length of this list is arbitrary but long enough to find the winning results baseline = [((2**(12*n)-1)//13,12*n+1) for n in range(1,6)] #Alternate between Fermat and ladder to add solutions into the main list results=[] results+=baseline results+=ladder_vector(baseline) results+=project_vector(baseline) results+=project_vector(ladder_vector(baseline)) results+=ladder_vector(project_vector(baseline)) #Eliminate duplicates, sort and cut off results beyond solution final = [f for f in list(set(results)) if f[1]<51] final.sort(key=lambda a: a[1]) print(*final, sep='\n')LikeLike
Tony Brooke-Taylor 5:52 pm on 17 May 2021 Permalink |
Now replicated Jim’s result: needed to be smarter about looping in the main program.
LikeLike
Brian Gladman 11:08 pm on 17 May 2021 Permalink |
Congratulations for sticking with it Tony!
LikeLike