|
%I #23 Feb 24 2019 01:19:55
%S 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,
%T 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
%N 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.
%C This sequence is the inverse of A253426.
%C 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.
%C 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.
%C Each symbol in S has exactly one encoding in E1. Each symbol in S has one or more encodings in E2.
%C 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.
%C This sequence was inspired by the Punch-22 puzzle (see Kennedy link).
%C 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.
%C Juan Cristobal Olivares solved the Punch-22 puzzle (see Links).
%H R. Broughton, <a href="https://www.staff.ncl.ac.uk/roger.broughton/museum/iomedia/pt0.htm">5 Hole Paper Tape</a>
%H Jack Kennedy, <a href="http://realmode.com/punch22.html">Punch-22</a>
%H Juan Cristobal Olivares, <a href="http://blog.datalabs.cl/punch22/">Solution to the Punch-22 Puzzle</a>, Jan. 2, 2015.
%H Ronald L. Rivest and Adi Shamir, <a href="http://people.csail.mit.edu/rivest/pubs/RS82c.pdf">How to Reuse a "Write-Once" Memory</a>, 1982
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Punched_tape">Punched tape</a>
%e 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.
%e 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.
%Y Cf. A253426.
%K nonn,more,hard
%O 1,2
%A _Robert C. Lyons_, Jan 03 2015
%E Added a(9)-a(64) to reflect the addition of a(6)-a(9) to A253426 by _Bert Dobbelaere_
|
