A063776 -id:A063776 - cp's OEIS frontend

A051293 Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.

1, 2, 5, 8, 15, 26, 45, 76, 135, 238, 425, 768, 1399, 2570, 4761, 8856, 16567, 31138, 58733, 111164, 211043, 401694, 766417, 1465488, 2807671, 5388782, 10359849, 19946832, 38459623, 74251094, 143524761, 277742488, 538043663, 1043333934, 2025040765, 3933915348

Offset: 1

John W. Layman, Oct 30 1999

a(n) is asymptotic to 2^(n+1)/n. More precisely, I conjecture for any m > 0, a(n) = 2^(n+1)/n * Sum_{k=0..m} A000670(k)/n^k + o(1/n^(m+1)) (A000670 = preferential arrangements of n labeled elements) which can be written a(n) = 2^n/n * 2 + Sum_{k=1..m} A000629(k)/n^k + o(1/n^(m+1)) (A000629 = necklaces of sets of labeled beads). In fact I conjecture that a(n) = 2^(n+1)/n * (1 + 1/n + 3/n^2 + 13/n^3 + 75/n^4 + 541/n^5 + o(1/n^5)). - Benoit Cloitre, Oct 20 2002

A082550(n) = a(n+1) - a(n). - Reinhard Zumkeller, Feb 19 2006

			a(4) = 8 because each of the 8 subsets {1}, {2}, {3}, {4}, {1,3}, {2,4}, {1,2,3}, {2,3,4} has an integer average.

Alois P. Heinz, Table of n, a(n) for n = 1..3332 (first 300 terms from T. D. Noe)
63rd Annual William Lowell Putnam Mathematical Competition, Problem A3, Mathematics Magazine 76 (2003), 76-80.

Row sums of A061865 and A327481.

Cf. A000629, A000670, A082550, A114976.

with(numtheory):
b:= n-> add(2^(n/d)*phi(d), d=select(x-> x::odd, divisors(n)))/n:
a:= proc(n) option remember; `if`(n<1, 0, b(n)-1+a(n-1)) end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jul 15 2019

Table[ Sum[a = Select[Divisors[i], OddQ[ # ] & ]; Apply[Plus, 2^(i/a)*EulerPhi[a]]/i, {i, n}] - n, {n, 34}]
Table[Count[Subsets[Range[n]],?(IntegerQ[Mean[#]]&)],{n,35}] (* _Harvey P. Dale, Apr 14 2018 *)

a(n)=sum(k=1,n,sumdiv(k,d,d%2*2^(k/d)*eulerphi(d))/k-1)

from sympy import totient, divisors
def A051293(n): return sum((sum(totient(d)<>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))-n # Chai Wah Wu, Feb 22 2023

a(n) = Sum_{i=1..n} (A063776(i) - 1).

Extended by Robert G. Wilson v, Oct 16 2002

A000016 a(n) is the number of distinct (infinite) output sequences from binary n-stage shift register which feeds back the complement of the last stage.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 6, 10, 16, 30, 52, 94, 172, 316, 586, 1096, 2048, 3856, 7286, 13798, 26216, 49940, 95326, 182362, 349536, 671092, 1290556, 2485534, 4793492, 9256396, 17895736, 34636834, 67108864, 130150588, 252645136, 490853416

Offset: 0

N. J. A. Sloane

Also a(n+1) = number of distinct (infinite) output sequences from binary n-stage shift register which feeds back the complement of the sum of its contents. E.g., for n=5 there are 6 such sequences.
Also a(n+1) = number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} i*x_i = 0 (mod n+1) = size of Varshamov-Tenengolts code VT_0(n). E.g., |VT_0(5)| = 6 = a(6).
Number of binary necklaces with an odd number of zeros. - Joerg Arndt, Oct 26 2015
Also, number of subsets of {1,2,...,n-1} which sum to 0 modulo n (cf. A063776). - Max Alekseyev, Mar 26 2016
From Gus Wiseman, Sep 14 2019: (Start)
Also the number of subsets of {1..n} containing n whose mean is an element. For example, the a(1) = 1 through a(8) = 16 subsets are:
  1  2  3    4    5      6      7        8
        123  234  135    246    147      258
                  345    456    357      468
                  12345  1236   567      678
                         1456   2347     1348
                         23456  2567     1568
                                12467    3458
                                13457    3678
                                34567    12458
                                1234567  14578
                                         23578
                                         24568
                                         45678
                                         123468
                                         135678
                                         2345678
(End)
Number of self-dual binary necklaces with 2n beads (cf. A263768, A007147). - Bernd Mulansky, Apr 25 2023

			For n=3 the 2 output sequences are 000111000111... and 010101...
For n=5 the 4 output sequences are those with periodic parts {0000011111, 0001011101, 0010011011, 01}.
For n=6 there are 6 such sequences.

B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 172.
J. Hedetniemi and K. R. Hutson, Equilibrium of shortest path load in ring network, Congressus Numerant., 203 (2010), 75-95. See p. 83.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. Stoffer, Delay equations with rapidly oscillating stable periodic solutions, J. Dyn. Diff. Eqs. 20 (1) (2008) 201, eq. (39)

Seiichi Manyama, Table of n, a(n) for n = 0..3334 (first 201 terms from T. D. Noe)
Nicolás Álvarez, Victória Becher, Martín Mereb, Ivo Pajor, and Carlos Miguel Soto, On extremal factors of de Bruijn-like graphs, Univ. Buenos Aires (Argentina 2023). See also arXiv:2308.16257 [math.CO], 2023. See references.
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 17.
A. E. Brouwer, The Enumeration of Locally Transitive Tournaments, Math. Centr. Report ZW138, Amsterdam, 1980.
S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk, Estimating the size of correcting codes using extremal graph problems, Optimization, 227-243, Springer Optim. Appl., 32, Springer, New York, 2009.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Sébastien Designolle, Tamás Vértesi, and Sebastian Pokutta, Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms, arXiv:2310.20677 [quant-ph], 2023.
T. M. A. Fink, Exact dynamics of the critical Kauffman model with connectivity one, arXiv:2302.05314 [cond-mat.stat-mech], 2023.
R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887-896.
A. A. Kulkarni, N. Kiyavash and R. Sreenivas, On the Varshamov-Tenengolts Construction on Binary Strings, 2013.
E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations, Pacific J. Math., 110 (1984), 203-221.
R. Pries and C. Weir, The Ekedahl-Oort type of Jacobians of Hermitian curves, arXiv preprint arXiv:1302.6261 [math.NT], 2013.
N. J. A. Sloane, On single-deletion-correcting codes
N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs
Yan Bo Ti, Gabriel Verret, and Lukas Zobernig, Abelian Varieties with p-rank Zero, arXiv:2203.08401 [math.NT], 2022.
Antonio Vera López, Luis Martínez, Antonio Vera Pérez, Beatriz Vera Pérez, and Olga Basova, Combinatorics related to Higman's conjecture I: Parallelogramic digraphs and dispositions, Linear Algebra Appl. 530, 414-444 (2017).
Index entries for sequences related to tournaments
Index entries for sequences related to necklaces
Index entries for sequences related to subset sums modulo m

The main diagonal of table A068009, the left edge of triangle A053633.
Cf. A000048, A000031, A000013, A053634, A182469.
Subsets whose mean is an element are A065795.
Dominated by A082550.
Partitions containing their mean are A237984.
Subsets containing n but not their mean are A327477.
Cf. A051293, A135342, A240850, A327471, A327478.

a000016 0 = 1
a000016 n = (`div` (2 * n)) $ sum $
   zipWith (*) (map a000010 oddDivs) (map ((2 ^) . (div n)) $ oddDivs)
   where oddDivs = a182469_row n
-- Reinhard Zumkeller, May 01 2012

A000016 := proc(n) local d, t; if n = 0 then return 1 else t := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t := t + NumberTheory:-Totient(d)* 2^(n/d)/(2*n) fi od; return t fi end:

a[0] = 1; a[n_] := Sum[Mod[k, 2] EulerPhi[k]*2^(n/k)/(2*n), {k, Divisors[n]}]; Table[a[n], {n, 0, 35}](* Jean-François Alcover, Feb 17 2012, after Pari *)

a(n)=if(n<1,n >= 0,sumdiv(n,k,(k%2)*eulerphi(k)*2^(n/k))/(2*n));

from sympy import totient, divisors
def A000016(n): return sum(totient(d)<>(~n&n-1).bit_length(),generator=True))//n if n else 1 # Chai Wah Wu, Feb 21 2023

a(n) = Sum_{odd d divides n} (phi(d)*2^(n/d))/(2*n), n>0.
a(n) = A063776(n)/2.
a(n) = 2^(n-1) - A327477(n). - Gus Wiseman, Sep 14 2019

More terms from Michael Somos, Dec 11 1999

A327475 Number of subsets of {1..n} whose mean is an integer, where {} has mean 0.

Original entry on oeis.org

1, 2, 3, 6, 9, 16, 27, 46, 77, 136, 239, 426, 769, 1400, 2571, 4762, 8857, 16568, 31139, 58734, 111165, 211044, 401695, 766418, 1465489, 2807672, 5388783, 10359850, 19946833, 38459624, 74251095, 143524762, 277742489, 538043664, 1043333935, 2025040766, 3933915349

Offset: 0

Gus Wiseman, Sep 13 2019

nonn

			The a(0) = 1 through a(5) = 16 subsets:
  {}  {}   {}   {}       {}       {}
      {1}  {1}  {1}      {1}      {1}
           {2}  {2}      {2}      {2}
                {3}      {3}      {3}
                {1,3}    {4}      {4}
                {1,2,3}  {1,3}    {5}
                         {2,4}    {1,3}
                         {1,2,3}  {1,5}
                         {2,3,4}  {2,4}
                                  {3,5}
                                  {1,2,3}
                                  {1,3,5}
                                  {2,3,4}
                                  {3,4,5}
                                  {1,2,4,5}
                                  {1,2,3,4,5}

If the subset is required to contain n, we get A063776.

Cf. A000016, A051293, A065795, A082550, A135342, A327474, A327481.

with(numtheory):
b:= n-> add(2^(n/d)*phi(d), d=select(x-> x::odd, divisors(n)))/n:
a:= proc(n) option remember; `if`(n=0, 1, b(n)-1+a(n-1)) end:
seq(a(n), n=0..36);  # Alois P. Heinz, Jan 13 2024

Table[Length[Select[Subsets[Range[n]],#=={}||IntegerQ[Mean[#]]&]],{n,0,10}]

from sympy import totient, divisors
def A327475(n): return sum((sum(totient(d)<>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))-n+1 # Chai Wah Wu, Feb 22 2023

a(n) = A051293(n) + 1.

A327481 Triangle read by rows where T(n,k) is the number of nonempty subsets of {1..n} with mean k.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 3, 7, 3, 1, 1, 3, 9, 9, 3, 1, 1, 3, 9, 19, 9, 3, 1, 1, 3, 9, 25, 25, 9, 3, 1, 1, 3, 9, 29, 51, 29, 9, 3, 1, 1, 3, 9, 31, 75, 75, 31, 9, 3, 1, 1, 3, 9, 31, 93, 151, 93, 31, 9, 3, 1, 1, 3, 9, 31, 105, 235, 235, 105, 31, 9, 3, 1

Offset: 1

Gus Wiseman, Sep 13 2019

All terms are odd.

			Triangle begins:
                         1
                       1   1
                     1   3   1
                   1   3   3   1
                 1   3   7   3   1
               1   3   9   9   3   1
             1   3   9  19   9   3   1
           1   3   9  25  25   9   3   1
         1   3   9  29  51  29   9   3   1
       1   3   9  31  75  75  31   9   3   1
     1   3   9  31  93 151  93  31   9   3   1
   1   3   9  31 105 235 235 105  31   9   3   1
The subsets counted in row n = 5:
  {1}  {2}      {3}          {4}      {5}
       {1,3}    {1,5}        {3,5}
       {1,2,3}  {2,4}        {3,4,5}
                {1,3,5}
                {2,3,4}
                {1,2,4,5}
                {1,2,3,4,5}

Row sums are A051293.
The sequence of rows converges to A066571.
The version for partitions is A327482.
Cf. A000016, A063776, A065795, A135342, A327474, A327475, A327483, A327484.

Table[Length[Select[Subsets[Range[n]],Mean[#]==k&]],{n,10},{k,n}]

A068009 Square array T(m,n) with m (row) >= 1 and n (column) >= 0 read by antidiagonals: number of subsets of {1,2,3,...n} that sum to 0 mod m (including the empty set, whose sum is 0).

Original entry on oeis.org

1, 2, 1, 4, 1, 1, 8, 2, 1, 1, 16, 4, 2, 1, 1, 32, 8, 4, 1, 1, 1, 64, 16, 6, 2, 1, 1, 1, 128, 32, 12, 4, 2, 1, 1, 1, 256, 64, 24, 8, 4, 2, 1, 1, 1, 512, 128, 44, 16, 8, 3, 1, 1, 1, 1, 1024, 256, 88, 32, 14, 6, 3, 1, 1, 1, 1, 2048, 512, 176, 64, 26, 12, 5, 2, 1, 1, 1, 1, 4096, 1024, 344, 128, 52, 22, 10, 4, 2, 1, 1, 1, 1

Offset: 0

Antti Karttunen, Feb 11 2002

When p is an odd prime, T(p,k+p) = 2*T(p,k) + (2^k * ((2^p) - 2)/p) for all k >= 0. [Sophie LeBlanc]
When m divides n (with n >= m), T(m,n) = (1/m) Sum_{d | m and d is odd} phi(d) * 2^(n/d). [N. Kitchloo and L. Pachter; D. Rusin]
A068009(C(i+1,2), i) = 2, A068009(C(i,2)+1, i) = A000009(i-1) + 1. [AK, cf. A068049]

			Table for T(m,n) (with rows m >= 1 and columns n >= 0) begins as follows:
  1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, ...
  1, 1, 2, 4,  8, 16, 32,  64, 128, 256,  512, 1024, ...
  1, 1, 2, 4,  6, 12, 24,  44,  88, 176,  344, ...
  1, 1, 1, 2,  4,  8, 16,  32,  64, 128,  ...
  1, 1, 1, 2,  4,  8, 14,  26,  52, ...
  1, 1, 1, 2,  3,  6, 12,  22, ...
  1, 1, 1, 1,  3,  5, 10, ...
  1, 1, 1, 1,  2,  4, ...
  1, 1, 1, 1,  2, ...
  1, 1, 1, 1, ...
  1, 1, 1, ...
  1, 1, ...
  1, ...
  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Antti Karttunen, Scheme code for computing this table and its rows.
N. Kitchloo and L. Pachter, An interesting result about subset sums, Nov 27 1993.
William Kuszmaul, A new approach to enumerating statistics modulo n, arXiv:1402.3839 [math.CO], 2014.
Lior Pachter, Subset sums, 2015.
Bill Pet, Sophie LeBlanc, Will Self et al., Subsets of {1,2,3,...,n} (discussion in sci.math).
R. P. Stanley and M. F. Yoder, A study of Varshamov codes for asymmetric channels, JPL Technical Report 32-1526, Vol. XIV (1972), 117-123.
Index entries for sequences related to subset sums mod m

Main diagonal: A000016, superdiagonal: A063776. The first term greater than one occurs on each row m in the position A002024(m) and these are given in A068049.

Row 1: A000079, row 2: A011782, row 3: A068010, row 5: A068011, row 6: A068012, row 7: A068013, row 9: A068030, row 10: A068031, row 11: A068032, row 12: A068033, row 13: A068034, row 14: A068035, row 15: A068036, row 16: A068037, row 17: A068038, row 18: A068039, row 19: A068040, row 20: A068041, row 21: A068042, row 25: A068043, row 32: A068044, row 64: A068045.

b:= proc(n, m, t) option remember; `if`(n=0, `if`(t=0, 1, 0),
       b(n-1, m, t)+ b(n-1, m, irem(t+n,m)))
    end:
T:= (m, n)-> b(n, m, 0):
seq(seq(T(1+m, d-m), m=0..d), d=0..12);  # Alois P. Heinz, Jan 18 2014

max = 13; row[m_] := (ClearAll[t]; im = IdentityMatrix[m]; v = Join[ {Last[im]}, Most[im] ]; t[0] = im[[1]]; t[k_] := t[k] = (im + MatrixPower[v, k]) . t[k-1]; Table[ t[k][[1]], {k, 0, max}]); rows = Table[ row[m], {m, 1, max}]; A068009 = Flatten[ Table[ rows[[m-n+1, n]], {m, 1, max, 1}, {n, m, 1, -1}]] (* Jean-François Alcover, Apr 02 2012, after Will Self *)
b[n_, m_, t_] := b[n, m, t] = If[n == 0, If[t == 0, 1, 0], b[n-1, m, t]+b[n-1, m, Mod[t+n, m]]]; T[m_, n_] := b[n, m, 0]; Table[Table[T[1+m, d-m], {m, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jan 13 2015, after Alois P. Heinz *)

A082550 Number of sets of distinct positive integers whose arithmetic mean is an integer, the largest integer of the set being n.

Original entry on oeis.org

1, 1, 3, 3, 7, 11, 19, 31, 59, 103, 187, 343, 631, 1171, 2191, 4095, 7711, 14571, 27595, 52431, 99879, 190651, 364723, 699071, 1342183, 2581111, 4971067, 9586983, 18512791, 35791471, 69273667, 134217727, 260301175, 505290271, 981706831, 1908874583, 3714566311

Offset: 1

Naohiro Nomoto, May 03 2003

Equivalently, number of nonempty subsets of [n] the sum of whose elements is divisible by n. - Dimitri Papadopoulos, Jan 18 2016

			a(5) = 7: the seven sets are (1+2+3+4+5)/5 = 3, 5/1 = 5, (1+5)/2 = 3, (1+3+5)/3 = 3, (3+5)/2 = 4, (3+4+5)/3 = 4, (1+2+4+5)/4 = 3.

Cf. A008965, A051293, A063776, A309402.

Row sums of A267632.

Table[Length[Select[Select[Subsets[Range[n]],Max[#]==n&], IntegerQ[ Mean[ #]]&]], {n,22}] (* Harvey P. Dale, Jul 23 2011 *)
Table[Total[Table[Length[Select[Select[Subsets[Range[n]], Length[#] == k &],IntegerQ[Total[#]/n] &]], {k, n}]], {n, 10}] (* Dimitri Papadopoulos, Jan 18 2016 *)

a(n) = sumdiv(n, d, (d%2)* 2^(n/d)*eulerphi(d))/n - 1; \\ Michel Marcus, Feb 10 2016

from sympy import totient, divisors
def A082550(n): return (sum(totient(d)<>(~n&n-1).bit_length(),generator=True))<<1)//n-1 # Chai Wah Wu, Feb 22 2023

a(n) = A063776(n) - 1.
a(n) = A051293(n+1) - A051293(n). - Reinhard Zumkeller, Feb 19 2006
a(n) = A008965(n) for odd n. - Dimitri Papadopoulos, Jan 18 2016
G.f.: -x/(1 - x) - Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m + 1)). - Petros Hadjicostas, Jul 13 2019
a(n) = A309402(n,n). - Alois P. Heinz, Jul 28 2019

a(22) from Harvey P. Dale, Jul 23 2011

a(23)-a(32) from Dimitri Papadopoulos, Jan 18 2016

A065795 Number of subsets of {1,2,...,n} that contain the average of their elements.

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 72, 124, 218, 390, 706, 1292, 2388, 4436, 8292, 15578, 29376, 55592, 105532, 200858, 383220, 732756, 1403848, 2694404, 5179938, 9973430, 19229826, 37125562, 71762396, 138871260, 269021848, 521666984, 1012520400, 1966957692, 3824240848

Offset: 1

John W. Layman, Dec 05 2001

nonn

Also the number of subsets of {1,2,...,n} with sum of entries divisible by the largest element (compare A000016). See the Palmer Melbane link for a bijection. - Joel B. Lewis, Nov 13 2014

			a(4)=6, since {1}, {2}, {3}, {4}, {1,2,3} and {2,3,4} contain their averages.
From _Gus Wiseman_, Sep 14 2019: (Start)
The a(1) = 1 through a(6) = 16 subsets:
  {1}  {1}  {1}      {1}      {1}          {1}
       {2}  {2}      {2}      {2}          {2}
            {3}      {3}      {3}          {3}
            {1,2,3}  {4}      {4}          {4}
                     {1,2,3}  {5}          {5}
                     {2,3,4}  {1,2,3}      {6}
                              {1,3,5}      {1,2,3}
                              {2,3,4}      {1,3,5}
                              {3,4,5}      {2,3,4}
                              {1,2,3,4,5}  {2,4,6}
                                           {3,4,5}
                                           {4,5,6}
                                           {1,2,3,6}
                                           {1,4,5,6}
                                           {1,2,3,4,5}
                                           {2,3,4,5,6}
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..3333
Palmer Melbane, Combinations under constraint, Art of Problem Solving thread. - _Joel B. Lewis_, Nov 13 2014

Subsets containing n whose mean is an element are A000016.
The version for integer partitions is A237984.
Subsets not containing their mean are A327471.
Cf. A051293, A063776, A066571, A135342, A324736, A325705, A326083, A326836, A327478, A327481.

Table[ Sum[a = Select[Divisors[i], OddQ[ # ] &]; Apply[ Plus, 2^(i/a) * EulerPhi[a]]/i, {i, n}]/2, {n, 34}]
(* second program *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,Mean[#]]&]],{n,0,10}] (* Gus Wiseman, Sep 14 2019 *)

a(n) = (1/2)*sum(i=1, n, (1/i)*sumdiv(i, d, if (d%2, 2^(i/d)*eulerphi(d)))); \\ Michel Marcus, Dec 20 2020

from sympy import totient, divisors
def A065795(n): return sum((sum(totient(d)<>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))>>1 # Chai Wah Wu, Feb 22 2023

a(n) = (1/2)*Sum_{i=1..n} (f(i) - 1) where f(i) = (1/i) * Sum_{d | i and d is odd} 2^(i/d) * phi(d).
a(n) = (n + A051293(n))/2.
a(n) = 2^n - A327471(n). - Gus Wiseman, Sep 14 2019

Edited and extended by Robert G. Wilson v, Nov 15 2002

A300190 Number of solutions to 1 +- 2 +- 3 +- ... +- n == 0 (mod n).

Original entry on oeis.org

1, 0, 2, 4, 4, 0, 10, 32, 30, 0, 94, 344, 316, 0, 1096, 4096, 3856, 0, 13798, 52432, 49940, 0, 182362, 699072, 671092, 0, 2485534, 9586984, 9256396, 0, 34636834, 134217728, 130150588, 0, 490853416, 1908874584, 1857283156, 0, 7048151672, 27487790720

Offset: 1

Seiichi Manyama, Feb 28 2018

nonn

Apparently a(2*n + 1) = A053656(2*n + 1) for n >= 0. - Georg Fischer, Mar 26 2019

			Solutions for n = 7:
--------------------------
1 +2 +3 +4 +5 +6 +7 =  28.
1 +2 +3 +4 +5 +6 -7 =  14.
1 +2 -3 +4 -5 -6 +7 =   0.
1 +2 -3 +4 -5 -6 -7 = -14.
1 +2 -3 -4 +5 +6 +7 =  14.
1 +2 -3 -4 +5 +6 -7 =   0.
1 -2 +3 +4 -5 +6 +7 =  14.
1 -2 +3 +4 -5 +6 -7 =   0.
1 -2 -3 -4 -5 +6 +7 =   0.
1 -2 -3 -4 -5 +6 -7 = -14.

Seiichi Manyama, Table of n, a(n) for n = 1..3334 (terms 1..1000 from Alois P. Heinz)

Number of solutions to 1 +- 2^k +- 3^k +- ... +- n^k == 0 (mod n): this sequence (k=1), A300268 (k=2), A300269 (k=3).
Cf. A000016, A026119, A053656, A058377, A063776, A300307, A300328.
Cf. A016825 (4n+2).

b:= proc(n, i, m) option remember; `if`(i=0, `if`(n=0, 1, 0),
      add(b(irem(n+j, m), i-1, m), j=[i, m-i]))
    end:
a:= n-> b(0, n-1, n):
seq(a(n), n=1..60);  # Alois P. Heinz, Mar 01 2018

b[n_, i_, m_] := b[n, i, m] = If[i == 0, If[n == 0, 1, 0], Sum[b[Mod[n + j, m], i - 1, m], {j, {i, m - i}}]];
a[n_] := b[0, n - 1, n];
Array[a, 60] (* Jean-François Alcover, Apr 29 2020, after Alois P. Heinz *)

def A(n)
  ary = [1] + Array.new(n - 1, 0)
  (1..n).each{|i|
    i1 = 2 * i
    a = ary.clone
    (0..n - 1).each{|j| a[(j + i1) % n] += ary[j]}
    ary = a
  }
  ary[(n * (n + 1) / 2) % n] / 2
end
def A300190(n)
  (1..n).map{|i| A(i)}
end
p A300190(100)

a(4*n+1) = A000016(n), a(4*n+2) = 0, a(4*n+3) = A000016(n), a(4*n+4) = 2 * A000016(n) for n > 0.

a(2^n) = 2^A000325(n) for n > 1.

cp's OEIS Frontend

A283843 a(n) = A063776(n) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A283844 a(n) = A063776(2*n) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A051293 Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A000016 a(n) is the number of distinct (infinite) output sequences from binary n-stage shift register which feeds back the complement of the last stage.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A327475 Number of subsets of {1..n} whose mean is an integer, where {} has mean 0.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A327481 Triangle read by rows where T(n,k) is the number of nonempty subsets of {1..n} with mean k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A068009 Square array T(m,n) with m (row) >= 1 and n (column) >= 0 read by antidiagonals: number of subsets of {1,2,3,...n} that sum to 0 mod m (including the empty set, whose sum is 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs