16
\$\begingroup\$

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 , 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
\$\endgroup\$
1
  • \$\begingroup\$ Brownie points for beating/matching my 6 byte Jelly answer \$\endgroup\$ May 23 at 22:52

16 Answers 16

8
\$\begingroup\$

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!

\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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))\$.

\$\endgroup\$
5
\$\begingroup\$

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)
                               }
\$\endgroup\$
4
  • \$\begingroup\$ I can't get the code properly aligned. Is it because of BQN's weird character set? \$\endgroup\$ May 24 at 17:49
  • 1
    \$\begingroup\$ I would argue it is more the fact that the monospace fonts used by SE are broken, but yeah some characters from BQN's character get rendered shorter or wider than other characters \$\endgroup\$
    – ovs
    May 24 at 17:54
  • 1
    \$\begingroup\$ @ovs I've only heard of a single monospace font that actually includes every character in Unicode. There's a lot of them, y'know :p. (And IIRC BQN uses some rather unusual characters that rarely monospace correctly) \$\endgroup\$ May 24 at 17:56
  • 3
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 24 at 17:57
4
\$\begingroup\$

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!

\$\endgroup\$
0
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ total(...) is redundant, and both \sum can be \$\endgroup\$
    – Steffan
    May 24 at 0:32
  • \$\begingroup\$ @Steffan Ah yep, I was using a different strategy (list comprehensions) that used total before I switched to using summations. \$\endgroup\$
    – Aiden Chow
    May 24 at 0:38
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ -2 bytes, because the recursive function doesn't need to be named f ;-) \$\endgroup\$
    – pajonk
    May 24 at 9:55
  • \$\begingroup\$ @pajonk - Wow, that's so slick. Thanks for the golf and thanks for the idea! Really nice. \$\endgroup\$ May 24 at 10:29
3
\$\begingroup\$

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), 60 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!!!

\$\endgroup\$
1
  • \$\begingroup\$ 59 bytes \$\endgroup\$
    – att
    May 24 at 18:36
3
\$\begingroup\$

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!

\$\endgroup\$
6
  • \$\begingroup\$ 45 bytes \$\endgroup\$
    – att
    May 24 at 18:19
  • 1
    \$\begingroup\$ 41 bytes second \$\endgroup\$
    – att
    May 24 at 18:25
  • \$\begingroup\$ @att Could you explain how your solution works? I really wanna get better at golfing Mathematica :D \$\endgroup\$
    – JSorngard
    May 24 at 20:18
  • \$\begingroup\$ I^(4...) is shorter than E^(2Pi I...). Product is rather long, so (for simpler expressions) it's shorter to take a product by applying Times (or rather, 1##&) to a list. +++... saves one byte over (1+...) since unary + has lower precedence than ^. Finally, Sum is just better than Tr@Table, and iterators can omit the initial value if it's 1. \$\endgroup\$
    – att
    May 24 at 20:34
  • \$\begingroup\$ 39 bytes inputting [k, n] instead of [n, k] \$\endgroup\$
    – att
    May 24 at 20:36
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

LæOsÖO

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You actually beat me by 26 seconds and I saw this already here as soon as I clicked submit (although I did write out all of the explanation before posting >.<) and upvoted straight away. I'm guessing caird's was one of ours or a slight variation like ŒP§ọƇL or ŒP§%¬S. \$\endgroup\$ May 24 at 10:50
  • \$\begingroup\$ @JonathanAllan Actually, I had ŒP§ḍ@S (but still a slight variation on both yours and Steffan's answers) \$\endgroup\$ May 24 at 20:06
2
\$\begingroup\$

Factor + math.combinatorics math.unicode, 50 bytes

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

Try it online!

Takes input as k n.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 20 bytes

I№﹪EX²N↨E⮌↨ι²∧λ⊕μ¹N⁰

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

     ²                  Literal integer `2`
    X                   Raised to power
      N                 First input as an integer
   E                    Map over implicit range
           ι            Current value
          ↨             Converted to base
            ²           Literal integer `2`
         ⮌              Reversed
        E               Map over bits
              λ         Current bit
             ∧          Logical And
                μ       Current index
               ⊕        Incremented
       ↨         ¹      Take the sum
  ﹪                     Vectorised modulo
                  N     Second input as an integer
 №                 ⁰    Count the zeros
I                       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:

≔EN¬ιθFNUMθ⁺κ§θ⁻λ⊕ιI§θ⁰

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

≔EN¬ιθ

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

FN

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

UMθ⁺κ§θ⁻λ⊕ι

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

I§θ⁰

Output the first element of the result.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.