1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
from jigsaw import (generate_shapes, select_pieces, grid_out, solve_rect as solve_rect) from collections import defaultdict from itertools import count # generate solutions for a square of width and height <wh> def solve_sq(wh, pieces, dsh): for shs in select_pieces(wh ** 2, pieces, dsh, min_pc=2): for s in solve_rect(shs, wh, wh, dsh): if len(set(s)) > 1: yield s # find solutions for sets of squares def solve_sqs(sql, pieces, dsh, res=()): if not sql: yield res else: for s in solve_sq(sql[0], pieces, dsh): nu = tuple(x for x in pieces if x not in set(s)) yield from solve_sqs(sql[1:], nu, dsh, res + (s,)) # find sums of numerical square values that sum to a given value (t) def sum_sq(t, mv, sv=()): if not t: if len(sv) > 1: yield sv else: for c in count(mv if not sv else sv[-1] + 1): if (sq := c * c) > t: return yield from sum_sq(t - sq, mv, sv + (c,)) # find pieces that can be made from groups of connected # squares within a four by three grid of squares pieces = generate_shapes(4, 3, two_sided=False, max_sq=4) # find their total area max_area = sum(len(s[0][0]) for s in pieces.values()) # find the possible groups of squares that can be made # from the pieces and index them on their total area a2s = defaultdict(list) for area in range(2 * 2 + 3 * 3, max_area + 1): for sqt in sum_sq(area, 2): a2s[area] += [sqt] # for each area that is made up of squares for area in a2s.keys(): # consider any overall area that is not uniquely # identified by the squares it can make if len(a2s[area]) > 1: # select combinations of pieces that can make this area for ks in select_pieces(area, pieces.keys(), pieces, min_pc=4): # check this subset can make more than one set of squares sl = [] for sqs in a2s[area]: for res in solve_sqs(sqs, ks, pieces): if res: # only consider the first solution found sl.append((sqs, res)) break # do we have more than one solution with this # set of pieces? if len(sl) > 1: # output the number of pieces and example solutions print(f"\n\n{len(ks)} pieces:") for sqs, res in sl: for wh, r in zip(sqs, res): grid_out(r, wh, wh) |

It uses either specific rectangle fitting code or Donald Knuth’s ‘Algorithm X’ (by changing ‘solve_rect as solve_rect’ to ‘solve_rectx as solve_rect’ in line 2). It produces the solution with the following two sets of squares in under a second.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
from itertools import permutations sf = [] def sub_fact(n): if n == 0: return 1 return n * sub_fact(n - 1) + (-1 if n % 2 == 1 else 1) for n in range(1, 20): sfact = sub_fact(n) sf.append(sfact) for a, b in permutations(sf, 2): if b > a and a != 0 and b // a == 206: num1, num2 = sf.index(a) + 1, sf.index(b) + 1 print (f"1st number of friends/derangments = {num1}/{a}") print (f"2nd number of friends/derangments = {num2}/{b} ") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# The number of derangements, D(n), of N items (permutations in # which all items change their original positions) is given by: # # D(1) = 0; N > 1: D(N) = N.D(N - 1) + (-1)^N # or: # # D(n) = [n! / e] d, ds = 0, [0] for n in range(2, 20): # compute D(n) and add 206 times its value as a target d = n * d + 1 - 2 * (n & 1) ds.append(d) # have we hit a target? q, r = divmod(d, 206) if r == 0 and q in ds: print(f"{d} derangements and {n} friends (earlier {q} and {ds.index(q) + 1}).") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# whole number a = n+1 + n+2 + n+3 ... + n+j if it is the sum of j consecutive # numbers so a = n*j + j*(j+1)/2 # a - j*(j+1)/2 = n * j # (a - j*(j+1)/2)/j = n # # this is true for any a and any j if (a-(j*(j+1)/2))%j==0 and a >= j*(j+1)/2 #i.e. (a-(j*(j+1)/2))/j=n with n integer aprev = 0 for a in range(99, 999): tot = 0 for j in range (2, 45): # 990 = 1 + 2 + 3 ... + 44 tot += a >= j * (j + 1) / 2 and (a - (j * (j + 1) / 2)) % j == 0 if tot == 2: if aprev + 1 == a: print ("Ben's number", a," Amelia's number", aprev) aprev = a |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
# Numbers that can be represented as the sums of consecutive integers # # This analysis is an extension of John Crabtree's original work. # # Let N = 2^k.A.B where A and B are both odd with B > A and k = 0, 1, 2, ... # # (1) Let i = (A.B - 1) / 2 and consider the sequence of A.B terms: # # 2^k - i, 2^k - i + 1, ..., 2^k, ..., 2^k + i - 1, 2^k + i # # These sum to N and are all positive provided that A.B <= 2^(k + 1) # # Now let i = (A.B + 1) / 2 - 2^k and consider the 2^(k + 1) term sequence: # # i, i + 1, ..., i + 2^(k + 1) - 1 # # These also sum to N and are all positive provided that A.B >= 2^(k + 1) # # So this sequence has min(A.B, 2^{k + 1}) terms. # # (2) Let i = (A - 1) / 2 and consider the sequence of A terms: # # 2^k.B - i, 2^k.B - i + 1, ..., 2^k.B, ..., 2^k.B + i - 1, 2^k.B + i # # These have a sum of N and, since 2^k.B > i, they are all positive. # # This sequence has A terms. # # (3) Let i = (B - 1) / 2 and consider the sequence of B terms: # # 2^k.A - i, 2^k.A - i + 1, ..., 2^k.A, ..., 2^k.A + i - 1, 2^k.A + i # # These sum to N and are all positive provided that B <= 2^(k + 1).A # # Now let i = (B + 1) / 2 - 2^k.A and consider the 2^(k + 1).A term sequence: # # i, i + 1, ..., i + 2^(k + 1).A - 1 # # These also sum to N and are all positive provided that B >= 2^(k + 1).A # # This sequence has min(B, 2^{k + 1}.A) terms. # # So numbers that are the product a power of 2 and two different odd numbers # will always have more than two representations. # # So the only such numbers that could have exactly two representations are # the product of a power of 2 and the square of a prime. # # Note also that the number of ways that a number N can be written as the sum of M # consecutive integers (M > 1) is one less than the number of odd divisors of N. # We are looking for two consecutive values each with exactly two representations. # Let the odd value be p^2 and the even value be 2^(2.k + 1).r^2 where p and q are # both prime. So we have: # # p^2 - 2.(2^k.q)^2 = +/- 1 # # which is a quadratic diophantine equation. from heapq import merge from number_theory import is_prime, Qde # derive the two additive sequences for the value 2^k.p def seqs(k, p): p2, k2 = p * p, 2 ** k if p2 <= 2 * k2: b1, l1 = k2 - (p2 - 1) // 2, p2 else: b1, l1 = (p2 + 1) // 2 - k2, 2 * k2 b2, l2 = k2 * p - (p - 1) // 2, p s1 = f"{b1:,}({l1:,})" s2 = f"{b2:,}({l2:,})" return ' / '.join((s1, s2) if b1 <= b2 else (s2, s1)) cnt = 0 # merge quadratic diophantine solutions for right hand sides of -1 and +1 for p, r in merge(Qde(2, -1).solve(), Qde(2, 1).solve()): # output the first four solutions if cnt == 4: break # p must be prime if is_prime(p): # find q and k such that r = 2^k.q with q odd q, k = r, 0 while not q % 2: q //= 2 k += 1 k = 2 * k + 1 # q must also be prime if is_prime(q): # find additive sequences for the two solutions u = (seqs(0, p), seqs(k, q)) # output the solutions in right numerical order v = (p * p, 2 * r * r) a, b = reversed(v) if v[0] - v[1] == 1 else v c, d = reversed(u) if v[0] - v[1] == 1 else u print(f"{a:,} / {b:,}\n {c:}\n {d}\n") cnt += 1 |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from collections import defaultdict from itertools import count d = defaultdict(list) for n in range(1, 500): # sum <cnt> consecutive integers starting with <n> for cnt in count(2): csum = cnt * (2 * n + cnt - 1) // 2 if csum >= 1000: break # save three digit results if csum >= 100: d[csum] += [(n, cnt)] # Find two consecutive numbers that can each be # expressed in exactly two ways as consecutive sums for m in d.keys(): if m + 1 in d.keys(): if len(d[m]) == 2 and len(d[m + 1]) == 2: print(f"Amelia's number is {m} -> {d[m]}") print(f"Ben's number is {m + 1} -> {d[m + 1]}") |