S2T2

Jim Randell 2:35 pm on 5 August 2026 Permalink Reply
Tags: by: Nick MacKinnon ( 61 )   

• 

  Jim Randell 2:36 pm on 5 August 2026 Permalink | Reply

  We can attack the problem in a straightforward fashion, by just searching for a viable pair of consecutive numbers, but it is not very efficient.

  The following Python program runs in 1.47s (using PyPy).

  from enigma import (irange, tau, tuples, nsplit, printf)
  
  # generate (number, tau) pairs
  def generate(a, b):
    for n in irange(a, b):
      yield (n, tau(n))
  
  # check parity constraint for numbers <ns>
  def check(ns):
    for n in ns:
      # parity of n
      p = n % 2
      # count the number of digits in n, with parity p
      k = sum(1 for d in nsplit(n) if d % 2 == p)
      # the number of digits should have parity p
      if k % 2 != p: return
    # looks good
    return True
  
  # consider consecutive pairs of numbers
  for ((a, ta), (b, tb)) in tuples(generate(25, 999999), 2):
    # the sum of their numbers of factors is odd
    if not ((ta + tb) % 2 == 1): continue
    # the number of factors of their sum is odd
    if not (tau(a + b) % 2 == 1): continue
    # the odd number has an odd number of odd digits
    # the even number has an even number of even digits
    if not check((a, b)): continue
  
    # output solution
    printf("({a}, {b})")
  

  But with a bit of analysis we can do better:

  Divisors of a number come in pairs, so most numbers have an even number of divisors. The exception is when one of the divisor pairs is repeated, (i.e. (d, d)) and so the number itself is a perfect square (i.e. d²).

  The sum of the number of divisors of the numbers is odd, so one of the numbers (n or (n + 1)) must be a perfect square.

  So the numbers are either (x², x² + 1) or (x² − 1, x²).

  And the sum of the numbers must also have an odd number of divisors, so must be an odd perfect square.

  So we either have:

  (n, n + 1) = (x², x² + 1) and
  2x² + 1 = (2y + 1)²
  ⇒
  x² = 2y(y + 1)

  or:

  (n, n + 1) = (x² − 1, x²) and
  2x² − 1 = (2y + 1)²
  ⇒
  x² = 2y(y + 1) + 1

  The following Python program starts by considering increasing y values, and calculates corresponding x values.

  It has an internal runtime of just 548µs.

  from enigma import (irange, inf, isqrt, sq, nsplit, printf)
  
  # check parity constraint for numbers <ns>
  def check(ns):
    for n in ns:
      # parity of n
      p = n % 2
      # count number of digits in n with parity p
      k = sum(1 for d in nsplit(n) if d % 2 == p)
      # the number of digits should also have parity p
      if k % 2 != p: return False
    # looks good
    return True
  
  # consider increasing y values
  for y in irange(1, inf):
    Y = 2 * y * (y + 1)
    # calculate viable x^2 values
    x2 = sq(isqrt(Y + 1))
    if x2 > 999999: break
    # calculate the numbers we are interested in
    if x2 == Y + 1: ns = (x2 - 1, x2)
    elif x2 == Y: ns = (x2, x2 + 1)
    else: continue
    # check and output solution
    if check(ns):
      printf("{ns}")
  

  Solution: The odd number in the pair is 970225.

  The pair of numbers is: (970224, 970225) = (985² − 1, 985²).

  970224 (even) has 4 even digits, and 80 divisors.

  970225 (odd) has 3 odd digits, and 9 divisors.

  The sum of the numbers of divisors is 89 (odd)

  The sum of the numbers, 1940449, also has 9 divisors (odd).

  ---

  We can use even more analysis to find larger solutions with the required property efficiently:

  By writing X = 2x, Y = 2y + 1 we can rewrite the equations as:

  X² − 2Y² = ±2

  These are forms of Pell’s equation, that can be solved using the pells.py library [link].

  The following Python program can be used to find much larger solutions to the puzzle (default is the first 10).

  import pells
  from enigma import (sq, nsplit, merge, first, fail, arg, printf)
  
  # check parity constraint for numbers <ns>
  def check(ns):
    for n in ns:
      # parity of n
      p = n % 2
      # count number of digits in n with parity p
      k = sum(1 for d in nsplit(n) if d % 2 == p)
      # the number of digits should also have parity p
      if k % 2 != p: return False
    # looks good
    return True
  
  def solve():
    # consider solutions to the pells equation: X^2 - 2.Y^2 = [+2, -2]
    for (X, Y) in merge(pells.diop_quad(1, -2, k) for k in [+2, -2]):
      # recover the k value (+2 or -2)
      k = X*X - 2*Y*Y
      # calculate the numbers we are interested in
      x2 = sq(X//2)
      if k == -2: ns = (x2, x2 + 1)
      elif k == +2: ns = (x2 - 1, x2)
      else: fail()
      # check and return solution
      if check(ns): yield ns
  
  # find the smallest N solutions
  N = arg(10, 0, int)
  for ns in first(solve(), N):
    printf("{ns}")
  

  LikeLike

• 

  Ruud 8:01 am on 6 August 2026 Permalink | Reply

  from functools import cache
  
  
  @cache
  def number_of_digits_with_parity(n, parity):
      return sum(c in '13579' for c in str(n)) if parity else sum(c in '02468' for c in str(n))
  
  
  @cache
  def number_of_factors(n):
      return len(set(x for tup in ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0) for x in tup))
  
  
  for i1, i2 in zip(range(25, 1000000), range(26, 1000000)):
      if (
          (number_of_factors(i1) + number_of_factors(i2)) % 2 == 1
          and number_of_factors(i1 + i2) % 2 == 1
          and number_of_digits_with_parity(i1, 0) % 2 == 0
          and number_of_digits_with_parity(i2, 1) % 2 == 1
      ):
          print(i1, i2)
  
  
  

  LikeLike

  • 

    Jim Randell 10:13 am on 6 August 2026 Permalink | Reply

    @Ruud: How do you know the smaller number is the even one?

    Perhaps the tests should be:

    number_of_digits_with_parity(i1, i1 % 2) % 2 == i1 % 2 and
    number_of_digits_with_parity(i2, i2 % 2) % 2 == i2 % 2
    

    (In fact, from the recurrence relations for solutions to the corresponding Pell’s equations we can show that solution pairs are always (<even>, <odd>), so a brute force approach won’t miss solutions if it just consider these pairs).

    LikeLike

    • 

      ruudvanderham 10:15 am on 6 August 2026 Permalink | Reply

      Yes, you are right. I had the test originally, but removed it later by mistake.

      LikeLike