Re: A simple proof for the following?

From: Vladimir (vzajic_at_bnl.gov)
Date: 11/21/04 

Date: Sun, 21 Nov 2004 14:30:07 +0000 (UTC)

On 20 Nov 2004, c.j[dot]w wrote:
>Hello,
>
>Is there for the following statement a simple proof (or a way to >show that it is plausible)?
>
>Statement: Any 8-bit word can be stored as a 14-bit word, with the
>14-bit word having at least two zeros between every one.
>
>Thanks in advance,
>Carl

Let a(m) be the number of different m-bit words and b(n) be the
number of different n-bit words having at least 2 zeros between every
one.

b(1) = 2 (0, 1)
b(2) = 3 (00, 01, 10)
b(3) = 4 (000, 001, 010, 100)

For n >= 4, the MSB (the n-th bit) can be 0 or 1. If MSB=0, then the
next bit (the (n-1)-st bit) is arbitrary and we get b(n-1) n-1 words.
If MSB=1, then the next 2 bits (the (n-1)-st and (n-2)-nd bits) must
be zeros, the following bit (the (n-3)-rd bit) is arbitrary and we
get b(n-3) n-3 words. Hence,

b(n) = b(n-1) + b(n-3) for n>=4

{b(n), n = 0, 1, ...} =
= {2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, ...}

Sequence A000930 at Sloane's encyclopedia.

a(8) = 2^8 = 255
b(14) = 277

a(8) < b(14)
 

Relevant Pages

  • Re: Reducing Pseudorandomness
    ... I have a case where I need a pseudorandom number generated. ... the sequence can be generated very efficiently by a device called ... a linear shift register, by initializing ... the register to contain any seqeunce of n-bits (the all zeros being ...
    (comp.lang.pascal.delphi.misc)
  • Re: Why dont we just zero out FFT bins?
    ... supress and replace those bins in the FFT with zeros? ... append the time sequence from the IFFT with a bunch of zeros. ... let's say that you could create a filter with "brick wall" transitions ...
    (comp.dsp)
  • Re: Request for Review of ZF Inconsistency Proof
    ... denote the infinite set of denumerable binary strings with alphabet ... sequence of 0s and 1s (or alternatively, ... "tail of zeros"), via reverse binary notation. ...
    (sci.logic)
  • Re: random distribution of number sequences
    ... the percentage of zeros / ones can be entered. ... So if we choose to sample n sub-sequences of all zeros, ... Lets build up the complete sequence. ... preferably the same, cat. ...
    (comp.soft-sys.matlab)
  • Re: 8 Bit Random Numbers
    ... only 1016 "zeros" for each complete cycle, since 8 zeros are left out. ... which approach would you say is more linear? ... The XOR gates are run in parallel rather than in serial, ... For your original sequence of 3,4,5,7, use 0xB8 or 0x1D, depending upon ...
    (sci.electronics.basics)