cp's OEIS Frontend

A319416 Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to the empty string.

%I A319416 #25 Nov 26 2019 20:03:05
%S A319416 1,1,1,2,2,1,2,3,3,2,1,2,2,2,3,4,4,3,2,2,2,1,2,3,3,2,2,3,3,3,4,5,5,4,
%T A319416 3,3,3,2,2,3,3,2,1,2,2,2,3,4,4,3,2,2,2,2,3,4,3,3,3,4,4,4,5,6,6,5,4,4,
%U A319416 4,3,3,3,4,3,2,2,2,2,3,4,4,3,2,2,2,1,2
%N A319416 Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to the empty string.
%C A319416 Here we are using Lenormand's "raboter" map in a stricter sense than in A318921 and A319419. If S is a binary string with successive runs of lengths b,c,d,e,..., the "raboter" map sends S to the binary string with successive runs of lengths b-1,c-1,d-1,e-1,... Runs of length 0 are omitted (they are indicated by dots in the examples below).
%C A319416 To get a(n), start with S equal to the binary expansion of n beginning with the most significant bit, and keep applying the map until we reach the empty string.
%C A319416 After the first step, the string may start with a string of 0's: this is acceptable because we are working with strings, not binary expansions of numbers.
%C A319416 For example, 34 = 100010 -> .00.. = 00 -> 0. = 0 -> . (the empty string), taking 3 steps, so a(34) = 3.
%C A319416 Note: this is not the same as the number of applications of the map k -> A318921(k) needed to reduce the binary expansion of n to zero (because A318921 does not distinguish between 0 and the empty string).
%C A319416 This is also not the same as the number of applications of the map k -> A319419(k) needed to reduce the binary expansion of n to -1 (because A319419 does not distinguish between a string of 0's and a single 0).
%C A319416 The value k appears for the first time when n = 2^k - 1.
%H A319416 Rémy Sigrist, <a href="/A319416/b319416.txt">Table of n, a(n) for n = 0..16384</a>
%H A319416 Claude Lenormand, <a href="/A318921/a318921.pdf">Deux transformations sur les mots</a>, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
%H A319416 N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, <a href="https://vimeo.com/314786942">Part I</a>, <a href="https://vimeo.com/314790822">Part 2</a>, <a href="https://oeis.org/A320487/a320487.pdf">Slides.</a> (Mentions this sequence)
%e A319416 n: repeatedly applying the map / number of steps = a(n)
%e A319416 0: 0 -> . / 1
%e A319416 1: 1 -> . / 1
%e A319416 2: 10 -> . / 1
%e A319416 3: 11 -> 1 -> . / 2
%e A319416 4: 100 -> 0 -> . / 2
%e A319416 5: 101 -> . / 1
%e A319416 6: 110 -> 1 -> . / 2
%e A319416 7: 111 -> 11 -> 1 -> . / 3
%e A319416 8: 1000 -> 00 -> 0 -> . / 3
%e A319416 9: 1001 -> 0 -> . / 2
%e A319416 10: 1010 -> . / 1
%e A319416 11: 1011 -> 1 -> . / 2
%e A319416 12: 1100 -> 10 -> . / 2
%e A319416 ...
%t A319416 degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
%t A319416 Table[degdep[IntegerDigits[n,2]],{n,0,50}] (* _Gus Wiseman_, Nov 25 2019 *)
%o A319416 (PARI) a(n) = my (b=binary(n), w=#b); for (k=1, oo, my (ww=0); for (i=2, w, if (b[i-1]==b[i], b[ww++]=b[i])); if (ww==0, return (k), w=ww)) \\ _Rémy Sigrist_, Sep 23 2018
%Y A319416 Positions of 1's are A000975.
%Y A319416 Positions of 2's are A329862.
%Y A319416 The version for runs-resistance is A318928.
%Y A319416 The version for compositions is A329861.
%Y A319416 Binary words counted by cuts-resistance are A319421 or A329860.
%Y A319416 Cf. A318921, A319411, A319419, A319420, A329744, A329767, A329863, A329865.
%K A319416 nonn,base
%O A319416 0,4
%A A319416 _N. J. A. Sloane_, Sep 21 2018
%E A319416 More terms from _Rémy Sigrist_, Sep 23 2018