login
Lexicographically least sequence of nonnegative integers that avoids 5/4-powers.
1

%I #42 May 08 2020 16:13:25

%S 0,0,0,0,1,1,1,1,0,2,0,2,1,0,1,0,0,1,0,1,1,2,1,2,0,0,0,0,1,3,1,1,0,1,

%T 0,2,1,0,1,3,0,2,0,0,1,1,1,1,0,0,0,2,1,2,1,0,0,1,0,1,1,0,1,2,0,2,0,0,

%U 1,3,1,1,0,0,0,3,1,1,1,0,0,2,0,1,1,0,1,3,0,1,0,0,1,2,1,1,0,0,0,2,1,1,1,0,0,3,0,1,1,0,1,2,0,1,0,0,1,3,1,1

%N Lexicographically least sequence of nonnegative integers that avoids 5/4-powers.

%C This sequence is 6-regular.

%C From _M. F. Hasler_, Oct 03 2016: (Start)

%C Avoiding 5/4-powers means avoiding factors of the form xyx where 3|x| = |y| >= 1.

%C The index of the first occurrence of 0, 1, 2, 3,.... is 0, 4, 9, 29, 725, 7351, 12607, .... (not in the OEIS, neither if the indices are shifted by 1). (End)

%H Eric Rowland, <a href="/A277144/b277144.txt">Table of n, a(n) for n = 0..20000</a>

%H Lara Pudwell and Eric Rowland, <a href="http://arxiv.org/abs/1510.02807">Avoiding fractional powers over the natural numbers</a>, arXiv:1510.02807 [math.CO] (2015).

%H Eric Rowland, <a href="/A277144/a277144.txt">List of first 400000 terms</a>

%H Eric Rowland and Manon Stipulanti, <a href="https://arxiv.org/abs/2005.03158">Avoiding 5/4-powers on the alphabet of nonnegative integers</a>, arXiv:2005.03158 [math.CO], 2020.

%F From _Eric Rowland_, May 08 2020: (Start)

%F a(6*n + 123061) = a(n + 5920) + 3 if n = 0,2 mod 8;

%F a(6*n + 123061) = a(n + 5920) + 1 if n = 4,6 mod 8;

%F a(6*n + 123061) = a(n + 5920) + 2 if n = 1 mod 2.

%F (End)

%e The sequence cannot start 0,0,0,0,0,... because this would be a 5/4-power (with y = (0,0,0)). Thus it must start 0,0,0,0,1,.... This cannot be followed by a 0 (y = (0,0,1)), and the same applies after the next two 1's (with y = (0,1,1), or y = (1,1,1)). Only after the fourth 1, a 0 is again possible. Thereafter, neither a 1 (x = 1, y = 110) nor a 0 (x = 00, y = 001111) is possible, so it must be followed by a 2. - _M. F. Hasler_, Oct 03 2016

%o (PARI) {a=vector(2000);for(n=5,#a,until(0,for(x=1,n\5,a[n-x+1..n]==a[n-5*x+1..n-4*x]&&a[n]++&&next(2));break));a[1..200]} \\ _M. F. Hasler_, Oct 03 2016

%K nonn

%O 0,10

%A _Eric Rowland_, Oct 01 2016