Design a site like this with WordPress.com
Get started

Tagged: by: Bill Kinally Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:35 pm on 2 December 2022 Permalink | Reply
    Tags: by: Bill Kinally   

    Teaser 3141: Multiple extensions 

    From The Sunday Times, 4th December 2022 [link] [link]

    All the phone extensions at Mick’s work place are four-digit numbers with no zeros or twos, and no digit appears more than once in a number. He can enter all the extension numbers on the keypad by starting at key 2 (but not pressing it) then moving in any direction, including diagonally, to an adjacent key and pressing it; then similarly moving to and pressing adjacent keys until the number is entered. A couple of examples of his extension numbers are 3685 and 5148.

    He phoned two different extension numbers this morning and later realised that one was an exact multiple of the other.

    What was the larger extension number he dialled?

    [teaser3141]

     

    • Jim Randell 4:54 pm on 2 December 2022 Permalink | Reply

      The following Python program runs in 58ms. (Internal run time is 6.2ms).

      Run: [ @replit ]

      from enigma import (nconcat, div, ordered, printf)

# adjacency matrix
adj = {
  1: [2, 4, 5],
  2: [1, 3, 4, 5, 6],
  3: [2, 5, 6],
  4: [1, 2, 5, 7, 8],
  5: [1, 2, 3, 4, 6, 7, 8, 9],
  6: [2, 3, 5, 8, 9],
  7: [4, 5, 8],
  8: [4, 5, 6, 7, 9],
  9: [5, 6, 8],
}

# generate k-length numbers with no repeated digits
def solve(k, ds):
  if k == 0:
    yield ds
  else:
    for d in adj[ds[-1]]:
      if d not in ds:
        yield from solve(k - 1, ds + [d])

# start at 2, and dial 4 more digits
ns = list()
for ds in solve(4, [2]):
  n = nconcat(ds[1:])
  # look for previous numbers that pair with this one
  for m in ns:
    (x, y) = ordered(m, n)
    k = div(y, x)
    if k:
      printf("{y} = {k} * {x}")
  # add in the new number
  ns.append(n)

      (Or a more efficient (but longer) variation on this code [@replit]).

      Solution: The larger number was: 4758.

      And the smaller number was: 1586.

      4758 = 3 × 1586

      Like

  • Jim Randell 6:56 pm on 26 August 2022 Permalink | Reply
    Tags: by: Bill Kinally   

    Teaser 3127: Putting in a shift 

    From The Sunday Times, 28th August 2022 [link] [link]

    Next month’s four week rota for Monday to Friday dinner duties starting on Monday 1st is covered by five teachers each having the following duty allocations. Ann, Ben and Ed each have four, Celia six and Dave has two. Strangely, all the prime number dates (1 is not a prime) are covered by Ben, Celia and Dave, while the others are covered by Ann, Celia and Ed. After working a duty, nobody works on either of the following two shifts, so anyone working on a Friday will not work on the following Monday or Tuesday. Celia has no duties on Mondays while Ben and Ed have none on Wednesdays.

    In date order, who is on duty from Monday to Friday of the first week?

    [teaser3127]

     

    • Jim Randell 7:32 pm on 26 August 2022 Permalink | Reply

      This Python program runs in 56ms. (Internal run time is 2.8ms).

      Run: [ @replit ]

      from enigma import (enigma, irange, multiset, append, chunk, join, printf)

# dates to allocate (1 - 26 without Sat (6) or Sun (0))
dates = list(n for n in irange(1, 26) if n % 7 not in {0, 6})

# counts for each worker
count = dict(A=4, B=4, C=6, D=2, E=4)

# primes
primes = set(enigma.primes.between(1, 26))

# allocate candidates to a list of dates
def solve(ds, i=0, vs=()):
  if i == len(ds):
    # check prime numbers are covered by B, C, D
    if set(v for (d, v) in zip(ds, vs) if d in primes) != set('BCD'): return
    # and non-primes are covered by A, C, E
    if set(v for (d, v) in zip(ds, vs) if d not in primes) != set('ACE'): return
    # valid solution
    yield vs
  else:
    # consider the next date
    k = ds[i]
    # day of week (Mon = 1 ... Fri = 5)
    w = k % 7
    # consider candidates for next shift
    for v in ('BCD' if k in primes else 'ACE'):
      if w == 1:
        if v == 'C': continue
      elif w == 3:
        if v in 'BE': continue
      if v not in vs[-2:] and vs.count(v) < count[v]:
        # solve for the rest
        yield from solve(ds, i + 1, append(vs, v))

# format a week
fmt = lambda x: join(x, sep=" ", enc="()")

# find possible rotas and collect solutions (= rota for first week)
ss = multiset()
for vs in solve(dates):
  weeks = list(chunk(vs, 5))
  printf("[{weeks}]", weeks=join((fmt(x) for x in weeks), sep=" "))
  ss.add(weeks[0])

# output solutions
for (ks, n) in ss.most_common():
  printf("{ks} [{n} solutions]", ks=fmt(ks))

      Solution: The rota for the first week is (Mon – Fri): Ann, Ben, Dave, Celia, Ben.

      The complete rota is:

      Week 1: A B D C B
      Week 2: E C A B C
      Week 3: A E D C B; or: E A D C B
      Week 4: E C A E C

      The prime days (of which there are 7) are covered by B, C, D (which means all A and E’s days must be non-prime).

      Similarly the non-prime days are covered by A, C, E (which means all B and D’s days must be prime).

      So between them B (4 days) and D (2 days) must cover 6 of the 7 prime days, so C must have 1 prime (and 5 non-prime) days.

      We can use this analysis to simplify the program slightly, although the run time is already very quick.

      Like

    • Frits 9:50 pm on 26 August 2022 Permalink | Reply

      Faster when run with PyPy.

         
from enigma import SubstitutedExpression

# days  (1 - 5, 8 - 12, 15 - 19, 22, 26)
days = list(n for n in range(1, 27) if n % 7 not in {0, 6})

# prime days up to 26
P = {3, 5, 7}
P = {2, 3, 5} | {x for x in range(9, 26, 2) if x in days and all(x % p for p in P)}

# daynum: day --> day index
d_ind = {d: i for i, d in enumerate(days)}

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 27):
  vs = set()
  if d == 0 or d not in days:
    vs.update('ABCDEFGHIJKLMNOPQRST')
    
  if d in P: 
    vs.update('AFGHERST')  # Ann and Ed
  else:
    vs.update('BIJKDQ')    # Ben and Dave
  
  if d % 7 == 1: 
    vs.update('CLMNOP')    # Celia not on Monday  
  if d % 7 == 3:
    vs.update('BIJKERST')  # Ben and Ed not on Wednesday 
   
  d2i[d] = vs

# check gap of at least 2 work days
def check(seq):
  for i, s in enumerate(seq[1:], start=1):
    if d_ind[s] - d_ind[seq[i - 1]] < 3: return False
  return True  

# the alphametic puzzle
p = SubstitutedExpression(
  [
    "check([B, I, J, K])",
    "check([D, Q])",
    "check([C, L, M, N, O, P])",
    "check([A, F, G, H])",
    "check([E, R, S, T])",
  ],
  answer="(A, F, G, H, B, I, J, K, C, L, M, N, O, P, D, Q, E, R, S, T)",
  base=27,
  d2i=d2i,
  env=dict(check=check),
  reorder=0,
  denest=1,     # use denest=1 if not run with PyPy
  verbose=0,    # use 256 to see the generated code
)

order = "AAAABBBBCCCCCCDDEEEE"
# collect answers
sols = set()
for (_, ans) in p.solve():
  mix = sorted(zip(ans, order))
  #print(f"{', '.join(x[1] for x in mix)}")
  sols.add(', '.join(x[1] for i, x in enumerate(mix) if i < 5))

# print answers
for s in sols:  
  print(s)

      Like

    • Hugh+Casement 7:04 am on 27 August 2022 Permalink | Reply

      Next month’s rota?? It was the 1st of August that was a Monday this year.
      It seems the puzzles editor doesn’t read the puzzles.

      Like

    • Frits 1:06 pm on 27 August 2022 Permalink | Reply

      Similar to my previous version but faster.
      I experienced some order problems with a set for P so I decided to use a tuple.

         
from itertools import combinations

# select items from <a> that do not occur in <b>
diff = lambda a, b: tuple(x for x in a if x not in b)

# days  (1 - 5, 8 - 12, 15 - 19, 22, 26)
days = [n for n in range(1, 27) if n % 7 not in {0, 6}]

# don't use a set for P as a set is an unordered collection in CPython
# (results differ depending on the CPython release)

# primes work days up to 26
P = (3, 5)
P = (2, 3, 5) + tuple(x for x in range(7, 27, 2) 
                 if x in days and all(x % p for p in P))
                 
NP = diff(days, P)

# day --> day index
d_ind = {d: i for i, d in enumerate(days)}

# check for a gap between shifts of at least 2 work days
def check(seq):
  for i in range(len(seq) - 1):
    if d_ind[seq[i + 1]] - d_ind[seq[i]] < 3: return False
  return True  
  
sols = set()
for b4 in combinations(P, 4):
  if not check(b4): continue              # check gaps between shifts 
  # Ben not on Wednesday
  if any(x for x in b4 if x % 7 == 3): continue
  for d2 in combinations(diff(P, b4), 2):
    if not check(d2): continue            # check gaps between shifts 
    c1 = diff(P, b4 + d2)
    # Celia not on Monday
    if c1[0] % 7 == 1: continue

    for c5 in combinations(NP, 5):
      # Celia not on Monday
      if any(x for x in c5 if x % 7 == 1): continue
      c6 = tuple(sorted(c5 + c1))
      if not check(c6): continue        # check gaps between shifts 
        
      for e4 in combinations(diff(NP, c5), 4):
        if not check(e4): continue          # check gaps between shifts 
        # Ed not on Wednesday
        if any(x for x in e4 if x % 7 == 3): continue
        
        a4 = diff(NP, e4 + c5)
        if not check(a4): continue        # check gaps between shifts 
        
        mix = sorted(str(y).zfill(2) + "ABCDE"[i]
              for i, x in enumerate([a4, b4, c6, d2, e4]) for y in x)
        sols.add(tuple(x[2] for x in mix[:5]))    
     
# print answers
for s in sols:  
  print("answer: ", *s)

      Like

  • Jim Randell 4:42 pm on 4 September 2020 Permalink | Reply
    Tags: by: Bill Kinally   

    Teaser 3024: Triple jump 

    From The Sunday Times, 6th September 2020 [link]

    From a set of playing cards, Tessa took 24 cards consisting of three each of the aces, twos, threes, and so on up to the eights. She placed the cards face up in single row and decided to arrange them such that the three twos were each separated by two cards, the threes were separated by three cards and so forth up to and including the eights, duly separated by eight cards. The three aces were numbered with a one and were each separated by nine cards. Counting from the left, the seventh card in the row was a seven.

    In left to right order, what were the numbers on the first six cards?

    [teaser3024]

     

    • Jim Randell 5:03 pm on 4 September 2020 Permalink | Reply

      (See also: Enigma 369).

      I assume that for each set of three cards with value n (the aces have a value of 9): the leftmost one is separated from the middle one by n other cards, and the middle one is separated from the rightmost one by n other cards. (So the leftmost and rightmost instances are not separated by n cards).

      I treat the puzzle as if cards with values 2 to 9 were used (3 copies of each). Then when we have found a solution we can replace the value 9 cards with aces.

      This Python program runs in 50ms.

      Run: [ @repl.it ]

      from enigma import update, join, printf

# generate sequences in <s> where 3 occurrences of the numbers in <ns> are
# separated by <n> other slots
def generate(s, ns):
  if not ns:
    yield s
  else:
    n = ns[0]
    for (i, x) in enumerate(s):
      j = i + n + 1
      k = j + n + 1
      if not(k < len(s)): break
      if not(x is None and s[j] is None and s[k] is None): continue
      yield from generate(update(s, [i, j, k], [n, n, n]), ns[1:])

# start with 24 slots
s = [None] * 24
# we are told where the 7's are:
s[6] = s[14] = s[22] = 7
# place the remaining cards
for ss in generate(s, [9, 8, 6, 5, 4, 3, 2]):
  # output solution
  printf("{ss}", ss=join(("??23456781"[x] for x in ss), sep=" "))

      Solution: The first 6 cards are: 1, 2, 6, 8, 2, 5.

      Without pre-placing the 7’s there are four sequences that work (or two sequences, and their reverses):

      (1 2 6 8 2 5 7 2 4 6 1 5 8 4 7 3 6 5 4 3 1 8 7 3)
(3 1 7 5 3 8 6 4 3 5 7 1 4 6 8 5 2 4 7 2 6 1 2 8)
(8 2 1 6 2 7 4 2 5 8 6 4 1 7 5 3 4 6 8 3 5 7 1 3)
(3 7 8 1 3 4 5 6 3 7 4 8 5 1 6 4 2 7 5 2 8 6 2 1)

      The answer to the puzzle is the first of these sequences.

      Like

      • Jim Randell 11:15 am on 5 September 2020 Permalink | Reply

        Here is a MiniZinc model to solve the puzzle:

        %#! minizinc -a

include "globals.mzn";

% index of middle cards with values 2 to 9
var 11..14: i9;
var 10..15: i8;
var  9..16: i7;
var  8..17: i6;
var  7..18: i5;
var  6..19: i4;
var  5..20: i3;
var  4..21: i2;

% each card is in a different slot
constraint all_different([
  i9, i9 - 10, i9 + 10,
  i8, i8 - 9, i8 + 9,
  i7, i7 - 8, i7 + 8,
  i6, i6 - 7, i6 + 7,
  i5, i5 - 6, i5 + 6,
  i4, i4 - 5, i4 + 5,
  i3, i3 - 4, i3 + 4,
  i2, i2 - 3, i2 + 3,
]);

% there is a 7 in slot 7
constraint i7 - 8 = 7;

solve satisfy;

        Like

        • Jim Randell 4:32 pm on 5 September 2020 Permalink | Reply

          And here’s an alternative implementation in Python that collects the indices of the central cards of each value, rather than filling out the slots:

          from enigma import irange, update, join, printf

# generate indices for the central number in <ns> where the 3
# occurrences are separated by <n> other slots
def solve(ns, m=dict(), used=set()):
  if not ns:
    yield m
  else:
    n = ns[0]
    # consider possible indices for the middle card with value n
    d = n + 1
    for i in irange(d, 23 - d):
      (j, k) = (i - d, i + d)
      if not used.intersection((i, j, k)):
        yield from solve(ns[1:], update(m, [(n, i)]), used.union((i, j, k)))

# place 7 (at 6, 14, 22), and solve for the remaining cards
for m in solve([9, 8, 6, 5, 4, 3, 2], { 7: 14 }, set([6, 14, 22])):
  # construct the solution sequence
  s = [0] * 24
  for (n, i) in m.items():
    d = n + 1
    s[i] = s[i - d] = s[i + d] = (1 if n == 9 else n)
  # output solution
  printf("{s}", s=join(s, sep=" "))

          Like

    • Frits 8:57 pm on 5 September 2020 Permalink | Reply

      Based on Jim’s MiniZinc model.

      Only the last”v” call is necessary, the rest is added for performance., it’s a bit messy.

       
from enigma import SubstitutedExpression, irange, seq_all_different

p = SubstitutedExpression([
    "K < 3",
    "M < 3",
    "O < 3",
    "O > 0",
    "A < 3 and AB > 3 and AB < 22",       # i2
    "C < 3 and CD > 4 and CD < 21",       # i3
    "E < 3 and EF > 5 and EF < 20",       # i4
    "G < 3 and GH > 6 and GH < 19",       # i5
    "IJ > 7 and IJ < 18",                 # i6
    "KL = 15",                            # i7
    "MN > 9 and MN < 16",                 # i8
    "OP > 10 and OP < 15",                # i9
    "v([KL, KL - 8, KL + 8, \
        MN, MN - 9, MN + 9])",
    "v([KL, KL - 8, KL + 8, \
        MN, MN - 9, MN + 9, \
        OP, OP - 10, OP + 10])",
    "v([AB, AB - 3, AB + 3, \
        KL, KL - 8, KL + 8, \
        MN, MN - 9, MN + 9, \
        OP, OP - 10, OP + 10])",
    "v([AB, AB - 3, AB + 3, \
        CD, CD - 4, CD + 4, \
        KL, KL - 8, KL + 8, \
        MN, MN - 9, MN + 9, \
        OP, OP - 10, OP + 10])",
    "v([AB, AB - 3, AB + 3, \
        CD, CD - 4, CD + 4, \
        EF, EF - 5, EF + 5, \
        KL, KL - 8, KL + 8, \
        MN, MN - 9, MN + 9, \
        OP, OP - 10, OP + 10])",
    "v([AB, AB - 3, AB + 3, \
        CD, CD - 4, CD + 4, \
        EF, EF - 5, EF + 5, \
        GH, GH - 6, GH + 6, \
        IJ, IJ - 7, IJ + 7, \
        KL, KL - 8, KL + 8, \
        MN, MN - 9, MN + 9, \
        OP, OP - 10, OP + 10])",
   ],
    verbose=0,
    d2i="",          # allow leading zeroes
    code="v = lambda x: seq_all_different(x)",
    answer="(AB, CD, EF, GH, IJ, KL, MN, OP)",
    distinct="",
)

out = [2, 3, 4, 5, 6, 7, 8, 1]

# Print answers
for (_, ans) in p.solve(verbose=0):
  print("Numbers on first 6 cards: ", end="")
  for k in range(1,7):
    for i in range(8):
      if ans[i] == k: print(f"{out[i]} ", end="")
      if ans[i] - i - 3 == k: print(f"{out[i]} ", end="")
  print()

      Like

  • Jim Randell 5:22 pm on 7 February 2020 Permalink | Reply
    Tags: by: Bill Kinally   

    Teaser 2994: Consecutive sums 

    From The Sunday Times, 9th February 2020 [link]

    Amelia noticed that 15 is equal to 1+2+3+4+5 or 4+5+6 or 7+8, so there are three possible ways that it can be expressed as the sum of consecutive whole numbers. She then told Ben that she had found a three-digit number which can be expressed as the sum of consecutive whole numbers in just two different ways. “That’s interesting”, said Ben. “I’ve done the same, but my number is one more than yours”.

    What is Ben’s number?

    [teaser2994]

     

    • Jim Randell 5:36 pm on 7 February 2020 Permalink | Reply

      The following Python program runs in 221ms.

      Run: [ @repl.it ]

      from collections import defaultdict
from enigma import (subsets, irange, T, printf)

# collect consecutive sums for 3-digit numbers
d = defaultdict(list)
for (i, j) in subsets(irange(1, 500), size=2):
  n = T(j) - T(i - 1)
  if 99 < n < 1000:
    d[n].append((i, j))

# find consecutive numbers expressible in 2 different ways
for (n, vs) in d.items():
  if len(vs) == 2:
    vs1 = d.get(n + 1, None)
    if vs1 and len(vs1) == 2:
      printf("{n} -> {vs}; {n1} -> {vs1}", n1=n + 1)

      Solution: Ben’s number is 289.

      289 can be expressed as:

      289 = 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25
      289 = 144 + 145

      Amelia’s number is 288, which can be expressed as:

      288 = 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36
      288 = 95 + 96 + 97

      Like

      • Jim Randell 6:36 pm on 7 February 2020 Permalink | Reply

        Here is a neater program that uses the technique described in the comments of Enigma 1. It runs in 83ms.

        Run: [ @repl.it ]

        from enigma import (divisors, irange, cached, printf)

S = cached(lambda n: sum(d % 2 for d in divisors(n)))

# find 2 consecutive 3-digit numbers with S(n) == 3
for a in irange(100, 998):
  b = a + 1
  if S(a) == S(b) == 3:
    printf("{a}, {b}")

        Analytically:

        In order for the numbers to have exactly 3 odd divisors they must be of the form:

        n = (2^k)(p^2)

        where p is an odd prime.

        And we are looking for two consecutive numbers, so one will be even and one will be odd (k = 0).

        We can look for 3-digit numbers manually, or programatically:

        from enigma import (primes, tuples, printf)

# collect 3-digit numbers with S(n) = 3
ns = list()

# consider p^2 term
for p in primes.between(3, 31):
  n = p * p
  while n < 1000:
    if n > 99: ns.append(n)
    n *= 2
ns.sort()

# find consecutive pairs
for (a, b) in tuples(ns, 2):
  if b == a + 1:
    printf("{a}, {b}")

        We find the following 3-digit numbers with exactly 3 odd divisors:

        [p=3] 144, 288, 576
        [p=5] 100, 200, 400, 800
        [p=7] 196, 392, 784
        [p=11] 121, 242, 484, 968
        [p=13] 169, 338, 676
        [p=17] 289, 578
        [p=19] 361, 722
        [p=23] 529
        [p=29] 841
        [p=31] 961

        And there are only two consecutive numbers in this list:

        288 = (2^5)(3^2)
        289 = (2^0)(17^2)

        Like

        • Frits 10:52 pm on 3 August 2020 Permalink | Reply

          Over the first 500 million numbers (> 99) only 2 consecutive numbers exist.

          from enigma import Primes, printf, irange
 
# collect 3-digit numbers with S(n) = 3
ns = list()
test = 500000000
 
# consider p^2 term
for p in Primes(test).irange(3, test):
  n = p * p
  #print(n)
  while n < test**2:
    if n > 99: ns.append(n)
    n *= 2
ns.sort()

# find consecutive pairs

for i in irange(0, len(ns) - 2):
  if ns[i+1] == ns[i] + 1:
    printf("{ns[i]}, {ns[i+1]}")

          Output:

          288, 289
          1681, 1682

          Like

          • Jim Randell 10:24 am on 4 August 2020 Permalink | Reply

            @Frits: I found some notes (and a program) that I wrote at the time on looking for larger solutions:

            For consecutive numbers one of the following equations must hold:

            p² − (2^k)q² = +1
            p² − (2^k)q² = −1

            where p and q are odd primes.

            So we can consider solutions to the following forms of Pell’s Equation:

            x² − 2y² = +1
            x² − 2y² = −1

            and look for solutions were x is an odd prime and y is an odd prime multiplied by a power of 2.

            I have the following code (in a file called pells.py) that uses SymPy to solve Pell’s equations:

            try:
  # newer versions of SymPy
  from sympy.solvers.diophantine.diophantine import diop_DN
except ImportError:
  # older versions of SymPy
  from sympy.solvers.diophantine import diop_DN

# interleave a sequence of iterators
def interleave(ss):
  while ss:
    xs = list()
    for (i, s) in enumerate(ss):
      try:
        yield next(s)
      except StopIteration:
        xs.insert(0, i)
    for i in xs:
      del ss[i]

# initial values from a sequence of iterators
def initial(ss):
  for s in ss:
    try:
      yield next(s)
    except StopIteration:
      pass

def solutions(D, N, x, y):
  # initial solution
  yield (D, N, x, y)
  # to go further we need the fundamental solution to (D, 1)
  if N == 1:
    (u, v) = (x, y)
  else:
    [s] = diop_DN(D, 1)
    (u, v) = map(int, s)
  while True:
    t = (x, y)
    (x, y) = (u * x + D * v * y, v * x + u * y)
    if (x, y) == t: break
    assert x * x - D * y * y == N
    yield (D, N, x, y)

# generate solutions to Pell's equations
#
#  x^2 - D.y^2 = N
#
# each equation may have multiple infinite families of solutions
#
# return values are (D, N, x, y), satisfying the above equation
#
# fn=interleave will generate solutions from each family interleaved
#
# fn=initial will generate just the first solution from each family
#
# Python 3 style definition: def pells(*DNs, fn=interleave):
def pells(*DNs, **kw):
  fn = kw.get('fn', interleave)
  ss = list()
  for (D, N) in DNs:
    # consider fundamental solutions
    for s in diop_DN(D, N):
      (x, y) = map(int, s)
      ss.append(solutions(D, N, x, y))
  return fn(ss)

            Which I then use in the following program:

            Run: [ @repl.it ]

            from pells import pells
from enigma import (irange, is_prime_mr, drop_factors, first, printf)

is_prime = lambda n: is_prime_mr(n, r=10)

# look for possible solutions (from the first 60)
for (D, N, x, y) in first(pells((2, 1), (2, -1)), 60):
  # extract p, q
  p = x
  if not (p > 2 and is_prime(p)): continue
  (k, q) = drop_factors(y, 2)
  if not (q > 2 and is_prime(q)): continue
  # output solution
  (a, b) = (x * x, 2 * y * y)
  printf("{a} - {b} = {N} [p={p} q={q}]")

            I used the program to check up to 6,000 solutions to the Pell’s equations (by which time the numbers under consideration are huge), and found the following pairs:

            [p² − (2^k)q² = +1]

            289 − 288 = 1
            [n=1; p=17 q=3]

            [p² − (2^k)q² = −1]

            49 − 50 = −1
            [n=1; p=7 q=5]

            1681 − 1682 = −1
            [n=2; p=41 q=29]

            3971273138702695316401 − 3971273138702695316402 = −1
            [n=14; p=63018038201 q=44560482149]

            367680737852094722224630791187352516632102801 − 367680737852094722224630791187352516632102802 = −1
            [n=29; p=19175002942688032928599 q=13558774610046711780701]

            Like

            • Frits 8:51 am on 7 August 2020 Permalink | Reply

              @Jim,

              On PuzzlingInPython [{broken link removed}] the Pell equation has been reduced to:

              (x_{k+1}, y_{k+1}) = (3x_k+4y_k,2x_k+3y_k)

              In an overnight run with this formula I checked up to 7000 solutions (only using one core) finding no more than you did.

              Like

    • Frits 8:10 pm on 3 August 2020 Permalink | Reply

      Where did you find formula n = (2^k)(p^2) ?
      I only found a reference at OEIS A072502 ?

      from enigma import irange, printf, tau

# The requested numbers appear in OEIS as A072502
# Gary Detlefs suggested the tau equation
S = lambda n: tau(2*n) == (tau(n) + 3)
 
for a in irange(100, 998):
  b = a + 1
  if S(a) and S(b) :
    printf("{a}, {b}")

      Like

      • Jim Randell 9:58 am on 4 August 2020 Permalink | Reply

        @Frits:

        If a number is a power of 2 (= 2^n) then it will have only 1 odd divisor: 1.

        If a number has exactly 1 odd prime factor (= (2^n)p), then it will have exactly 2 odd divisors: 1, p.

        If a number has exactly 2 different odd prime factors (= (2^n)(p.q)), then it will have exactly 4 odd divisors: 1, p, q, p.q.

        But if the 2 odd prime factors are the same (so the number is (2^n)(p^2)), then it will have exactly 3 odd divisors: 1, p, p².

        Like

  • Jim Randell 6:14 pm on 27 September 2019 Permalink | Reply
    Tags: by: Bill Kinally   

    Teaser 2975: Hollow cube land 

    From The Sunday Times, 29th September 2019 [link]

    I have a large box of toy building bricks. The bricks are all cubes (the same size), and can be pushed together then dismantled.

    I decided to build the largest cube possible by leaving out all the interior bricks. When my hollow cube was finished I had two bricks left over. I put all the bricks back in the box and gave it to my two children. Each in turn was able to use every brick in the box to construct two hollow cubes, again with all interior bricks removed. Their cubes were all different sizes.

    This would not have been possible had the box contained any fewer bricks.

    How many bricks were in the box?

    [teaser2975]

     

    • Jim Randell 6:57 pm on 27 September 2019 Permalink | Reply

      For n ≥ 2 we can calculate the “hollow cube” number as:

      h(n) = n³ − (n − 2)³ = 6(n − 1)² + 2

      We can then check for values where it is possible to make h(n) + 2 from the sum of two smaller h() numbers, in (at least) two different ways.

      This Python 3 program runs in 81ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, printf)

# "hollow cube" numbers (n >= 2)
h = lambda n: 6 * (n - 1) ** 2 + 2

# solve the puzzle using formula for h(n)
def solve():
  d = dict()
  for n in irange(3, inf):
    # calculate h(n)
    x = h(n)
    printf("[h({n}) = {x}]")
    # can x + 2 be made from the sum of 2 smaller h numbers?
    ss = list(s for s in subsets(d.keys(), size=2) if sum(d[k] for k in s) == x + 2)
    # in 2 different ways?
    if len(ss) > 1:
      printf("t={t} [n={n} x={x}, ss={ss}]", t=x + 2)
      return
    # add the number to the list
    d[n] = x

solve()

      Solution: There were 3754 bricks in the box.

      The setter was able to build a hollow cube measuring 26 units along each side, using up 3752 of the bricks (leaving 2 unused).

      One child produced cubes measuring 8 and 25 units along each side, using up 296 + 3458 = 3754 bricks.

      The other child produced cubes measuring 16 and 21 units along each side, using up 1352 + 2402 = 3754 bricks.

      Analytically:

      We are looking for numbers p, q such that:

      6(n − 1)² + 4 = 6(p − 1)² + 2 + 6(q − 1)² + 2
      (n − 1)² = (p − 1)² + (q − 1)²

      So we can look for Pythagorean triples that share a hypotenuse. The smallest is:

      25² = 7² + 24² = 15² + 20²

      from which we see the setter’s cube measured 26 units, and the children’s were (8, 25) units and (16, 21) units.

      For more than 2 children the smallest solution is with 25354 bricks. The setter built a cube measuring 66 units, and there can be up to 4 children with cubes measuring (17, 64), (26, 61), (34, 57), (40, 53) units. Corresponding to:

      65² = 16² + 63² = 25² + 60² = 33² + 56² = 39² + 52²

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: