Sunday Times Teaser 2827 – Password

by Graham Smithers

Published: 27 November 2016 (link)

My computer password consists of different digits written in decreasing order.

I can rearrange the digits to form a perfect cube. A further rearrangement gives a perfect square. Another rearrangement gives a prime number. A further rearrangement gives a number that is divisible by the number of digits in the password. Yet another rearrangement gives a number that is divisible by all but one of its digits.

What is my password?

5 Comments Leave one →

Brian Gladman permalink


from itertools import permutations
from functools import reduce
from number_theory import is_prime

# consider perfect cubes
for i in range(3, 2146):
  dgts = sorted((int(x) for x in str(i ** 3)), reverse=True)
  
  # it cannot contain duplicated digits
  if len(set(dgts)) != len(dgts):
    continue

  # since a rearrangement of its digits is a prime, the sum
  # of its digits cannot be divisible by 3 (or 6 or 9)
  if sum(dgts) % 3 == 0:
    continue
  
  # the password cannot contain more than one of (0, 3, 6, 9)
  # since it is divisible by all but one of its digits
  if len([x for x in dgts if x in (0, 3, 6, 9)]) > 1:
    continue
  
  # consider the properties of numbers formed by rearranging
  # its digits
  has_sq = has_pr = has_dl = has_dd = 0
  
  for p in permutations(dgts):
    nbr = reduce(lambda x, y: 10 * x + y, p)
    
    # is this number a perfect square?
    has_sq |= (int(nbr ** (1/2) + 0.5) ** 2 == nbr)
    
    # is it a prime?      
    has_pr |= is_prime(nbr)
    
    # is it divisible by the length of the password?
    has_dl |= (nbr % len(dgts) == 0)
    
    # is it divisible by all but one of its digits?
    has_dd |= sum(1 for x in dgts if x and not nbr % x) + 1 == len(dgts)
    
  # the password has all properties in rearrangements of its digits 
  if has_sq and has_pr and has_dl and has_dd:
    print('The password is {}.'.format(''.join(str(x) for x in dgts)))

from itertools import permutations

from functools import reduce

from number_theory import is_prime

# consider perfect cubes

for i in range(3, 2146):

dgts = sorted((int(x) for x in str(i ** 3)), reverse=True)

# it cannot contain duplicated digits

if len(set(dgts)) != len(dgts):

continue

# since a rearrangement of its digits is a prime, the sum

# of its digits cannot be divisible by 3 (or 6 or 9)

if sum(dgts) % 3 == 0:

continue

# the password cannot contain more than one of (0, 3, 6, 9)

# since it is divisible by all but one of its digits

if len([x for x in dgts if x in (0, 3, 6, 9)]) > 1:

continue

# consider the properties of numbers formed by rearranging

# its digits

has_sq = has_pr = has_dl = has_dd = 0

for p in permutations(dgts):

nbr = reduce(lambda x, y: 10 * x + y, p)

# is this number a perfect square?

has_sq |= (int(nbr ** (1/2) + 0.5) ** 2 == nbr)

# is it a prime?

has_pr |= is_prime(nbr)

# is it divisible by the length of the password?

has_dl |= (nbr % len(dgts) == 0)

# is it divisible by all but one of its digits?

has_dd |= sum(1 for x in dgts if x and not nbr % x) + 1 == len(dgts)

# the password has all properties in rearrangements of its digits

if has_sq and has_pr and has_dl and has_dd:

print('The password is {}.'.format(''.join(str(x) for x in dgts)))

Jim Randell permalink

Here’s my solution.


# looking at digital roots:
#
# the digital root of a square is 1, 4, 7, 9
# the digital root of a cube is 1, 8, 9
# the digital root of prime (except 3) is 1, 2, 4, 5, 7, 8
#
# so we need a number with a digital root of 1

from collections import defaultdict
from itertools import count, permutations
from enigma import irange, is_duplicate, digrt, join, nconcat, is_prime, printf

# store numbers by digit content
def numbers(fn):
  d = defaultdict(list)
  for i in count(0):
    n = fn(i)
    if n > 9876543210: break
    # check digital root
    if digrt(n) != 1: continue
    s = str(n)
    # check digits are distinct
    if is_duplicate(s): continue

    d[join(sorted(s))].append(n)
  return d

cubes = numbers(lambda x: x ** 3)
squares = numbers(lambda x: x ** 2)

# count the number of ds that divide n
def divides(n, ds):
  return sum(1 for d in ds if d != 0 and n % d == 0)

# find keys that have both squares and cubes
for k in cubes.keys():
  if k not in squares: continue

  # find rearrangements...
  ds = list(int(x) for x in k)
  rs = list(nconcat(p) for p in permutations(ds))

  # ... divisible by the length of k
  n = len(k)
  r1 = list(x for x in rs if x % n == 0)
  if not r1: continue

  # ... divisible by all but one of the digits in k
  r2 = list(x for x in rs if divides(x, ds) == n - 1)
  if not r2: continue

  # ... primes
  r3 = list(x for x in rs if is_prime(x))
  if not r3: continue

  printf("password={k}, cube={c}, square={s}", k=k[::-1], c=cubes[k], s=squares[k])
  printf("divisible by {n} = {r1}")
  printf("divisible by all but one digits of {k} = {r2}")
  printf("primes = {r3}")
  printf()

# looking at digital roots:

# the digital root of a square is 1, 4, 7, 9

# the digital root of a cube is 1, 8, 9

# the digital root of prime (except 3) is 1, 2, 4, 5, 7, 8

# so we need a number with a digital root of 1

from collections import defaultdict

from itertools import count, permutations

from enigma import irange, is_duplicate, digrt, join, nconcat, is_prime, printf

# store numbers by digit content

def numbers(fn):

d = defaultdict(list)

for i in count(0):

n = fn(i)

if n > 9876543210: break

# check digital root

if digrt(n) != 1: continue

s = str(n)

# check digits are distinct

if is_duplicate(s): continue

d[join(sorted(s))].append(n)

return d

cubes = numbers(lambda x: x ** 3)

squares = numbers(lambda x: x ** 2)

# count the number of ds that divide n

def divides(n, ds):

return sum(1 for d in ds if d != 0 and n % d == 0)

# find keys that have both squares and cubes

for k in cubes.keys():

if k not in squares: continue

# find rearrangements...

ds = list(int(x) for x in k)

rs = list(nconcat(p) for p in permutations(ds))

# ... divisible by the length of k

n = len(k)

r1 = list(x for x in rs if x % n == 0)

if not r1: continue

# ... divisible by all but one of the digits in k

r2 = list(x for x in rs if divides(x, ds) == n - 1)

if not r2: continue

# ... primes

r3 = list(x for x in rs if is_prime(x))

if not r3: continue

printf("password={k}, cube={c}, square={s}", k=k[::-1], c=cubes[k], s=squares[k])

printf("divisible by {n} = {r1}")

printf("divisible by all but one digits of {k} = {r2}")

printf("primes = {r3}")

printf()

I’ve used some useful routines from the enigma.py library [ https://www.magwag.plus.com/jim/enigma.html ].

Jim Randell permalink

I should say that I didn’t write code to ensure that all the 6 mentioned arrangements of digits were different (which I think is implied by the puzzle text), as there was only one possible solution anyway, and looking at the arrangements found by the program it is certainly possible to find 6 different arrangements satisfying the conditions of the problem.

Reply

Tony Smith permalink

Hi Brian
(1) I think your program would work without the tests for divisibility by 3 and restriction to at most one of 0,3,6,9. If I am right, how would this affect running time?
(2) Part of the analysis by John Crabtree on your other website shows quickly that the password can only have 4 or 5 digits (he seems to have tested 7 digits despite showing that this would give divisibility by 3).
Knowing this, your range of cube roots would be much smaller. How would this affect running time?
(3) Using a bit more of John’s analysis shows that only 13 cube roots need to be tested. Would you be able to write a simpler/quicker program to do this?

Best wishes
Tony (non-programming reader and occasional correspondent)

Reply
- Brian Gladman permalink
  
  Hi Tony,
  
  (1) As it is now the program completes in 40 milliseconds on my system. If I leave out the two tests you mention, it remains correct (as you say) but it takes over 11 seconds to complete. The answer is still found quickly but the program spends a lot of time considering the larger cubes.
  
  (2) If I limit the program (as it is now) to five digit cubes, it completes in 20 milliseconds. If I leave out the two tests you mention, this time increases to 35 milliseconds.
  
  (3) Some of the conditions set in the teaser might not be necessary if only 13 cubes need to be tested so it is possible that the program could be simpler (not as long). But I haven’t looked at what is possible here.
  
  I didn’t limit the cubes because I only incorporated the logic steps that occurred to me during the initial coding and this wasn’t one of them. And after adding these steps it was fast enough so I didn’t see the need to go any further.
  
  It is worth noting that the two logic steps I use (with the removal of cubes with duplicated digits) gets the number of cubes down to seven: 4^3, 5^3, 8^3, 13^3, 35^3, 38^3 and 88^3 leading to only six passwords that require further testing (5^3 and 8^3 share the same set of digits as do 35^3 and 38^3).
  
  Reply

Sunday Times Teaser 2827 – Password

by Graham Smithers

Published: 27 November 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta