cp's OEIS Frontend

A325679 Number of compositions of n such that every restriction to a circular subinterval has a different sum.

%I A325679 #13 Mar 25 2025 19:18:31
%S A325679 1,1,1,3,3,5,5,13,13,27,21,41,41,77,63,143,129,241,203,385,347,617,
%T A325679 491,947,835,1445,1185,2511,1991,3585,2915,5411,4569,8063,6321,11131,
%U A325679 10133,16465,13207,23817,20133,33929,26663,48357,41363,69605,54363,95727,81183,132257,106581
%N A325679 Number of compositions of n such that every restriction to a circular subinterval has a different sum.
%C A325679 A composition of n is a finite sequence of positive integers summing to n.
%C A325679 A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.
%C A325679 For n > 0, a(n) is the number of subsets of Z_n which contain 0 and such that every ordered pair of distinct elements has a different difference (modulo n). The elements of a subset correspond with the partial sums of a composition. For example, when n = 8 the subset {0,2,7} corresponds with the composition (251). - _Andrew Howroyd_, Mar 24 2025
%H A325679 Andrew Howroyd, <a href="/A325679/b325679.txt">Table of n, a(n) for n = 0..80</a>
%e A325679 The a(1) = 1 through a(8) = 13 compositions:
%e A325679   (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)
%e A325679             (12)  (13)  (14)  (15)  (16)   (17)
%e A325679             (21)  (31)  (23)  (24)  (25)   (26)
%e A325679                         (32)  (42)  (34)   (35)
%e A325679                         (41)  (51)  (43)   (53)
%e A325679                                     (52)   (62)
%e A325679                                     (61)   (71)
%e A325679                                     (124)  (125)
%e A325679                                     (142)  (152)
%e A325679                                     (214)  (215)
%e A325679                                     (241)  (251)
%e A325679                                     (412)  (512)
%e A325679                                     (421)  (521)
%t A325679 suball[q_]:=Join[Take[q,#]&/@Select[Tuples[Range[Length[q]],2],OrderedQ],Drop[q,#]&/@Select[Tuples[Range[2,Length[q]-1],2],OrderedQ]];
%t A325679 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Total/@suball[#]&]],{n,0,15}]
%o A325679 (PARI)
%o A325679 a(n)={
%o A325679    my(recurse(k,b,w)=
%o A325679       if(k >= n, 1,
%o A325679          b+=1<<k;
%o A325679          my(t=bitand((1<<n)-1, bitor(b<<k, b<<(k-n))));
%o A325679          if(k, self()(k+1, b-(1<<k), w)) +
%o A325679             if(!bitand(w,t), self()(k+1, b, w + t));
%o A325679        ));
%o A325679    recurse(0,0,0);
%o A325679 } \\ _Andrew Howroyd_, Mar 24 2025
%Y A325679 Cf. A000079, A008965, A108917, A143823, A169942, A276024.
%Y A325679 Cf. A325545, A325676, A325677, A325678, A325680, A325681, A325687, A382399.
%K A325679 nonn
%O A325679 0,4
%A A325679 _Gus Wiseman_, May 13 2019
%E A325679 a(21) onwards from _Andrew Howroyd_, Mar 24 2025