S2T2

Jim Randell 7:08 am on 21 March 2019 Permalink Reply
Tags: by: Bob Walker ( 10 )   

• 

  Jim Randell 7:09 am on 21 March 2019 Permalink | Reply

  If the circle is divided into k sectors, then for each starting sector (and there are k of them) we can make a contiguous region consisting of 1, 2, 3, …, (k − 1) sectors. We don’t make a region of k sectors because that is the whole circle, so we add that in separately giving a total number of arrangements of:

  n(k) = k(k − 1) + 1 = k² − k + 1

  To make the arrangements correspond to the numbers 1, 2, 3, … n(k), the whole circle needs to correspond to the value n(k), and there needs to be a single sector corresponding to the number 1. So we place the number 1 in the first sector, and then distribute the remaining (n(k) − 1) between the remaining (k − 1) sectors.

  This Python 3 program finds the solution in 83ms.

  Run: [ @replit ]

  from itertools import permutations
  from enigma import (irange, arg, printf)
  
  # generate (non-empty) tuples of adjacent sectors
  def sectors(k):
    # consider n consecutive sectors
    for n in irange(1, k - 1):
      # possible start sector
      for i in irange(0, k - 1):
        yield tuple((i + j) % k for j in irange(0, n - 1))
    # the whole circle
    yield tuple(irange(0, k - 1))
  
  # decompose <t> into <n> different numbers, min <m>
  def decompose(t, n, m, s=[]):
    if n == 1:
      if not (t < m):
        yield s + [t]
    else:
      for x in irange(m, t - n):
        yield from decompose(t - x, n - 1, x + 1, s + [x])
  
  # number of sectors to divide the circle into
  k = arg(5, 0, int, prompt="number of sectors")
  assert k > 1
  
  # make a list of adjacent sectors
  ss = list(sectors(k))
  t = len(ss)
  printf("[k={k}: {t} arrangements]")
  
  # put 1 at sector 0, and decompose the remainder
  for d in decompose(t - 1, k - 1, 2):
    for p in permutations(d):
      if p[0] > p[-1]: continue
      s = (1,) + p
      # calculate the values of adjacent sectors
      vs = set(sum(s[i] for i in x) for x in ss)
      if len(vs) == t:
        printf("{s}")
  

  Solution: The five sectors have values: 1, 2, 3, 5, 10 (in numerical order).

  They can be arranged like this:

  

  As well as the example given it is also possible to make a circle with 4 sectors using the values: 1, 3, 2, 7.

  The program is suitable for experimenting with small values of k. (One simple way to improve the program is to note that as well as a 1 sector, we will also need a 2 sector in the remaining decomposition).

  Here are the number of solutions for various values of k:

   k  n(k)  solutions
   1     1    1
   2     3    1
   3     7    1
   4    13    2
   5    21    1
   6    31    5
   7    43    0
   8    57    6
   9    73    4
  10    91    6
  11   111    0
  12   133   18
  13   157    0
  14   183   20
  ...

  (See: OEIS A058241 [ link ]).

  We’ve come across the following formula before:

  n(k) = k^2 − k + 1

  Specifically in the exploration of Teaser 2907, where it is the number of elements in a finite projective plane of order (k − 1).

  The fact that there is no solution for (k = 7, n = 43), (k = 11, n = 111) and (k = 13, n = 157) makes me wonder if there is a link with projective planes, as finite projective planes of order 6, 10, and 12 (probably) do not exist.

  ---

  For a more efficient way to generate “magic circles” see my comment on Enigma 985.

  LikeLike

  • 

    Frits 11:47 am on 13 June 2022 Permalink | Reply

    @Jim,

    You might use (and in Enigma 985):

       
    for x in irange(m, t - n * (n - 1) // 2):
    

    in decompose() as we need different numbers. It doesn’t seem to make much of a difference in the performance.

    LikeLike

    • 

      Jim Randell 11:29 am on 14 June 2022 Permalink | Reply

      @Frits: If I were to re-write the code now I would probably just use [[ decompose() ]] from enigma.py (and [[ tuples() ]] to generate the adjacent sectors). [See: @replit]

      from enigma import (irange, tuples, decompose, arg, printf)
      
      # generate (non-empty) tuples of adjacent sectors
      def sectors(k):
        # the whole circle
        t = tuple(irange(k))
        # consider n consecutive sectors
        for n in irange(1, k - 1):
          yield from tuples(t, n, circular=1)
        # and the whole circle
        yield t
      
      # number of sectors to divide the circle into
      k = arg(5, 0, int)
      assert k > 1
      
      # make a list of adjacent sectors
      ss = list(sectors(k))
      t = len(ss)
      printf("[k={k}: {t} arrangements]")
      
      # put 1 at sector 0, and 2 somewhere, and decompose the remainder
      for d in decompose(t - 3, k - 2, increasing=0, sep=1, min_v=3, fn=list):
        # insert 2 somewhere
        for i in irange(0, (0 if k == 2 else k - 3)):
          s = list(d)
          s.insert(i, 2)
          if s[0] > s[-1]: continue
          # insert 1 at sector 0
          s.insert(0, 1)
          # calculate the value for adjacent sectors
          vs = set(sum(s[i] for i in x) for x in ss)
          if len(vs) == t:
            printf("{s}", s=tuple(s))
      

      But using magic_circles.py gives a much shorter and faster program:

      from enigma import (arg, printf)
      from magic_circles import magic_circle
      
      # number of sectors to divide the circle into
      k = arg(5, 0, int, prompt="number of sectors")
      assert k > 1
      
      # find magic k-circles
      for s in magic_circle(k):
        # output solution
        printf("{s}")
      

      LikeLike