Divisible subset sums

Question

_{Inspired by the recent 3Blue1Brown video}

Consider, for some positive integer \$n\$, the set \$\{1, 2, ..., n\}\$ and its subsets. For example, for \$n = 3\$, we have

$$\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$$

If we take the sum of these subsets, we can then ask ourselves the following question:

Of the sums of the subsets of \$\{1, 2, ..., n\}\$, how many are divisible by some given integer \$k\$?

Again, using \$n = 3\$ as an example, we have our subset sums as

$$0, 1, 2, 3, 3, 4, 5, 6$$

For \$k = 2\$, there are \$4\$ subsets whose sum is divisible by \$k\$: \$\emptyset, \{2\}, \{1,3\}\$ and \$\{1,2,3\}\$.

---

Given two positive integers \$n \$ and \$k\$, with \$2 \le k \le n\$, output the number of subsets of \$\{1, 2, 3, ..., n-1, n\}\$ such that their sum is divisible by \$k\$.

You may take input and give output in any reasonable manner and format. This is code-golf, so the shortest code in bytes wins.

---

Test cases

   n    k    out
   3    2      4
   5    5      8
  13    8   1024
   2    2      2
   7    7     20
  14    4   4096
  15   10   3280
   9    5    104
   7    2     64
  11    4    512
  15    3  10944
  16    7   9364
  13    5   1640
  11    6    344
  12   10    410
   9    9     60

And, a couple of larger ones, taken from the approach in the 3Blue1Brown video:

 200, 5 -> 321387608851798055108392418468232520504440598757438176362496
2000, 5 -> 22962613905485090484656664023553639680446354041773904009552854736515325227847406277133189726330125398368919292779749255468942379217261106628518627123333063707825997829062456000137755829648008974285785398012697248956323092729277672789463405208093270794180999311632479761788925921124662329907232844394066536268833781796891701120475896961582811780186955300085800543341325166104401626447256258352253576663441319799079283625404355971680808431970636650308177886780418384110991556717934409897816293912852988275811422719154702569434391547265221166310540389294622648560061463880851178273858239474974548427800576

Answer 1

Python 3, 54 bytes

f=lambda n,k,r=0:n and f(n-1,k,r)+f(n-1,k,r-n)or r%k<1

Try it online!

Answer 2

JavaScript (ES6), 40 bytes

Expects (k)(n).

k=>g=(n,s=0)=>n--?g(n,s)+g(n,s-~n):s%k<1

Try it online!

Commented

k =>           // outer function taking k
g = (          // inner recursive function taking:
  n,           //   n
  s = 0        //   s = sum of set entries
) =>           //
n-- ?          // if n is not equal to 0 (decrement it afterwards):
  g(n, s) +    //   do a recursive call with s unchanged
  g(n, s - ~n) //   do a recursive call where n+1 is added to s
:              // else:
  s % k < 1    //   increment the final result if k divides s

Answer 3

PARI/GP, 34 bytes

f(n,k)=prod(i=1,n,x^i+1)%(x^k-1)%x

Attempt This Online!

Longer but faster, 43 bytes:

f(n,k)=lift(prod(i=1,n,Mod(x^i+1,x^k-1)))%x

Attempt This Online!

Using generating functions. Finds the constant term of the polynomial \$\prod_{i=1}^n(X^i+1)\$ in the ring \$\mathbb{Z}[X]/((X^k-1))\$.

Answer 4

BQN, 26 bytes

{+´0=𝕨|+´¨1+(⥊(↕2˘)/¨<)↕𝕩}

This block takes n as its right argument and k as its left one

Explanation:

    {
     +´                         # count (sum of booleans)
       0=𝕨|                     # values divisible by left argument (k)
            +´¨1+(⥊(↕2˘)/¨<)↕𝕩  # in the list of the sums of the subsets
                 (⥊(↕2˘)/¨<)    #   get all the subsets of
                            ↕𝕩  #   all natural integers inferior to the right argument (n)
            +´¨1+               #   +1 (otherwise values would go from 0 to (n-1) instead of the expected 1 to n)
                               }

Answer 5

Vyxal R, 5 bytes

ṗṠ$Ḋ∑

Try it Online!

 Ṡ    # Sums of
ṗ     # Powersets of 1...input
  $Ḋ  # Are divisible by other input?
    ∑ # Count those where they are

Vyxal Rrs, 3 bytes

ṗṠḊ

Try it Online!

Answer 6

Desmos, 74 65 bytes

-9 bytes thanks to Steffan

f(n,k)=∑_{N=1}^{2^n}0^{mod(∑_{a=1}^namod(floor(2N/2^a),2),k)}

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 7

R, 79 bytes

function(n,m)sum(!sapply(apply(expand.grid(rep(list(!1:0),n)),1,which),sum)%%m)

Attempt This Online!

expand.grid generates all permutations of n elements of TRUE/FALSE; then which identifies the TRUE index in each permutation: this is the powerset of 1:n; get the sum of each (using sapply), find those that are zero modulo m, and sum the results.

Performing the which and sum calculations together costs more in R < 4.1, since we need to declare a new function, but this is offset in more-recent R versions that can use \ as a short form:

---

R≥4.1, 72 bytes

\(n,m)sum(!apply(expand.grid(rep(list(!1:0),n)),1,\(x)sum(which(x)))%%m)

Attempt This Online!

---

I wrote all that, and then - before posting - browsed down to Arnauld's and att's answers, and realised that porting their beautiful recursive approach into R would be hugely shorter. Upvote them!

R≥4.1, 49 47 bytes

Edit: -2 bytes thanks to a very nice golf by pajonk, using the indexing operator [ as the recursive function name

`[`=\(k,n,s=0)`if`(n,k[n-1,s]+k[n-1,s+n],!s%%k)

Attempt This Online!

Answer 8

C (gcc), 79 bytes

a;p;s;b;f(n,k){for(a=b=0;++b<1<<n;a+=s%k<1)for(p=s=0;p<n;s+=1<<p++&b?p:0);++a;}

Try it online!

Port of Arnauld's JavaScript answer:

C (gcc), ⁶⁰ 59 bytes

t;g(n,s){n=n?g(n,s+n--)+g(n,s):s%t<1;}f(n,k){t=k;n=g(n,0);}

Try it online!

Saved a byte thanks to att!!!

Answer 9

Wolfram Language (Mathematica), 53 41 38 bytes

-12 -15 bytes, thanks @att!

Tr[1##&@@@+++I^(4##&~Array~{##}/#)]/#&

Try it online!

Previous solution by @att

Sum[1##&@@+++I^(4k/#2Range@#),{k,#2}]/#2&

Try it online!

Previous solution by me:

f=PolynomialMod;f[Product[1+x^i,{i,1,#1}],x^#2-1]~f~x&

Try it online!

First I forgot the & and Mathematica simplified the entire expression to QPochammer[-1,x,1+#1]/2. At first I was quite happy: a way to shorten the code! Before I realized that it can't be right because this removes an entire argument of the function.
Sad times :(

Using 58 bytes we can get code that is much faster at evaluating the answer for large inputs, with the only issue that it gives the answer as an expression involving exponentials of complex expressions:

Tr[Product[1+E^(2i I π k/#2),{i,1,#}]~Table~{k,1,#2}]/#2&

The expressions are equivalent to the correct number, but Mathematica only simplifies it down if we add FullSimplify@ in front, resulting in a total of 71 bytes.

Try it online!

Answer 10

Jelly, 6 bytes

ŒP§ọTL

A dyadic Link that accepts \$n\$ on the left and \$k\$ on the right and yields the count of subset sums of \$[1,n]\$ divisible by \$k\$.

Try it online!

How?

ŒP§ọTL - Link: n, k
ŒP     - powerset of [1,n]
  §    - sums
   ọ   - how many times is each divisible by k?
    T  - truthy indices
     L - length

---

Alternatively, using filter-keep: ŒP§ọƇL

Answer 11

05AB1E, 6 bytes

LæOsÖO

Try it online!

Answer 12

Jelly, 6 bytes

ŒP§%ċ0

Try it online!

How?

ŒP§%ċ0  Full program: Dyadic link f(n, k):
ŒP      Powerset of n, which is implicitly converted to range [1..n]
  §     Sum of each
   %    Modulo each by k
    ċ0  Count the number of zeros

Edit: Whoops, Jonathan Allan beat me by one minute.

Answer 13

Factor + math.combinatorics math.unicode, 50 bytes

[ [1,b] all-subsets swap '[ Σ _ mod 0 = ] count ]

Try it online!

Takes input as k n.

Answer 14

Burlesque, 17 bytes

roR@{++dv}x/1iafl

Try it online!

ro     # Range 1..n
R@     # All subsets
{
 ++    # Sum
 dv    # Divides (a%b == 0)
}
x/     # reorder stack
1ia    # Insert divisor in position 1 (zero-indexed)
fl     # Count of matches

Answer 15

Charcoal, 20 bytes

Ｉ№﹪ＥＸ²Ｎ↨Ｅ⮌↨ι²∧λ⊕μ¹Ｎ⁰

Try it online! Link is to verbose version of code. Explanation:

     ²                  Literal integer `2`
    Ｘ                   Raised to power
      Ｎ                 First input as an integer
   Ｅ                    Map over implicit range
           ι            Current value
          ↨             Converted to base
            ²           Literal integer `2`
         ⮌              Reversed
        Ｅ               Map over bits
              λ         Current bit
             ∧          Logical And
                μ       Current index
               ⊕        Incremented
       ↨         ¹      Take the sum
  ﹪                     Vectorised modulo
                  Ｎ     Second input as an integer
 №                 ⁰    Count the zeros
Ｉ                       Cast to string
                        Implicitly print

Base 1 conversion is used to sum as the first subset is empty and Sum doesn't like that.

For 23 bytes, a much more efficient version:

≔ＥＮ¬ιθＦＮＵＭθ⁺κ§θ⁻λ⊕ιＩ§θ⁰

Try it online! Link is to verbose version of code. Takes arguments in the order k, n. Explanation:

≔ＥＮ¬ιθ

Make a list of k elements where the first is 1 and the rest are 0.

ＦＮ

For i from 1..n (actually 0-indexed but I use Incremented(i) below)...

ＵＭθ⁺κ§θ⁻λ⊕ι

... cyclically rotate the list by i and vectorised add it back.

Ｉ§θ⁰

Output the first element of the result.

Answer 16

Husk, 7 bytes

#¦⁰mΣṖḣ

Try it online!

#¦⁰mΣṖḣ  
      ḣ  # get the sequence 1..arg2
     Ṗ   # and get the powerset (all finite subsets);
   m     # now map over each subset:
    Σ    # get the sum
#        # and count the number of results
 ¦       # that are divisible by
  ⁰      # arg1