Sunday Times Teaser 2544 – Neighbourly Nonprimes

by Tom Wills-Sandford

Published: 26 June 2011 (link)

I live in a long road with houses numbered 1 to 150 on one side. My house is in a group of consecutively numbered houses where the numbers are all nonprime, but at each end of the group the next house number beyond is prime. There are a nonprime number of houses in this group. If I told you the lowest prime number which is a factor of at least one of my two next-door neighbours’ house numbers, then you should be able to work out my house number.

What is it?

2 Comments Leave one →

Brian Gladman permalink


from collections import defaultdict
from number_theory import is_prime, factors

# accumulate numbers in sequences of consecutive non-primes
# below 150 for sequences of non-prime length greater than 1
p0, hnbrs = 3, []
for p in range(5, 150):
  if is_prime(p):
    if p - p0 > 1 and not is_prime(p - p0):
      hnbrs.extend(range(p0, p))
    p0 = p + 1

# consider the possible house numbers
d = defaultdict(list)
for hn in hnbrs:
  # find the minimum prime that is a factor of at
  # least one of the adjacent houses to this one
  f = min(tuple(factors(hn - 1)) + tuple(factors(hn + 1)))
  # and keep a record of the house numbers associated
  # with this prime value
  d[f].append(hn)
  
# look for a prime value that is associated 
# with only one house number
for k, hn_list in d.items():
  if len(hn_list) == 1:
    print('The house number is {}.'.format(*hn_list))

from collections import defaultdict

from number_theory import is_prime, factors

# accumulate numbers in sequences of consecutive non-primes

# below 150 for sequences of non-prime length greater than 1

p0, hnbrs = 3, []

for p in range(5, 150):

if is_prime(p):

if p - p0 > 1 and not is_prime(p - p0):

hnbrs.extend(range(p0, p))

p0 = p + 1

# consider the possible house numbers

d = defaultdict(list)

for hn in hnbrs:

# find the minimum prime that is a factor of at

# least one of the adjacent houses to this one

f = min(tuple(factors(hn - 1)) + tuple(factors(hn + 1)))

# and keep a record of the house numbers associated

# with this prime value

d[f].append(hn)

# look for a prime value that is associated

# with only one house number

for k, hn_list in d.items():

if len(hn_list) == 1:

print('The house number is {}.'.format(*hn_list))

Frits permalink

@Brian,

Using your function partition_unique and first part of your code.


# Jim Randell found out that we can use a little shortcut to check if a 
# prime p divides one of the neighbours of n. If we consider the product of 
# the neighbours ((n - 1) and (n + 1)), then if the prime divides the product, 
# it must divide one of the neighbours. Now:
#
#    (n - 1)(n + 1) = n^2 - 1 
#
# So, if the residue of n^2 modulo p is 1, 
#     then p divides one of the neighbours of n.

from partition_unique import partition_unique

# set of prime numbers
P = {2, 3, 5, 7}
P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}
P |= {x for x in range(101, 151, 2) if all(x % p for p in P)}

# accumulate numbers in sequences of consecutive non-primes
# below 150 for sequences of non-prime length greater than 1
p0, hnbrs = 3, []
for p in range(5, 150):
  if p in P:
    if p - p0 > 1 and not (p - p0) in P:
      hnbrs.extend(range(p0, p))
    p0 = p + 1

# the lowest prime number that is a factor of at least one of my neighbours
# house numbers uniquely identifies my house number
f = lambda n: [p for p in P if (n * n) % p == 1][0]
hs = partition_unique(range(hnbrs[0], hnbrs[-1] + 1), f)[0]

# output solution
print(f"group = [{hnbrs[0]} .. {hnbrs[-1]}]; house = {hs}")

# Jim Randell found out that we can use a little shortcut to check if a

# prime p divides one of the neighbours of n. If we consider the product of

# the neighbours ((n - 1) and (n + 1)), then if the prime divides the product,

# it must divide one of the neighbours. Now:

# (n - 1)(n + 1) = n^2 - 1

# So, if the residue of n^2 modulo p is 1,

# then p divides one of the neighbours of n.

from partition_unique import partition_unique

# set of prime numbers

P = {2, 3, 5, 7}

P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}

P |= {x for x in range(101, 151, 2) if all(x % p for p in P)}

# accumulate numbers in sequences of consecutive non-primes

# below 150 for sequences of non-prime length greater than 1

p0, hnbrs = 3, []

for p in range(5, 150):

if p in P:

if p - p0 > 1 and not (p - p0) in P:

hnbrs.extend(range(p0, p))

p0 = p + 1

# the lowest prime number that is a factor of at least one of my neighbours

# house numbers uniquely identifies my house number

f = lambda n: [p for p in P if (n * n) % p == 1][0]

hs = partition_unique(range(hnbrs[0], hnbrs[-1] + 1), f)[0]

# output solution

print(f"group = [{hnbrs[0]} .. {hnbrs[-1]}]; house = {hs}")

Sunday Times Teaser 2544 – Neighbourly Nonprimes

by Tom Wills-Sandford

Published: 26 June 2011 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta