cp's OEIS Frontend

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.

%I A353108 #72 Jun 11 2023 12:26:43
%S A353108 1,1,2,4,2,10,0,12,8,12,0,36,0,40,0,0,12,102,0,84,0,0,0
%N 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.
%C A353108 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 A353108 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 A353108 a(n) = 2 * A058241(n) for n > 2.
%e A353108 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 A353108 For n = 2, the only solution (starting at 1) consists of the two numbers { 1, 2 }; arranging these around a circle as
%e A353108         1
%e A353108       /   \
%e A353108       \   /
%e A353108         2
%e A353108 gives the same cycle, i.e., { 1, 2 } whether read clockwise or counterclockwise from 1, so a(2) = 1.
%e A353108 For n = 3, the two cycles (starting at 1) are { 1, 2, 4 } and { 1, 4, 2 }, so a(3) = 2.
%e A353108 For n = 8, the twelve solutions are
%e A353108   { 1,  2, 10, 19,  4,  7,  9,  5 },
%e A353108   { 1,  3,  5, 11,  2, 12, 17,  6 },
%e A353108   { 1,  3,  8,  2, 16,  7, 15,  5 },
%e A353108   { 1,  4,  2, 10, 18,  3, 11,  8 },
%e A353108   { 1,  4, 22,  7,  3,  6,  2, 12 },
%e A353108   { 1,  6, 12,  4, 21,  3,  2,  8 },
%e A353108 and the same six cycles read in the opposite direction from 1 (e.g.,
%e A353108   { 1,  2, 10, 19,  4,  7,  9,  5 }
%e A353108 read in reverse order starting at 1 is
%e A353108   { 1,  5,  9,  7,  4, 19, 10,  2 }
%e A353108 each of which counts as a separate solution), so a(8) = 12.
%o A353108 (C++)
%o A353108 #include <vector>
%o A353108 #include <iostream>
%o A353108 #include <algorithm>
%o A353108 void show(const std::vector<int>& aa, int n) {
%o A353108   for(int i=0;i<n;++i){
%o A353108     std::cout << " " << aa[i];
%o A353108   }
%o A353108   std::cout << std::endl;
%o A353108 }
%o A353108 int sum(const std::vector<int>& aa, int n, int nn, int o){
%o A353108   int s=0;
%o A353108   for(int i=0;i<nn;++i) {
%o A353108     s += aa[(o+i)%n];
%o A353108   }
%o A353108   return s;
%o A353108 }
%o A353108 int test(const std::vector<int>& aa, int n, int t) {
%o A353108   std::vector<unsigned char> flags(t,0);
%o A353108   for(int nn=1;nn<n;++nn) {
%o A353108     for(int o=0;o<n;++o) {
%o A353108       int s=sum(aa,n,nn,o);
%o A353108       if (s >= t || flags[s]) return 0;
%o A353108       flags[s] = 1;
%o A353108     }
%o A353108   }
%o A353108   return 1;
%o A353108 }
%o A353108 int inc(std::vector<int>& aa, int p, int v) {
%o A353108   if (p==1) return 0;
%o A353108   if (aa[p-1] == v) {
%o A353108     int r = inc(aa,p-1,v);
%o A353108     if (r==0) return r;
%o A353108     aa[p-1] = 1;
%o A353108   } else {
%o A353108     ++aa[p-1];
%o A353108   }
%o A353108   return 1;
%o A353108 }
%o A353108 int a(int n){
%o A353108   int t=n*(n-1)+1;
%o A353108   std::vector<int> aa(n);
%o A353108   for (int i=0;i<n;++i) aa[i]=i+2;
%o A353108   aa[0]=1;aa[1]=2;
%o A353108   int count = 0;
%o A353108   while(inc(aa,n,t-n*(n-1)/2)) {
%o A353108     if (test(aa,n,t)) {
%o A353108       show(aa,n);
%o A353108       ++count;
%o A353108     }
%o A353108   }
%o A353108   return count;
%o A353108 }
%Y A353108 Cf. A058241.
%K A353108 nonn,hard,more
%O A353108 1,3
%A A353108 _Paul K. Davies_, Jun 18 2022
%E A353108 a(12)-a(23) computed from A058241 by _Max Alekseyev_, Jun 10 2023