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

%I #25 Nov 26 2019 20:03:05

%S 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 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 4,3,3,3,4,3,2,2,2,2,3,4,4,3,2,2,2,1,2

%N 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 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 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 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 For example, 34 = 100010 -> .00.. = 00 -> 0. = 0 -> . (the empty string), taking 3 steps, so a(34) = 3.

%C 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 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 The value k appears for the first time when n = 2^k - 1.

%H Rémy Sigrist, <a href="/A319416/b319416.txt">Table of n, a(n) for n = 0..16384</a>

%H 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 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 n: repeatedly applying the map / number of steps = a(n)

%e 0: 0 -> . / 1

%e 1: 1 -> . / 1

%e 2: 10 -> . / 1

%e 3: 11 -> 1 -> . / 2

%e 4: 100 -> 0 -> . / 2

%e 5: 101 -> . / 1

%e 6: 110 -> 1 -> . / 2

%e 7: 111 -> 11 -> 1 -> . / 3

%e 8: 1000 -> 00 -> 0 -> . / 3

%e 9: 1001 -> 0 -> . / 2

%e 10: 1010 -> . / 1

%e 11: 1011 -> 1 -> . / 2

%e 12: 1100 -> 10 -> . / 2

%e ...

%t degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;

%t Table[degdep[IntegerDigits[n,2]],{n,0,50}] (* _Gus Wiseman_, Nov 25 2019 *)

%o (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 Positions of 1's are A000975.

%Y Positions of 2's are A329862.

%Y The version for runs-resistance is A318928.

%Y The version for compositions is A329861.

%Y Binary words counted by cuts-resistance are A319421 or A329860.

%Y Cf. A318921, A319411, A319419, A319420, A329744, A329767, A329863, A329865.

%K nonn,base

%O 0,4

%A _N. J. A. Sloane_, Sep 21 2018

%E More terms from _Rémy Sigrist_, Sep 23 2018