A093614 - OEIS

%I #24 Feb 16 2025 08:32:53

%S 5,6,10,12,15,17,18,20,24,25,30,31,33,34,35,36,40,42,45,48,50,51,54,

%T 55,60,62,63,65,66,68,70,72,75,78,80,84,85,90,93,95,96,99,100,102,105,

%U 108,110,114,115,119,120,124,125,126,127,129,130,132,135,136,138

%N Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind.

%C Goldwasser et al. proved that 2^k+-1 belongs to the set, for k>4.

%C Closed under multiplication by positive integers. - _Don Knuth_, May 11 2006

%H Ralf Stephan and Thomas Buchholz, <a href="/A093614/b093614.txt">Table of n, a(n) for n = 1..1000</a> [terms 1 through 61 were computed by Ralf Stephan, May 22 2004; terms 62 through 1000 by Thomas Buchholz, May 16 2014]

%H M. Hunziker, A. Machiavelo and J. Park, <a href="http://dx.doi.org/10.1016/j.tcs.2004.03.031">Chebyshev polynomials over finite fields and reversibility of sigma-automata on square grids</a>, Theoretical Comp. Sci., 320 (2004), 465-483.

%H K. Sutner, <a href="http://dx.doi.org/10.1007/BF03023823">Linear cellular automata and the Garden-of-Eden</a>, Math. Intelligencer, 11 (No. 2, 1989), 49-53.

%H K. Sutner, <a href="http://dx.doi.org/10.1007/3-540-51498-8_44">The computational complexity of cellular automata</a>, in Lect. Notes Computer Sci., 380 (1989), 451-459.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LightsOutPuzzle.html">Lights-Out Puzzle</a>

%o (PARI)

%o { F2(n)=local(t, t1, t2, tmp); t1=Mod(0, 2); t2=Mod(1, 2); t=Mod(1, 2)*x; for(k=2, n, tmp=t*t2-t1; t1=t2; t2=tmp); tmp }

%o for(n=2, 200, t=F2(n); if(gcd(t, subst(t, x, 1-x))!=1, print1(n", ")))

%Y Equals A117870(n) + 1.

%Y Cf. A094425 (primitive elements), A076436.

%K nonn

%O 1,1

%A _Ralf Stephan_, May 22 2004

%E More terms from _Thomas Buchholz_, May 16 2014