

A253548


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


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 Punch22 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 "WriteOnce" Memory' (see Links). The paper provides a solution to the Punch22 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 WOMcode exists.
Juan Cristobal Olivares solved the Punch22 puzzle (see Links).


LINKS

Table of n, a(n) for n=1..64.
R. Broughton, 5 Hole Paper Tape
Jack Kennedy, Punch22
Juan Cristobal Olivares, Solution to the Punch22 Puzzle, Jan. 2, 2015.
Ronald L. Rivest and Adi Shamir, How to Reuse a "WriteOnce" 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: A140858 A075458 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



