A253548 Minimal width k for a paper tape such that n symbols can be encoded on a k-hole paper tape so that a used paper tape can always be reused at least once.

1, 2, 3, 3, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9

Offset

1,2

Comments

This sequence is the inverse of A253426.

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 a(n)-hole paper tape is represented as an a(n)-digit binary string, and nonzero bits correspond to punched holes.

a(n) is the minimum number of binary digits that allows n symbols to be encoded as a(n)-bit binary strings, such that the symbol set S has two separate a(n)-bit encoding schemes (E1 and E2), and for each pair of symbols s and t (where s != t), the E1 encoding of s can be transformed to the E1 or E2 encoding of t by flipping one or more bits from 0 to 1.

Each symbol in S has exactly one encoding in E1. Each symbol in S has one or more encodings in E2.

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

This sequence was inspired by the Punch-22 puzzle (see Kennedy link).

Ronald L. Rivest and Adi Shamir explored these types of problems extensively in their 1982 paper entitled 'How to Reuse a "Write-Once" Memory' (see Links). The paper provides a solution to the Punch-22 puzzle; thus, a(26) <= 7. The paper states that a(29) cannot be 7. Using notation from their paper, a(n) is equal to the minimum k such that an <n>^2/k WOM-code exists.

Juan Cristobal Olivares solved the Punch-22 puzzle (see Links).

Links

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

R. Broughton, 5 Hole Paper Tape

Jack Kennedy, Punch-22

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

Ronald L. Rivest and Adi Shamir, How to Reuse a "Write-Once" Memory, 1982

Wikipedia, Punched tape

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 = 4: 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.

Crossrefs

Cf. A253426.

Sequence in context: A332271 A350255 A267861 * A083036 A241920 A202305

Adjacent sequences: A253545 A253546 A253547 * A253549 A253550 A253551

Keyword

nonn,more,hard

Author

Robert C. Lyons, Jan 03 2015

Extensions

Added a(9)-a(64) to reflect the addition of a(6)-a(9) to A253426 by Bert Dobbelaere

Status

approved