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.

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

Offset

0,4

Comments

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).

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.

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.

For example, 34 = 100010 -> .00.. = 00 -> 0. = 0 -> . (the empty string), taking 3 steps, so a(34) = 3.

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).

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).

The value k appears for the first time when n = 2^k - 1.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..16384

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.

N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)

Example

n: repeatedly applying the map / number of steps = a(n)
0: 0 -> . / 1
1: 1 -> . / 1
2: 10 -> . / 1
3: 11 -> 1 -> . / 2
4: 100 -> 0 -> . / 2
5: 101 -> . / 1
6: 110 -> 1 -> . / 2
7: 111 -> 11 -> 1 -> . / 3
8: 1000 -> 00 -> 0 -> . / 3
9: 1001 -> 0 -> . / 2
10: 1010 -> . / 1
11: 1011 -> 1 -> . / 2
12: 1100 -> 10 -> . / 2
...

Mathematica

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&, q, Length[#]>0&]]-1;
Table[degdep[IntegerDigits[n, 2]], {n, 0, 50}] (* Gus Wiseman, Nov 25 2019 *)

Prog

(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

Crossrefs

Positions of 1's are A000975.

Positions of 2's are A329862.

The version for runs-resistance is A318928.

The version for compositions is A329861.

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

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

Sequence in context: A165915 A269783 A043276 * A284559 A284583 A064742

Adjacent sequences: A319413 A319414 A319415 * A319417 A319418 A319419

Keyword

nonn,base

Author

N. J. A. Sloane, Sep 21 2018

Extensions

More terms from Rémy Sigrist, Sep 23 2018

Status

approved