S2T2

Jim Randell 6:33 am on 22 June 2025 Permalink Reply
Tags: by: Colin Vout ( 37 )   

• 

  Jim Randell 6:39 am on 22 June 2025 Permalink | Reply

  The following Python program produces non-trivial (i.e. >1-digit) representations that are “anarithms”, in numerical order.

  It runs in 66ms. (Internal runtime is 494µs).

  from enigma import (irange, inf, nsplit, join, printf)
  
  # the two bases (A < B)
  (A, B) = (5, 8)
  
  # consider increasing numbers of digits
  for k in irange(2, inf):
    (x, y) = (B**(k - 1), (A**k) - 1)
    if x > y: break
    for n in irange(x, y):
      (a, b) = (nsplit(n, base=A), nsplit(n, base=B))
      if sorted(a) == sorted(b):
        # output solution
        printf("k={k}: {n} -> {a} [base {A}], {b} [base {B}]", a=join(a), b=join(b))
  

  Solution: The number is 540 (decimal).

  In base 5 it is represented: 4130.

  And in base 8 it is represented: 1034.

  LikeLike

  • 

    Jim Randell 2:56 pm on 22 June 2025 Permalink | Reply

    Or, as we want the largest possible number, we can consider the candidate values starting with the largest. Then we can stop after the first solution is found.

    This Python program has an internal runtime of 227µs.

    from enigma import (irange, inf, nsplit, rev, join, printf)
    
    # find largest number for bases A, B (where A < B)
    def solve(A, B):
      assert A < B
      # intervals to consider
      ivs = list()
      for k in irange(2, inf):
        (x, y) = (B**(k - 1), (A**k) - 1)
        if x > y: break
        ivs.append((x, y))
    
      # consider each interval from largest to smallest
      for (x, y) in rev(ivs):
        for n in irange(y, x, step=-1):
          (a, b) = (nsplit(n, base=A), nsplit(n, base=B))
          if sorted(a) == sorted(b):
            # output solution
            printf("{n} -> {a} [base {A}], {b} [base {B}]", a=join(a), b=join(b))
            return
    
    # solve for base 5 and base 8
    solve(5, 8)
    

    LikeLike

• 

  Frits 8:00 pm on 23 June 2025 Permalink | Reply

  Not my fastest version but still fast and relatively simple.

  # get digits of a number in base <b> (converted from <n> in base 10)
  def int2base(n, b):
    ds = []
    while n:
        ds.append(int(n % b))
        n //= b
    return ds
  
  b1, b2 = 5, 8
  rng, invalid = [], set(range(b1, 10))
  # get a list of valid ranges per number of digits
  for n, _ in enumerate(iter(bool, 1), 2): # infinite  loop
    mn, mx = b2**(n - 1), b1**n - 1
    if mx < mn: break
    rng.append((mn, mx))
  
  # for decreasing number of digits
  for mn, mx in reversed(rng):
    # check all numbers in the valid range
    for n in range(mx, mn - 1, -1):
      # check for invalid digits
      if not invalid.isdisjoint(n_b2 := int2base(n, b2) ): continue
  
      # base 8 and base 5 are anarithms of each other
      if sorted(int2base(n, b1)) == sorted(n_b2):
        print(f"answer: {n}")
        exit(0)
  

  LikeLike