%I #67 Aug 06 2024 10:56:10
%S 1,2,4,5,8,16,28,37,64
%N 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.
%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 n-hole paper tape is represented as an n-digit binary string, and nonzero bits correspond to punched holes.
%C 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.
%C Each n-bit encoding in E1 and E2 must map to exactly one symbol; two different symbols cannot share the same n-bit encoding.
%C This sequence was inspired by the Punch-22 puzzle published by J. Kennedy and solved by J. Cristobal Olivares, cf links.
%C 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.
%C 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
%C 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
%H R. Broughton, <a href="https://www.staff.ncl.ac.uk/roger.broughton/museum/iomedia/pt0.htm">5 Hole Paper Tape</a>
%H Bert Dobbelaere, <a href="/A253426/a253426.txt">Known bounds for a(1..50)</a>
%H IBM Research, <a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/March2015.html">Ponder This. March 2015 challenge</a>. Mar 02 2015.
%H Jack Kennedy, <a href="http://realmode.com/punch22.html">Punch-22</a>
%H Robert C. Lyons, <a href="/A253426/a253426.py.txt">Python script for finding terms of the sequence</a>, Jan 05 2015.
%H Juan Cristobal Olivares, <a href="http://blog.datalabs.cl/punch22/">Solution to the Punch-22 Puzzle</a>, Jan 02 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>, Information and Control 55, 1--19 (1982).
%H Simon Tatham, <a href="/A253426/a253426_1.txt">Known bounds for a(1..50)</a> (all from Bert Dobbelaere except the lower bound for a(10)).
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Punched_tape">Punched tape</a>
%H Yaakobi et al., <a href="https://citeseerx.ist.psu.edu/pdf/dd2840e6d742da0ca0eac4dd920664d5079047e9">Codes for write-once memories</a>, 2012. - _Bert Dobbelaere_, Feb 14 2017
%F a(n) >= 2^floor(n/2).
%F From _Bert Dobbelaere_, Feb 12 2017: (Start)
%F Lower bound: a(n) >= a(k)*a(n-k), 0 < k <n.
%F Upper bound: a(n) <= max{k<n}(min(Sum_{j=0..k}(C(n,j)), 2^(n-k))). (End)
%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 = 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.
%e 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.
%e 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
%e From _Bert Dobbelaere_, Feb 12 2017: (Start)
%e For a(6) and a(9), the upper and lower bound formulas coincide, fixing their values respectively to 16 and 64.
%e 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:
%e 1WHTRLZREOPVQATMGBFIDOANJRAX2KYCIVCAUILY2URLDBXFAJTMR1EPIQNZWGVS
%e KMKBYSGDXIQ2RPIWNARGIVJQSFB1ZELUSRIOCZQKVCGEAN1JCLUWFXB2PYKDMTOH
%e For a(8), a computer search easily achieves the upper bound of 37. (End)
%e From _Bert Dobbelaere_, Feb 14 2017: (Start)
%e Found by computer search that a(11) >= 185 and a(12)=299.
%e Yaakobi et al. reported a(16) >= 2^11 and a(33) >= 2^24. (End)
%K nonn,more,hard,nice
%O 1,2
%A _Robert C. Lyons_, Dec 31 2014
%E Edited by _M. F. Hasler_, Jan 04 2015
%E a(6)-a(9) from _Bert Dobbelaere_, Feb 12 2017