Teaser 2788: Red-letter days
From The Sunday Times, 28th February 2016 [link] [link]
The months of my 2016 calendar are headed M, T, W, Th, F, Sa, Su, with the dates 1, 2, 3… in a grid of squares underneath. I have shaded all the days on which I have meetings planned – all of them being on weekdays. For example, in February the days 1, 2, 3, 4, 8 and 9 are shaded: these shaded squares form a connected piece and the product of the numbers is a perfect cube. The same is true of the shaded squares in another month – and in fact it’s the largest possible such cube in the calendar. My last meeting in that month is on my aunt’s birthday.
What is her birthday?
[teaser2788]
Frits and 
John Crabtree, 
Tony Brooke-Taylor, 
Dirk, 
GeoffR, 
Hugh Casement, and 3 others are discussing. 
S2T2 
Jim Randell 8:42 am on 29 April 2021 Permalink |
This Python program examines each month to find regions that give the maximum possible cube.
For each month the grid is filled out, and then we calculate the total number of each possible prime factor available, and any date that contributes a prime factor that occurs fewer than 3 times is removed. We then examine subsets of the remaining numbers that have a product which is a cube, and form a connected region.
It runs in 421ms.
Run: [ @replit ]
from datetime import (date, timedelta) from enigma import (grid_adjacency, irange, factor, multiset, call, subsets, multiply, is_cube, union, Accumulator, printf) # enable internal caching for is_cube is_cube.cache_enabled = 1 # prime factors of numbers from 1 to 31 factors = dict((n, factor(n)) for n in irange(1, 31)) # the adjacency matrix for a 5x5 grid adj = grid_adjacency(5, 5) # is a region of the grid connected? def is_connected(js): # start with one of the cells, and try to connect the rest in rs = set(js[1:]) js = js[:1] while js and rs: js = union(adj[i] for i in js).intersection(rs) rs.difference_update(js) return not rs # 1 day increment day = timedelta(days=1) # find regions with maximal product r = Accumulator(fn=max, collect=1) # consider possible months (although we could skip Feb) seen = dict() for m in irange(1, 12): # fill out the grid for a particular month grid = dict() (d, i) = (date(2016, m, 1), None) while d.month == m: j = d.weekday() if j < 5: i = (j if i is None else i + 1) grid[i] = d.day d += day # remove dates that cannot be used while 1: # accumulate all the prime factors of numbers in the grid fs = call(multiset.from_seq, (factors[n] for n in grid.values())) # remove any numbers with a factor with a count < 3 ks = list(k for (k, n) in grid.items() if any(fs[f] < 3 for f in factors[n])) if not ks: break for k in ks: del grid[k] # have we already done this month k = tuple(sorted(grid.items())) if k in seen: printf("[month {m} duplicates month {x}]", x=seen[k]) continue seen[k] = m printf("[month {m}: {grid}", grid=sorted(grid.values())) # find subsets whose product is a cube for ks in subsets(grid.keys(), min_size=1): p = multiply(grid[k] for k in ks) if not (is_cube(p) and is_connected(ks)): continue vs = sorted(grid[k] for k in ks) r.accumulate_data(p, (m, vs)) printf("-> {vs} -> {p}^3", p=is_cube(p)) printf("max product = {x}^3", x=is_cube(r.value)) for (m, vs) in r.data: printf("month {m} -> {vs}")Solution: Her birthday is 27th June.
Which is a Monday in 2016.
The largest cube achievable is 15120³ = 3456649728000.
It occurs in June using dates (1), 3, 6, 7, 8, 9, 10, 14, 15, 16, 20, 21, 27. (Using 1 is optional).
The maximal cubes found for each month are:
The following diagram shows the regions that give the maximum cube for each month:
(1 is optional, except where it is required to keep the region connected, i.e. Aug, Feb).
LikeLike
Frits 6:49 pm on 30 April 2021 Permalink |
Based on Jim’s program with the idea to find the maximum product as soon as possible.
from datetime import date, timedelta from itertools import combinations from enigma import multiply, is_cube # exclude days where a prime factor can not occur 3 times per month ex_days = [11, 13, 17, 19, 22, 23, 26, 29, 31] # also exclude days on small islands ex_days += [18, 24, 25, 30] zeroes = [[0 for x in range(5)] for y in range(5)] # calculate minimal number of <s> entries to exceed <mprod> def min_entries(s, lim): p = 1 for i, v in enumerate(s): p *= v if p > lim: break return len(s) - i # chain as many cells of sequence <s> as possible def chain_cells(i, j, s, done): if i < 0 or i > 4 or j < 0 or j > 4: return [] if done[i][j] == 1: return [] ind = i * 5 + j if ind not in s: return [] chain = [ind] done[i][j] = 1 # check adjacent cells chain += chain_cells(i - 1, j, s, done) chain += chain_cells(i + 1, j, s, done) chain += chain_cells(i, j - 1, s, done) chain += chain_cells(i, j + 1, s, done) return chain # 1 day increment day = timedelta(days=1) (mprod, mentries, bday) = (0, 1, "") # consider possible months (although we could skip Feb) seen = dict() grids = dict() # build and store grids for m in range(1, 13): # fill out the grid for a particular month grid = dict() (d, i) = (date(2016, m, 1), None) while d.month == m: j = d.weekday() if j < 5: d1 = d.day i = (j if i is None else i + 1) if d1 not in ex_days: grid[i] = d1 d += day grids[m] = grid # start with the month with the most entries for m in sorted(grids, key=lambda m: len(grids[m]), reverse=True): grid = grids[m] # have we already done this month k = tuple(sorted(grid.items())) if k in seen: continue seen[k] = m allprod = multiply(grid[k] for k in grid) if mprod: d1 = allprod / mprod # not enough numbers in grid to exceed mprod if d1 < 1: continue # calculate minimal number of entries to exceed <mprod> mentries = min_entries(grid.values(), d1) # find subsets whose product is a cube for k in range(len(grid), 0, -1): if k < mentries: break for ks in combinations(grid.keys(), k): p = multiply(grid[k] for k in ks) if not(p >= mprod and is_cube(p)): continue (i, j) = (ks[0] // 5, ks[0] % 5) # days have to be connected if len(ks) > len(chain_cells(i, j, ks, [x.copy() for x in zeroes])): continue if p > mprod: mprod = p # calculate minimal number of entries to exceed <mprod> mentries = min_entries(grid.values(), allprod / mprod) vs = [grid[k] for k in ks] bday = str(vs[-1]) + "-" + str(m) + "-2016" print(f"month {m}: -> {vs} -> {is_cube(p)}^3") print(f"max product = {is_cube(mprod)}^3") print(f"birthday {bday}")LikeLike