Brainteaser 1040: An uncommon number
From The Sunday Times, 4th July 1982 [link]
Your problem this week is to find an unusual nine-digit number. It comprises the digits from 1 to 9, in some order, each used once and only once.
The number formed by the first digit (reading from the left) is exactly divisible by 1 (which doesn’t tell you a lot!), the number formed by the first two digits is exactly divisible by 2, that formed by the first three digits is exactly divisible by 3, and so on, which the number formed by the first eight digits being divisible by 8, and with the complete number of nine digits being divisible by 9.
It is perhaps surprising that such a number exists, and even more surprising that is should be unique.
What is the number?
This puzzle is included in the books Microteasers (1986) and The Sunday Times Book of Brainteasers (1994).
[teaser1040]
John Crabtree and 
Dirk, 
GeoffR, 
Hugh Casement, and 3 others are discussing. 
Frits and 
Tony Brooke-Taylor, 
Brian Gladman, 
S2T2 
Jim Randell 9:06 am on 29 March 2021 Permalink |
This puzzle has also appeared recently as Puzzle #102, Teaser 3053.
See my comment on Enigmatic Code for the solution.
Here are the results for an n-digit (decimal) number, consisting of some arrangement of the digits 1..n, such that the leftmost k digits are divisible by k, for k = 1..n:
And taking the final entry, a 10-digit number in base 10, using all 10 digits, such that the leftmost k digits are divisible by k, for k = 1..10; we can extend this to other bases:
(see: OEIS A11456 [ @oeis ]).
LikeLike
Jim Randell 6:01 pm on 29 March 2021 Permalink |
And if we drop the requirement that digits cannot be reused, we can see that any left prefix of a polydivisible number [ @wikipedia ] must also be polydivisible.
This program generates all possible polydivisible numbers in a given base (and with a given set of digits):
from enigma import (irange, int2base, args, printf) ds = args([10], 0, int) base = ds.pop(0) if not ds: ds = list(irange(base)) printf("[base = {base}; digits = {ds}]") (k, ns) = (1, list(ds)) while ns: (k_, ns_) = (k + 1, list()) for n in ns: # output current numbers printf("{k} -> {n}", n=int2base(n, base=base)) # can we extend this number? if n > 0: for d in ds: n_ = base * n + d if n_ % k_ == 0: ns_.append(n_) (k, ns) = (k_, ns_)And we find that the longest base 10 polydivisible number, using the digits 0-9 (although 1 and 9 do not appear), has 25 digits:
In base 16 there are 3 maximal length (39-digit) polydivisible numbers:
LikeLike