A353108 - OEIS

%I #72 Jun 11 2023 12:26:43

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

%N 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.

%C 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.

%H Donald Bell, <a href="https://www.newscientist.com/article/mg25433902-500-puzzle-171-can-you-work-out-which-numbers-are-on-the-bracelet/">Puzzle #171: Can you work out which numbers are on the bracelet?</a>, New Scientist, 8 June 2022.

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

%e 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.

%e For n = 2, the only solution (starting at 1) consists of the two numbers { 1, 2 }; arranging these around a circle as

%e         1

%e       /   \

%e       \   /

%e         2

%e gives the same cycle, i.e., { 1, 2 } whether read clockwise or counterclockwise from 1, so a(2) = 1.

%e For n = 3, the two cycles (starting at 1) are { 1, 2, 4 } and { 1, 4, 2 }, so a(3) = 2.

%e For n = 8, the twelve solutions are

%e   { 1,  2, 10, 19,  4,  7,  9,  5 },

%e   { 1,  3,  5, 11,  2, 12, 17,  6 },

%e   { 1,  3,  8,  2, 16,  7, 15,  5 },

%e   { 1,  4,  2, 10, 18,  3, 11,  8 },

%e   { 1,  4, 22,  7,  3,  6,  2, 12 },

%e   { 1,  6, 12,  4, 21,  3,  2,  8 },

%e and the same six cycles read in the opposite direction from 1 (e.g.,

%e   { 1,  2, 10, 19,  4,  7,  9,  5 }

%e read in reverse order starting at 1 is

%e   { 1,  5,  9,  7,  4, 19, 10,  2 }

%e each of which counts as a separate solution), so a(8) = 12.

%o (C++)

%o #include <vector>

%o #include <iostream>

%o #include <algorithm>

%o void show(const std::vector<int>& aa, int n) {

%o   for(int i=0;i<n;++i){

%o     std::cout << " " << aa[i];

%o   }

%o   std::cout << std::endl;

%o }

%o int sum(const std::vector<int>& aa, int n, int nn, int o){

%o   int s=0;

%o   for(int i=0;i<nn;++i) {

%o     s += aa[(o+i)%n];

%o   }

%o   return s;

%o }

%o int test(const std::vector<int>& aa, int n, int t) {

%o   std::vector<unsigned char> flags(t,0);

%o   for(int nn=1;nn<n;++nn) {

%o     for(int o=0;o<n;++o) {

%o       int s=sum(aa,n,nn,o);

%o       if (s >= t || flags[s]) return 0;

%o       flags[s] = 1;

%o     }

%o   }

%o   return 1;

%o }

%o int inc(std::vector<int>& aa, int p, int v) {

%o   if (p==1) return 0;

%o   if (aa[p-1] == v) {

%o     int r = inc(aa,p-1,v);

%o     if (r==0) return r;

%o     aa[p-1] = 1;

%o   } else {

%o     ++aa[p-1];

%o   }

%o   return 1;

%o }

%o int a(int n){

%o   int t=n*(n-1)+1;

%o   std::vector<int> aa(n);

%o   for (int i=0;i<n;++i) aa[i]=i+2;

%o   aa[0]=1;aa[1]=2;

%o   int count = 0;

%o   while(inc(aa,n,t-n*(n-1)/2)) {

%o     if (test(aa,n,t)) {

%o       show(aa,n);

%o       ++count;

%o     }

%o   }

%o   return count;

%o }

%Y Cf. A058241.

%K nonn,hard,more

%O 1,3

%A _Paul K. Davies_, Jun 18 2022

%E a(12)-a(23) computed from A058241 by _Max Alekseyev_, Jun 10 2023