S2T2

Jim Randell 9:11 am on 5 June 2025 Permalink Reply
Tags: by: C Higgins ( 35 ), by: H Bradley ( 35 )   

• 

  Jim Randell 9:11 am on 5 June 2025 Permalink | Reply

  A simple search yields the largest possible number in a reasonable time.

  This Python program runs in 194ms. (Internal runtime is 122ms).

  from enigma import (irange, nrev, is_cube, printf)
  
  # consider 7-digit numbers
  for n in irange(9999999, 1000000, step=-1):
  
    # difference between n and its reverse is the cube of a divisor of n
    d = abs(n - nrev(n))
    if d == 0: continue
    x = is_cube(d)
    if x is None or n % x != 0: continue
  
    # output soultion
    printf("{n} [diff = {d} = {x}^3]")
    break  # we want the largest number
  

  Solution: Watson’s number is: 9841788.

  We have:

  abs(9841788 − 8871489) = 970299 = 99³
  9841788 = 99 × 99412

  ---

  Because the number is quite large the search doesn’t have to look too far, but we can speed it up.

  Writing the number as ABCDEFG then the difference between it and its reverse is a cube, so:

  abs(ABCDEFG − GFEDCBA) = x³
  where x divides ABCDEFG

  And we can rewrite the argument to abs() as:

  99 × (10101(A − G) + 1010(B − F) + 100(C − E))

  From which we see x must have factors of 3 and 11.

  And the original number is divisible by x, so it must be a multiple of 33, which means we can skip candidates that are not divisible by 33. And this gives us a nice compact program, with a much more acceptable runtime.

  The following Python program runs in 76ms. (Internal runtime is 12.4ms).

  from enigma import (irange, nrev, is_cube, printf)
  
  # consider 7-digit numbers
  for n in irange.round(9999999, 1000000, step=-33, rnd='I'):
  
    # difference between n and its reverse is a cube of a divisor of n
    d = abs(n - nrev(n))
    if d == 0: continue
    x = is_cube(d)
    if x is None or n % x != 0: continue
  
    # output solution
    printf("{n} [diff = {d} = {x}^3]")
    break  # we want the largest number
  

  There are 198 such 7-digit numbers, of which the largest is the required answer. The rest can be seen by removing the final [[ break ]] from the program.

  The smallest number with this property is 10164:

  abs(10164 − 46101) = 35937 = 33³
  10164 = 33 × 308

  LikeLike

• 

  Frits 1:19 pm on 5 June 2025 Permalink | Reply

  I have been discussing this Teaser with Brian Gladman for the last couple of days.
  This program has an interal runtime of 12 resp 135 microseconds (Py/PyCPython).

  from functools import reduce
  
  d2n = lambda *s: reduce(lambda x,  y: 10 * x + y, s)
  
  # the number's digits: abcdefg
  #
  # dif =   99^3.(a - g)                   (credit: Brian Gladman)
  #       + 99^2.{3.(a - g) + 10.(b - f) + (c - e)}
  #       + 99^1.(3.(a - g) + 20.(b - f) + (c - e)}
  #
  # dif must be a multiple of 99. If abs(dif) also must be a cube then
  # dif must be at least a multiple of 33^3.
  mx = int((10**7)**(1/3))
  
  # 4th digit from the end of the difference must be 0 or 9
  cbs = [i**3 for i in range(33, mx + 1, 33) if (cb := i**3) % 99 == 0 and 
                                                 str(cb)[-4] in "09"]
  
  # formula (10^6 - 1).(a - g) + 10.(10^4 - 1).(b - f) + 100.(10^2 - 1).(c - e)
  # equals <cb> if abcdefg > gfedcba otherwise it equals -<cb>
  mx = 0
  # process all possible differences (cubes)
  for cb in cbs:
    cr = round(cb ** (1/ 3))
    # if n % cr = 0 then abc9efg % cr must be one of 10 values 
    # (we can know them in advance)
    d9mods = [(i * (1000 % cr)) % cr for i in range(10)]
    s_d9mods = set(d9mods)
    for a in range(9, 0, -1):
      if mx and a < int(str(mx)[0]): break
      for b in range(9, -1, -1):
        if mx and b < int(str(mx)[1]): break
        for g in range(9, -1, -1):
          # a != g otherwise difference = ...0 and a cube root = ...0 
          #        which is impossible as a != 0 (and thus g != 0)
          if g == a: continue
          p1 = 999999 * (a - g)
          for f in range(9, -1, -1):
            p1p2 = p1 + 99990 * (b - f)
            # 99.(c - e) = (+/-)cb - p1p2  
            c_min_e, r = divmod((cb if a > g else -cb) - p1p2 , 9900)
            if not r and -10 < c_min_e < 10:
              # list of possible c's
              cs = (range(c_min_e, 10) if c_min_e > 0 else range(10 + c_min_e))
              for c in reversed(cs):
                e = c - c_min_e
                r = (n9 := d2n(a, b, c, 9, e, f, g)) % cr
                if r in s_d9mods:
                  d = 9 - d9mods.index(r)
                  n = n9 + 1000 * (d - 9)
                  if n > mx:
                    mx = n
                  break # propagate this break till we have a new <cb>
              else: continue
              break  
          else: continue
          break  
        else: continue
        break  
      else: continue
      break  
  
  print(f"answer: {mx}")    
  

  LikeLike

  • 

    Frits 4:03 pm on 5 June 2025 Permalink | Reply

    Instead of using d9mods to determine “d” we can also use:

    d = ((a + c + e + g) - (b + f)) % 11
    

    LikeLike

• 

  Frits 1:49 pm on 5 June 2025 Permalink | Reply

  Less efficient.

  This program has an interal runtime of 1.1 resp 3.2 ms (PyPy/CPython).

  from collections import defaultdict
  
  # difference must be a multiple of 99. If difference also is a cube then
  # the difference must be at least a multiple of 33^3.
  mx = int((10**7)**(1/3))
  
  # 4th digit from the end of the difference must be 0 or 9
  cbs = {i**3 for i in range(33, mx + 1, 33) if (cb := i**3) % 99 == 0 and 
                                                str(cb)[-4] in "09"}
  # 7-digit number = abcdefg
  # make a dictionary of possible <fg>'s per <ab> 
  d = defaultdict(set)
  for cube in cbs:
    last2 = (cube % 100)
    for ab in range(10, 100):
      ba = int(str(ab)[::-1])
      # 2 situations: fg < ba or fg > ba
      for i, fg in enumerate([(100 + ba - last2) % 100, (ba + last2) % 100]):
        gf = int(str(fg).zfill(2)[::-1]) 
        if i: 
          if ab > gf: 
            d[ab] |= {fg}
        else: 
          if ab < gf: 
            d[ab] |= {fg}   
        # ab = gf implies dif = ...00 which can't be a multiple of 33^3  
  
  for ab in reversed(range(10, 100)):
    ab_ = 100000 * ab 
    for cde in reversed(range(1000)):
      abcde = ab_ + 100 * cde
      # check all possible fg's
      for fg in sorted(d[ab], reverse=True):
        n = abcde + fg
        r = int(str(n)[::-1])
        # find whether the cube root of the difference
        # is an integer that is a divisor of the number
        if abs(n - r) in cbs:
          # calculate cube root of the difference
          cr = round(abs(n - r) ** (1/3))
          if n % cr == 0: 
            print("answer:", n)
            exit(0)
  

  LikeLike

• 

  Jim Randell 3:01 pm on 6 June 2025 Permalink | Reply

  I’ve obviously not spent as much time analysing this as Frits. But here is an alternative approach that uses the [[ express() ]] function from the enigma.py library to express the difference between the original number and its reverse in terms of the differences between digits of the number (using the expression given in my original comment).

  It then generates all 198 possible 7-digit numbers with the property, and selects the largest of them.

  It has an internal runtime of 2.3ms.

  from enigma import (Accumulator, irange, inf, cb, express, cproduct, nconcat, group, subsets, unpack, printf)
  
  # collect pairs of digits by their difference
  diff = group(subsets(irange(0, 9), size=2, select='M'), by=unpack(lambda x, y: x - y))
  
  # find n for difference d, must be divisible by x (a multiple of 11)
  def solve(d, x):
    # find d1 = (A - G), d2 = (B - F), d3 = (C - E) values
    ms = [100, 1010, 10101]  # multiples of (C - E), (B - F), (A - G)
    # solve for quantities -9 ... +9
    for (q1, q2, q3) in express(d // 99, ms, min_q=-9, max_q=9):
      # consider +d and -d
      for (d3, d2, d1) in [(q1, q2, q3), (-q1, -q2, -q3)]:
        # find possible digit values
        for (A, G) in diff[d1]:
          if A == 0: continue
          for ((B, F), (C, E)) in cproduct([diff[d2], diff[d3]]):
            # x is a multiple of 11, so there is only one possible value for D
            D = (A - B + C + E - F + G) % 11
            if D > 9: continue
            n = nconcat(A, B, C, D, E, F, G)
            if n % x == 0:
              yield n
  
  # find the largest value
  r = Accumulator(fn=max)
  
  # consider possible differences
  for x in irange(33, inf, step=33):
    d = cb(x)
    if d > 9999999: break
    # find possible n values
    for n in solve(d, x):
      r.accumulate_data(n, (d, x))
  
  # output solution
  (n, (d, x), t) = (r.value, r.data, r.count)
  printf("max(n) = {n} [diff = {d} = {x}^3] [from {t} values]")
  

  LikeLike

  • 

    Frits 12:15 pm on 7 June 2025 Permalink | Reply

    @Jim,

    An interesting idea to use “express”.

    It looks like “n” is ordered within the (A, G) loop.

    If you use “irange(9, 0, -1)” in the diff formula you can break after the yield and propagate the break until you are out of the (A, G) loop.

    LikeLike

• 

  ruudvanderham 1:24 pm on 7 June 2025 Permalink | Reply

  import peek
  
  for i in range(9999999, 1000000 - 1, -1):
      if (diff := i - int("".join(*[reversed(str(i))]))) > 0:
          if (c := round(diff ** (1 / 3))) ** 3 == diff:
              if i % c == 0:
                  peek(i, diff, c)
                  break

  LikeLike