cp's OEIS Frontend

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

%I A093614 #24 Feb 16 2025 08:32:53
%S A093614 5,6,10,12,15,17,18,20,24,25,30,31,33,34,35,36,40,42,45,48,50,51,54,
%T A093614 55,60,62,63,65,66,68,70,72,75,78,80,84,85,90,93,95,96,99,100,102,105,
%U A093614 108,110,114,115,119,120,124,125,126,127,129,130,132,135,136,138
%N A093614 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 A093614 Goldwasser et al. proved that 2^k+-1 belongs to the set, for k>4.
%C A093614 Closed under multiplication by positive integers. - _Don Knuth_, May 11 2006
%H A093614 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 A093614 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 A093614 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 A093614 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 A093614 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LightsOutPuzzle.html">Lights-Out Puzzle</a>
%o A093614 (PARI)
%o A093614 { 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 A093614 for(n=2, 200, t=F2(n); if(gcd(t, subst(t, x, 1-x))!=1, print1(n", ")))
%Y A093614 Equals A117870(n) + 1.
%Y A093614 Cf. A094425 (primitive elements), A076436.
%K A093614 nonn
%O A093614 1,1
%A A093614 _Ralf Stephan_, May 22 2004
%E A093614 More terms from _Thomas Buchholz_, May 16 2014