A281922 Consider a string of n 1. From left to right for any couple of consecutive numbers apply the transform 11 -> 10, 10 -> 11, 00 -> 00, 01 -> 01. At any further step restart the process considering the value of the rightmost digit as input to the leftmost one to apply the transform again. Sequence gives the number of steps necessary to reach again a string of n 1 or -1 if such a number does not exist.

2, 5, 4, 17, -1, 109, 8, 65, 89, 1115, -1, 7297, 2531, 4369, 16, 257, 155174, 195814, 495146, 5201, 1334551, 1725452, 1485482, -1, -1, -1, 17256565, 277691849, 6145997, 2029501, 32, 1025, 67672804, 1157011598, 12054050100, 22287270331, 15597512810, -1

Offset: 2

Author

Paolo P. Lava, Feb 15 2017

Keywords

• sign
• hard

Comments

a(n) <= 2^n if it exists.

a(2^k) = 2^k.

a(2^k + 1) = 2^(2*k) + 1.

Up to a(34), it appears that if the number does not exist the configuration of the first step is repeated further on: for a(6) it happens after 22 steps (see example), 1086 for a(12), 2192338 for a(25), 22996 for a(26), 41943036 for a(27).

Examples

			a(5) = 17. We start with 1 1 1 1 1, then the first two digit at left are 1 1 and applying the transform we get 1 0 1 1 1; again, the second and third digit from left are 0 1 and applying the transform we get 1 0 1 1 1;  the third and fourth digit from left are 1 1 and we get 1 0 1 0 1; the fourth and fifth digit from left are 0 1 and we get 1 0 1 0 1. This is the result of the first step. To start the second one we consider the rightmost digit of the first step, that is 1, as input of the leftmost digit, that is another 1. So, applying the transform 1 1 -> 1 0, we get 0 0 1 0 1; now the first and second digit at left are 0 0 that results in 0 0 1 0 1; the second and third digit at left are 0 1 that results in 0 0 1 0 1; the third and fourth digit at left are 1 0 that results in 0 0 1 1 1; the fourth and fifth digit from left are 1 1 that results in 0 0 1 1 0. This is the result of the second step. Here below the list of all the steps leading back to 1 1 1 1 1:
0    1 1 1 1 1
1    1 0 1 0 1
2    0 0 1 1 0
3    0 0 1 0 0
4    0 0 1 1 1
5    1 1 0 1 0
6    1 0 0 1 1
7    0 0 0 1 0
8    0 0 0 1 1
9    1 1 1 0 1
10   0 1 0 0 1
11   1 0 0 0 1
12   0 0 0 0 1
13   1 1 1 1 0
14   1 0 1 0 0
15   1 1 0 0 0
16   1 0 0 0 0
17   1 1 1 1 1
a(6) = -1 because after 22 steps we get again 1 0 1 0 1 0 (first step):
0    1 1 1 1 1 1
1    1 0 1 0 1 0
2    1 1 0 0 1 1
3    0 1 1 1 0 1
4    1 0 1 0 0 1
5    0 0 1 1 1 0
6    0 0 1 0 1 1
7    1 1 0 0 1 0
8    1 0 0 0 1 1
9    0 0 0 0 1 0
10   0 0 0 0 1 1
11   1 1 1 1 0 1
12   0 1 0 1 1 0
13   0 1 1 0 1 1
14   1 0 1 1 0 1
15   0 0 1 0 0 1
16   1 1 0 0 0 1
17   0 1 1 1 1 0
18   0 1 0 1 0 0
19   0 1 1 0 0 0
20   0 1 0 0 0 0
21   0 1 1 1 1 1
22   1 0 1 0 1 0
		

Links

• Lars Blomberg, Table of n, a(n) for n = 2..42

Crossrefs

Cf. A046932.

Programs

Maple

with(numtheory): P:=proc(q) local a,b,j,k,n,ok,ok2,s,t;
for n from 2 to q do a:=array(1..n); b:=array(1..n);
for k from 1 to n do a[k]:=1; if k mod 2=0 then b[k]:=0; else b[k]:=1; fi; od;
for k from 1 to n-1 do if a[k]=1 then a[k+1]:=(a[k+1]+1) mod 2; fi; od;
t:=1; ok:=1; s:=0; while n>s do t:=t+1; if a[n]=1 then a[1]:=(a[1]+1) mod 2; fi;
for k from 1 to n-1 do if a[k]=1 then a[k+1]:=(a[k+1]+1) mod 2; fi; od;
ok2:=1; for j from 1 to n do if a[j]<>b[j] then ok2:=0; break; fi; s:=add(a[k],k=1..n); od;
if ok2=1 then ok:=0; print(-1); break; fi; od; if ok=1 then print(t); fi; od; end: P(100);

Extensions

a(35)-a(39) from Lars Blomberg, Apr 20 2017