cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A098966 Number of (k+1)-tuples of integers modulo n (x_1,...,x_k,s) such that at least one subset of the x_i sums to s mod n. In other words, n^k times the expected number of distinct subset sums mod n of k integers mod n chosen uniformly at random. Read by antidiagonals, i.e., with entries in the order (n,k)=(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...

This page as a plain text file.
%I A098966 #6 Jul 27 2017 03:41:25
%S A098966 1,1,3,1,7,5,1,15,21,7,1,31,73,43,9,1,63,233,215,73,11,1,127,717,951,
%T A098966 497,111,13,1,255,2173,3971,2865,959,157,15,1,511,6545,16171,15161,
%U A098966 6863,1657,211,17,1,1023,19665,65167,77369,44391,14521,2631,273,19
%N A098966 Number of (k+1)-tuples of integers modulo n (x_1,...,x_k,s) such that at least one subset of the x_i sums to s mod n. In other words, n^k times the expected number of distinct subset sums mod n of k integers mod n chosen uniformly at random. Read by antidiagonals, i.e., with entries in the order (n,k)=(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...
%C A098966 a(n,k) <= n^(k+1).
%F A098966 a(n, 1) = 2*n - 1;
%F A098966 a(n, 2) = 4*n^2 - 6*n + 3;
%F A098966 a(n, 3) = 8*n^3 - 28*n^2 + 44*n - 23, n odd;
%F A098966 a(n, 3) = 8*n^3 - 28*n^2 + 44*n - 25, n even;
%F A098966 a(1, k) = 1;
%F A098966 a(2, k) = 2^(k+1) - 1;
%F A098966 a(3, k) = 3^(k+1) - 2*k - 2.
%e A098966 Table begins
%e A098966   1,  1,   1,    1,     1, ...
%e A098966   3,  7,  15,   31,    63, ...
%e A098966   5, 21,  73,  233,   717, ...
%e A098966   7, 43, 215,  951,  3971, ...
%e A098966   9, 73, 497, 2865, 15161, ...
%e A098966   ...
%t A098966 <<DiscreteMath`Combinatorica`;
%t A098966 SubsetSums[l_]:=Plus@@#&/@Subsets[l];
%t A098966 NumSumsModN[l_, n_]:=Length[Union[Mod[SubsetSums[l], n]]];
%t A098966 a[1, k_]:=1;
%t A098966 a[n_, k_]:=Plus@@Table[NumSumsModN[IntegerDigits[x, n, k], n], {x, 0, n^k-1}];
%t A098966 Flatten[Table[a[n, j-n], {j, 1, 10}, {n, 1, j-1}]]
%Y A098966 First column is A005408; second column is A054569; second row is A000225.
%K A098966 nonn,tabl
%O A098966 1,3
%A A098966 Andrew Childs (amchilds(AT)caltech.edu) and Wim van Dam (vandam(AT)cs.ucsb.edu), Oct 13 2004