A253426 Reusable Paper Tape Numbers: Maximum number of symbols that can be encoded on an n-hole paper tape, such that a used paper tape can always be reused at least once.

1, 2, 4, 5, 8, 16, 28, 37, 64

Offset

1,2

Comments

Since many people are not familiar with punch paper tape technology, we provide the following more formal description of the sequence, where each row on an n-hole paper tape is represented as an n-digit binary string, and nonzero bits correspond to punched holes.

a(n) is the maximum number of symbols that can be encoded by a set of n-bit binary strings which can be split up as a disjoint union of two sets ("encoding schemes") E1 and E2, such that each symbol s has exactly one code in E1, and one or more codes in E2 such that any other symbol's code from E1 can be transformed to one of the encodings of s (in E1 or E2) by flipping one or more bits from 0 to 1.

Each n-bit encoding in E1 and E2 must map to exactly one symbol; two different symbols cannot share the same n-bit encoding.

This sequence was inspired by the Punch-22 puzzle published by J. Kennedy and solved by J. Cristobal Olivares, cf links.

Ronald L. Rivest and Adi Shamir explored these types of problems extensively in their 1982 paper, which provides a solution to the Punch-22 puzzle; thus, a(7) >= 26. The paper states that a(7) cannot be 29. Thus, a(7) is 26, 27 or 28. Using notation from their paper, a(n) is equal to the maximum k, such that a <k>^2/n WOM-code exists.

a(n) >= n+1 for n > 2 since a "trivial" encoding system of n+1 symbols is to assign them the codes c[k]=2^(k-1) for k=1..n and c[n+1]=0, and as second code the 1's complement, i.e., d[k] = 2^n-1-c[k]. Therefore, a(5) >= 6, which improves the lower bound 2^floor(n/2). For n >= 6 this bound is less than 2^floor(n/2). This latter bound is obtained by assigning to the 2^[n/2] symbols the codes c[k] = k-1, 1 <= k <= 2^[n/2], as well as, for k > 1, all the codes of the form c[k]*2^[n/2]+x where x takes all values different from c[k], while the codes c[k]*(2^[n/2]+1) would represent the first symbol also coded c[1]=0. - M. F. Hasler, Jan 02 2015

The lower bound follows from considering the code as concatenation of two smaller codes. The upper bound is derived from that fact that the worst case minimum number of holes to be punched during the first write determines the maximum reachable alphabet size using the remaining unpunched holes. For the lower and upper bounds see Formula section. - Bert Dobbelaere, Feb 12 2017

Links

Table of n, a(n) for n=1..9.

R. Broughton, 5 Hole Paper Tape

Bert Dobbelaere, Known bounds for a(1..50)

IBM Research, Ponder This. March 2015 challenge. Mar 02 2015.

Jack Kennedy, Punch-22

Robert C. Lyons, Python script for finding terms of the sequence, Jan 05 2015.

Juan Cristobal Olivares, Solution to the Punch-22 Puzzle, Jan 02 2015.

Ronald L. Rivest and Adi Shamir, How to Reuse a "Write-Once" Memory, Information and Control 55, 1--19 (1982).

Simon Tatham, Known bounds for a(1..50) (all from Bert Dobbelaere except the lower bound for a(10)).

Wikipedia, Punched tape

Yaakobi et al., Codes for write-once memories, 2012. - Bert Dobbelaere, Feb 14 2017

Formula

a(n) >= 2^floor(n/2).

From Bert Dobbelaere, Feb 12 2017: (Start)

Lower bound: a(n) >= a(k)*a(n-k), 0 < k <n.

Upper bound: a(n) <= max{k<n}(min(Sum_{j=0..k}(C(n,j)), 2^(n-k))). (End)

Example

Example for n = 2: Symbol set S is ('A', 'B'). Encoding scheme E1 is ( 'A' => 00, 'B' => 01 ), and encoding scheme E2 is ( 'A' => 11, 'B' => 10 ). The symbol 'A' encoded as 00 can be transformed to 'B' encoded as 10 by flipping the leftmost bit from 0 to 1. The symbol 'B' encoded as 01 can be transformed to 'A' encoded as 11 by flipping the leftmost bit from 0 to 1.
Example for n = 3: Symbol set S is ('A', 'B', 'C', 'D'). Encoding scheme E1 is ( 'A' => 000, 'B' => 001, 'C' => 010, 'D' => 100 ), and encoding scheme E2 is ( 'A' => 111, 'B' => 110, 'C' => 101, 'D' => 011 ). The symbol 'B' encoded as 001 can be transformed to 'C' encoded as 101 by flipping the leftmost bit from 0 to 1. The symbol 'B' encoded as 001 can be transformed to 'A' encoded as 111 by flipping the leftmost two bits from 0 to 1.
The same method yields a(4) = 5 (it can be shown that 6 letters cannot be encoded in a "reusable way" with 4 bit), and a(5) >= 6.
a(5) = 8, since encoding of {A,...,H} is possible by assigning to A...F the values 0, 1, 2, 4, 8, 16 and their 1's complement and to B..E the additional values 00111, 01011, 01101, 01110, and to G resp. H the values 00011 and 11100 resp. 01100 and 10011. The author has checked that 9 symbols are not possible. - M. F. Hasler, Jan 02 2015
From Bert Dobbelaere, Feb 12 2017: (Start)
For a(6) and a(9), the upper and lower bound formulas coincide, fixing their values respectively to 16 and 64.
For a(7), a solution with 28 symbols was found by Bert Dobbelaere on Jun 28 2016. As Rivest and Shamir proved a(7)<29, we finally determined a(7)=28. Below is a solution for this case expressed as sequence of 128 symbols:
    1WHTRLZREOPVQATMGBFIDOANJRAX2KYCIVCAUILY2URLDBXFAJTMR1EPIQNZWGVS
    KMKBYSGDXIQ2RPIWNARGIVJQSFB1ZELUSRIOCZQKVCGEAN1JCLUWFXB2PYKDMTOH
For a(8), a computer search easily achieves the upper bound of 37. (End)
From Bert Dobbelaere, Feb 14 2017: (Start)
Found by computer search that a(11) >= 185 and a(12)=299.
Yaakobi et al. reported a(16) >= 2^11 and a(33) >= 2^24. (End)

Crossrefs

Sequence in context: A326173 A045591 A045581 * A092061 A256760 A281646

Adjacent sequences: A253423 A253424 A253425 * A253427 A253428 A253429

Keyword

nonn,more,hard,nice

Author

Robert C. Lyons, Dec 31 2014

Extensions

Edited by M. F. Hasler, Jan 04 2015

a(6)-a(9) from Bert Dobbelaere, Feb 12 2017

Status

approved