A353108 a(n) is the number of cycles of n numbers arranged so that every integer in 1..n*(n-1)+1 occurs as the sum of up to n adjacent numbers. Both a solution and its reverse are counted unless they are identical.

1, 1, 2, 4, 2, 10, 0, 12, 8, 12, 0, 36, 0, 40, 0, 0, 12, 102, 0, 84, 0, 0, 0

Offset

1,3

Comments

For n = 1 and n = 2, there is only one solution, and it is counted once because the numbers encountered in moving around the circle, starting at 1, are the same regardless of direction; see Example section.

Links

Table of n, a(n) for n=1..23.

Donald Bell, Puzzle #171: Can you work out which numbers are on the bracelet?, New Scientist, 8 June 2022.

Formula

a(n) = 2 * A058241(n) for n > 2.

Example

For n = 1, the only solution consists of the single number { 1 }, and a "cycle" consisting of { 1 } is the same whether read forward or backward, so a(1) = 1.
For n = 2, the only solution (starting at 1) consists of the two numbers { 1, 2 }; arranging these around a circle as
        1
      /   \
      \   /
        2
gives the same cycle, i.e., { 1, 2 } whether read clockwise or counterclockwise from 1, so a(2) = 1.
For n = 3, the two cycles (starting at 1) are { 1, 2, 4 } and { 1, 4, 2 }, so a(3) = 2.
For n = 8, the twelve solutions are
  { 1,  2, 10, 19,  4,  7,  9,  5 },
  { 1,  3,  5, 11,  2, 12, 17,  6 },
  { 1,  3,  8,  2, 16,  7, 15,  5 },
  { 1,  4,  2, 10, 18,  3, 11,  8 },
  { 1,  4, 22,  7,  3,  6,  2, 12 },
  { 1,  6, 12,  4, 21,  3,  2,  8 },
and the same six cycles read in the opposite direction from 1 (e.g.,
  { 1,  2, 10, 19,  4,  7,  9,  5 }
read in reverse order starting at 1 is
  { 1,  5,  9,  7,  4, 19, 10,  2 }
each of which counts as a separate solution), so a(8) = 12.

Prog

(C++)
#include <vector>
#include <iostream>
#include <algorithm>
void show(const std::vector<int>& aa, int n) {
  for(int i=0; i<n; ++i){
    std::cout << " " << aa[i];
  }
  std::cout << std::endl;
}
int sum(const std::vector<int>& aa, int n, int nn, int o){
  int s=0;
  for(int i=0; i<nn; ++i) {
    s += aa[(o+i)%n];
  }
  return s;
}
int test(const std::vector<int>& aa, int n, int t) {
  std::vector<unsigned char> flags(t, 0);
  for(int nn=1; nn<n; ++nn) {
    for(int o=0; o<n; ++o) {
      int s=sum(aa, n, nn, o);
      if (s >= t || flags[s]) return 0;
      flags[s] = 1;
    }
  }
  return 1;
}
int inc(std::vector<int>& aa, int p, int v) {
  if (p==1) return 0;
  if (aa[p-1] == v) {
    int r = inc(aa, p-1, v);
    if (r==0) return r;
    aa[p-1] = 1;
  } else {
    ++aa[p-1];
  }
  return 1;
}
int a(int n){
  int t=n*(n-1)+1;
  std::vector<int> aa(n);
  for (int i=0; i<n; ++i) aa[i]=i+2;
  aa[0]=1; aa[1]=2;
  int count = 0;
  while(inc(aa, n, t-n*(n-1)/2)) {
    if (test(aa, n, t)) {
      show(aa, n);
      ++count;
    }
  }
  return count;
}

Crossrefs

Cf. A058241.

Sequence in context: A303165 A188813 A324958 * A072866 A061393 A260361

Adjacent sequences: A353105 A353106 A353107 * A353109 A353110 A353111

Keyword

nonn,hard,more

Author

Paul K. Davies, Jun 18 2022

Extensions

a(12)-a(23) computed from A058241 by Max Alekseyev, Jun 10 2023

Status

approved