Consecutive coin flips

Question

This is a cross-post of a problem I posted to anarchy golf: http://golf.shinh.org/p.rb?tails

Given two integers \$ n \$ and \$ k \$ \$ (0 \le k \le n) \$, count the number of combinations of \$ n \$ coin tosses with at least \$ k \$ tails in a row.

For example, if \$ n = 3 \$ and \$ k = 2 \$, the answer is \$ 3 \$:

HHH ❌
HHT ❌
HTH ❌
HTT ✔️
THH ❌
THT ❌
TTH ✔️
TTT ✔️

For convenience sake, you do not need to handle the case where \$ n = k = 0 \$.

Rules

• The input must take in two integers \$ n \$ and \$ k \$, and output the answer as a single integer
• Inaccuracies due to integer overflow are acceptable, but floating point errors are prohibited
• As usual for code-golf, the shortest code in bytes wins

Test Cases

 n,  k  ->  ans
---------------
 1,  0  ->  2
 1,  1  ->  1
 2,  0  ->  4
 2,  1  ->  3
 2,  2  ->  1
 3,  1  ->  7
 3,  2  ->  3
 3,  3  ->  1
 5,  2  ->  19
 6,  4  ->  8
 9,  2  ->  423
12,  0  ->  4096
13,  5  ->  1262
14,  8  ->  256
16,  7  ->  2811

More terms are listed under OEIS A109435.

Answer 1

Python, 50 bytes

lambda n,k:sum(k*"1"in bin(i)for i in range(2**n))

Attempt This Online!

Brute-force solution seems to be the shortest.

---

Python, 67 bytes

lambda n,k:2**n-(g:=lambda a:a*k>0and(a<3or g(a-1)*2-g(a+~k)))(n+2)

Attempt This Online!

-11 bytes thanks to Neil.

More mathematical answer.

$$ f(n, k) = 2^n - k \operatorname{-bonacci}(n+k) \\ k \operatorname{-bonacci}(n) = \begin{cases} 0 & n < k-1 \\ 1 & n = k-1 \\ \sum^k_{i=1} k \operatorname{-bonacci}(n-i) & n > k-1 \end{cases} $$

Answer 2

x86-64 machine code, 28 bytes

31 C0 99 52 89 F1 FF C9 78 07 D1 EA 72 F8 75 F4 41 FF C0 5A FF C2 0F A3 FA 73 E8 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes n in EDI and k in ESI and returns the answer in EAX.

In assembly:

f:  xor eax, eax
    cdq
a:  push rdx
b:  mov ecx, esi
c:  dec ecx
    js d
    shr edx, 1
    jc c
    jnz b
    .byte 0x41
d:  inc eax
    pop rdx
    inc edx
    bt edx, edi
    jnc a
    ret

Answer 3

Vyxal s, 13 9 8 bytes

EƛbĠṠ⁰≥a

Try it Online!

A very neat little answer I'm very happy with.

Explained

EƛbĠṠ⁰≥a
Eƛ       # to each item in the range [1, 2 ** N)
  bĠṠ    #   get the sums of consecutive digits of the binary representation of that number
     ⁰≥a #   are any of those greater than K? This is essentially getting all consecutive runs of flips and getting there length. Works because there's only 1s and 0s
# the s flag sums that list. 

Answer 4

Python, 55 bytes

f=lambda n,k:n>=k and 2*f(n-1,k)-(-1<<n>>-~k)-f(n+~k,k)

Attempt This Online!

Slightly longer than @pxeger's Python answer but more efficient.

How?

Uses the recurrence

\$f(n,k)=2f(n-1,k)+2^{n-k-1}-f(n-k-1,k)\qquad(n>k)\$

which is obtained by counting words that have k consecutive 1's somewhere in the first n-1 places, words that end in a 0 followed by k 1's and the overlap of these two groups.

Answer 5

JavaScript (ES7), 59 bytes

Expects (n)(k).

Fully bitwise because binary string manipulation in JS is too verbose.

(n,i=1<<n)=>g=k=>i--&&(h=m=>i&m^m?h(m*2):m<=i)(2**k-1)+g(k)

Try it online!

---

JavaScript (ES7), 38 bytes

Saved 2 bytes thanks to @Neil

Expects (k)(n). Returns true for 1.

Uses loopy walt's recursion formula.

k=>g=n=>n>k?2*g(--n)-g(n-=k)+2**n:n==k

Try it online!

Answer 6

K (ngn/k), 21 19 bytes

-2 bytes saved thanks to a suggestion by coltim on another answer.

Enumerates all binary length-n sequences and counts the ones with runs of at least k 1s.

{+/y<|/1(1+*)\!x#2}

Try it online!

Answer 7

PARI/GP, 40 bytes

k->g(n,r=k)=if(!r,2^n,n,g(n--,r--)+g(n))

Attempt This Online!

A port of @tsh's JavaScript answer.

---

PARI/GP, 42 bytes

k->n->(y=1-x)/(y-=x)/(x+y/x^k)%x^(n+1)\x^n

Attempt This Online!

According to OEIS, the generating function for column \$k\$ is \$\frac{x^k}{(1-\sum_{i=1}^k x^i)(1-2x)}\$, which could be simplified to \$\frac{(1-x)}{(1-2x)(x+(1-2x)/x^k)}\$.

Answer 8

Jelly, 8 bytes

1xẇⱮSɓ2ṗ

Try it online!

\$k\$ on the left, \$n\$ on the right.

   Ɱ        For each
     ɓ2ṗ    sequence of n 1s and 2s,
  ẇ         does it contain as a sublist
1x          k 1s?
    S       Sum.

Answer 9

Factor + sequences.repeating, 58 bytes

[ "1"swap cycle swap 2^ iota [ >bin subseq? ] with count ]

Try it online!

---

Longer but much cooler:

Factor, 67 bytes

[| n k | n 2^ ""n [ dup k short tail* sum suffix ] times last - ]

Try it online!

\$2^n\$ minus the \$(n+k-1)\$th k-bonacci number.

Example:

\$n=6, k=4\$

The tetranacci sequence begins: \$0, 1, 1, 2, 4, 8, 15, 29, \color{red}{56}\$

\$2^6-56=8\$

Answer 10

C (gcc), ⁸⁹ 88 bytes

m;r;a;b;c;f(n,k){for(c=b=1<<n;b--;c-=m<k)for(a=b,m=r=0;a;m=r>m?r:m)r+=a&1?:-r,a/=2;m=c;}

Try it online!

Saved a byte thanks to ceilingcat!!!

Answer 11

C (standard compliant), 78 bytes

int f(int n,int k,int c){return n?n+c-k?k-c?f(n-1,k,0)+f(n-1,k,c+1):1<<n:1:0;}

For the readable version:

int f(int n,int k,int c){
    if(n==0)return 0; // no more coin flip left => no possible path
    if(n==(k-c))return 1; // last coin flip and 1 tail is lacking
    if(k==c)return 1<<n; // we have done k tails in a row, any path is a good path, and there are 2^n
    return f(n-1,k,0) // possible paths if we get a head
    +f(n-1,k,c+1); // possible paths if we get a tail
}

Answer 12

APL(Dyalog Unicode), 28 bytes ^SBCS

{1⊥⍵≤⌈/∘(≢¨⊆⍨)⍤1⍉(⍺⍴2)⊤⍳2*⍺}

Try it on APLgolf!

Alternatively (same length): {1⊥(∨/(⍵⍴1)⍷⊢)⍤1⍉(⍺⍴2)⊤⍳2*⍺}

Answer 13

Retina, 39 bytes

.+,(.+)
<$1*1>
"$+"+%`$
0$"1
<(.*)>.*\1

Try it online! No test suite due to the way the program uses history. Explanation:

.+,(.+)
<$1*1>

Replace the input with a string of k 1s wrapped in <>s.

"$+"+

Repeat n times.

%`$
0$"1

Duplicate each row, appending 0 and 1 to each copy respectively.

<(.*)>.*\1

Count the number of rows where the binary portion contains k 1s.

Answer 14

05AB1E, 8 bytes

TIã$×δåO

Try it online or verify all test cases or try it step-by-step.

Explanation:

T        # Push 10
 I       # Push the first input `n`
  ã      # Take the cartesian product of the two, to create all possible n-sized strings
         # containing 0s and 1s
   $     # Push 1 and the second input `k`
    ×    # Repeat the 1 `k` amount of times as string
     δ   # Map over the list we created earlier, using this "1"-string as argument:
      å  #  Check if the "1"-string is a substring of the string we're mapping over
       O # Sum to get the amount of truthy values
         # (which is output implicitly as result)

Answer 15

Retina 0.8.2, 94 bytes

.+,(.+)
1$&$*0;$&$*11;$1$*,1,
+`1;1*,(((1)|,)*)
;$1$#3$*1,
+`^(1+)0
$1$1
r`\2;;(1*,)*(1*),$

1

Try it online! Link includes test cases. Explanation:

.+,(.+)
1$&$*0;$&$*11;$1$*,1,

Create 2ⁿ in binary, n+1 in unary, then a list of k 0s and a 1.

+`1;1*,(((1)|,)*)
;$1$#3$*1,

Repeat n+1 times, drop the first element of the list, and append the sum of the remaining elements. This calculates the n+1th k-bonacci number.

+`^(1+)0
$1$1

Convert the 2ⁿ from binary into unary.

   r`\2;;(1*,)*(1*),$

Subtract the n+1th k-bonacci number from 2ⁿ.

1

Convert to decimal.

Rather than trying to count the number of n coin tosses with at least k tails in a row, it's easier to consider the number of n coin tosses that do not have k tails in a row. By considering them grouped by the number of tails that they end with, it's possible to determine a recurrence relation for the number of rows. For example, with k=3:

• For 0 coin tosses, 1 ends in 0 tails, 0 end in 1 tails, and 0 end in 2 tails. Total 1 matching row.
• For 1 coin toss, 1 ends in 0 tails, 1 ends in 1 tails, and 0 end in 2 tails. Total 2 matching rows.
• For 2 coin tosses, 2 end in 0 tails, 1 ends in 1 tails, and 1 ends in 2 tails. Total 4 matching rows.
• For 3 coin tosses, 4 end in 0 tails, 2 end in 1 tails, and 1 ends in 2 tails. Total 7 matching rows.
• For 4 coin tosses, 7 end in 0 tails, 4 end in 1 tails, and 2 end in 2 tails. Total 13 matching rows.
• For n coin tosses:
  • The number that end in 0 tails is the total for n-1 coin tosses, since the value is simply that plus an extra toss of heads.
  • The number that end in 1 tails is the number that end in 0 tails for n-1 coin tosses, with each row having an extra toss of tails. However, this is also the total for n-2 coin tosses.
  • The number that end in 2 tails is the number that end in 1 tails for n-1 coin tosses, with each row having an extra toss of tails. Recursively, we see that this is also the total for n-3 coin tosses.
  • The total is the sum of these which is also the total of the previous three totals. Thus, this forms a 3-binacci sequence.

In general, the number of n coin tosses that do not have k tails in a row is a k-binacci sequence.

The number of n coin tosses with at least k tails in a row plus the number of n coin tosses that do not have k tails in a row is of course the total possible number of rows, 2ⁿ.

Answer 16

JavaScript (Node.js), 39 bytes

k=>g=(n,r=k)=>r?n&&g(--n,--r)+g(n):2**n

Try it online!

k=>    // Number of tails required in a row
g=(
  n,   // Number of coins we will flip
  r=k  // Number of tails still required in a row
)=>
  r?   // Do we still require tails?
   n&& // And we have more coins can flip?
    g(--n,--r)+ // Luckily, tail this time
    g(n):       // Nope, head this time
  2**n // We don't care what we get from remaining coins

Answer 17

R, 72 68 bytes

Edit: -4 bytes thanks to @Dominic van Essen.

\(n,k)sum(sapply(1:2^n-1,\(x,r=rle(intToBits(x)>0))any(r$l*r$v>=k)))

Attempt This Online!

Answer 18

BQN, 20 bytes

{+´⥊∨´¨∧´˘¨𝕩⊸↕¨↕𝕨⥊2}

-1 byte thanks to @Razetime!

Try it here!

Explanation

• ↕𝕨⥊2 generate binary sequences of length n
• 𝕩⊸↕¨ convert each binary sequence to subsequences of length k
  • example: 1010 with k=3 becomes 101, 010
• ∨´¨∧´˘¨ AND each subsequence, then OR each result
• +´⥊ sum to get total number of 1s

Answer 19

Pip, 14 bytes

0<1XbNTB_MS,Ea

Attempt This Online!

Brute force, same concept as pxeger's Python answer.

-5 bytes thanks to DLosc

Answer 20

Burlesque, 36 bytes

s11rzjCBg1{{gw:pd{-]g1>=}fl}fl}qL[IE

Try it online!

s1     # Save k
1rz    # [0, 1]
jCB    # Combinations up to n
g1     # Get k
{      # Catch k == 0
 {gw   # Group with length ([1, 1, 0] -> [[2, 1], [1, 0]])
  :pd  # Filter for tails
  {    # Filter
   -]  # Head
   g1  # k
   >=  # Greater than or equal
  }
  fl   # Count matches
 }
 fl    # Count matches
}
qL[    # Length of combinations (when k == 0)
IE     # If else

Answer 21

Charcoal, 15 bytes

ＮθＩＬΦＸ²Ｎ№⍘ι²×θ1

Try it online! Link is to verbose version of code. Takes k as the first input and n as the second input. Explanation: Uses brute force, so takes exponential time in n.

Ｎθ              Input `k` as an integer
      ²         Literal integer `2`
     Ｘ          Raised to power
       Ｎ        Input `n` as an integer
    Φ           Filtered where
          ι     Current value
         ⍘      Converted to base
           ²    Literal integer `2`
        №       Count i.e. contains
              1 Literal string `1`
            ×   Repeated by
             θ  Input `k`
   Ｌ            Take the length
  Ｉ             Cast to string
                Implicitly print

27 bytes for an efficient version (approximately linear time):

ＮθＮη⊞υ¹Ｆ⊕θ⊞υ↨¹✂⮌υ⁰η¹Ｉ⁻Ｘ²θ⊟υ

Try it online! Link is to verbose version of code. Takes n as the first input and k as the second input. Explanation:

ＮθＮη

Input n and k.

⊞υ¹

Start with the zeroth term of the k-bonacci sequence.

Ｆ⊕θ⊞υ↨¹✂⮌υ⁰η¹

Calculate n+1 additional terms.

Ｉ⁻Ｘ²θ⊟υ

Subtract the n+1th term from 2ⁿ.

Answer 22

Perl 5 -pl, 35 bytes

$b=<>;$_=grep/T{$b}/,glob"{H,T}"x$_

Try it online!

Answer 23

MATLAB, 71 bytes

function f(n,k),sum(contains(string(dec2bin(0:2^n-1)),repmat('1',1,k)))

The binary representation of all numbers from 0-2^n-1 will give each combination of coin flips. From that, I can search the resulting string vector for repeated instances of 1 ( my choice for tails) that are at least k long and sum the logical array for the result.

Try it online!

Answer 24

Excel, 49 bytes

=COUNT(FIND(REPT(1,B2),BASE(SEQUENCE(2^A2)-1,2)))

Input for n is in A2 and k is in B2.

• SEQUENCE(2^A2)-1 creates an array from 0 to (2^n)-1.
• BASE(~,2)) converts that array to binary.
• REPT(1,B2) creates a string of k 1s.
• FIND(REPT(~),BASE(~)) tries to find that repeated string in each binary element in the array. This returns an array of integers (if it's found in that element) and errors (if it's not).
• COUNT(FIND(~)) counts the numbers in that array.