S2T2

Jim Randell 10:34 am on 18 October 2020 Permalink Reply
Tags: by: M. C. Moore ( 2 )   

• 

  Jim Randell 10:35 am on 18 October 2020 Permalink | Reply

  On each of 14 days, Jack delivers n leaflets:

  On the first day 1 leaflet to each of n houses.
  On the second day 2 leaflets to each of(n / 2) houses.
  …
  On the 14th day n leaflets to 1 house.

  So we are looking for n, an even number, greater than 300, with exactly 14 divisors.

  We can then calculate the total number of houses visited by determining the sum of the divisors.

  This Python program runs in 45ms.

  Run: [ @repl.it ]

  from enigma import (irange, inf, divisors, printf)
  
  for n in irange(302, inf, step=2):
    ds = divisors(n)
    if len(ds) == 14:
      t = sum(ds)
      printf("t={t} [n={n} ds={ds}]")
      break
  

  Solution: Delivery was made to 762 houses.

  And there were 14×320 = 4480 leaflets to deliver.

  ---

  We can find numbers with exactly k divisors by considering factorisations of k (see: Enigma 1226).

  In this case, 14 = 1 × 14 = 2 × 7, so any number of the form:

  n = p^13
  n = p^1 × q^6

  for primes, p and q, will have exactly 14 divisors. [*]

  And we know one of the primes is 2.

  2^13 = 8192, which is too big.

  So we know: n = p × q^6.

  If p = 2, then the smallest possible values for n is 2 × 3^6 = 1458, which is also too big.

  So q = 2, and possible values for n are:

  3 × 2^6 = 192
  5 × 2^6 = 320
  7 × 2^6 = 448
  …

  The only sensible candidate is: n = 320, the 14 divisors are:

  1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 160, 320

  and their sum is 762.

  The sum can also be worked out directly from the prime factorisation of n:

  If σ(n) = the sum of the divisors of n, we have:

  σ(5 × 2^6) = σ(5) × σ(2^6)
  = (1 + 5) × (2^7 − 1)
  = 6 × 127
  = 762

  ---

  [*] In the published solution it is claimed that only numbers of the form (p^6 × q) have exactly 14 divisors.

  LikeLike

• 

  Frits 10:28 pm on 18 October 2020 Permalink | Reply

  Only to check if I could solve it with [[SubstitutedExpression]] without using external functions.

  from enigma import  SubstitutedExpression
  
  p = SubstitutedExpression([
      # Consider first 7 divisors (1, 2, .....)
      "XYZ > 300",
      "XYZ % 2 == 0",   # as specified
      "XYZ % IJ == 0",  # 7th divisor
      "XYZ % GH == 0",  # 6th divisor
      "XYZ % EF == 0",  # 5th divisor
      "XYZ % CD == 0",  # 4th divisor
      "XYZ % AB == 0",  # 3rd divisor
      # put them in order
      "GH < IJ",
      "EF < GH",
      "CD < EF", 
      "AB < CD", 
      "2 < AB ",
      # limit 7th divisor 
      "IJ < (XYZ // IJ)",
      # make sure there are only 7 divisors before 8th divisor
      "sum(1 for x in range(1, (XYZ // IJ)) if XYZ % x == 0) == 7",
      ],
      verbose=0,
      d2i={k:"X" for k in [x for x in range(0,10) if x != 3]},
      #accumulate=min,
      answer="(1, 2, AB, CD, EF, GH, IJ, XYZ)",
      distinct="",
      #reorder=0
  )
  
  # Solve and print answers
  
  for (_, ans) in p.solve():
   hs = 0
   # sum the divisors
   for i in range(0,7):
     hs += ans[i] + ans[7]//ans[i]
   print(f"{hs} houses") 
  

  LikeLike