Teaser 1850: Linear town
From The Sunday Times, 1st March 1998 [link]
The new transcontinental road across Eastern Europe into Asia was to outshine the Pan-American Highway, in that the old concept of a linear town had been revived. It was to have houses on each side of its entire length. Even the contract for the house numbers was huge. They started at 1 and ran to a neatly bureaucratic 1 followed by a number of noughts. One manufacturer’s representative delayed by her sick child, arrived just before the deadline to submit a bid to provide all the digits required. Unfortunately her computer had been programmed to calculate the sum of all the digits required, rather than the number of digits. This incorrect answer started with some digits that formed a number equal to the cube of her daughter’s age. Luckily, from this total she was able to work out the number of digits actually needed.
How many digits were needed?
[teaser1850]
Brian Gladman, 
SpanishJim, 
Jim Olson and 
Tony Smith are discussing. 
GeoffR, and 
Hugh Casement are discussing. 
Frits are discussing. 
John Crabtree, and 
Mark Valentine are discussing. 
S2T2 
Jim Randell 11:30 am on 24 January 2023 Permalink |
Let N(k) be the number of digits used when expressing the numbers [0, …, (10^k) − 1] in decimal.
We can start with:
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.
At each stage the number of digits required for the house numbers [1, …, 10^k] is:
Similarly we can calculate S(k), the sum of the digits in the numbers [0, …, 10^(k − 1)].
We start with:
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)
Hence:
And the required sum of the digits for the houses numbered [1, …, 10^k] is:
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=", ")) breakSolution: 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