S2T2

Jim Randell 11:29 am on 24 January 2023 Permalink Reply
Tags: by: Rex Gooch ( 3 )   

• 

  Jim Randell 11:30 am on 24 January 2023 Permalink | Reply

  Let N(k) be the number of digits used when expressing the numbers [0, …, (10^k) − 1] in decimal.

  We can start with:

  N(1) = len([0, …, 9]) = 10

  And if we think about moving from N(k) to N(k + 1) then we need to add in the (k + 1) digit numbers.

  These come in 9 groups, each consisting of 10^k numbers each with (k + 1) digits.

  N(1) = 10
  N(k + 1) = N(k) + 9(k + 1)10^k

  At each stage the number of digits required for the house numbers [1, …, 10^k] is:

  N'(k) = N(k) − 1 + k + 1
  N'(k) = N(k) + k

  Similarly we can calculate S(k), the sum of the digits in the numbers [0, …, 10^(k − 1)].

  We start with:

  S(1) = sum([0, …, 9]) = 45

  And if we think about moving from N(k) to N(k + 1), then we add in the (k + 1) digit numbers.

  There are 9 groups, each of which considers of 10^k numbers, that start with digits 1 .. 9, and the non-leading digits of each group sum to S(k)

  S(k + 1) = S(k) + 45.10^k + 9.S(k) = 10.S(k) + 45.10^k

  Hence:

  S(1) = 45
  S(k + 1) = 10.S(k) + 45.10^k

  And the required sum of the digits for the houses numbered [1, …, 10^k] is:

  S'(k) = S(k) + 1

  The following Python program calculates increasing (k, N(k), S(k)) values, until we find appropriate values to solve the puzzle.

  It runs in 50ms. (Internal runtime is 109µs).

  Run: [ @replit ]

  from enigma import (irange, cb, join, printf)
  
  # generate: (k, N(k), S(k)) values
  def generate():
    k = 1
    m = 10
    N = 10
    S = 45
    while k < 10:
      yield (k, N, S)
      N += 9 * (k + 1) * m
      S *= 10
      S += 45 * m
      k += 1
      m *= 10
  
  # suppose the child is aged between 3 and 16
  cubes = set(str(cb(x)) for x in irange(3, 16))
  
  # consider increasing values
  for (k, N, S) in generate():
    # adjust for numbers [1 ... 10^k]
    N += k
    S += 1
    # look for matching prefixes
    S = str(S)
    xs = list(x for x in cubes if S.startswith(x))
    if xs:
      printf("N(10^{k}) = {N}; S(10^{k}) = {S}; prefix = {xs}", xs=join(xs, sep=", "))
      break
  

  Solution: The number of digits required is: 5,888,896.

  The houses are numbered from 1 to 1,000,000.

  The sum of the digits required is: 27,000,001.

  Which has a prefix of 27, so the child is aged 3.

  LikeLike