Puzzle
4 minute read

Ponder This Challenge - February 2017 - How many Boolean sequences

Ponder This Challenge:

When you run the following pseudo code on a sequence of six bits, in exactly 14 cases you get a non-zero value. How many such cases would you get for all sequences of 42 bits?

s=2
r=0
for b in v:
    if (s modulo 7) = b:
        r = r+2*b-1
    s = 6+s*(5+s*s*s*(2+s*(3+s))) + b*(5+s*(5+s*(6+s*s*(3+s*6))))
return r

Bonus question: If we would have asked a similar question for sequences of 14 bits, what would be the connection of the result to IBM?

Hint: We asked a similar bonus question in the past, and the number of solvers was then a multiplication of two prime numbers.

Solution

  • Trying to run the program yields very large numbers, but note that since we are only interested in s modulo 7, we can make the computations modulo 7.
    We are actually implementing a finite automaton. From the polynomial, we get that transition as

    Current s	0 1 2 3 4 5 6  

New s if b=0	6 3 5 3 6 3 1  

New s if b=1	4 0 4 0 4 4 4

    The states actually represent:

    0 last 3 bits are 001
    1 last 3 bits are 100
    2 initial state
    3 last 2 bits are 00
    4 last bit is 1
    5 last bit is 0
    6 last 2 bits are 10

    And what this finite automaton is counting is the number of times the 1001 pattern appears, minus the number of times the pattern 0010 appears.
    So we are looking for the number of binary sequences where these two patterns appear a different number of times.
    This can be computed using dynamic programming, which produces the result 3271652365264 for 42 bits.
    As for the bonus: we get 8296 for 14 bits, but when solving for the complementary problem (the number of sequences where these two patterns appear the same number of times), we get 8088, which is the record breaking number of patents IBM received in 2016.

Solvers

  • *Robert Gerbicz (30/01/2017 05:02 PM IDT)
  • Motty Porat (30/01/2017 06:00 PM IDT)
  • *Oleg Vlasii (30/01/2017 06:42 PM IDT)
  • *Bert Dobbelaere (30/01/2017 09:21 PM IDT)
  • Uoti Urpala (30/01/2017 10:56 PM IDT)
  • Tyler Mullen (30/01/2017 11:29 PM IDT)
  • *George W Barnett (31/01/2017 09:01 AM IDT)
  • Hanlin Ren (31/01/2017 09:47 AM IDT)
  • Aviv Nisgav (31/01/2017 03:53 PM IDT)
  • *Shwetabh Garg (31/01/2017 05:00 PM IDT)
  • Kang Jin Cho (31/01/2017 05:51 PM IDT)
  • Armin Krauss (31/01/2017 06:24 PM IDT)
  • Jesse Rearick (01/02/2017 04:41 AM IDT)
  • Ran Sharon (01/02/2017 04:14 PM IDT)
  • Joseph DeVincentis (01/02/2017 04:26 PM IDT)
  • Reiner Martin (01/02/2017 11:06 PM IDT)
  • Shirish Chinchalkar (02/02/2017 02:18 AM IDT)
  • Raymond Lo (02/02/2017 08:42 AM IDT)
  • Lorenz Reichel (02/02/2017 09:26 AM IDT)
  • *Teake Nutma (02/02/2017 11:32 AM IDT)
  • Dan Dima (02/02/2017 01:55 PM IDT)
  • Sergey Koposov (02/02/2017 05:20 PM IDT)
  • Yan-Wu He (02/02/2017 05:34 PM IDT)
  • Sebastian Bohm & Martí Bosch (02/02/2017 07:52 PM IDT)
  • JJ Rabeyrin (03/02/2017 02:05 AM IDT)
  • Kipp Johnson (03/02/2017 05:05 AM IDT)
  • Bryce Fore (03/02/2017 06:23 AM IDT)
  • Adrian Orzepowski (03/02/2017 02:51 PM IDT)
  • Paolo Farinelli (03/02/2017 06:10 PM IDT)
  • Pieter Meijer (04/02/2017 01:24 AM IDT)
  • Liubing Yu (04/02/2017 01:45 PM IDT)
  • Daniel Blazewicz (04/02/2017 08:01 PM IDT)
  • David F.H. Dunkley (05/02/2017 02:03 AM IDT)
  • Siddharth Joshi (06/02/2017 09:47 AM IDT)
  • Steven Langerwerf (06/02/2017 11:58 AM IDT)
  • Mathias Schenker (06/02/2017 05:33 PM IDT)
  • Stijn Vermeeren (07/02/2017 07:17 PM IDT)
  • Todd Will (07/02/2017 11:11 PM IDT)
  • Serge Batalov (08/02/2017 07:02 AM IDT)
  • Muralidhar Seshadri (08/02/2017 07:37 PM IDT)
  • Leandro Augusto de Araújo Silva (08/02/2017 08:08 PM IDT)
  • Peter Gerritson (09/02/2017 09:23 PM IDT)
  • Dieter Beckerle (09/02/2017 11:47 PM IDT)
  • Sean Egan (10/02/2017 09:50 AM IDT)
  • *Anders Bisbjerg Madsen (10/02/2017 03:22 PM IDT)
  • Daniel Bitin (10/02/2017 05:49 PM IDT)
  • Sergey Grishaev (11/02/2017 12:59 AM IDT)
  • Aradesh (11/02/2017 01:58 PM IDT)
  • Martin Thiim (12/02/2017 12:51 PM IDT)
  • Ricardo Koller (12/02/2017 10:02 PM IDT)
  • William Gunther (13/02/2017 01:34 AM IDT)
  • David Greer (13/02/2017 06:39 PM IDT)
  • Andreas Stiller (13/02/2017 07:37 PM IDT)
  • *Paul McKenney (13/02/2017 09:57 PM IDT)
  • Yoni Tate (14/02/2017 06:09 PM IDT)
  • Jim Clare (15/02/2017 12:52 AM IDT)
  • Michael J. Swart (15/02/2017 05:15 PM IDT)
  • William Mantzel (16/02/2017 12:05 AM IDT)
  • Susan Brommer (16/02/2017 07:30 PM IDT)
  • Thomas Satzger (17/02/2017 12:33 AM IDT)
  • Radu Haiduc (17/02/2017 02:33 AM IDT)
  • Stéphane Higueret (18/02/2017 07:40 AM IDT)
  • Dan Ignatoff (19/02/2017 08:38 AM IDT)
  • *Shouky Dan & Tamir Ganor (19/02/2017 07:32 PM IDT)
  • Alessandro Marzo (21/02/2017 06:01 PM IDT)
  • Adir HaCohen (22/02/2017 09:16 AM IDT)
  • Adrian Neacsu (24/02/2017 06:57 PM IDT)
  • Anatoly Vorobey (25/02/2017 03:01 AM IDT)
  • Nyles Heise (26/02/2017 07:10 AM IDT)
  • Vladimir M. Milovanović (26/02/2017 01:14 PM IDT)
  • Chris Shannon (27/02/2017 10:01 AM IDT)
  • Georgiy Korneev (28/02/2017 08:05 PM IDT)
  • Erik Wünstel (28/02/2017 11:13 PM IDT)
  • Radu-Alexandru Todor (28/02/2017 01:28 PM IDT)
  • Douglas Rofes (01/03/2017 09:41 AM IDT)
  • Michael Golubev (01/03/2017 09:48 AM IDT)
  • Martin Sergio H. Faester (01/03/2017 04:32 PM IDT)
  • Maxim Razin (02/03/2017 04:30 AM IDT)

Related posts