Sunday Times Teaser 3060 – Even and Odd

by BRG on May 14, 2021

by Edmund Marshall

Published Sunday May 16 2021 (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?

From → Uncategorized

One Comment Leave one →

Brian Gladman permalink


# To reach 1 the previous value must be 2; to reach 2 the
# previous value must be 4; and so on..  Since 1 can only
# be reached from a power of 2, we need an integer n such 
# that 13.n + 1 == 2^e for integer e as small as possible
p, c = 1, 0
while True:
  p *= 2
  c += 1
  n, r = divmod(p - 1, 13)
  if not r:
    print(f"{n} in {c + 1} steps.")
    break

# To reach 1 the previous value must be 2; to reach 2 the

# previous value must be 4; and so on.. Since 1 can only

# be reached from a power of 2, we need an integer n such

# that 13.n + 1 == 2^e for integer e as small as possible

p, c = 1, 0

while True:

p *= 2

c += 1

n, r = divmod(p - 1, 13)

if not r:

print(f"{n} in {c + 1} steps.")

break

or we can start from 1 and run the process backwards


# run the process backwards from one
current, step = [1], 0
while True:
  previous, odd_cnt = [], 0
  # collect all previous values that could result in the
  # current list of values
  for n in current:
    # if we arrived here from an even number by halving
    previous.append(2 * n)
    # if we arrived here from an odd number by 
    # multiplying by thirteen and adding one
    p, r = divmod(n - 1, 13)
    if not r and p & 1:
      previous.append(p)
      odd_cnt += 1

  # prepare for next step back
  current = previous
  step += 1
  if odd_cnt:
    print(f"{step} steps -> {len(current):2} values", end='')  
    t = sorted(n for n in current if n & 1)
    print(f" (odd = {' / '.join(f'{x:,}' for x in t)})")
  if odd_cnt == 3:
    break

# run the process backwards from one

current, step = [1], 0

while True:

previous, odd_cnt = [], 0

# collect all previous values that could result in the

# current list of values

for n in current:

# if we arrived here from an even number by halving

previous.append(2 * n)

# if we arrived here from an odd number by

# multiplying by thirteen and adding one

p, r = divmod(n - 1, 13)

if not r and p & 1:

previous.append(p)

odd_cnt += 1

# prepare for next step back

current = previous

step += 1

if odd_cnt:

print(f"{step} steps -> {len(current):2} values", end='')

t = sorted(n for n in current if n & 1)

print(f" (odd = {' / '.join(f'{x:,}' for x in t)})")

if odd_cnt == 3:

break

Now modified to answer the extra puzzle posed by Jim Randell on his S2T2 site.

Sunday Times Teaser 3060 – Even and Odd

by Edmund Marshall

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta