New Scientist Enigma 511 – Double, Double
by Susan Denham
From Issue #1663, 6th May 1989
I wrote an odd number on the board and asked the class how many numbers (including the original number itself) could be made by writing exactly the same digits but in different orders. For example, if the number had been 5051, the answer would have been nine, namely 5051, 5015, 5105, 5150, 5501,5510, 1055, 505 and 1550). Clever Dick got the right answer immediately, so to keep him busy I told him to repeat the exercise with exactly double my original number.
“That just doubles the number of ways, Miss,” he reported. I told him to double again and repeat the exercise, and again he reported “that doubles the number of ways get again, Miss.”
So I told him to double the number yet again and to repeat the exercise with the four-figure answer. “It’s doubled the number of ways again, Miss,” he replied and, as always, he was quite right.
What number did l write on the board?
-
Brian Gladman permalink123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960from itertools import countdef unique_permutations(seq):"""generate unique permutations of sequence <s>using Knuth's 'Algorithm L'"""seq = sorted(seq)# precalculate the loop indices for speedi_indexes = range(len(seq) - 1, -1, -1)k_indexes = i_indexes[1:]while True:yield tuple(seq)# working backwards from the last-but-one index, to# find the index of the first decrease in valuefor k in k_indexes:if seq[k] < seq[k + 1]:breakelse:# the seq is weakly decreasing so we are donereturn# working backwards starting with the last item# find the first one greater than the one at kk_val = seq[k]for i in i_indexes:if k_val < seq[i]:break(seq[k], seq[i]) = (seq[i], seq[k])# reverse the part after but not including kseq[k + 1:] = seq[-1:k:-1]# the number on the boardfor nbr in count(1, 2):lp, lc, cnt, nv = 0, 0, 0, nbr# nv is the number as it is being repeatedly doubledwhile True:cnt += 1lp = lc# count all the different numbers obtained when the digits# in the current number are permutednd = [int(''.join(x)) for x in unique_permutations(str(nv))]lc = len(nd)# only continue for the first number or if the subsequent# numbers each double the number of 'permuted' numbersif cnt > 1 and lc != 2 * lp:break# if the number of numbers has doubled four timesif cnt == 4:# and the latest number has four digitsif 1000 <= nv < 10000:print(f"The number was {nbr}")exit()nv += nv